レッスン
理論 — レーベンシュタイン距離ビジュアライザー
レーベンシュタイン距離とは、2 つの文字列について、一方を他方へ変えるのに必要な 1 文字単位の編集の最小回数です。編集とは挿入・削除・置換のいずれかを指します。これは「やり方のあらゆる可能性にわたる最小値」であり、だからこそ目で見て求めるのは難しく、表を使えば簡単になります。編集手順の組み合わせは天文学的な数にのぼりますが、この方法はその一つも列挙せずに最短のものを求めます。
各記号の意味
m, n- 2 つの文字列 A と B の長さ。
D(i, j)- A の先頭 i 文字を B の先頭 j 文字へ変える最小コスト。このページの表の 1 マスにあたります。
[aᵢ ≠ bⱼ]- その 2 文字が異なれば 1、一致すれば 0。置換の値段で、置換する必要がなければ無料になります。
d- 求める答え
D(m, n)。右下のマスです。
公式の導き方
- マスを埋める前に、1 マスの意味を決めます。
D(i, j)を、A の先頭i文字を B の先頭j文字へ変えるのに必要な最小の編集回数とします。求めたいのはD(m, n)であり、ほかのマスはすべて同じ問いの小さい版です。 - 端は考えるまでもありません。何もない状態から B の先頭
j文字を作るにはj回すべて挿入するしかないのでD(0, j) = j。A の先頭i文字を何もない状態まで削るにはi回すべて削除するしかないのでD(i, 0) = i。これが表の最上行と左端の列であり、そこが単に数を増やしていくだけの理由です。 - ここからが要となる一歩です。
D(i, j)の最適な手順を一つ取り、その最後の一手だけを見ます。可能性はちょうど三つしかありません。aᵢを削除してD(i−1, j)を残したか、bⱼを挿入してD(i, j−1)を残したか、aᵢとbⱼを対応づけてD(i−1, j−1)を残したかです。いずれもすでに埋め終えたマスです。 - したがってそのマスは三つのうち最も安いものになります。
D(i, j) = min( D(i−1, j) + 1, D(i, j−1) + 1, D(i−1, j−1) + [aᵢ ≠ bⱼ] )。左から右へ、上から下へ埋めていけば、どのマスに来たときにも三つの隣は既知です。これがアルゴリズムのすべてで、m × nマス、1 マスにつき 3 回の比較で終わります。
表示の読み方
このページの表がまさにその表です。行が A、列が B で、左上に一つ余分にある行と列が手順 2 の空の接頭辞です。だからそこは 0, 1, 2, 3 と数えるだけになっています。マスの濃淡は値そのもので、淡い対角の帯は 2 つの文字列がまだ安く一致している場所です。どのマスでもカーソルを合わせるかタップすれば、下のパネルがそのマスについて手順 3 を書き下します — 三つの候補それぞれの計算と、勝った候補の強調表示です。色のついた線は右下から逆にたどった最適経路の一つで、その下のアラインメント帯は同じ経路を文字で書き出したものです。
- 前提
- 編集はどれもちょうど 1 のコストで、文字は完全一致で比較されます。大文字小文字の吸収も、Unicode の正規化も、どの文字が似ているかという概念もありません。その結果がこのページで二つ見えます。ここで数えているのは UTF-16 の符号単位であって、あなたが文字と呼ぶものではありません。片方の欄に絵文字を 1 つだけ入力すると表は 3 × 1 になります。絵文字 1 つが 2 単位だからで、削除には 2 かかります。また、合成済みの
éを使ったcaféと、eに結合アクセントを付けたcaféは、画面上は見分けがつかないのに距離 2 と出ます。 - 成り立たない場合
- 表は
m × nマスなので、手間は 2 つの長さの積で増えます。単語 2 つなら問題ありませんが、100 万語の辞書に対する 1 件の問い合わせでは絶望的です。表が 100 万枚必要になります。ここで自然に望まれるのはもっと賢いアルゴリズムですが、驚くべきことに事実上存在しません。Backurs と Indyk は 2015 年に、真に劣二次時間の編集距離が求まるなら強指数時間仮説が覆ることを示しました。実際のスペルチェッカーはこの下限を破るのではなく、避けています。距離が小さな上限を超えた時点で打ち切るか、ほとんどの候補がそもそも比較されないように索引を張るのです。
全プロセスの詳細解説
-
kittenをsittingに変換する最小コストの編集手順 5 ステップ
kitten を sitting に変換せよ。最もコストの低い編集系列を求め、それより低コストなものが存在しないことを証明せよ。さらに、2 つ目の単語が辞書全体である場合にこの計算コストがどうなるかを算出せよ。
-
漸化式こそがアルゴリズムのすべてである。各セルは、削除、挿入、または現在の 2 文字を整列させること（両者が一致していれば最後の操作は無料）によってここに到達するコストを求める。あるセルに必要なのは、上および左に隣接する 3 つのセルだけであり、左から右へ 1 回スキャンすれば表全体が埋まる。
-
表を埋める前に、解の範囲を挟み込む。文字列の長さの差は 1 であるため、少なくとも 1 回の挿入は避けられない。また、単語全体を完全に書き換えるコストは 7 である。解はその間に存在し、この時点ですでに大半の推測が排除される。
-
3 回の編集で達成できる。k → s の置換、e → i の置換、g の挿入である。それぞれが 1 回の正当な編集であり、この手順の連鎖によって目的の文字列に到達する。
-
3 回の編集を示しただけでは、距離が高々 3 であることしか証明できない。表は距離が正確に 3 であることを証明する。なぜなら、右下の角に至るすべての経路がスコア化され、その途中のすべてのセルで最小値が取られるからである。これこそが、単に解を見つけることと、それが決して上回られない（最善である）と知ることの違いである。
-
コストは文字のペアごとに 1 セルであり、ここでは 42 セルに過ぎず、取るに足らない。しかし、1 単語あたり 7 文字からなる 100 000 単語の辞書に対しては、わずか 1 回の検索で 400 万回を超えるセルの更新が必要となる。
解答
ツールは 3 と、類似度 57.14%（これは 1 − 3/7、すなわち長い方の単語で正規化した距離）を出力する。どちらも手計算で 1 分もあれば埋められる表から得られる。スケーラビリティを欠いているのは表そのものである。計算量は Θ(mn) であるため、両方の文字列の長さを 2 倍にすると計算量は 4 倍になり、これまで使ったすべてのスペルチェッカーはこれを回避する設計になっている。抜け道は、より高速な表を作ることではない。レーベンシュタイン距離が三角不等式を満たすこと、すなわち d(a, c) ≤ d(a, b) + d(b, c) を利用して、インデックスが候補との実際の距離を測定することなく、それが離れすぎていることを証明できる点にある。
-
参考文献 (4)
- The theory section ends on why nobody has a much faster algorithm. This is the result that says they probably cannot have one: A. Backurs & P. Indyk, "Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False)." SIAM Journal on Computing 47(3), 1087–1097, 2018; first presented at STOC 2015.
- The grid this tool fills, and why filling each cell once is enough: R. A. Wagner & M. J. Fischer, "The String-to-String Correction Problem." Journal of the ACM 21(1), 168–173, 1974 — the dynamic-programming algorithm for the edit distance Levenshtein had defined in 1965.
- The fourth move in the Damerau cost model, and the survey of typing errors that argued for it: F. J. Damerau, "A technique for computer detection and correction of spelling errors." Communications of the ACM 7(3), 171–176, 1964.
- Insight block 3 ends on the problem of recovering the route without keeping the grid. This is the paper that solved it: D. S. Hirschberg, "A linear space algorithm for computing maximal common subsequences." Communications of the ACM 18(6), 341–343, 1975.