首頁 後端開發 php教程 关于PHP的相似度计算函数:levenshtein的使用介绍_PHP教程

关于PHP的相似度计算函数:levenshtein的使用介绍_PHP教程

Jul 21, 2016 pm 03:11 PM
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() 函数提供需要更少修改的更精确的结果。
例子

复制代码 代码如下:

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


输出: 1 30

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

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

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

复制代码 代码如下:

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


执行会报Warning: The general Levenshtein support is not there yet。这是因为现在这个方法还没有实现,仅仅是放了一个坑在那。

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;


在用状态转移方程前,我们需要初始化(n+1)(m+1)的矩阵d,并让第一行和列的值从0开始增长。 扫描两字符串(nm级的),对比字符,使用状态转移方程,最终$a[$l1][$l2]为其结果。

简单实现过程如下:

复制代码 代码如下:

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

 
    for ($i = 0; $i         $a[0][$i + 1] = $i + 1;
    }
    for ($i = 0; $i         $a[$i + 1][0] = $i + 1;
    }

    for ($i = 0; $i         for ($j = 0; $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的实现中,实现者在注释中很清楚的标明:此函数仅优化了内存使用,而没有考虑速度,从其实现算法看,时间复杂度为O(m×n)。其优化点在于将上面的状态转移方程中的二维数组变成了两个一组数组。简单实现如下:
复制代码 代码如下:

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

    $dis = 0;
    for ($i = 0; $i         $p1[$i] = $i;
    }

    for ($i = 0; $i         $p2[0] = $p1[0] + 1;

        for ($j = 0; $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);

如上为PHP内核开发者对前面经典DP的优化,其优化点在于不停的复用两个一维数组,一个记录上次的结果,一个记录这一次的结果。如果按照PHP的参数,分别给三个操作赋值不同的值,在上面的算法中将对应的1变成操作对应的值就可以了。 min函数的第一个参数对应的是修改,第二个参数对应的是删除源码天空,第三个参数对应的是添加。

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

www.bkjia.comtruehttp://www.bkjia.com/PHPjc/326849.htmlTechArticle使用说明 先看手册上 levenshtein() 函数的说明: levenshtein() 函数返回两个字符串之间的 Levenshtein 距离。 Levenshtein 距离,又称编辑距离,指的...
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

AI Hentai Generator

AI Hentai Generator

免費產生 AI 無盡。

熱門文章

R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
2 週前 By 尊渡假赌尊渡假赌尊渡假赌
倉庫:如何復興隊友
4 週前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒險:如何獲得巨型種子
3 週前 By 尊渡假赌尊渡假赌尊渡假赌

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

適用於 Ubuntu 和 Debian 的 PHP 8.4 安裝和升級指南 適用於 Ubuntu 和 Debian 的 PHP 8.4 安裝和升級指南 Dec 24, 2024 pm 04:42 PM

適用於 Ubuntu 和 Debian 的 PHP 8.4 安裝和升級指南

CakePHP 專案配置 CakePHP 專案配置 Sep 10, 2024 pm 05:25 PM

CakePHP 專案配置

CakePHP 日期和時間 CakePHP 日期和時間 Sep 10, 2024 pm 05:27 PM

CakePHP 日期和時間

CakePHP 檔案上傳 CakePHP 檔案上傳 Sep 10, 2024 pm 05:27 PM

CakePHP 檔案上傳

CakePHP 路由 CakePHP 路由 Sep 10, 2024 pm 05:25 PM

CakePHP 路由

討論 CakePHP 討論 CakePHP Sep 10, 2024 pm 05:28 PM

討論 CakePHP

如何設定 Visual Studio Code (VS Code) 進行 PHP 開發 如何設定 Visual Studio Code (VS Code) 進行 PHP 開發 Dec 20, 2024 am 11:31 AM

如何設定 Visual Studio Code (VS Code) 進行 PHP 開發

CakePHP 快速指南 CakePHP 快速指南 Sep 10, 2024 pm 05:27 PM

CakePHP 快速指南

See all articles