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

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

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

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

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

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

例として、CAとABCの編集距離を求める。CAに1回の隣接文字交換および1回の文字挿入を施せば CA → AC → ABC となるから、ダメラウ・レーベンシュタイン距離は $\operatorname {LD} ({\text{CA}},{\text{ABC}})=2$ である。これに対して、制限距離（あるいは最適文字列整列距離 Optimal String Alignment, OSA）を求めるための編集は1回の文字削除に続いて2回の文字挿入を施す CA → A → AB → ABC であり、制限距離は ${\textstyle \operatorname {OSA} ({\text{CA}},{\text{ABC}})=3}$ である。ダメラウ・レーベンシュタイン距離を求めるときに使った編集 CA → AC → ABC が使えないのは、B を挿入する時点で同じ文字列を2回編集しており、この編集は制限距離を求める操作では禁止されているからである。制限距離については、三角不等式が一般には成立しないことに注意する。実際、 $\operatorname {OSA} ({\text{CA}},{\text{AC}})+\operatorname {OSA} ({\text{AC}},{\text{ABC}})<\operatorname {OSA} ({\text{CA}},{\text{ABC}})$ である。つまり制限距離は計量ではない。

ここでは計算が簡単な制限ダメラウ・レーベンシュタイン距離を求める。文字列 ${\textstyle a}$ の先頭から数えて ${\textstyle i}$ 番目の1文字を ${\textstyle a[i]}$ とし、 ${\textstyle a}$ の先頭から ${\textstyle i}$ 番目までの長さ ${\textstyle i}$ の部分文字列を ${\textstyle a[1,i]}$ とする。2つの文字列 $a$ および ${\textstyle b}$ の間の制限ダメラウ・レーベンシュタイン距離を定義するためにまず、文字列 ${\textstyle a}$ の部分文字列 ${\textstyle a[1,i]}$ と、 ${\textstyle b}$ の部分文字列 ${\textstyle b[1,j]}$ の間の制限距離関数 ${\textstyle \operatorname {d} _{a,b}(i,j)}$ を、次のように再帰的に定義する： ^[7] ^:A:11

$\qquad \operatorname {d} _{a,b}(i,j)=\min {\begin{cases}0&{\text{if }}i=j=0\\\operatorname {d} _{a,b}(i-1,j)+1&{\text{if }}i>0\\\operatorname {d} _{a,b}(i,j-1)+1&{\text{if }}j>0\\\operatorname {d} _{a,b}(i-1,j-1)+1_{(a[i]\neq b[j])}&{\text{if }}i,j>0\\\operatorname {d} _{a,b}(i-2,j-2)+1&{\text{if }}i,j>1{\text{ and }}a[i]=b[j-1]{\text{ and }}a[i-1]=b[j]\\\end{cases}}$

ここで ${\textstyle 1_{(a[i]\neq b[j])}}$ は、 ${\textstyle a[i]=b[j]}$ のとき ${\textstyle 0}$ になり、それ以外の場合に ${\textstyle 1}$ となる指示関数である。これらの場合分けはそれぞれ、次に示す部分文字列末尾の編集操作（あるいは編集操作しないこと）に対応している：

${\textstyle 0}$ ：2つの長さ ${\textstyle 0}$ の文字列を一致させるのに必要な編集回数は ${\textstyle 0}$
${\textstyle \operatorname {d} _{a,b}(i-1,j)+1}$ ： ${\textstyle a[1,i]}$ が、 ${\textstyle a[1,i-1]}$ に1回の挿入をすることで得られたと見なして編集回数を ${\textstyle 1}$ だけ増やす
$\operatorname {d} _{a,b}(i,j-1)+1$ ： ${\textstyle b[1,j]}$ が、 ${\textstyle b[1,j-1]}$ に1回の挿入をすることで得られたと見なして編集回数を ${\textstyle 1}$ だけ増やす
${\textstyle \operatorname {d} _{a,b}(i-1,j-1)+1_{(a[i]\neq b[j])}}$ ： ${\textstyle a[i]}$ と ${\textstyle b[j]}$ が一致する場合には、 ${\textstyle a[1,i]}$ と ${\textstyle b[1,j]}$ の間の距離は ${\textstyle a[1,i-1]}$ と ${\textstyle b[1,j-1]}$ の間の距離に等しいので編集回数を変更しない。 ${\textstyle a[i]}$ と ${\textstyle b[j]}$ が一致しない場合には、 ${\textstyle a[i]}$ を ${\textstyle b[j]}$ に、あるいは ${\textstyle b[j]}$ を ${\textstyle a[i]}$ に置換したと見なして編集回数を ${\textstyle 1}$ だけ増やす
${\textstyle \operatorname {d} _{a,b}(i-2,j-2)+1}$ ： ${\textstyle a[i]=b[j-1]}$ かつ ${\textstyle a[i-1]=b[j]}$ のとき、 ${\textstyle a[i-1]}$ と ${\textstyle a[i]}$ の交換、あるいは ${\textstyle a[i-1]}$ と ${\textstyle a[i]}$ の交換をしたと見なして編集回数を ${\textstyle 1}$ 回だけ増やす

${\textstyle a}$ と ${\textstyle b}$ の間の制限ダメラウ・レーベンシュタイン距離は、文字列全体の関数値 ${\textstyle \operatorname {d} _{a,b}(|a|,|b|)}$ で与えられる。ここで ${\textstyle |a|}$ および ${\textstyle |b|}$ はそれぞれ文字列 ${\textstyle a}$ および ${\textstyle b}$ の長さ（文字数）である。

アルゴリズム

ここでは2つのアルゴリズムを示す。1つ目は、制限ダメラウ・レーベンシュタイン距離^[7]を求めるアルゴリズム^[8]である。これは2つ目のアルゴリズムに比べて単純である。2つ目のアルゴリズムは、非制限ダメラウ・レーベンシュタイン距離を求めるもので、レーベンシュタイン距離に隣接交換を追加して計算する^[9]。隣接交換を追加すると非常に複雑になる。

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

制限ダメラウ・レーベンシュタイン距離は、レーベンシュタイン距離を計算するワグナー・フィッシャー動的計画法アルゴリズムを単純に拡張することで計算できる。その擬似コードは：

 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)]

レーベンシュタイン距離を求めるアルゴリズムとの違いは、隣接文字交換にあたる計算が含まれる点である。

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

次は、真のダメラウ・レーベンシュタイン距離を求めるアルゴリズムである。このアルゴリズムでは、アルファベットに含まれる全文字 $Σ$ の個数 $|\Sigma |$ が必要になる。成分が $[0, |Σ|)$ に含まれる配列を使うからである^[7]^: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}$ の平均以上つまり $2W_{T}\geq W_{I}+W_{D}$ の場合に成立する^[9]）。したがって、1つの部分文字列を2回以上編集する2つの対称な方法：

隣接文字を交換して任意の個数の文字をその間に挿入する
文字列を削除し、その削除によって新たに隣り合うことになった隣接文字を交換する

のいずれかだけを考えればよい。このアイディアを素直に実行するアルゴリズムは、文字列の長さ $M$ および $N$ に対して $O(MN\cdot \max(M,N))$ の計算複雑性を持つ。ローランスとワグナーのアイディア^[9]を使ったアルゴリズムでは、最悪の場合でも $O(MN)$ に改善される。

Bitapアルゴリズムを、隣接交換を処理するように変更できる。この例については参考文献^[1]の情報収集の節を見よ。

応用

ダメラウ・レーベンシュタイン距離は、自然言語処理において重要である。自然言語では文字列が短く、誤り（綴り間違い）の個数が2を超えることは少ない。このような場合、制限編集距離と非制限編集距離の値が異なることは稀である。オーメンとローク^[8]は、一般化交換を導入して制限編集距離を拡張した。しかし、制限編集距離は一般には三角不等式を満足せず計量ではないので、メトリックツリーに使えないことに注意すべきである。

DNA

DNAでは挿入、削除、置換、および交換が頻繁に生じ、しかもどれも同程度の時間スケールで起こるので、ダメラウ・レーベンシュタイン距離は2つのDNA鎖の間の変化を計る計量として使うことができる。DNA、タンパク質、および他のバイオインフォマティクスなど、要素の整列に関連する課題では、ダメラウ・レーベンシュタイン距離に深く関係するニードルマン・ブンシュ・アルゴリズムやスミス・ウォーターマン・アルゴリズムなどを使うのが一般的である。

輸出規制

アメリカ合衆国政府は統合スクリーニング・リストAPI^[10]で、あいまい語検索のためにダメラウ・レーベンシュタイン距離を利用している。

その他

Ispell はダメラウ・レーベンシュタイン距離が1の単語を訂正候補として提示する

脚注

[脚注の使い方]

^ Brill, Eric; Moore, Robert C. (2000). An Improved Error Model for Noisy Channel Spelling Correction (PDF). Proceedings of the 38th Annual Meeting on Association for Computational Linguistics. pp. 286–293. doi:10.3115/1075218.1075255. 2012年12月21日時点のオリジナル (PDF)よりアーカイブ。
^ ^a ^b Bard, Gregory V. (2007), “Spelling-error tolerant, order-independent pass-phrases via the Damerau–Levenshtein string-edit distance metric”, Proceedings of the Fifth Australasian Symposium on ACSW Frontiers : 2007, Ballarat, Australia, January 30 - February 2, 2007, Conferences in Research and Practice in Information Technology, 68, Darlinghurst, Australia: Australian Computer Society, Inc., pp. 117–124, ISBN 978-1-920682-49-1 .
^ Li (2006). Exploring distributional similarity based models for query spelling correction (PDF). Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics. pp. 1025–1032. doi:10.3115/1220175.1220304. 2010年4月1日時点のオリジナル (PDF)よりアーカイブ。
^ Levenshtein, Vladimir I. (February 1966), “Binary codes capable of correcting deletions, insertions, and reversals”, Soviet Physics Doklady 10 (8): 707–710
^ Damerau, Fred J. (March 1964), “A technique for computer detection and correction of spelling errors”, Communications of the ACM 7 (3): 171–176, doi:10.1145/363958.363994
^ The method used in: Majorek, Karolina A.; Dunin-Horkawicz, Stanisław et al. (2013), “The RNase H-like superfamily: new members, comparative structural analysis and evolutionary classification”, Nucleic Acids Research 42 (7): 4160–4179, doi:10.1093/nar/gkt1414, PMC 3985635, PMID 24464998
^ ^a ^b ^c Boytsov, Leonid (May 2011). “Indexing methods for approximate dictionary searching”. Journal of Experimental Algorithmics 16: 1. doi:10.1145/1963190.1963191.
^ ^a ^b Oommen, B. J.; Loke, R. K. S. (1997). “Pattern recognition of strings with substitutions, insertions, deletions and generalized transpositions”. Pattern Recognition 30 (5): 789–800. doi:10.1016/S0031-3203(96)00101-X.
^ ^a ^b ^c Lowrance, Roy; Wagner, Robert A. (April 1975), “An Extension of the String-to-String Correction Problem”, J ACM 22 (2): 177–183, doi:10.1145/321879.321880
^ http://developer.trade.gov/consolidated-screening-list.html

さらに学ぶために

Navarro, Gonzalo (March 2001), “A guided tour to approximate string matching”, ACM Computing Surveys 33 (1): 31–88, doi:10.1145/375360.375365

[1] Brill, Eric; Moore, Robert C. (2000). An Improved Error Model for Noisy Channel Spelling Correction (PDF). Proceedings of the 38th Annual Meeting on Association for Computational Linguistics. pp. 286–293. doi:10.3115/1075218.1075255. 2012年12月21日時点のオリジナル (PDF)よりアーカイブ。

[bard-2] Bard, Gregory V. (2007), “Spelling-error tolerant, order-independent pass-phrases via the Damerau–Levenshtein string-edit distance metric”, Proceedings of the Fifth Australasian Symposium on ACSW Frontiers : 2007, Ballarat, Australia, January 30 - February 2, 2007, Conferences in Research and Practice in Information Technology, 68, Darlinghurst, Australia: Australian Computer Society, Inc., pp. 117–124, ISBN 978-1-920682-49-1 .

[3] Li (2006). Exploring distributional similarity based models for query spelling correction (PDF). Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics. pp. 1025–1032. doi:10.3115/1220175.1220304. 2010年4月1日時点のオリジナル (PDF)よりアーカイブ。

[4] Levenshtein, Vladimir I. (February 1966), “Binary codes capable of correcting deletions, insertions, and reversals”, Soviet Physics Doklady 10 (8): 707–710

[5] Damerau, Fred J. (March 1964), “A technique for computer detection and correction of spelling errors”, Communications of the ACM 7 (3): 171–176, doi:10.1145/363958.363994

[6] The method used in: Majorek, Karolina A.; Dunin-Horkawicz, Stanisław et al. (2013), “The RNase H-like superfamily: new members, comparative structural analysis and evolutionary classification”, Nucleic Acids Research 42 (7): 4160–4179, doi:10.1093/nar/gkt1414, PMC 3985635, PMID 24464998

[Boytsov-7] Boytsov, Leonid (May 2011). “Indexing methods for approximate dictionary searching”. Journal of Experimental Algorithmics 16: 1. doi:10.1145/1963190.1963191.

[oommen-8] Oommen, B. J.; Loke, R. K. S. (1997). “Pattern recognition of strings with substitutions, insertions, deletions and generalized transpositions”. Pattern Recognition 30 (5): 789–800. doi:10.1016/S0031-3203(96)00101-X.

[LW75-9] Lowrance, Roy; Wagner, Robert A. (April 1975), “An Extension of the String-to-String Correction Problem”, J ACM 22 (2): 177–183, doi:10.1145/321879.321880

[10] ttp://developer.trade.gov/consolidated-screening-list.html

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[1]

[10]