編集距離アルゴリズム

Kindleの「問題解決力を鍛える! アルゴリズムとデータ構造」の編集距離アルゴリズムの編集操作に関する記述がいまいち飲み込めなかったので解釈法を残しておく。

文字列S, Tの編集距離において、SをTに合わせるための以下の2操作が等価という記述があった。

1. Sの好きな箇所に任意の1文字を追加
2. Sの任意の1文字を削除

上記の2操作がなぜ等価なのかを、以下を例に考える

S=""
T="a"

SをTに合わせるのだから、1の処理を行い一致させる。これにより編集距離が1になる。

S="a"
T=""

SとTを入れ替えるた場合、2の処理を行い一致させる。これにより編集距離が1になる。

つまり、1と2の操作は文字列S, Tを入れ替えると操作も逆になる関係であり実質的な違いは何もない。
そのため等価であるということ。