無料CGI、PHPサイト(確認画面付きメールフォーム・メーリングリスト・メルマガ設置、逆アクセスランキング、画像カウンター等)PHPマニュアル by k-sky

levenshtein

(PHP 4 >= 4.0.1, PHP 5)

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

説明

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

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

上記の最も簡単な形式では、この関数はパラメータとして引数を二つだけとり、 str1 から str2 に変換する際に必要な 挿入、置換、削除演算の数のみを計算します。

2 番目の形式では、挿入、置換、削除演算のコストを定義する 3 番目のパラメータが追加されます。この形式は 1 番目の形式より一般的で 汎用性が高いですが、効率的ではありません。

パラメータ

str1

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

str2

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

cost_ins

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

cost_rep

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

cost_del

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

返り値

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

例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