レーベンシュタイン距離

レーベンシュタイン距離（レーベンシュタインきょり、）は、二つの文字列または一般の記号列の差異を、1個の記号の挿入・削除・置換によって一方を他方へ変換するために必要な最小操作回数として表す距離である。古典的な定義では、挿入・削除・置換の各操作のコストを1とするV. I. Levenshtein, “Binary codes capable of correcting deletions, insertions, and reversals”, Doklady Akademii Nauk SSSR, 163(4), 845–848, 1965. 英訳は Soviet Physics Doklady, 10(8), 707–710, 1966. Math-Net.。

名称は、1965年にこの距離を符号理論の文脈で導入したウラジーミル・レーベンシュタインにちなむ。レーベンシュタイン距離は編集距離（edit distance）の代表的な一種である。「編集距離」という語は、文脈によってはレーベンシュタイン距離そのものを指すが、より一般には、許される編集操作や各操作のコストを変更した距離の総称としても用いられるGonzalo Navarro, “A guided tour to approximate string matching”, ACM Computing Surveys, 33(1), 31–88, 2001. doi:10.1145/375360.375365.。

定義

二つの文字列

と

を考える。を、の先頭文字との先頭文字の間のレーベンシュタイン距離とする。

空文字列に対しては

である。、のとき、

ただし、

と定める。3つの候補はそれぞれ、元の文字列からの削除、目的文字列の文字の挿入、一致または置換に対応するRobert A. Wagner and Michael J. Fischer, “The String-to-String Correction Problem”, Journal of the ACM, 21(1), 168–173, 1974. doi:10.1145/321796.321811.。求める距離はである。

例

「kitten」を「sitting」へ変換する場合、例えば次の3操作で変換できる。

kitten → sitten（k を s に置換） sitten → sittin（e を i に置換） sittin → sitting（末尾に g を挿入）

これより距離は高々3である。一方、2回以下の編集では変換できないため、

となる。

性質

古典的なレーベンシュタイン距離は距離の公理を満たす。すなわち、非負性、同一性、対称性、三角不等式が成立する。

長さとの文字列について、

が成り立つ。下限は、挿入または削除1回で文字列長が1しか変化しないことによる。上限は、共通する長さの部分を置換し、残りを挿入または削除すればよいことから得られる。

二つの文字列の長さが等しい場合、ハミング距離はレーベンシュタイン距離の上界である。

ハミング距離では置換しか許されないのに対し、レーベンシュタイン距離では挿入・削除も使用できるためである。

置換を許さず、挿入と削除だけを許す場合には、二つの文字列の長さを、最長共通部分列の長さをとすると、最小編集回数は

となる。古典的なレーベンシュタイン距離では置換1回のコストが1であるため、この式はそのままでは適用できない。

計算法

動的計画法

標準的な計算法は動的計画法であり、各接頭辞間の距離をの表に保存する。

function LevenshteinDistance(s[1..m], t[1..n]): create d[0..m, 0..n]

for i = 0..m: d[i,0] = i

for j = 0..n: d[0,j] = j

for i = 1..m: for j = 1..n: if s[i] = t[j]: 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 // 一致または置換 )

return d[m,n]

全ての表を計算する場合、時間計算量は、空間計算量もである。「だから常に高速」という意味ではなく、長い列どうしを大量に比較する用途では二次時間が実用上の制約となり得る。

距離の値だけが必要な場合、各行は直前の行と現在の行だけに依存するため、短い方の文字列を列方向に取れば必要な作業領域をに減らせる。

編集操作列の復元

表全体を保持している場合は、右下のから、現在の値を与えた直前のセルを逆向きにたどることで、最適な編集操作列を復元できる。同じ最小値を与える経路が複数存在することがあり、その場合、距離は同じでも最適な編集操作列は一意ではない。

距離が小さい場合の計算

二つの文字列の実際の編集距離が文字列長に比べて小さい場合、表全体を計算する必要はない。Ukkonen は、距離の上限や実際の距離を利用して、動的計画表の必要な帯状領域だけを調べる厳密アルゴリズムを示したEsko Ukkonen, “Algorithms for approximate string matching”, Information and Control, 64(1–3), 100–118, 1985. doi:10.1016/S0019-9958(85)80046-2.。ここでいう「近似文字列照合」は、距離の値を近似するという意味ではなく、完全一致でない文字列も照合対象に含めるという意味である。

ビット並列法

Myers は1999年、動的計画法の複数の状態をマシン語のビット列に詰め、ビット演算を用いて並列に更新する方法を示した。これは近似パターン照合を高速化する代表的な手法の一つであるGene Myers, “A fast bit-vector algorithm for approximate string matching based on dynamic programming”, Journal of the ACM, 46(3), 395–415, 1999. doi:10.1145/316542.316550.。

また、Bitapアルゴリズムも、許容する編集距離が小さいパターン照合に利用され、agrep などの実装で知られる。

計算量に関する結果

一般の場合の正確な編集距離については、Backurs と Indyk が2015年、Strong Exponential Time Hypothesis (SETH) が真であるならば、任意の定数に対して時間で解くアルゴリズムは存在しない、という条件付き下界を示したArturs Backurs and Piotr Indyk, “Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)”, Proceedings of the 47th Annual ACM Symposium on Theory of Computing, 51–58, 2015. doi:10.1145/2746539.2746612.。これは無条件の二次時間下界ではなく、SETH に依存する結果である。

変種と関連する距離

重み付き編集距離

挿入・削除・置換に異なるコストを与えたり、文字の組合せごとに置換コストを変えたりする拡張を重み付き編集距離という。任意のコストを設定しても自動的に距離の公理が保たれるわけではなく、例えば方向によって異なるコストを与えれば対称性が失われることがある。

ダメラウ・レーベンシュタイン距離は、隣接する2文字の転置を追加の編集操作として許す代表的な関連距離である。

= 正規化

レーベンシュタイン距離は文字列が長いほど大きな値を取り得るため、長さの異なる文字列を比較するときには正規化した値を用いることがある。ただし、正規化レーベンシュタイン距離に唯一の標準定義があるわけではない。

日本の研究・実務資料では、例えば

とし、0を完全一致、1に近いほど差が大きい値として扱う方法や、その補数

を類似度として用いる方法が見られる藤岡雄大・高久雅生「日本のテレビ放送における番組のシリーズを同定する手法の開発」『情報知識学会誌』32巻2号, 2022, pp.267–286. J-STAGE.デジタル庁『政府等保有データのAI学習データへの変換に係る調査研究最終報告書』2025年. デジタル庁.。

日本語・Unicode文字列での注意

数学的な定義は「記号列」に対して行われるため、実装では何を1記号として数えるかを明示する必要がある。Unicode文字列では、符号化後のバイト列、コード単位、Unicodeコードポイント、あるいはユーザーが1文字と知覚する単位に近い書記素クラスタを比較単位とすることができ、選択によって距離が異なる場合がある。

例えば、日本語の「ガ」は単一のコードポイントとして表現することも、「カ」と結合濁点の2コードポイントとして表現することもできる。見た目や意味が同じでもコードポイント列が異なるため、コードポイント単位で単純比較すると距離が生じる可能性がある。Unicode Standard Annex #15 は、こうした正規等価な表現を扱う NFC・NFD などの正規化形式を定義しているUnicode Consortium, “Unicode Standard Annex #15: Unicode Normalization Forms”. Unicode Consortium.。

また、Unicode Standard Annex #29 は、利用者が1文字と知覚する単位の近似として extended grapheme cluster を定義しているUnicode Consortium, “Unicode Standard Annex #29: Unicode Text Segmentation”. Unicode Consortium.。日本語では濁点・半濁点を結合文字として持つ表現などがあるため、検索、OCR評価、表記ゆれ処理などでは、どの単位で分割してから距離を計算するかが結果に影響し得る。

互換正規化 NFKC・NFKD は、半角・全角などの互換表現も統合し得る一方、アプリケーションが保持したい表記上の差まで失わせる場合がある。そのため、「常にNFKCを適用すべき」ということではなく、用途に応じて正規化方針を定める必要がある。

応用

スペル訂正・OCR

スペルチェッカーや光学文字認識 (OCR) の誤り訂正では、認識結果と辞書語との文字列距離を候補選択に利用できる。日本語OCRに関する研究では、英字・カタカナの認識誤り訂正において、一次候補を絞り込んだ後、入力語と候補語とのレーベンシュタイン距離を計算して最終候補を選ぶ方法が提案されている畑田稔・遠藤裕英「日本語OCRにおける英字・カタカナのスペル誤り訂正法」『情報処理学会論文誌』38巻7号, 1317–1327, 1997年. CiNii Research.。

自然言語処理

レーベンシュタイン距離は文字だけでなく、単語や音素などを記号とする列にも適用できる。自然言語処理では、文の単語列を比較する評価指標として編集距離が用いられる例がある。日本の文法誤り訂正研究では、入力文と出力文の単語に基づくレーベンシュタイン距離を集計した「単語編集率」がコーパスの特徴量として用いられている三田雅人・水本智也・金子正弘・永田亮・乾健太郎「文法誤り訂正モデルの横断評価」『自然言語処理』28巻1号, 160–182, 2021年. doi:10.5715/jnlp.28.160.。

音声認識

音声認識では、参照転記と認識結果の単語列を編集操作で整列し、置換数、削除数、挿入数、参照側の単語数から

として Word Error Rate (WER) を求める。これは単語を記号とみなした編集距離に基づく評価であるNational Institute of Standards and Technology, NIST Special Publication 1112. NIST.。

方言・音韻比較

音声・音韻を記号列として表し、レーベンシュタイン距離を方言間の差の定量化に利用する研究がある。日本の方言研究についても、先行研究でレーベンシュタイン距離を用いて「共通語度」を算出し、クラスタ分析による方言分類を行った事例が報告されている入江さやか・金明哲「方言録音文字化資料における拍bigramから見た方言分類―岐阜・愛知方言の所属は東か西か―」『計量国語学』32巻1号, 1–18, 2019年. J-STAGE.。

文書比較・剽窃検出

文書の類似性評価にも編集距離が用いられる。日本語文書では、そのまま文字列として比較するだけでなく、形態素解析などの前処理を行い、単語単位で比較する方法も研究されている。情報処理学会の研究報告では、オンライン提出レポートの剽窃検出に編集距離と圧縮比率を併用し、日本語文書では形態素解析を用いた前処理を行う方法が検討されている上田和志・富永浩之「類似性に基づくレポート剽窃の検出ツールのプラグイン化」『情報処理学会研究報告コンピュータと教育』2010-CE-103(4), 2010年. 情報処理学会電子図書館.。

バイオインフォマティクス

バイオインフォマティクスでは、編集距離と配列アラインメントは密接に関係する。挿入・削除・置換はDNAやタンパク質配列の差を表す単純なモデルとして利用できるが、実際の配列アラインメントでは、置換行列やギャップペナルティなど、古典的な単位コストのレーベンシュタイン距離より豊かなスコアモデルを用いることが多いBonnie Berger, Michael S. Waterman, and Yun William Yu, “Levenshtein Distance, Sequence Comparison and Biological Database Search”, IEEE Transactions on Information Theory, 67(6), 3287–3294, 2021. doi:10.1109/TIT.2020.2996543.。

したがって、レーベンシュタイン距離そのものから生物種の分岐年代を直接推定できる、と一般化して説明するのは適切ではない。系統推定や分岐年代推定には、進化モデルや置換率など、別の仮定と方法が必要になる。

歴史

レーベンシュタインは1965年、削除・挿入などの誤りを訂正できる符号の研究の中で、後にレーベンシュタイン距離と呼ばれる距離を導入した。現在一般的な二次元表による計算法は、レーベンシュタインの原論文そのものに提示されたものではない。

1970年代には文字列比較に対する動的計画法が複数の分野で発展し、Wagner と Fischer は1974年に文字列から文字列への訂正問題を一般的に定式化した。その後、距離が小さい場合の高速化、ビット並列法、オートマトンを用いる方法などが研究されている。

脚注

参考文献

Dan Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997, ISBN 0-521-58519-8. Gonzalo Navarro, “A guided tour to approximate string matching”, ACM Computing Surveys, 33(1), 31–88, 2001. Bonnie Berger, Michael S. Waterman, Yun William Yu, “Levenshtein Distance, Sequence Comparison and Biological Database Search”, IEEE Transactions on Information Theory, 67(6), 3287–3294, 2021.

レーベンシュタイン距離

Źródło i licencja