ダメラウ・レーベンシュタイン距離

ウィキペディア

ダメラウ・レーベンシュタイン距離

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/13 02:02 UTC 版)

ダメラウ・レーベンシュタイン距離（ダメラウ・レーベンシュタインきょり、英: Damerau–Levenshtein distance）は、2つの配列の間の編集距離を測定するために情報理論と計算機科学で使われる文字列計量である。2つの単語間のダメラウ・レーベンシュタイン距離は、一方の単語を他方の単語に変換するのに必要な最小の操作回数である。ここで1回の「操作」とは1文字の挿入、削除、置換、あるいは2つの隣り合う文字の交換である。ダメラウ・レーベンシュタイン距離はフレデリック J. ダメラウとウラジミール I. レーベンシュタインにちなんで名付けられた 。

古典的なレーベンシュタイン距離を定義する操作は3つの古典的単文字編集操作、すなわち文字の挿入、削除、および置換である。ダメラウ・レーベンシュタイン距離を定義する操作にはこれらに加えて隣接文字交換が含まれている。

ダメラウによると、スペルミス全体の80%以上は、これら4操作のうちの1操作の誤り1つで表現できる。ダメラウの論文では、最大1回の編集操作で訂正できる綴り間違いのみが考慮されていた。当初の動機は、スペルチェッカなどのアプリケーション・ソフトウェアを改善するために人間のスペルミス間の距離を測定することであったが、ダメラウ・レーベンシュタイン距離は、生物学においてタンパク質配列の変異を測定するためにも使われている。

ダメラウ・レーベンシュタイン距離と制限ダメラウ・レーベンシュタイン距離

同じ文字列を2度以上編集することを許さない条件のもとで求められる編集距離を制限編集距離と呼ぶ。制限編集距離は最適文字列整列距離と呼ばれる量に一致することが知られている。この条件を課さない（つまり同じ文字列を1回より多く編集してよい）場合には、単に編集距離と呼ぶ。制限レーベンシュタイン距離は常にレーベンシュタイン距離に一致する。これは、レーベンシュタイン距離の計算では編集操作は1文字ごとであり、1度編集した文字列を2度編集する必要がないからである。しかし2文字の編集操作が存在するダメラウ・レーベンシュタイン距離に関しては、制限ダメラウ・レーベンシュタイン距離とダメラウ・レーベンシュタイン距離とが一致しない場合がある。

例として、CAとABCの編集距離を求める。CAに1回の隣接文字交換および1回の文字挿入を施せば CA → AC → ABC となるから、ダメラウ・レーベンシュタイン距離は $\operatorname {LD} ({\text{CA}},{\text{ABC}})=2$

ウィキペディア小見出し辞書

ダメラウ・レーベンシュタイン距離

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/25 09:06 UTC 版)

「ダメラウ・レーベンシュタイン距離」の記事における「ダメラウ・レーベンシュタイン距離」の解説

次は、真のダメラウ・レーベンシュタイン距離を求めるアルゴリズムである。このアルゴリズムでは、アルファベットに含まれる全文字 Σ の個数 | Σ | が必要になる。成分が [0, |Σ|) に含まれる配列を使うからである:A:93。擬似コードは： algorithm DL-distance is input: strings a[1..length(a)], b[1..length(b)] output: distance, integer da := |Σ|個の整数からなる配列 for i := 1 to |Σ| inclusive do da[i] := 0 let d[−1..length(a), −1..length(b)] // d は次元が length(a)+2, length(b)+2 の二次元整数配列 // d の添字は -1 から始まり、a, b, および da の添字は 1 から始まることに注意 maxdist := length(a) + length(b) d[−1, −1] := maxdist for i := 0 to length(a) inclusive do d[i, −1] := maxdist d[i, 0] := i for j := 0 to length(b) inclusive do d[−1, j] := maxdist d[0, j] := j for i := 1 to length(a) inclusive do db := 0 for j := 1 to length(b) inclusive do k := da[b[j]] ℓ := db if a[i] = b[j] then cost := 0 db := j else cost := 1 d[i, j] := minimum(d[i−1, j−1] + cost, //置換 d[i, j−1] + 1, //挿入 d[i−1, j ] + 1, //削除 d[k−1, ℓ−1] + (i−k−1) + 1 + (j-ℓ−1)) //交換 da[a[i]] := i return d[length(a), length(b)] 非制限ダメラウ・レーベンシュタイン距離を求める正しいアルゴリズムを作るには次のことに注意する：1度交換された文字がそのあと2度と編集されないような編集操作の最適配列が存在する（交換のコスト W T が挿入のコスト W I と削除のコスト W D の平均以上つまり 2 W T ≥ W I + W D の場合に成立する）。したがって、1つの部分文字列を2回以上編集する2つの対称な方法： 隣接文字を交換して任意の個数の文字をその間に挿入する 文字列を削除し、その削除によって新たに隣り合うことになった隣接文字を交換する のいずれかだけを考えればよい。このアイディアを素直に実行するアルゴリズムは、文字列の長さ M および N に対して O ( M N ⋅ max ( M , N ) ) の計算複雑性を持つ。ローランスとワグナーのアイディアを使ったアルゴリズムでは、最悪の場合でも O ( M N ) に改善される。 Bitapアルゴリズムを、隣接交換を処理するように変更できる。この例については参考文献の情報収集の節を見よ。