PHP マニュアル: 二つの文字列のレーベンシュタイン距離を計算する

説明

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

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

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

パラメータ

string1: レーベンシュタイン距離を計算する文字列のひとつ。
string2: レーベンシュタイン距離を計算する文字列のひとつ。
insertion_cost: 挿入のコストを定義します。
replacement_cost: 置換のコストを定義します。
deletion_cost: 削除のコストを定義します。

戻り値

この関数は、引数で指定した二つの文字列のレーベンシュタイン距離を返します。

変更履歴

バージョン	説明
8.0.0	これより前のバージョンでは、引数を2個、または5個指定して呼び出さなければなりませんでした。
8.0.0	これより前のバージョンでは、引数文字列の一つが 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

参考

soundex
similar_text
metaphone