首頁 後端開發 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脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

記事本++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

PHP 8.4 帶來了多項新功能、安全性改進和效能改進,同時棄用和刪除了大量功能。 本指南介紹如何在 Ubuntu、Debian 或其衍生版本上安裝 PHP 8.4 或升級到 PHP 8.4

我後悔之前不知道的 7 個 PHP 函數 我後悔之前不知道的 7 個 PHP 函數 Nov 13, 2024 am 09:42 AM

如果您是經驗豐富的PHP 開發人員,您可能會感覺您已經在那裡並且已經完成了。操作

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

Visual Studio Code,也稱為 VS Code,是一個免費的原始碼編輯器 - 或整合開發環境 (IDE) - 可用於所有主要作業系統。 VS Code 擁有大量針對多種程式語言的擴展,可以輕鬆編寫

在PHP API中說明JSON Web令牌(JWT)及其用例。 在PHP API中說明JSON Web令牌(JWT)及其用例。 Apr 05, 2025 am 12:04 AM

JWT是一種基於JSON的開放標準,用於在各方之間安全地傳輸信息,主要用於身份驗證和信息交換。 1.JWT由Header、Payload和Signature三部分組成。 2.JWT的工作原理包括生成JWT、驗證JWT和解析Payload三個步驟。 3.在PHP中使用JWT進行身份驗證時,可以生成和驗證JWT,並在高級用法中包含用戶角色和權限信息。 4.常見錯誤包括簽名驗證失敗、令牌過期和Payload過大,調試技巧包括使用調試工具和日誌記錄。 5.性能優化和最佳實踐包括使用合適的簽名算法、合理設置有效期、

php程序在字符串中計數元音 php程序在字符串中計數元音 Feb 07, 2025 pm 12:12 PM

字符串是由字符組成的序列,包括字母、數字和符號。本教程將學習如何使用不同的方法在PHP中計算給定字符串中元音的數量。英語中的元音是a、e、i、o、u,它們可以是大寫或小寫。 什麼是元音? 元音是代表特定語音的字母字符。英語中共有五個元音,包括大寫和小寫: a, e, i, o, u 示例 1 輸入:字符串 = "Tutorialspoint" 輸出:6 解釋 字符串 "Tutorialspoint" 中的元音是 u、o、i、a、o、i。總共有 6 個元

您如何在PHP中解析和處理HTML/XML? 您如何在PHP中解析和處理HTML/XML? Feb 07, 2025 am 11:57 AM

本教程演示瞭如何使用PHP有效地處理XML文檔。 XML(可擴展的標記語言)是一種用於人類可讀性和機器解析的多功能文本標記語言。它通常用於數據存儲

解釋PHP中的晚期靜態綁定(靜態::)。 解釋PHP中的晚期靜態綁定(靜態::)。 Apr 03, 2025 am 12:04 AM

靜態綁定(static::)在PHP中實現晚期靜態綁定(LSB),允許在靜態上下文中引用調用類而非定義類。 1)解析過程在運行時進行,2)在繼承關係中向上查找調用類,3)可能帶來性能開銷。

什麼是PHP魔術方法(__ -construct,__destruct,__call,__get,__ set等)並提供用例? 什麼是PHP魔術方法(__ -construct,__destruct,__call,__get,__ set等)並提供用例? Apr 03, 2025 am 12:03 AM

PHP的魔法方法有哪些? PHP的魔法方法包括:1.\_\_construct,用於初始化對象;2.\_\_destruct,用於清理資源;3.\_\_call,處理不存在的方法調用;4.\_\_get,實現動態屬性訪問;5.\_\_set,實現動態屬性設置。這些方法在特定情況下自動調用,提升代碼的靈活性和效率。

See all articles