普段何気なく使っている diff。でもそのアルゴリズムは単純ではない。



<p>diff with C++

http://labs.unoh.net/2008/11/diff_with_c.html</p>

<p>要素の追加と削除の回数、つまりは編集の回数を Levenshtein Distance（レーベンシュタイン距離、編集距離）と呼ぶ。概念は、1965年にロシアの学者 Vladimir Levenshtein（ウラジミール・レーベンシュタイン）によって提唱された。</p>

<p>古くはスペルチェッカーで、今はDNA配列の類似性を計算するために使われているそうだ。

http://ja.wikipedia.org/wiki/レーベンシュタイン距離</p>