この関数は、引数で指定した二つの文字列のLevenshtein距離を返します。
引数文字列の一つが255文字の制限より長い場合に-1を返します。
(255は名前や辞書比較に関して十分な長さであり、PHPでの通常の比較に 関しては問題となる制約ではありません)
Levenshtein距離は
str1
を
str2
に変換するために置換、挿入、削除しな ければならない最小の文字数として定義されます。アルゴリズムの複雑 さは、
O(m*n)
です。 ただし、
n
および
m
は、
str1
および
str2
の長さです。 (O(max(n,m)**3)となる
similar_text()
よりは良いですが まだかなりの計算量です)
上記の最も簡単な形式では、この関数はパラメータとして引数を二つだ けとり、
str1
から
str2
に変換する際に必要な挿入、置換、削除演 算の数のみを計算します。
2番目の形式では、挿入、置換、削除演算のコストを定義する3番目のパ
ラメータが追加されます。この形式は1番目の形式より一般的で汎用性が 高いですが、効率的ではありません。
3番目の形式(これは未実装です)は、最も一般的で汎用的ですが、最も遅
い形式でもあります。この形式では各演算毎にコストを定義するために ユーザ定義関数をコールします。
ユーザ定義関数は、次のような引数を指定してコールされます。
適用する演算: 'I'、'R'、'D'
文字列1の文字の実体
文字列2の文字の実体
文字列1での位置
文字列2での位置
文字列1での残りの文字
文字列2での残りの文字
ユーザ定義関数を使用する形式では、挿入、置換、削除のコストを定義
する際に特定の記号(文字)またはこれらの記号を含む句の相関や差異を
考慮する手法をとることが可能となります。しかし、この代償として他
の二つの形式では動作するCPUレジスタの使用に関する最適化の実行は行 われず、キャッシュも動作しなくなります。
soundex()
、
similar_text()
、
metaphone()
も参照下さい。