ウノウラボ Unoh Labs: diff with C++

ミートソーススパゲティを作るときは、ミートソースから作るのが信条のbokkoです。それはさておき、今日はdiffのお話です。 diff diffは指定した2つのファイルの差分を求めるコマンド、もしくはその差分そのものを指します。普段から何気なく使用しているコマンドですが、その中で使われているアルゴリズムは結構難しいです。 差分を計算するということ 差分を計算するというのは以下の3つを求めることに帰結します。 ・Levenshtein Distance(Edit Distance) ・LCS(Longest Common Subsequence) ・SES(Shortest Edit Script) 上から順に1つずつ説明していきます。 Levenshtein Distance Levenshtein Distanceは2つのシーケンスの違いを数値化したもので編集距離とも言います。これは後述

[itotto]

分かりやすい

[Ctrans]

ウノウラボ Unoh Labs: diff with C++

[tyru]

diffのアルゴリズムの説明やライブラリ。ヘッダをインクルードするだけで使える。

[masterq]

差分抽出のアルゴリズムについて。 pythonにはdifflibがあるけど、rubyにはそんなんないのかな？

[decoy2004]

差分を計算するというのは以下の3つを求めることに帰結します。

[takeshiketa]

差分アルゴリズム

[amachang]

ミートソーススパゲティを作るときは、ミートソースから作る／diff は C++ で作る／追加回数+削除回数=編集距離／シーケンス間の最短経路／LCSで分割して左右のシーケンスをまたLCSで分割／ hpp だけで使いやすい。

[hassylin]

diff

[hiromark]

考え方のプロセスがいろいろ応用できそうだ。

[neumann]

diff

[wacky]

diffコマンドで使われている差分アルゴリズムと自作diffライブラリ「dtl」の紹介。

[ajapo]

Diffのアルゴリズム概観とC++での実装