ダメラウ・レーベンシュタイン距離
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/25 09:06 UTC 版)
「ダメラウ・レーベンシュタイン距離」の記事における「ダメラウ・レーベンシュタイン距離」の解説
次は、真のダメラウ・レーベンシュタイン距離を求めるアルゴリズムである。このアルゴリズムでは、アルファベットに含まれる全文字 Σ の個数 | Σ | {\displaystyle |\Sigma |} が必要になる。成分が [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 {\displaystyle W_{T}} が挿入のコスト W I {\displaystyle W_{I}} と削除のコスト W D {\displaystyle W_{D}} の平均以上つまり 2 W T ≥ W I + W D {\displaystyle 2W_{T}\geq W_{I}+W_{D}} の場合に成立する）。したがって、1つの部分文字列を2回以上編集する2つの対称な方法： 隣接文字を交換して任意の個数の文字をその間に挿入する 文字列を削除し、その削除によって新たに隣り合うことになった隣接文字を交換する のいずれかだけを考えればよい。このアイディアを素直に実行するアルゴリズムは、文字列の長さ M {\displaystyle M} および N {\displaystyle N} に対して O ( M N ⋅ max ( M , N ) ) {\displaystyle O(MN\cdot \max(M,N))} の計算複雑性を持つ。ローランスとワグナーのアイディアを使ったアルゴリズムでは、最悪の場合でも O ( M N ) {\displaystyle O(MN)} に改善される。 Bitapアルゴリズムを、隣接交換を処理するように変更できる。この例については参考文献の情報収集の節を見よ。
※この「ダメラウ・レーベンシュタイン距離」の解説は、「ダメラウ・レーベンシュタイン距離」の解説の一部です。
「ダメラウ・レーベンシュタイン距離」を含む「ダメラウ・レーベンシュタイン距離」の記事については、「ダメラウ・レーベンシュタイン距離」の概要を参照ください。
Weblioに収録されているすべての辞書からダメラウ・レーベンシュタイン距離を検索する場合は、下記のリンクをクリックしてください。
全ての辞書からダメラウ・レーベンシュタイン距離
を検索
- ダメラウ・レーベンシュタイン距離のページへのリンク
