diff とバイオインフォマティクス
普段何気なく使っている 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>