編集距離で理解する動的計画法(DP)

水曜日, 12月 16, 2020

自然言語処理

t f B! P L

おひさしぶりんこ。

今日は動的計画法(DP)で編集距離(Edit distance)を計算します。

計算結果の記録と漸化式による次の値の計算がDPの要点だと思うので、編集距離の計算を例にこれを見ていきます。

編集距離とは

2つの文字列が与えられたとき、一方の文字列に挿入(Insert)、削除(Delete)、置換(Replace)のいずれかの操作を繰り返し適用すると、もう一方の文字列に一致させることができます。
これら3つの操作を「編集」と呼びます。

一方の文字列を編集し、もう一方の文字列に一致させるのに要する最小の編集回数のことを編集距離といいます。
何の意味もないですが、やろうと思えばいくらでも無駄な操作が可能なので、最小回数が編集距離になります。

編集距離が小さければその文字列はお互いに似ている、ということは直感的にもわかりやすいと思います。

DPによる編集距離の計算

S1=m|S_1| = m
S2=n|S_2| = n
とします。

(m+1)×(n+1)(m+1) \times (n+1)の配列DDを用意し、この上でDPの計算を行います。
結論からいうと、
D[i][j]D[i][j]には、

  • S1S_1の先頭からii文字目までS1iS_1^i
  • S2S_2の先頭からjj文字目までS2jS_2^j

編集距離が格納されていきます。

なので、求めたい編集距離は、計算終了後にD[m][n]D[m][n]に格納されているはずです。

アルゴリズム

以下の2つの事実により、機械的に計算していくだけで、D[m][n]D[m][n]が求まります。

文字列S1S_1を編集し、文字列S2S_2へ帰着させる状況を考えます。

0行目および0列目の値は簡単に埋められる

1つ目は、配列DDの0行目および0列目の値は簡単に埋められるという点です。

0行目とは、D[0][j]D[0][j]ですから、S10S_1^0(空文字列)とS2jS_2^jの編集距離です。

これは、D[0][j]=jD[0][j]=jになることがすぐにわかります。なぜなら、S2jS_2^jに一致するよう、空文字列S10S_1^0jj回だけ文字を挿入させればよいからです。

同様の議論で、0列目もD[i][0]=iD[i][0]=iとなることがわかります。

これで配列DDの一番上の行(0行目)と一番左の列(0列目)が埋まりました。

セルの値は上・左・左上に隣接する3セルの値から計算できる

もう1つ目は、あるセルの値は上・左・左上に隣接する3セルの値から計算できる、という点です。

これはつまり、D[i][j]D[i][j]の値は、左のD[i1][j]D[i-1][j]、上のD[i][j1]D[i][j-1]、左上のD[i1][j1]D[i-1][j-1]から計算できるということになります。

左のD[i1][j]D[i-1][j]と、D[i][j]D[i][j]を比べると、後者のほうがS1S_1側文字列が1文字長い状態です。

つまり、S1i1S_1^{i-1}ii文字目をInsert(挿入)すれば、S1iS_1^{i}になり、D[i][j]D[i][j]と同じ状態になります。挿入操作が1回必要なので、

=> D[i][j]=D[i1][j]+1D[i][j]=D[i-1][j]+1

同様の議論で、

=> D[i][j]=D[i][j1]+1D[i][j] = D[i][j-1]+1

になります。

最後に、左上のD[i1][j1]D[i-1][j-1]のケースです。
これは、D[i][j]D[i][j]とどのように関係があるのでしょうか。
これに関しては、S1S_1ii文字目と、S2S_2jj文字目が一致するかどうかで場合分けします。

一致している場合、S1S_1ii文字目と、S2S_2jj文字目は一切編集不要なので、S1i1S_1^{i-1}と、S2j1S_2^{j-1}の編集距離のみ考えればよく、これはD[i1][j1]D[i-1][j-1]そのものです。

=> D[i][j]=D[i1][j1]D[i][j] = D[i-1][j-1]

一致しない場合、S1S_1ii文字目を、S2S_2jj文字目にReplace(置換)すると、上記「一致する場合」と同じ状態になります。置換操作が1回必要なので、

=> D[i][j]=D[i1][j1]+1D[i][j] = D[i-1][j-1]+1

となります。
このように、D[i1][j1]D[i-1][j-1]との関係は場合分けして計算します。

以上をもってD[i][j]D[i][j]の候補は、

  • D[i1][j]+1D[i-1][j]+1
  • D[i][j1]+1D[i][j-1]+1
  • D[i1][j1]D[i-1][j-1] if S1[i]==S2[j]S_1[i]==S_2[j] else D[i1][j1]+1D[i-1][j-1]+1

の3択に絞られました。
正解はこの中の最小値を取ります。編集距離は最小回数なので、最小値を取らないと無駄な操作をした回数を含んでしまいます。

一見して、1足しているだけのものが多いですが、D[i1][j]D[i-1][j]D[i][j1]D[i][j-1]D[i1][j1]D[i-1][j-1]はそれぞれ別の値なので、やはりこの中から最小値を選ぶ必要があります。

このように、漸化式などを用いて以前の計算結果を再利用するので、DPの基本になります。

0行目および0列目はすでに埋まっているため、あとはこの漸化式を適用していくだけで、表のマス目をすべて埋めることができます。

https://gitlab.com/-/snippets/2065496

QooQ