levenshtein

説明

int levenshtein ( string str1, string str2)

int levenshtein ( string str1, string str2, int cost_ins, int cost_rep, int cost_del)

int levenshtein ( string str1, string str2, function cost)

この関数は、引数で指定した二つの文字列の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()も参照下さい。