12.89 util.levenshtein - Levenshtein編集距離 ¶

Module: util.levenshtein ¶

このモジュールは二つのシーケンスの間の編集距離を計算する手続きを提供します。 編集距離とは、ひとつのシーケンスからもうひとつのシーケンスへと変更する 編集操作の数です。3つのアルゴリズムが実装されています。

Levenshtein distance

1要素の削除、1要素の追加、1要素の置き換えそれぞれを1操作と数えます。

Damerau-Levenshtein distance

削除、追加、置き換えに加え、隣合った要素の入れ替えも1操作と数えます。

Restricted edit distance

Optimal string alignmentとも呼ばれます。Damerau-Levenshteinと似ていますが、 隣合った要素の入れ替えを行った場合、それらの要素は以降の編集を受けません。

これらのアルゴリズムは文字列に対して使われることが多いですが、 このモジュールの手続きはシーケンスになら何でも使えます (gauche.sequence - シーケンスフレームワーク参照)。

Function: l-distance seq-A seq-B :key elt= cutoff ¶

Function: l-distances seq-A seq-Bs :key elt= cutoff ¶

Function: re-distance seq-A seq-B :key elt= cutoff ¶

Function: re-distances seq-A seq-Bs :key elt= cutoff ¶

Function: dl-distance seq-A seq-B :key elt= cutoff ¶

Function: dl-distances seq-A seq-Bs :key elt= cutoff ¶

{util.levenshtein} それぞれ、与えられたシーケンス間のLevenshtein距離(l-*)、 Restricted edit距離(re-*)およびDamerau-Levenshtein距離(dl-*)を 計算します。アルゴリズム毎にふたつのAPIが提供されます。 単数形の*-distanceは、二つのシーケンスseq-Aとseq-Bを取り、 両者の間の距離を計算します。 複数形の*-distancesは、一つのシーケンスseq-Aと シーケンスのリストseq-Bsをとり、seq-Bsの各シーケンスと seq-Aとの距離を計算します。

あるシーケンスと、多数のシーケンスとの間の距離を計算したいなら、 単数形のAPIを繰り返し呼ぶより複数形のAPIを使う方が効率的です。 複数形のAPIでは内部で使うデータ構造を再利用するので、 重複するアロケーションと初期化の時間を節約できます。

シーケンスは、<sequence>プロトコルを満足するオブジェクトであれば 何でも構いません (gauche.sequence - シーケンスフレームワーク参照)。

キーワード引数elt=はシーケンスの要素同士を比較するのに使われます。 デフォルトはeqv?です。

キーワード引数cutoffは非負の正確な整数でなければなりません。与えられた場合、 二つのシーケンスの距離を比較していて、それがcutoff以上になることがわかったら、 それ以上の計算を打ち切り#fを結果とします。 これは、特にたくさんのシーケンスから、ごく限られた限度以下の距離を持つものを探す 場合に便利です。

現在の実装ではだいたい、Levenshteinが最も速く、Damerau-Levenshteinが最も遅く、 Restricted editがその中間です。置換を1操作と考える必要がなければ、 Levenshteinを使うのが良いでしょう。catからactは Levenshtein距離では2ですが他の距離では1です。 置換を1操作とする必要があれば、re-かdl-を 使うことになります。re-の落とし穴は、それが三角不等式を満たさないことです。 つまり、3つのシーケンスX, Y, Zがある時、 (Damerau-)Levenshtein距離Lは常に L(X;Z) <= L(X;Y) + L(Y;Z) を満たしますが、Restricted edit距離には その保証がありません。

(l-distance "cat" "act")  ⇒ 2
(l-distances "cat" '("Cathy" "scathe" "stack")
  :elt= char-ci=?)
  ⇒ (2 3 4)

(re-distance "cat" "act") ⇒ 1

(re-distances "pepper"
  '("peter" "piper" "picked" "peck" "pickled" "peppers")
  :cutoff 4)
  ⇒ (2 2 4 4 #f 1)

(dl-distance '(a b c d e) '(c d a b e)) ⇒ 4

註: 単数形のAPIの第2引数にうっかりシーケンスのリストを渡してしまった場合でも、 直ちにエラーになるとは限らないことに注意。リスト自体もシーケンスだからです。