差分検出アルゴリズム
差分検出のアルゴリズム
差分検出アルゴリズムの基本用語
差分検出アルゴリズムの話をした時によく出る用語
編集距離（edit distance）
文字列Aを1文字ずつ挿入・削除してBになる操作回数のこと
上記の操作に「置換」を加えたものはレーベンシュタイン距離とも言う
レーベンシュタイン距離 - Wikipedia
SES（Shortest Edit Script）
最短の編集距離
最長共通部分列、LCS（Longest Common Subsequence）
双方の文字列に含まれる共通の文字列の中で一番長いもの
この「共通の」には一定の条件がある
やっていいのは文字の削除のみ
削除する文字は双方の文字列で異なっていても問題ない
文字の並べ替えをしてはいけない
つまり、
infightから文字を消してnitにするのはあり
initやfitもおｋ
infightに含まれる文字を並べ替えてhitにするのはダメ
文字を削除して最長になるものなので、例えばacdedとeacddではacdd(4文字)が最長になる
参考
最長共通部分列問題 - Wikipedia
誤訳が多いらしいので原文の記事を見たほうが良いかもしれない
アルゴリズムの種類
色々あるっぽい
動的計画法
動的計画法 - Wikipedia
O(ND)アルゴリズム
O(NP)アルゴリズム
参考
差分検出アルゴリズム三種盛り - Object.create(null)