levenshtein

(PHP 4 >= 4.0.1, PHP 5, PHP 7, PHP 8)

levenshtein計(jì)算兩個(gè)字符串之間的編輯距離

說明

levenshtein(string $str1, string $str2): int
levenshtein(
    string $str1,
    string $str2,
    int $cost_ins,
    int $cost_rep,
    int $cost_del
): int

編輯距離,是指兩個(gè)字串之間,通過替換、插入、刪除等操作將字符串str1轉(zhuǎn)換成str2所需要操作的最少字符數(shù)量。 該算法的復(fù)雜度是 O(m*n),其中 nm 分別是str1str2的長(zhǎng)度 (當(dāng)和算法復(fù)雜度為O(max(n,m)**3)的similar_text()相比時(shí),此函數(shù)還是相當(dāng)不錯(cuò)的,盡管仍然很耗時(shí)。)。

在最簡(jiǎn)單的形式中,該函數(shù)只以兩個(gè)字符串作為參數(shù),并計(jì)算通過插入、替換和刪除等操作將str1轉(zhuǎn)換成str2所需要的操作次數(shù)。

第二種變體將采用三個(gè)額外的參數(shù)來定義插入、替換和刪除操作的次數(shù)。此變體比第一種更加通用和適應(yīng),但效率不高。

參數(shù)

str1

求編輯距離中的其中一個(gè)字符串

str2

求編輯距離中的另一個(gè)字符串

cost_ins

定義插入次數(shù)

cost_rep

定義替換次數(shù)

cost_del

定義刪除次數(shù)

返回值

此函數(shù)返回兩個(gè)字符串參數(shù)之間的編輯距離,如果其中一個(gè)字符串參數(shù)長(zhǎng)度大于限制的255個(gè)字符時(shí),返回-1。

范例

示例 #1 levenshtein() 例子:

<?php
// 輸入拼寫錯(cuò)誤的單詞
$input 'carrrot';

// 要檢查的單詞數(shù)組
$words  = array('apple','pineapple','banana','orange',
                
'radish','carrot','pea','bean','potato');

// 目前沒有找到最短距離
$shortest = -1;

// 遍歷單詞來找到最接近的
foreach ($words as $word) {

    
// 計(jì)算輸入單詞與當(dāng)前單詞的距離
    
$lev levenshtein($input$word);

    
// 檢查完全的匹配
    
if ($lev == 0) {

        
// 最接近的單詞是這個(gè)(完全匹配)
        
$closest $word;
        
$shortest 0;

        
// 退出循環(huán);我們已經(jīng)找到一個(gè)完全的匹配
        
break;
    }

    
// 如果此次距離比上次找到的要短
    // 或者還沒找到接近的單詞
    
if ($lev <= $shortest || $shortest 0) {
        
// 設(shè)置最接近的匹配以及它的最短距離
        
$closest  $word;
        
$shortest $lev;
    }
}

echo 
"Input word: $input\n";
if (
$shortest == 0) {
    echo 
"Exact match found: $closest\n";
} else {
    echo 
"Did you mean: $closest?\n";
}

?>

以上例程會(huì)輸出:

Input word: carrrot
Did you mean: carrot?

參見