diffの動作原理を知る～どのようにして差分を導き出すのか | gihyo.jp

UNIXの基本的なコマンドの1つであるdiff。 これに実装されているアルゴリズムは実に興味深い世界が広がっています。 本稿では、筆者が開発した独自ライブラリ「dtl」をもとに「diffのしくみ」を解説します。 はじめに diffは2つのファイルやディレクトリの差分を取るのに使用するプログラムです。 ソフトウェア開発を行っている方であれば、SubversionやGitなどのバージョン管理システムを通して利用していることが多いかと思います。本稿ではそのdiffの動作原理について解説します。 差分の計算の際に重要な3つの要素 差分を計算するというのは次の3つを計算することに帰結します。 編集距離 2つの要素列の違いを数値化したもの LCS（Longest Common Subsequence） 2つの要素列の最長共通部分列 SES（Shortest Edit Script） ある要素列を別の要

[syque]

diff の動作原理。編集距離、LCS、SES という計算子

[caquu]

なるほどねー・・・。一行たりともわかんね。

[issyurn]

"2011-03-11"

[yasuharu519]

diff

[ymori76]

こういうのこういうの。こういう美味しそうなやつもっとください。

[kana321]

diffの動作原理を知る～どのようにして差分を導き出すのか

[dagjmpd]

diffの動作原理を知る～どのようにして差分を導き出すのか #gihyojp

[t-wada]

diff のアルゴリズムは非常に面白いな

[vcc]

MyersのアルゴリズムはWuのアルゴリズムと同じく，差分の計算問題をエディットグラフ上の最短経路問題に還元するもの。GNU diffutilsやGitのdiffエンジンのXLibdiffはこのアルゴリズムを基にしている

[ryochack]

diffの解説

[riywo]

やべぇ、、、diffってこんなに複雑なのか。。。

[geeksnil]

atoe

[kamei_rio]

__〆のヮの

[sakef]

diffの動作原理

[ks1234_1234]

へー。diffは使ってるけど，ただのユーザーだから，「原理」は考えたことなかったな。正規表現も使ってるけど，どう処理されてるかは知らないや。

[deep_one]

やっぱりかなり複雑だわ…。比較プログラムがたまに的外れなことをいってくるのも理解した。

[sucrose]

編集距離，LCS，SES

[katzchang]

あとでみよう

[makoto086]

RT: プログラミング：diffの動作原理を知る～どのようにして差分を導き出すのか｜gihyo.jp … 技術評論社 -

[horimislime]

gihyo.jp:

[richard_raw]

多治見寿和「プログラミング・テクニック」を1ページたりとも読破できない吾には早すぎた（爆）

[adilla]

diff

[K-Ono]

興味深いがさすがにあとで。

[iwskhtn]

また読む

[qnighy]

ハミング距離を求めるためのDPだっけ

[tetram]

diffの原理

[nbsn]

「この記事を読むのに必要な時間：およそ 7 分」みんな超あたまいいなぁ。１時間かかったよん。

[mainyaa]

あとでがんばって読む

[syanbi]

diffの動作原理について。

[polyamid]

後で読む

[efcl]

Diffアルゴリズムの解説

[nitoyon]

diff 原理。