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

ダメラウ・レーベンシュタイン距離（ダメラウ・レーベンシュタインきょり、）は、2つの配列の間の編集距離を測定するために情報理論と計算機科学で使われる文字列計量である。2つの単語間のダメラウ・レーベンシュタイン距離は、一方の単語を他方の単語に変換するのに必要な最小の操作回数である。ここで1回の「操作」とは1文字の挿入、削除、置換、あるいは2つの隣り合う文字の交換である。ダメラウ・レーベンシュタイン距離はとウラジミール I. レーベンシュタインにちなんで名付けられた 。
古典的なレーベンシュタイン距離を定義する操作は3つの古典的単文字編集操作、すなわち文字の挿入、削除、および置換である。ダメラウ・レーベンシュタイン距離を定義する操作にはこれらに加えて隣接文字交換が含まれている 。
ダメラウによると、スペルミス全体の80%以上は、これら4操作のうちの1操作の誤り1つで表現できる。ダメラウの論文では、最大1回の編集操作で訂正できる綴り間違いのみが考慮されていた。当初の動機は、スペルチェッカなどのアプリケーション・ソフトウェアを改善するために人間のスペルミス間の距離を測定することであったが、ダメラウ・レーベンシュタイン距離は、生物学においてタンパク質配列の変異を測定するためにも使われている 。
ダメラウ・レーベンシュタイン距離と制限ダメラウ・レーベンシュタイン距離.
同じ文字列を2度以上編集することを許さない条件のもとで求められる編集距離を制限編集距離と呼ぶ。制限編集距離は最適文字列整列距離と呼ばれる量に一致することが知られている。この条件を課さない（つまり同じ文字列を1回より多く編集してよい）場合には、単に編集距離と呼ぶ。制限レーベンシュタイン距離は常にレーベンシュタイン距離に一致する。これは、レーベンシュタイン距離の計算では編集操作は1文字ごとであり、1度編集した文字列を2度編集する必要がないからである。しかし2文字の編集操作が存在するダメラウ・レーベンシュタイン距離に関しては、制限ダメラウ・レーベンシュタイン距離とダメラウ・レーベンシュタイン距離とが一致しない場合がある。
例として、CAとABCの編集距離を求める。CAに1回の隣接文字交換および1回の文字挿入を施せば CA → AC → ABC となるから、ダメラウ・レーベンシュタイン距離はformula_1である。これに対して、制限距離（あるいは最適文字列整列距離 Optimal String Alignment, OSA）を求めるための編集は1回の文字削除に続いて2回の文字挿入を施す CA → A → AB → ABC であり、制限距離は formula_2である。ダメラウ・レーベンシュタイン距離を求めるときに使った編集 CA → AC → ABC が使えないのは、B を挿入する時点で同じ文字列を2回編集しており、この編集は制限距離を求める操作では禁止されているからである。制限距離については、三角不等式が一般には成立しないことに注意する。実際、formula_3である。つまり制限距離は計量ではない。
ここでは計算が簡単な制限ダメラウ・レーベンシュタイン距離を求める。文字列 formula_4の先頭から数えて formula_5番目の1文字を formula_6とし、formula_4の先頭から formula_5番目までの長さ formula_5の部分文字列を formula_10とする。2つの文字列 formula_11および formula_12の間の制限ダメラウ・レーベンシュタイン距離を定義するためにまず、文字列 formula_4の部分文字列 formula_10と、formula_12の部分文字列 formula_16の間の制限距離関数 formula_17を、次のように再帰的に定義する： 
formula_18
ここでformula_19は、formula_20のときformula_21になり、それ以外の場合にformula_22となる指示関数である。これらの場合分けはそれぞれ、次に示す部分文字列末尾の編集操作（あるいは編集操作しないこと）に対応している： 
formula_4とformula_12の間の制限ダメラウ・レーベンシュタイン距離は、文字列全体の関数値 formula_58で与えられる。ここでformula_59およびformula_60はそれぞれ文字列formula_4およびformula_12の長さ（文字数）である。
アルゴリズム.
ここでは2つのアルゴリズムを示す。1つ目は、制限ダメラウ・レーベンシュタイン距離""を求めるアルゴリズムである。これは2つ目のアルゴリズムに比べて単純である。2つ目のアルゴリズムは、非制限ダメラウ・レーベンシュタイン距離を求めるもので、レーベンシュタイン距離に隣接交換を追加して計算する。隣接交換を追加すると非常に複雑になる。
制限ダメラウ・レーベンシュタイン距離.
制限ダメラウ・レーベンシュタイン距離は、レーベンシュタイン距離を計算するワグナー・フィッシャー動的計画法アルゴリズムを単純に拡張することで計算できる。その擬似コードは： 
 algorithm OSA-distance is
 input: strings a[1..length(a)], b[1..length(b)]
 output: distance, integer
 let d[0..length(a), 0..length(b)] // d は整数二次元配列で次元は length(a)+1, length(b)+1
 // ここでは d は添字が 0 から始まる配列であり、a と b は添字が 1 から始まる配列であることに注意する
 for i := 0 to length(a) inclusive do
 d[i, 0] := i
 for j := 0 to length(b) inclusive do
 d[0, j] := j
 for i := 1 to length(a) inclusive do
 for j := 1 to length(b) inclusive do
 if a[i] = b[j] then
 cost := 0
 else
 cost := 1
 d[i, j] := minimum(d[i-1, j] + 1, // 削除
 d[i, j-1] + 1, // 挿入
 d[i-1, j-1] + cost) // 置換
 if i > 1 and j > 1 and a[i] = b[j-1] and a[i-1] = b[j] then // 隣接文字交換：ここから
 d[i, j] := minimum(d[i, j],
 d[i-2, j-2] + cost) // 隣接文字交換：ここまで
 return d[length(a), length(b)]
レーベンシュタイン距離を求めるアルゴリズムとの違いは、隣接文字交換にあたる計算が含まれる点である。
ダメラウ・レーベンシュタイン距離.
次は、真のダメラウ・レーベンシュタイン距離を求めるアルゴリズムである。このアルゴリズムでは、アルファベットに含まれる全文字 の個数formula_63が必要になる。成分が に含まれる配列を使うからである。擬似コードは：
 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度と編集されないような編集操作の最適配列が存在する（交換のコストformula_64が挿入のコストformula_65と削除のコストformula_66の平均以上つまりformula_67の場合に成立する）。したがって、1つの部分文字列を2回以上編集する2つの対称な方法：
のいずれかだけを考えればよい。このアイディアを素直に実行するアルゴリズムは、文字列の長さformula_68およびformula_69に対してformula_70の計算複雑性を持つ。ローランスとワグナーのアイディアを使ったアルゴリズムでは、最悪の場合でもformula_71に改善される。
Bitapアルゴリズムを、隣接交換を処理するように変更できる。この例については参考文献の情報収集の節を見よ。
応用.
ダメラウ・レーベンシュタイン距離は、自然言語処理において重要である。自然言語では文字列が短く、誤り（綴り間違い）の個数が2を超えることは少ない。このような場合、制限編集距離と非制限編集距離の値が異なることは稀である。オーメンとロークは、一般化交換を導入して制限編集距離を拡張した。しかし、制限編集距離は一般には三角不等式を満足せず計量ではないので、メトリックツリーに使えないことに注意すべきである。
DNA.
DNAでは挿入、削除、置換、および交換が頻繁に生じ、しかもどれも同程度の時間スケールで起こるので、ダメラウ・レーベンシュタイン距離は2つのDNA鎖の間の変化を計る計量として使うことができる。DNA、タンパク質、および他のバイオインフォマティクスなど、要素の整列に関連する課題では、ダメラウ・レーベンシュタイン距離に深く関係するニードルマン・ブンシュ・アルゴリズムやスミス・ウォーターマン・アルゴリズムなどを使うのが一般的である。
輸出規制.
アメリカ合衆国政府は統合スクリーニング・リストAPIで、あいまい語検索のためにダメラウ・レーベンシュタイン距離を利用している。