この記事は、2015年のGo Advent Calendarの25日目の記事です。 Go Advent Calendarのその2とその3ができる前、最終日だけ空いてて滑り込みで登録したのはいいけど、なんかネタないかなーと思いつつ、自分のgithubリポジトリを漁っていたらdiffのアルゴリズムをGoで実装したやつが出てきたので紹介してみます。 gonpはGoによるdiffのアルゴリズム実装です。元々は昔々C++で書いたdtlというdiffライブラリの簡易移植で、diffを取るのに必要な以下の要素を求めることができます。 編集距離(Edit Distance) LCS(Longest Common Subsequence) SES(Shortest Edit Script) diffのアルゴリズムにはさまざまな種類があり、中でもdiffに限らず様々な用途に応用可能な動的計画法が有名です。ただ
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-match-patch便利ですよね? これで行単位のdiffを出そうと思ったんですが、APIのリストとにらめっこしてもわからなかったのですが、検索したら大本のGoogle謹製の方のWikiにあったので、実装のメモです。 import "github.com/sergi/go-diff/diffmatchpatch" func lineDiff(src1, src2 string) []diffmatchpatch.Diff { dmp := diffmatchpatch.New() a, b, c := dmp.DiffLinesToChars(src1, src2) diffs := dmp.DiffMain(a, b, false) result := dmp.DiffCharsToLines(diffs, c) fmt.Println(result) return resu
I think the diff algo used for pack files was linked to one of the delta encoding out there: initially (2005) xdelta, and then libXDiff. But then, as detailed below, it shifted to a custom implementation. Anyway, as mentioned here: Git does deltification only in packfiles. But when you push via SSH git would generate a pack file with commits the other side doesn't have, and those packs are thin pa
posix shell で標準入力同士の diff (1) を実現する方法 コマンド command1 の出力結果と コマンド command2 の出力結果を diff (1) で比較したい場合、 一番手軽なのはそれぞれの出力を一時ファイルに出力して比較する方法である。 $ command1 > ${TMP:-/tmp}/output1 $ command2 > ${TMP:-/tmp}/output2 $ diff ${TMP:-/tmp}/output1 ${TMP:-/tmp}/output2 : $ rm ${TMP:-/tmp}/output1 ${TMP:-/tmp}/output2 しかし、この方法では一時ファイルを作成するので 処理効率が悪く一時ファイルの削除など後処理をする必要がある。 例えば bash (1) の場合は以下の様にする事で簡単に比較できる。 $ diff
Posted by timothy on Thursday December 08, 2011 @02:44PM from the now-with-raisins dept. itwbennett writes "At the Usenix Large Installation System Administration (LISA) conference being held this week in Boston, two Dartmouth computer scientists presented variants of the grep and diff Unix command line utilities that can handle more complex types of data. The new programs, called Context-Free Gre
差分を作る 作業ディレクトリで、以下を実行する。 $ svn diff -r 10:HEAD > foo.diff patchをあてる $ patch -p0 -E < foo.diff -E オプションを指定すると、パッチ適用後に空のファイルを削除する。 また、patchが当たるファイルを確認したい場合は、--dry-runオプションをつける。 patch -p0 --dry-run < foo.diff このとき、ファイルにpatchは適用されない。 あてたpatchを取り消す -Rオプションで、一応可能。 $ patch -p0 -R < foo.diff 元々-Rオプションは、差分の取り方が逆であったときに利用するオプション。 結果的に取り消すことができるが、そのような目的のオプションではないので、過信しないこと。
hg(mercurial)のmergeで衝突を見やすくした。Vimdiffを使うことにした。 かなり便利なった。 hgのマージ処理がやりにくい。 mercurialのmergeはそれなりに賢い。でも手作業マージが無くなるわけでもない。 $>hg merge を叩くと、衝突時にviが起動する。しかしコレが読みづらい。Mercurialが自動でファイルを混ぜてしまう。 コンフリクト箇所が一カ所なら対応できる。複数箇所のコンフリクトがあるとき マージ忘れが頻発する。 しかも、Mercurialが自動的に「<<<<<」マークする。ファイルにゴミが増える。 リリースファイルにゴミが発生しエラー発生する。 windowsならwin-merge WindowsでHGを使っている人はWinMergeを使っていた。楽ちんそうだった。 vimdiffが使いたい。 LinuxコンソールはVimdiffというvi
ふと、ビット並列アルゴリズムを使った編集距離を計算するアルゴリズムを書きたくなったので書いてみた。 まず、通常の編集距離であるLevenshtein Distanceを求めるアルゴリズムは以下のように書ける int levenshteinDistance(String A, String B) { int m = A.length(); int n = B.length(); int dp[] = new int[n + 1]; int next[] = new int[n + 1]; for (int i = 0; i <= n; i++) dp[i] = i; for (int i = 1; i <= m; i++) { next[0] = i; for (int j = 1; j <= n; j++) { if (A.charAt(i - 1) == B.charAt(j - 1))
id:smoking186 さんの指摘を受け, First Authorの名前などを付加しました. どうもです. 記事内のcodeは最適化などを施しておらず, 冗長に, 定義どおりに書いています. ifがまとめられたりとかしますが, そのあたりはご容赦を... Rubyでlevenshtein距離を見て以来, 個人的にdiffブームが来ていた. 計算量O(ND) / O(NP)のalgorithmなどがあるのは知っていたが, 論文(英語)および, 解説のみ, またはソースコードのみなど分かれているものが多く, algorithmに疎い自分には理解するのに大変時間がかかってしまった. しかしやっとわかったので, 解説+JS実装してみる. 解説とソースコードがセットだと, 多少はわかりやすくなるかと... 自分は正直これくらい細かく言われないとすぐにはわかんない人なので(the O(ND)だけ
colordiff がイマイチだという niha さんの話を見て、rietveld みたいな感じで色つけてくれる diff 欲しいよねえ的なことを書きました。そしたらなんか、突然ふってわいた記憶によると、微妙に書きかけた記憶があるなぁ…と思い、作業用ディレクトリを見たら colordiff というディレクトリがあって、完成しかけみたいな状態で放置プレイされてました。 というわけで置いておきます。 http://shinh.skr.jp/koneta/#colordiff 適当にパス通ったとこに置けば、 diff -u hoge fuga | colordiff.pyとかでいいはずです。スクリーンショット: なんか微妙に色のつけかたがダメな部分があるけど、まぁ実用上問題はないんじゃないかな…
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く