背景・目的
DPの一種である編集距離問題について勉強した．学習目標は頭の中で大雑把なcodeを記述でき，理論が紙と鉛筆を用いて簡単な概要説明ができるレベルとします．
参考文献
使用するテキストです.このテキストのDPの編集距離に関する内容を学びAtCoderの似たような問題を解くことを目標にした.
問題
AtCoder
例として用いた文字列
S = tokyo
T=kyoto
解釈
DPテーブルを設計し，その際に条件を最小の単位レベルで小さくしたレベルから，参照したり組み合わせたりしてスコアの合計を求めました.
dpテーブルを設計した後は，if分岐で検索対処の文字列とjの比較対象の文字列を照らし合わせながら参照したというものです.
内容
まず出力結果のdpテーブルは以下のようになりました．
| k | y | o | t | o | ||
|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | |
| t | 1 | 1 | 2 | 3 | 3 | 4 |
| o | 2 | 2 | 2 | 2 | 3 | 3 |
| k | 3 | 2 | 3 | 3 | 3 | 4 |
| y | 4 | 3 | 2 | 3 | 4 | 4 |
| o | 5 | 4 | 3 | 2 | 3 | 4 |
下記がそのコードです.
def edit_distance(s, t):
m = len(s)
n = len(t)
dp = [[float("inf")] * (n + 1) for _ in range(m + 1)]
dp[0][0] = 0
for i in range(m + 1):
for j in range(n + 1):
if s[i - 1] == t[j - 1]:
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1])
else:
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1)
if i > 0:
dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)
if j > 0:
dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1)
return dp[m][n]
主に３つの操作からなります．置換，挿入，削除です.
置換
if s[i - 1] == t[j - 1]:
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1])
else:
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1)
探索対象の一字の文字が一致した場合は前列からひとつの操作をする必要が無く値を求めることが出来るという考えからこのようなコードになっています. 例えば,
i=1,j=2
s==t==k
となるので,dpテーブルの対応するmath dp{i=0}{j=1}の値をそのまま持ってくることとなります．これは一致する文字列は前の行を参照していることを示していて，その後のelse文は一致しなければ前行から一つ変えるだけで，一つ増えた今の検索対象の結果になると示しているだけです．
排除
if i > 0:
dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)
これは現在の検索対象（置換操作によって$dp_{i-1,j}$の値が変化している場合も含む）の$dp_{i-1,j}$に対してdpテーブルの左側の値を参照したことを示します.つまり，増えた分の文字に対して, 一回分の削除するという操作をしたことを示しています．
挿入
if j > 0:
dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1)
これも削除と同様の考え方で上側の値に対して一回挿入という操作を行うということを示しています．
今後の展開
編集距離を先週から勉強していたが全く分からなかった．GMINIを使って分から無い文言やSETPを聞きながら勉強するとかなり効率的だと分かった．とりあえず，五章の章末問題を15分考えて分からなかったら解答見て15分それでも分からなかったらGminiを参考して勉強を進めるものとする.