[B! algorithm][diff] youpyのブックマーク

youpy id:youpy

algorithmとdiffに関するyoupyのブックマーク (2)

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）ある要素列を別の要
youpy 2011/03/13
diff

algorithm
リンク
Diff algorithm - 枕を欹てて聴く
id:smoking186 さんの指摘を受け, First Authorの名前などを付加しました. どうもです. 記事内のcodeは最適化などを施しておらず, 冗長に, 定義どおりに書いています. ifがまとめられたりとかしますが, そのあたりはご容赦を... Rubyでlevenshtein距離を見て以来, 個人的にdiffブームが来ていた. 計算量O(ND) / O(NP)のalgorithmなどがあるのは知っていたが, 論文(英語)および, 解説のみ, またはソースコードのみなど分かれているものが多く, algorithmに疎い自分には理解するのに大変時間がかかってしまった. しかしやっとわかったので, 解説+JS実装してみる. 解説とソースコードがセットだと, 多少はわかりやすくなるかと... 自分は正直これくらい細かく言われないとすぐにはわかんない人なので(the O(ND)だけ
youpy 2009/10/21
javascript

diff

algorithm
リンク
1