編集距離
説明
文字列 $S$ と文字列 $T$ との編集距離の遷移の考え方は図の通り。
$ s_i = t_j $ のとき $ ed(S_i, T_j) = ed(S_{i-1}, T_{j-1})$
$ s_i \not= t_j $ のとき $ ed(S_i, T_j) = min(ed(S_{i-1}, T_{j-1}, ed(S_{i-1}, T_j), ed(S_i, T_{j-1})) + 1 $
主に自分用の備忘録
主に自分用の備忘録
文字列 $S$ と文字列 $T$ との編集距離の遷移の考え方は図の通り。
$ s_i = t_j $ のとき $ ed(S_i, T_j) = ed(S_{i-1}, T_{j-1})$
$ s_i \not= t_j $ のとき $ ed(S_i, T_j) = min(ed(S_{i-1}, T_{j-1}, ed(S_{i-1}, T_j), ed(S_i, T_{j-1})) + 1 $