ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 求两个字符比较操作的最少距离的函数

求两个字符比较操作的最少距离的函数

原创 Linux操作系统 作者:0x0x0x 时间:2012-06-26 15:37:23 0 删除 编辑
问题抽象归类:(编辑距离问题)
设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括:
(1)  删除一个字符;
(2)  插入一个字符;
(3)  将一个字符改为另一个字符。
将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离,记为d(A,B)。试设计一个有效算法,对任给的2个字符串A和B,计算出它们的编辑距离d(A,B)。
要求:
输入:第1行是字符串A,第2行是字符串B。
输出:字符串A和B的编辑距离d(A,B)
 
这个帖子最初看到时,第一反应是取oracle文档查找,无意中竟让我找到了以下两个函数:

EDIT_DISTANCE Function
This function calculates the number of insertions, deletions or substitutions required to transform. string-1 into string-2.
 
EDIT_DISTANCE_SIMILARITY Function
This function calculates the number of insertions, deletions or substations required to transform. string-1 into string-2, and returns the Normalized value of the Edit Distance between two Strings. The value is typically between 0 (no match) and 100 (perfect match).
 
SQL> SELECT UTL_MATCH.EDIT_DISTANCE_SIMILARITY('shackleford', 'shackelford') FROM DUAL;
UTL_MATCH.EDIT_DISTANCE_SIMILARITY('SHACKLEFORD','SHACKELFORD')
---------------------------------------------------------------
                                                             82
SQL> SELECT UTL_MATCH.EDIT_DISTANCE('shacklefordg', 'shackelford') FROM DUAL;
UTL_MATCH.EDIT_DISTANCE('SHACKLEFORDG','SHACKELFORD')
-----------------------------------------------------
                                                    3

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/26977915/viewspace-733839/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2012-06-26

  • 博文量
    35
  • 访问量
    92206