levenshtein関数

類似文字列マッチの実装例 今度はPHPのlevenshtein関数を見て「そういえばこんな関数あったっけなぁ」と思い、ちょっとテスト。levenshtein関数が計算するlevenshtein（レーベンシュタイン）距離については、以下が詳しい。

• レーベンシュタイン距離 - Wikipedia
• http://www.merriampark.com/ld.htm

次のコードの元ネタは、PHPマニュアルに掲載されているサンプル。

<?php
$input = '';
if (isset($_POST['keyword']) && $_POST['keyword'] !== '') {
    $input = $_POST['keyword'];

    $words  = array('PHP','ソフトウェア','ほげほげ', 'あれこれ');
    $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 '入力した単語: ' . htmlspecialchars($input, ENT_QUOTES) . '<br>';
    if ($shortest == 0) {
        echo '一致するものが見つかりました：' . $closest . '<br>';
    } else {
        echo 'もしかして：' . $closest . '<br>';
    }
}
?>
<form action="" method="post">
キーワード：<input type="text" name="keyword">
</form>

ほほぅ。mbstring.internal_encoding=eucjp-winだと、一応日本語も通るみたい。
辞書が大きくなったときのパフォーマンスは？ということで、利用可能な全PHP関数を辞書にしてみた。これはDo You PHP?のEXPERIENCEに用意してみたけど、1100件程度しかない。。。十万単位とかそれ以上でどんな感じか見てみたい。
辞書次第では色々使えるな。。。