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

# levenshtein

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

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

### 説明

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

レーベンシュタイン距離は、`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() - 文字列の soundex キーを計算する
- similar_text() - 二つの文字列の間の類似性を計算する
- metaphone() - 文字列の metaphone キーを計算する

`↑` and `↓` to navigate • `Enter` to select • `Esc` to close • `/` to open