動的計画法でレーベンシュタイン距離を求めるメモ

分かると分かりやすい記事が多い

自分は馬鹿なのでもっとかみ砕いて残しておく

レーベンシュタイン距離とは

2つの文字列がどの程度近いかを表す指標
->ある文字列を、あるもう1つの文字列に変換するのに必要な操作の最小回数
ただし操作は以下の3つに限る

• 文字の削除
• 文字の追加
• 文字の置換
  例
  doramu : tomato
  toramu : tomato
  tomamu : tomato
  tomatu : tomato
  tomato : tomato
  で、レーベンシュタイン距離は4

動的計画法(Dynamic Programming)で解く

dpテーブルの設計

2つの文字列をs,tとし、dp[sの長さ + 1][tの長さ + 1]を作成
セルdp[i][j]が表すものは、
sの前からi文字をtの前からj文字に変換するのに必要な操作の最小回数

例
s = "sitting", t = "kitten"の場合
dp[2][4]が表すものは、"si"を"kitt"に変換するのに必要な操作の最小回数
この例でdpテーブルを作ると、以下で、3回と分かる。

		k	i	t	t	e	n
	0	1	2	3	4	5	6
s	1	1	2	3	4	5	6
i	2	2	1	2	3	4	5
t	3	3	2	1	2	3	4
t	4	4	3	2	1	2	3
i	5	5	4	3	2	2	3
n	6	6	5	4	3	3	2
g	7	7	6	5	4	4	3

dpテーブルでのセルの移動

変換の種類と同じく、全部で3種類ある

1. dp[i-1][j]からdp[i][j]への移動
2. dp[i][j-1]からdp[i][j]への移動
3. dp[i-1][j-1]からdp[i][j]への移動
   それぞれが何を表すか。

具体的にdpテーブルを更新しつつ考える。
まず、1行目と1列目は文字列がない状態から文字の追加、文字列がある状態から文字の削除という単純操作の回数を数えて、以下。

		k	i	t	t	e	n
	0	1	2	3	4	5	6
s	1
i	2
t	3
t	4
i	5
n	6
g	7

dp[1][1]はどのようにして決まるのだろうか
dp[1][1]は "s"を"k"に変換するのに必要な操作の最小回数
なので、直感的にすぐ"文字の置換を1回行う"ことが最小操作回数だと分かる。
でも今やっているのは動的計画法というアルゴリズムなので、一定の手順で考える必要がある。

① dp[0][1]からdp[1][1]への移動をする場合

""を"k"に変換するのに必要な操作の最小回数
から
"s"を"k"に変換するのに必要な操作の最小回数
を導くという事。
このとき、sをkに変換するのに、一旦sを削除すれば空文字からkへの変換に問題が置き換わる。
よって　
""を"k"に変換するのに必要な操作の最小回数 + 1(sの削除)回
が
"s"を"k"に変換するのに必要な操作の回数
となる。

② dp[1][0]からdp[1][1]への移動をする場合

"s"を""に変換するのに必要な操作の最小回数
から
"s"を"k"に変換するのに必要な操作の最小回数
を導くという事。
このとき、sをkに変換するのに、一旦sにkを追加すればskからkへの変換に問題が置き換わり、skからkへの変換はsから空文字への変換に問題が置き換わる。
よって　
"s"を""に変換するのに必要な操作の最小回数 + 1(kの追加)回
が
"s"を"k"に変換するのに必要な操作の回数
となる。

③ dp[0][0]からdp[1][1]への移動をする場合

""を""に変換するのに必要な操作の最小回数
から
"s"を"k"に変換するのに必要な操作の最小回数
を導くという事。
つまり、sをkに変換するのに必要な操作はsからkへの置換であり、kがsだった場合、置換は起こらない。
空文字から空文字への変換という問題に、1文字同士の比較変換という問題が上乗せされるという感覚。
よって　
""を""に変換するのに必要な操作の最小回数 + 1文字同士の比較、同じなら置換無しで0回、違うなら置換して1回
が
"s"を"k"に変換するのに必要な操作の回数
となる。

これらの移動の結果求められる回数が一番小さい移動を選ぶ。つまり、更新式は以下。

min({dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + (s[i-1] != t[j-1] ? 1 : 0)})

では移動を進めていく。dp[1][1]は0+1で1

		k	i	t	t	e	n
	0	1	2	3	4	5	6
s	1	1
i	2
t	3
t	4
i	5
n	6
g	7

dp[1][2]は1+1で2、経路は2つある。以降全て同じ。

		k	i	t	t	e	n
	0	1	2	3	4	5	6
s	1	1	2	3	4	5	6
i	2
t	3
t	4
i	5
n	6
g	7

dp[2][1]は1+1で2、経路は2つある。

		k	i	t	t	e	n
	0	1	2	3	4	5	6
s	1	1	2	3	4	5	6
i	2	2
t	3
t	4
i	5
n	6
g	7

dp[2][2]はs[2]とt[2]はどちらもiなので1+0で1

		k	i	t	t	e	n
	0	1	2	3	4	5	6
s	1	1	2	3	4	5	6
i	2	2	1
t	3
t	4
i	5
n	6
g	7

以降左からの経路で更新

		k	i	t	t	e	n
	0	1	2	3	4	5	6
s	1	1	2	3	4	5	6
i	2	2	1	2	3	4	5
t	3
t	4
i	5
n	6
g	7

s[3],t[3]は同じなのでdp[3][3]は左上から+0で更新。s[3],t[4]も同じだが左からの方が小さいのでdp[3][4]は左から更新

		k	i	t	t	e	n
	0	1	2	3	4	5	6
s	1	1	2	3	4	5	6
i	2	2	1	2	3	4	5
t	3	3	2	1	2	3	4
t	4
i	5
n	6
g	7

で、以下略。

		k	i	t	t	e	n
	0	1	2	3	4	5	6
s	1	1	2	3	4	5	6
i	2	2	1	2	3	4	5
t	3	3	2	1	2	3	4
t	4	4	3	2	1	2	3
i	5	5	4	3	2	2	3
n	6	6	5	4	3	3	2
g	7	7	6	5	4	4	3

最終的にはdpテーブルの右下の3がsittingとkittenのレーベンシュタイン距離になる。更新経路を追えばどのような操作でsittingがkittenになるかが分かる。

		k	i	t	t	e	n
	0	1	2	3	4	5	6
s	1	1	2	3	4	5	6
i	2	2	1	2	3	4	5
t	3	3	2	1	2	3	4
t	4	4	3	2	1	2	3
i	5	5	4	3	2	2	3
n	6	6	5	4	3	3	2
g	7	7	6	5	4	4	3

sitting->(gの削除)->sittin->(eの置換)->sitten->(sの置換)->kitten