編集距離(レーベンシュタイン距離)
recieve と入力すると、スマートフォンは receive を提案します。2つの単語が数回の編集しか離れていないので、惜しかったとわかるのです。この近さ、つまり編集距離を測るのは、動的計画法の代表的な問題です。
問題
編集は単語を1文字だけ変えます。1文字を挿入する、1文字を削除する、または1文字を別の文字に置換する、のいずれかです。2つの単語の編集距離は、一方をもう一方に変えるのに必要な最小の編集回数です。cat と cut の距離は1、cat と cast は1、cat と act は2です。1965年にこれを研究したソ連の数学者ウラジーミル・レーベンシュタインにちなんで、レーベンシュタイン距離とも呼ばれます。
表
d[i][j] を、一方の単語の最初の i 文字と、もう一方の単語の最初の j 文字の編集距離とします。単語を空にするには1文字ごとに1回の削除が必要なので d[i][0] = i、空から単語を作るには1文字ごとに1回の挿入が必要なので d[0][j] = j です。i 番目の文字と j 番目の文字が等しければ d[i][j] = d[i − 1][j − 1] です。そうでなければ、d[i][j] = 1 + d[i − 1][j − 1](置換)、d[i − 1][j](削除)、d[i][j − 1](挿入)の最小値です。
例
kitten と sitting の場合、表は7行8列です。右下のマスは3で、そこからさかのぼると次のようになります。k を s に置換し、i、t、t を残し、e を i に置換し、n を残し、g を挿入します。Kitten、sitten、sittin、sitting と3回の編集で変わり、これより短いリストがないことを表が証明しています。
編集をさかのぼって読む
右下のマスから始めて、その値がどの隣のマスから来たかを考えます。文字が一致し、マスが左上の隣と等しければ、その文字は残されています。斜めに進みます。左上の隣より1大きければ置換、上のマスより1大きければ削除、左のマスより1大きければ挿入です。複数の経路が同点になることもあり、どれも最短の編集リストになります。
歴史と応用
レーベンシュタインは1965年、誤り訂正符号の研究中にこの距離を導入しました。表を使う方法は何人もの研究者が発表しましたが、最も有名なのは1974年のロバート・ワグナーとマイケル・フィッシャーによるもので、そのためワグナー–フィッシャー法とよく呼ばれます。現在、編集距離はスペル候補の順位付け、データベース内のタイプミスを含む名前の照合、DNA やタンパク質の配列の比較、音声認識の評価などに使われています。
試してみよう
アプリを開いて「ステップ」を押してください。比べている2文字が見出しで光ります。文字が同じなら左上の青いマスをコピーし、違えば3つの青い隣のマスをすべて読んで、最小値に1を足します。最後にオレンジ色の経路が角から戻っていき、表の下に編集が表示されます。
よくある質問
編集距離は距離関数(メトリック)ですか?
はい。負になることはなく、0になるのは単語が等しいときだけで、どちら向きでも同じ値になり、3つ目の単語を経由しても短くなることはありません:d(a, c) ≤ d(a, b) + d(b, c)。そのため、近い候補を探すのに役立ちます。
ダメラウ・レーベンシュタイン距離とは何ですか?
編集を1種類追加した編集距離で、追加されるのは隣り合う2文字の入れ替えです。フレデリック・ダメラウは1964年、挿入・削除・置換・入れ替えを合わせるとスペルミスの80%以上をカバーできることを見いだしました。入れ替えを使うと、recieve と receive の距離は2ではなく1になります。
編集距離は O(m·n) より速く計算できますか?
大きくは速くできません。2015年、アルトゥルス・バックルスとピョートル・インディクは、ある ε > 0 について O(n^(2 − ε)) 時間で解く方法があれば、多くの研究者が正しいと考えている強指数時間仮説が崩れることを示しました。ただし、近い単語どうしなら、表の対角線のまわりの細い帯だけを計算すれば済みます。
DNA の比較で編集距離はどう使われますか?
生物学者は同じ表を、回数の代わりにスコアで使います。一致には点が入り、置換やギャップには文字に応じた点が引かれます。配列全体にはニードルマン–ウンシュ法(1970年)、最もよく一致する部分にはスミス–ウォーターマン法(1981年)が使われます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
編集距離を試す