民芸的プログラミング 〜ソフトウェア開発日記〜

アクセスカウンタ

zoom RSS diff は難しい

<<   作成日時 : 2009/12/21 23:00   >>

ブログ気持玉 0 / トラックバック 0 / コメント 0

日ごろ、何の気無しに使っている、diff というコマンド。
2つのファイルの差分を調べるのに便利だ。
先日、WinMerge という diff の GUI 版を使ったこともあり、興味が湧いてきた。
いったい、どういうアルゴリズムで動いているのか。

GNU diff のソースをダウンロードしてきて見てみたのだが、何をやっているのかさっぱり分からない。
「これって、もしかしたら、ものすごく難しいことをやっているのでは?」
そんな気がしてきて、ずばり「diff アルゴリズム」で Google 先生にお伺いを立てたところ、案の定だった。
http://hp.vector.co.jp/authors/VA007799/viviProg/doc5.htm
めちゃくちゃに難しい。

例えば、「a b c d f g h j q z」と「a b c d e f g i j k r x y z」という文字列比較だけをとってみても、一つ目の文字列のどの文字を足して、どの文字を削って、どの文字を置き換えれば、最短で2つ目の文字列になるのか、ちょっとやそっとではわからない。
人間の目で直感的に作業しても、それが本当に最短の作業量だったのかどうか、自信がなかったりする。
ちなみに上の文字列の例は、Wikipedia の「diff」の項目から引用したものである。
http://en.wikipedia.org/wiki/Diff

なぜか、Wikipedia 日本語版には、英語版にはあるアルゴリズム説明の部分がまったく無い。
もっとも、このレベルの話になると、日本語になっていたからといって理解できるものではないのだが。

それでも、日本語になっている資料を集めてみると、こんな感じ。
http://amoi.mib.jp/typo/articles/2007/12/11/diffalgorithm
http://www.slash-zero.jp/archives/program/468
http://www.slash-zero.jp/archives/program/476
http://www.atmarkit.co.jp/fcoding/articles/algorithm/10/algorithm10b.html
http://handasse.blogspot.com/2009/04/c_29.html

きっちりと時間をとって、自分の頭でしっかりと理解しないと、ものにはならなさそうだ。

こういう時、サンデープログラマーの限界をふと感じてしまったりする。
一日中、プログラムのことばかり考えているわけにもいかないから。

テーマ

関連テーマ 一覧


月別リンク

ブログ気持玉

クリックして気持ちを伝えよう!
ログインしてクリックすれば、自分のブログへのリンクが付きます。
→ログインへ

トラックバック(0件)

タイトル (本文) ブログ名/日時

トラックバック用URL help


自分のブログにトラックバック記事作成(会員用) help

タイトル
本 文

コメント(0件)

内 容 ニックネーム/日時

コメントする help

ニックネーム
本 文
diff は難しい 民芸的プログラミング 〜ソフトウェア開発日記〜/BIGLOBEウェブリブログ
文字サイズ:       閉じる