PHP マニュアル
前のページ |  | 次のページ

# levenshtein

(PHP 3>= 3.0.17, PHP 4 >= 4.0.1)

levenshtein -- 二つの文字列の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()も参照下さい。

前のページ | ホーム | 次のページ
join | 上に戻る | localeconv