差分検出のアルゴリズム

差分検出アルゴリズムの話をした時によく出る用語

編集距離（edit distance）

文字列Aを1文字ずつ挿入・削除してBになる操作回数のこと

上記の操作に「置換」を加えたものはレーベンシュタイン距離とも言う

SES（Shortest Edit Script）

最短の編集距離

最長共通部分列、LCS（Longest Common Subsequence）

双方の文字列に含まれる共通の文字列の中で一番長いもの

この「共通の」には一定の条件がある

やっていいのは文字の削除のみ

削除する文字は双方の文字列で異なっていても問題ない

文字の並べ替えをしてはいけない

つまり、

infight から文字を消して nit にするのはあり

init や fit もおｋ

infight に含まれる文字を並べ替えて hit にするのはダメ

文字を削除して最長になるものなので、例えば acded と eacdd では acdd (4文字)が最長になる

参考

誤訳が多いらしいので原文の記事を見たほうが良いかもしれない

色々あるっぽい