登录  /  注册

字符串函数 - 关于php的levenshtein函数能否给个通俗易懂的解释,手册看不懂!

php中文网
发布: 2016-06-06 20:47:59
原创
1022人浏览过

如题,越详细越好。谢谢了!

<code>levenshtein("Hello World","ello World");
</code>
登录后复制
登录后复制

它只要在第二个参数添加个'H',只作了1个步骤!也当然返回'1'啦!
这个函数还是蛮简单的,可是:

<code>levenshtein("Hello World","ello World",10,20,30);
</code>
登录后复制
登录后复制

第3个参数:插入一个字符的代价。默认是 1。
第4个参数:替换一个字符的代价。默认是 1。
第5个参数:删除一个字符的代价。默认是 1。
它们的意义在哪?
这个例子中它分别填了10,20,30。
然后返回'30'我不懂了!
它指的'代价'是什么意思?
10,20,30它又分别代表什么意思?

<code>levenshtein('aaa','aab',0,1,0);
</code>
登录后复制
登录后复制

这个例子中它只需替换一次就够了,为什么返回的步骤次数是'0'?

回复内容:

如题,越详细越好。谢谢了!

<code>levenshtein("Hello World","ello World");
</code>
登录后复制
登录后复制

它只要在第二个参数添加个'H',只作了1个步骤!也当然返回'1'啦!
这个函数还是蛮简单的,可是:

<code>levenshtein("Hello World","ello World",10,20,30);
</code>
登录后复制
登录后复制

第3个参数:插入一个字符的代价。默认是 1。
第4个参数:替换一个字符的代价。默认是 1。
第5个参数:删除一个字符的代价。默认是 1。
它们的意义在哪?
这个例子中它分别填了10,20,30。
然后返回'30'我不懂了!
它指的'代价'是什么意思?
10,20,30它又分别代表什么意思?

<code>levenshtein('aaa','aab',0,1,0);
</code>
登录后复制
登录后复制

这个例子中它只需替换一次就够了,为什么返回的步骤次数是'0'?

@怡红公子 已经回答的很好了,我想从底层实现上补充一下题主说的levenshtein('aaa','aab',0,1,0);这个例子,为什么会返回0?

PHP底层使用的算法是经典的矩阵方式(稍有改动),即分别将s1s2的每个字符作为矩阵的行(i[0,m])和列(j[0,n]),每个位置按顺序进行两两比较,如果相等则cost=0(因为不需要任何操作),否则cost=1(这个cost=1就是我们不传递后面3个参数时默认操作的cost了);但是,这里矩阵该项M[i,j]的值还不能直接就等于cost,因为要保证前面操作的传递性(比如你在前面插入了1个字符,后面的字符就要跟着往后挪一位;你在前面插删除了2个字符,后面就要跟着往前挪一位),M[i,j]的值等于M[i-1, j]+1, M[i, j-1]+1, M[i-1, j-1]+cost三个值中最小的(3个值分别表示插入、替换、删除的代价,取最小值表示采用操作代价最小的方式)。这样直到计算到项M[m, n]的值,就是我们需要求的“编辑距离”了。(最后我贴出了php底层c代码对应的php实现)

levenshtein('aaa','aab',1,1,1);的计算演示,单元格[3,3]为最终结果:

a a a
0 1 2 3
a 1 0 1 2
a 2 1 0 1
b 3 2 1 1

levenshtein('aaa','aab',0,1,0);的计算演示,单元格[3,3]为最终结果(因为[1,1]=0, 而且插入的cost设置成了0,导致后面M[i, j-1]的结果都是0,而0是最小值,导致最终返回0):

a a a
0 1 2 3
a 1 0 0 0
a 2 0 0 0
b 3 0 0 0

这里可以看出,levenshtein后面传递的3个参数,是对应的插入、替换、删除三种操作的当前代价(即替换上面求项M[i,j]值的时候后面+的1),而从算法角度来说,任何操作的最小代价单位是1,那么如果我们要得到一个“合理”的返回值,就不能传递0值。传递0就可能导致返回一个不合理,或者说没有实际参考价值的结果。当然,这是跟实际采用的算法密切相关的,就本例来说,最佳操作应该是替换(将aab中的b替换为a),但是PHP采用的算法来看,取的是3种操作方式中最小的值,而且要带入传递性,导致最终结果为0。

<code>#php底层c代码对应的php实现
function levenshtein_php($s1, $s2, $cost_ins=1, $cost_rep=1, $cost_del=1){
    $l1 = strlen($s1);
    $l2 = strlen($s2);

    if ($l1 == 0) {
        return $l2 * $cost_ins;
    }
    if ($l2 == 0) {
        return $l1 * $cost_del;
    }

    $p1 = array();
    $p2 = array();

    for ($i2 = 0; $i2 </code>
登录后复制

PS: 实际上有比利用矩阵结构更优的算法,就不在本题展开了。我没太多算法基础,尝试分析,欢迎批评指正!

通俗的来说就是检测两个字符串的相似程度的,一个字符串变成另外一个字符串的步骤越少的话就是越相似。

<code>$a = "levenshtein";
$b = "levenjdslkfjslkdjfklsjdfljsdlfjsldfjlsdjflsdjltein";
$c = "leveshetin";

$r = levenshtein($a, $b); //int(40)
$s = levenshtein($a, $c); //int(3)
</code>
登录后复制

$a变成$b需要在中间增加40个字符,从$a变成$c需要增加2个字符,删除1个字符,所以是3。

所谓的代价就是一次特定操作所占有的 权重/比重,比如你设置了删除字符的代价是30,做1次删除最后返回给你的就是1*30了。通过设置这个参数有助于尽量多做某个操作避免某个操作。至于后面那个,我个人是这样理解的,所谓的替换其实是经过了“删除”和“增加”两个步骤的合体,如果你把增加和删除设置成0的话就相当于禁止做这两个操作了,替换也就无法操作了。如果你随便给增加和删除来个非0值,则总会返回1。当然这都是我的个人想法,如果有不对的话可以提出来指正。

智能AI问答
PHP中文网智能助手能迅速回答你的编程问题,提供实时的代码和解决方案,帮助你解决各种难题。不仅如此,它还能提供编程资源和学习指导,帮助你快速提升编程技能。无论你是初学者还是专业人士,AI智能助手都能成为你的可靠助手,助力你在编程领域取得更大的成就。
来源:php中文网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2024 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号