編集距離(レーベンシュタイン距離)の求め方

編集距離は、2つの単語がどれくらい似ているかを表す量。

編集距離とは

「すうがく」という単語を最低何回「編集」すれば「すがた」という単語になるでしょうか?

ただし「編集」とは、
一文字挿入一文字削除一文字置換
のいずれかの操作のこととしましょう。

例えば、
「すうがく」の「う」を削除
→「すがく」の「く」を「た」に置換
→「すがた」
となり、「すうがく」から「すがた」へは編集2回で行けることになります。(編集1回では行けません)

このように、必要な「編集」の最低回数のことを編集距離と言います。
つまり「すうがく」と「すがた」の編集距離は $2$ です。

レーベンシュタイン距離

「編集」で許す操作は、挿入または削除または置換としましたが、置換を許さないなど、他にもバリエーションがあります。

このように「編集」の定義はいろいろありますが、挿入または削除または置換という「編集」による編集距離を、特にレーベンシュタイン距離と言います。
参考:Levenshtein distance

レーベンシュタイン距離の求め方

レーベンシュタイン距離は、動的計画法という手法を用いて求めることができます。具体的なアルゴリズムを、「すうがく」と「すがた」の例で説明します。

1.まず、表を準備します。
編集距離の求め方1

・2つの単語を、それぞれ縦と横に並べます。
・一行目、一列目は空文字に対応します。
・各マスに、対応する2つの部分文字列のレーベンシュタイン距離を入れていくのが目標です。例えば、Aには「すうが」と「すが」のレーベンシュタイン距離が入り、Bには、「すうがく」と空文字のレーベンシュタイン距離が入ります。

2.一行目と一列目を埋めていきます。
編集距離の求め方2

・空文字と「$n$ 文字の文字列」のレーベンシュタイン距離は $n$ なので、一行目と一列目が埋まります。

3.残ったマスを、上から、左から順々に埋めていきます。
編集距離の求め方3

各マスには、以下の3つの中で一番小さい数字を入れます。
・自分のマスの上のマスの数字 $+1$
・自分のマスの左のマスの数字 $+1$
・自分のマスの左上のマスの数字 $+c$
(ただし自分の縦と横の文字が等しい場合は $c=0$、異なる場合は $c=1$)

例えば、$x$ のマスは、
・上が $3$
・左が $1$
・左上が $2$(「が」と「す」は異なるので $c=1$)
なので、$1+1=2$ が入ります。

4.全て埋めたら、一番右下のマスが求める編集距離です。
編集距離の求め方4

「すうがく」と「すがた」のレーベンシュタイン距離は2です。

アルゴリズムがなぜ正しいか

上記の手順3で、なぜレーベンシュタイン距離を順々に求められるのかを大雑把に説明します。少し難しいです。

$a_1\dots a_N$ という文字列を $b_1\dots b_M$ に最短の編集回数で編集するにはどうすればよいでしょうか?
以下の3つの方法が考えられます。(※)
方法1:$a_1\dots a_N$ という文字列を $b_1\dots b_{M-1}$ に編集してから $b_M$ を挿入
方法2:$a_1\dots a_{N-1}$ の部分を $b_1\dots b_M$ に編集してから末尾の $a_N$ を削除
方法3:$a_1\dots a_{N-1}$ の部分を $b_1\dots b_{M-1}$ に編集してから末尾の $a_N$ を $b_M$ に置換。($a_N=b_M$ なら置換は不要)
それぞれが、手順3の各値に対応しています。

※厳密には、上記の3つの方法のいずれかで、必ず最短が実現できることを説明する必要があります。これは、真の最短手順において、$b_M$ がどこに由来するかで場合分けすれば確認できます。
・$b_M$ が新たに登場した場合、方法1で実現できます。
・$a_1$ から $a_{N-1}$ のいずれかが $b_M$ になった場合、方法2で実現できます。
・$a_N$ が $b_M$ になった場合、方法3で実現できます。

次:反射律、対称律、推移律の意味と例
前:グラフを表すデータ構造(隣接行列と隣接リスト)

スポンサーリンク

スポンサーリンク

誤植がございましたら @mathwordsnet までご連絡をお願いいたします。
ページ上部へ戻る