ダメラウ・レーベンシュタイン距離
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/03/26 01:20 UTC 版)
ダメラウ・レーベンシュタイン距離（ダメラウ・レーベンシュタインきょり、英: Damerau–Levenshtein distance）は、2つの配列の間の編集距離を測定するために情報理論と計算機科学で使われる文字列計量である。2つの単語間のダメラウ・レーベンシュタイン距離は、一方の単語を他方の単語に変換するのに必要な最小の操作回数である。ここで1回の「操作」とは1文字の挿入、削除、置換、あるいは2つの隣り合う文字の交換である。ダメラウ・レーベンシュタイン距離はフレデリック J. ダメラウとウラジミール I. レーベンシュタインにちなんで名付けられた[1] [2] [3]。
- ^ Brill, Eric; Moore, Robert C. (2000). “An Improved Error Model for Noisy Channel Spelling Correction”. Proceedings of the 38th Annual Meeting on Association for Computational Linguistics. pp. 286–293. doi:10.3115/1075218.1075255. オリジナルの2012-12-21時点におけるアーカイブ。
- ^ 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”. 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-04-01時点におけるアーカイブ。
- ^ 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
- 1 ダメラウ・レーベンシュタイン距離とは
- 2 ダメラウ・レーベンシュタイン距離の概要
- 3 応用
ダメラウ・レーベンシュタイン距離
出典: フリー百科事典『ウィキペディア（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アルゴリズムを、隣接交換を処理するように変更できる。この例については参考文献の情報収集の節を見よ。
※この「ダメラウ・レーベンシュタイン距離」の解説は、「ダメラウ・レーベンシュタイン距離」の解説の一部です。
「ダメラウ・レーベンシュタイン距離」を含む「ダメラウ・レーベンシュタイン距離」の記事については、「ダメラウ・レーベンシュタイン距離」の概要を参照ください。
- ダメラウ・レーベンシュタイン距離のページへのリンク
