PHP相似度计算函数：levenshtein用法示例

这篇文章主要为大家详细介绍了PHP相似度计算函数：levenshtein用法示例，具有一定的参考价值，可以用来参考一下。

感兴趣的小伙伴，下面一起跟随php教程的小玲来看看吧！

使用说明先看手册上 levenshtein() 函数的说明：

levenshtein() 函数返回两个字符串之间的 Levenshtein 距离。

Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

例如把 kitten 转换为 sitting：

sitten （k→s）sittin （e→i）sitting （→g）levenshtein() 函数给每个操作（替换、插入和删除）相同的权重。不过，您可以通过设置可选的 insert、replace、delete 参数，来定义每个操作的代价。

语法：

levenshtein(string1,string2,insert,replace,delete)

参数 描述

string1 必需。要对比的第一个字符串。string2 必需。要对比的第二个字符串。insert 可选。插入一个字符的代价。默认是 1。replace 可选。替换一个字符的代价。默认是 1。delete 可选。删除一个字符的代价。默认是 1。提示和注释

如果其中一个字符串超过 255 个字符，levenshtein() 函数返回 -1。levenshtein() 函数对大小写不敏感。levenshtein() 函数比 similar_text() 函数更快。不过，similar_text() 函数提供需要更少修改的更精确的结果。例子

代码如下:

<?php
/*   php教程 www.512Pic.com   */

    echo levenshtein("Hello World","ello World");
    echo "<br />";
    echo levenshtein("Hello World","ello World",10,20,30);
    ?>

源码分析levenshtein() 属于标准函数，在/ext/standard/目录下有专门针对此函数实现的文件：levenshtein.c。

levenshtein()会根据参数个数选择实现方式，针对参数为2和参数为5的情况，都会调用 reference_levdist() 函数计算距离。其不同在于对后三个参数，参数为2时，使用默认值1。

并且在实现源码中我们发现了一个在文档中没有说明的情况： levenshtein() 函数还可以传递三个参数，其最终会调用 custom_levdist() 函数。它将第三个参数作为自定义函数的实现，其调用示例如下：

代码如下:

echo levenshtein("Hello World","ello World", 'strsub');

reference_levdist() 函数的实现算法是一个经典的DP问题。

给定两个字符串x和y，求最少的修改次数将x变成y。修改的规则只能是如下三种之一：删除、插入、改变。用a[i][j]表示把x的前i个字符变成y的前j个字符所需的最少操作次数，则状态转移方程为：

代码如下:

当x[i]==y[j]时：a[i][j]  = min(a[i-1][j-1], a[i-1][j]+1, a[i][j-1]+1);
当x[i]!=y[j]时：a[i][j] =  min(a[i-1][j-1], a[i-1][j], a[i][j-1])+1;

简单实现过程如下：

代码如下:

<?PHP
    $s1 = "abcdd";
    $l1 = strlen($s1);
    $s2 = "aabbd";
    $l2 = strlen($s2);

 
    for ($i = 0; $i < $l1; $i++) {
        $a[0][$i + 1] = $i + 1;
    }
    for ($i = 0; $i < $l2; $i++) {
        $a[$i + 1][0] = $i + 1;
    }

    for ($i = 0; $i < $l2; $i++) {
        for ($j = 0; $j < $l1; $j++) {
            if ($s2[$i] == $s1[$j]) {
                $a[$i + 1][$j + 1] = min($a[$i][$j], $a[$i][$j + 1] + 1, $a[$i + 1][$j] + 1);
            }else{
                $a[$i + 1][$j + 1] = min($a[$i][$j], $a[$i][$j + 1], $a[$i + 1][$j]) + 1;
            }
        }
    }

    echo $a[$l1][$l2];
    echo "n";
    echo levenshtein($s1, $s2);

代码如下:

<?PHP
    $s1 = "abcjfdkslfdd";
    $l1 = strlen($s1);
    $s2 = "aab84093840932bd";
    $l2 = strlen($s2);

    $dis = 0;
    for ($i = 0; $i <= $l2; $i++){
        $p1[$i] = $i;
    }

    for ($i = 0; $i < $l1; $i++){
        $p2[0] = $p1[0] + 1;

        for ($j = 0; $j < $l2; $j++){
            if ($s1[$i] == $s2[$j]){
                $dis = min($p1[$j], $p1[$j + 1] + 1, $p2[$j] + 1);
            }else{
                $dis = min($p1[$j] + 1, $p1[$j + 1] + 1, $p2[$j] + 1);  // 注意这里最后一个参数为$p2  
            }
            $p2[$j + 1] = $dis;
        }
        $tmp = $p1;
        $p1 = $p2;
        $p2 = $tmp;  
    }

    echo "n";
    echo $p1[$l2];
    echo "n";
    echo levenshtein($s1, $s2);

Levenshtein distance说明Levenshtein distance最先是由俄国科学家Vladimir Levenshtein在1965年发明，用他的名字命名。不会拼读，可以叫它edit distance（编辑距离）。Levenshtein distance可以用来：Spell checking(拼写检查)Speech recognition(语句识别)DNA analysis(DNA分析)Plagiarism detection(抄袭检测) LD用mn的矩阵存储距离值。

注：关于PHP相似度计算函数：levenshtein用法示例的内容就先介绍到这里，更多相关文章的可以留意