levenshtein

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

levenshtein二つの文字列のレーベンシュタイン距離を計算する

説明

levenshtein(
    string $string1,
    string $string2,
    int $insertion_cost = 1,
    int $replacement_cost = 1,
    int $deletion_cost = 1
): int

レーベンシュタイン距離は、string1string2 に変換するために置換、挿入、削除 しなければならない最小の文字数として定義されます。アルゴリズムの複雑さは、 O(m*n) です。 ここで、n および m はそれぞれ string1 および string2 の長さです O(max(n,m)**3) となる similar_text() よりは良いですが、 まだかなりの計算量です)。

insertion_cost, replacement_cost かつ/または deletion_cost1 以外の場合、 変換コストが最も小さいアルゴリズムを採用します。 たとえば、$insertion_cost + $deletion_cost < $replacement_cost の場合、 置換をせず、挿入と削除が行われます。

パラメータ

string1

レーベンシュタイン距離を計算する文字列のひとつ。

string2

レーベンシュタイン距離を計算する文字列のひとつ。

insertion_cost

挿入のコストを定義します。

replacement_cost

置換のコストを定義します。

deletion_cost

削除のコストを定義します。

戻り値

この関数は、引数で指定した二つの文字列のレーベンシュタイン距離を返します。 引数文字列の一つが 255 文字の制限より長い場合に -1 を返します。

変更履歴

バージョン 説明
8.0.0 これより前のバージョンでは、 levenshtein() 関数は引数を2個、 または5個指定して呼び出さなければなりませんでした。

例1 levenshtein() の例

<?php
// スペルミスした単語を入力します
$input 'carrrot';

// チェックするための単語の配列
$words  = array('apple','pineapple','banana','orange',
                
'radish','carrot','pea','bean','potato');

// まだ最短距離は見つかっていません
$shortest = -1;

// 最短距離を見つけるため単語をループします
foreach ($words as $word) {

    
// 入力した単語と現在の単語の距離を
    // 計算します
    
$lev levenshtein($input$word);

    
// マッチするかどうかチェックします
    
if ($lev == 0) {

        
// 最短な単語はこれだ (マッチした)
        
$closest $word;
        
$shortest 0;

        
// ループを抜ける; マッチしたものを見つけました
        
break;
    }

    
// もし距離が次に見つけた最短距離よりも短い場合、
    // もしくは次の最短の単語がまだ見つかっていない場合
    
if ($lev <= $shortest || $shortest 0) {
        
// 最短のマッチと最短距離をセットします
        
$closest  $word;
        
$shortest $lev;
    }
}

echo 
"入力した単語: $input\n";
if (
$shortest == 0) {
    echo 
"一致するものが見つかりました: $closest\n";
} else {
    echo 
"もしかして: $closest\n";
}

?>

上の例の出力は以下となります。

入力した単語: carrrot
もしかして: carrot

参考

  • soundex() - 文字列の soundex キーを計算する
  • similar_text() - 二つの文字列の間の類似性を計算する
  • metaphone() - 文字列の metaphone キーを計算する

関連キーワード:  計算, cost, 二つ, levenshtein, 定義, コスト, replacement, insertion, int, 関数