Neil Fraser: Writing: Diff Strategies
by Neil Fraser, April 2006 Computing the differences between two sequences is at the core of many applications. Below is a simple example of the difference between two texts: Text 1: Apples are a fruit. Text 2: Bananas are also fruit. Diff: AppleBananas are also fruit. This paper surveys the literature on difference algorithms, compares them, and describes several techniques for improving the us
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） ある要素列を別の要
バージョン管理システムのdiffのパフォーマンス測定 - 考える人、コードを書く人
最近、C++でdiffを書いているせいか、バージョン管理システムで使われているdiffのパフォーマンスが気になったので、調べてみた。バージョン管理システムにおいてdiffはかなり重要である。というのも、diffもしくはそれに相当する処理は単に差分を表示する際だけでなく、updateやmerge時の差分適用など、至るところで行われるので、diffが遅いとバージョン管理システムにおけるありとあらゆる動作が遅くなってしまうからだ。 測定に使用したバージョン管理システム 測定に使用したバージョン管理システムは以下の通り。 Subversion-1.5.2 Monotone-0.41 Git-1.6.0.1 Mercurial-1.0.2 ちなみに上記のソフトを選択した理由は単に自分が普段から検証も含めて使用しているというだけです。 準備 まず、以下のような2種類のファイルの組合せを用意する。 Ty
Scala による diff の実装：Rainy Day Codings：So-net blog
「Scala で diff を書いてみた」[1] という記事に触発されて [2] の論文や [3] の解説を読んで diff のアルゴリズムを勉強して自分なりに Scala で実装してみました。 これは [2] で "An O((M+N)D) Greedy Algorithm" と呼ばれているほうの実装で、論文の後半では改良についても書いてあるけどそちらは読んでいません。 私なりに工夫をした部分は全体的に副作用を排除した所とエディットグラフの格子点をオブジェクトとして表現した点です。 元論文の擬似コードで "a number of simple optimizations are employed" とされている部分は可読性の観点から取り入れませんでした。ただ元論文が「D回の編集で到達する（対角線 k 毎の）最遠点の集合」を配列で管理しているのを Set で管理するようにしたのは本当はよろ
UnixコマンドのDiffやWdiffコマンドのロジックについて教えて下さい。…
UnixコマンドのDiffやWdiffコマンドのロジックについて教えて下さい。同様の機能をVBAに関数ないしはSubとして取り込みたいのです。関連情報でも結構ですので教えて下さい。
文書比較（diff）アルゴリズム
文書比較（diff）アルゴリズム 前のドキュメント 次のドキュメント ＶｉＶｉの文書比較（diff）機能で使用しているアルゴリズムについて解説する。 これらのアルゴリズムは Myers 氏らの論文によるもので、氏は筆者のためにわざわざ論文をＷｅｂサイトで入手可能な形式にしてくださった。この場を借りてお礼申し上げる。 オリジナル論文は以下のＷｅｂサイトから入手可能である。 http://www.cs.arizona.edu/people/gene [1] E.W.Myers, "An O(ND) Difference Algorithm and Its Variations", Algorithmica, 1 (1986), pp.251-266 [2] S. Wu, U. Manber, G. Myers and W. Miller, "An O(NP) Sequence Comparis
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
