levenshtein函數(shù)怎么在PHP中使用-創(chuàng)新互聯(lián)

levenshtein函數(shù)怎么在PHP中使用？相信很多沒有經(jīng)驗(yàn)的人對(duì)此束手無策，為此本文總結(jié)了問題出現(xiàn)的原因和解決方法，通過這篇文章希望你能解決這個(gè)問題。

十年的金華網(wǎng)站建設(shè)經(jīng)驗(yàn)，針對(duì)設(shè)計(jì)、前端、開發(fā)、售后、文案、推廣等六對(duì)一服務(wù)，響應(yīng)快，48小時(shí)及時(shí)工作處理。成都全網(wǎng)營(yíng)銷的優(yōu)勢(shì)是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動(dòng)調(diào)整金華建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì)，從而大程度地提升瀏覽體驗(yàn)。成都創(chuàng)新互聯(lián)從事“金華網(wǎng)站設(shè)計(jì)”,“金華網(wǎng)站推廣”以來，每個(gè)客戶項(xiàng)目都認(rèn)真落實(shí)執(zhí)行。

 levenshtein() 函數(shù)的說明：

levenshtein() 函數(shù)返回兩個(gè)字符串之間的 Levenshtein 距離。

Levenshtein 距離，又稱編輯距離，指的是兩個(gè)字符串之間，由一個(gè)轉(zhuǎn)換成另一個(gè)所需的最少編輯操作次數(shù)。許可的編輯操作包括將一個(gè)字符替換成另一個(gè)字符，插入一個(gè)字符，刪除一個(gè)字符。

例如把 kitten 轉(zhuǎn)換為 sitting：

sitten （k→s）
sittin （e→i）
sitting （→g）levenshtein() 函數(shù)給每個(gè)操作（替換、插入和刪除）相同的權(quán)重。不過，您可以通過設(shè)置可選的 insert、replace、delete 參數(shù)，來定義每個(gè)操作的代價(jià)。

語法：

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

參數(shù) 描述

string1 必需。要對(duì)比的第一個(gè)字符串。
string2 必需。要對(duì)比的第二個(gè)字符串。
insert 可選。插入一個(gè)字符的代價(jià)。默認(rèn)是 1。
replace 可選。替換一個(gè)字符的代價(jià)。默認(rèn)是 1。
delete 可選。刪除一個(gè)字符的代價(jià)。默認(rèn)是 1。
提示和注釋

如果其中一個(gè)字符串超過 255 個(gè)字符，levenshtein() 函數(shù)返回 -1。
levenshtein() 函數(shù)對(duì)大小寫不敏感。
levenshtein() 函數(shù)比 similar_text() 函數(shù)更快。不過，similar_text() 函數(shù)提供需要更少修改的更精確的結(jié)果。
例子


復(fù)制代碼 代碼如下:


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


輸出： 1 30

源碼分析
levenshtein() 屬于標(biāo)準(zhǔn)函數(shù)，在/ext/standard/目錄下有專門針對(duì)此函數(shù)實(shí)現(xiàn)的文件：levenshtein.c。

levenshtein()會(huì)根據(jù)參數(shù)個(gè)數(shù)選擇實(shí)現(xiàn)方式，針對(duì)參數(shù)為2和參數(shù)為5的情況，都會(huì)調(diào)用 reference_levdist() 函數(shù)計(jì)算距離。其不同在于對(duì)后三個(gè)參數(shù)，參數(shù)為2時(shí)，使用默認(rèn)值1。

并且在實(shí)現(xiàn)源碼中我們發(fā)現(xiàn)了一個(gè)在文檔中沒有說明的情況： levenshtein() 函數(shù)還可以傳遞三個(gè)參數(shù)，其最終會(huì)調(diào)用 custom_levdist() 函數(shù)。它將第三個(gè)參數(shù)作為自定義函數(shù)的實(shí)現(xiàn)，其調(diào)用示例如下：


復(fù)制代碼 代碼如下:


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


執(zhí)行會(huì)報(bào)Warning： The general Levenshtein support is not there yet。這是因?yàn)楝F(xiàn)在這個(gè)方法還沒有實(shí)現(xiàn)，僅僅是放了一個(gè)坑在那。

reference_levdist() 函數(shù)的實(shí)現(xiàn)算法是一個(gè)經(jīng)典的DP問題。

給定兩個(gè)字符串x和y，求最少的修改次數(shù)將x變成y。修改的規(guī)則只能是如下三種之一：刪除、插入、改變。
用a[i][j]表示把x的前i個(gè)字符變成y的前j個(gè)字符所需的最少操作次數(shù)，則狀態(tài)轉(zhuǎn)移方程為：


復(fù)制代碼 代碼如下:


當(dāng)x[i]==y[j]時(shí)：a[i][j]  = min(a[i-1][j-1], a[i-1][j]+1, a[i][j-1]+1);
當(dāng)x[i]!=y[j]時(shí)：a[i][j] =  min(a[i-1][j-1], a[i-1][j], a[i][j-1])+1;


在用狀態(tài)轉(zhuǎn)移方程前，我們需要初始化(n+1)(m+1)的矩陣d，并讓第一行和列的值從0開始增長(zhǎng)。 掃描兩字符串（nm級(jí)的），對(duì)比字符，使用狀態(tài)轉(zhuǎn)移方程，最終$a[$l1][$l2]為其結(jié)果。

簡(jiǎn)單實(shí)現(xiàn)過程如下：


復(fù)制代碼 代碼如下:


<?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的實(shí)現(xiàn)中，實(shí)現(xiàn)者在注釋中很清楚的標(biāo)明：此函數(shù)僅優(yōu)化了內(nèi)存使用，而沒有考慮速度，從其實(shí)現(xiàn)算法看，時(shí)間復(fù)雜度為O(m×n)。其優(yōu)化點(diǎn)在于將上面的狀態(tài)轉(zhuǎn)移方程中的二維數(shù)組變成了兩個(gè)一組數(shù)組。簡(jiǎn)單實(shí)現(xiàn)如下：


復(fù)制代碼 代碼如下:


<?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);  // 注意這里最后一個(gè)參數(shù)為$p2 
            }
            $p2[$j + 1] = $dis;
        }
        $tmp = $p1;
        $p1 = $p2;
        $p2 = $tmp; 
    }

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



如上為PHP內(nèi)核開發(fā)者對(duì)前面經(jīng)典DP的優(yōu)化，其優(yōu)化點(diǎn)在于不停的復(fù)用兩個(gè)一維數(shù)組，一個(gè)記錄上次的結(jié)果，一個(gè)記錄這一次的結(jié)果。如果按照PHP的參數(shù)，分別給三個(gè)操作賦值不同的值，在上面的算法中將對(duì)應(yīng)的1變成操作對(duì)應(yīng)的值就可以了。 min函數(shù)的第一個(gè)參數(shù)對(duì)應(yīng)的是修改，第二個(gè)參數(shù)對(duì)應(yīng)的是刪除源碼天空，第三個(gè)參數(shù)對(duì)應(yīng)的是添加。

Levenshtein distance說明
Levenshtein distance最先是由俄國(guó)科學(xué)家Vladimir Levenshtein在1965年發(fā)明，用他的名字命名。不會(huì)拼讀，可以叫它edit distance（編輯距離）。Levenshtein distance可以用來：
Spell checking(拼寫檢查)
Speech recognition(語句識(shí)別)
DNA analysis(DNA分析)
Plagiarism detection(抄襲檢測(cè)) LD用mn的矩陣存儲(chǔ)距離值。

看完上述內(nèi)容，你們掌握levenshtein函數(shù)怎么在PHP中使用的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！

新聞名稱：levenshtein函數(shù)怎么在PHP中使用-創(chuàng)新互聯(lián)
分享地址：http://muchs.cn/article26/dspicg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計(jì)公司、網(wǎng)站制作、虛擬主機(jī)、電子商務(wù)、微信小程序、做網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)

微信小程序開發(fā)