ダメラウ・レーベンシュタイン距離
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/13 02:02 UTC 版)
ダメラウ・レーベンシュタイン距離（ダメラウ・レーベンシュタインきょり、英: 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 となるから、ダメラウ・レーベンシュタイン距離は
Weblioに収録されているすべての辞書からダメラウ・レーベンシュタイン距離を検索する場合は、下記のリンクをクリックしてください。
全ての辞書からダメラウ・レーベンシュタイン距離
を検索
- ダメラウ・レーベンシュタイン距離のページへのリンク
