levenshtein
(PHP 3 >= 3.0.17, PHP 4 >= 4.0.1, PHP 5)
levenshtein --
二つの文字列の Levenshtein 距離を計算する
説明
int
levenshtein ( string str1, string str2 [, int cost_ins, int cost_rep, int cost_del] )
この関数は、引数で指定した二つの文字列の Levenshtein 距離を返します。
引数文字列の一つが 255 文字の制限より長い場合に -1 を返します。
Levenshtein 距離は、str1 を
str2 に変換するために置換、挿入、削除
しなければならない最小の文字数として定義されます。アルゴリズムの複雑さは、
O(m*n) です。
ただし、n および m は、
str1 および str2 の長さです
(O(max(n,m)**3) となる similar_text() よりは良いですが、
まだかなりの計算量です)。
上記の最も簡単な形式では、この関数はパラメータとして引数を二つだけとり、
str1 から
str2 に変換する際に必要な
挿入、置換、削除演算の数のみを計算します。
2 番目の形式では、挿入、置換、削除演算のコストを定義する
3 番目のパラメータが追加されます。この形式は 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 word: $input\n"; if ($shortest == 0) { echo "Exact match found: $closest\n"; } else { echo "Did you mean: $closest?\n"; }
?>
|
上の例の出力は以下となります。 Input word: carrrot
Did you mean: carrot? |
|
soundex(),
similar_text(),
metaphone()
も参照ください。