difff《ﾃﾞｭﾌﾌ》
下記の文章を比較してください。 Betty Botter bought some butter, But, she said, this butter's bitter; If I put it in my batter, It will make my batter bitter, But a bit of better butter Will make my batter better. So she bought a bit of butter Better than her bitter butter, And she put it in her batter, And it made her batter better, So 'twas better Betty Botter Bought a bit of better butter. 下記の文章を，ﾋﾋ較してくだちい． Be
Eclipse のライブラリを流用して diff 系ツールを自作する方法 - toyfish.blog
「また明日から 2 つのデータの差分を目視で見つける仕事が始まるお……」 「ほんとは diff を使って速度も精度も上げたいんだお……」 「でもこの PC には JDK と Eclipse しか入れちゃいけないお……」 「……だから Eclipse を使って diff っぽいツールを自作するお!!」 ほんとは WinMerge とか入れられればいいんですけどね。「WinMerge 入れられない! 入れにくい!!」な環境でなんとかしてみようと思ったわけです。 使うライブラリ Eclipse には「比較エディタ」という機能があり、2 つのファイルの差分を見ることができます。このとき差分検出に使われているライブラリ (というかプラグイン) は、classpath を通せば、自分のアプリケーションからも使えるっぽいです。 Eclipse 3.2 の場合でいうと、plugins ディレクトリにあるこ
stroy and friends - stroy
News teaser: new stroy is coming 2012.08.31 lots of fixes and changes and some features. generj 0.1 released download 2010.09.03 more on generj first release of a tool to generate java beans and matching xml bindings openCage-lang 0.4 released download 2010.09.02 more on openCage-lang second public release of openCage-lang. osashosa 0.1 released download 2010.07.14 first release of osashosa a drop
最長共通部分列問題 (Longest Common Subsequence) - naoyaのはてなダイアリー
部分列 (Subsequence) は系列のいくつかの要素を取り出してできた系列のことです。二つの系列の共通の部分列を共通部分列 (Common Subsecuence)と言います。共通部分列のうち、もっとも長いものを最長共通部分列 (Longest Common Subsequence, LCS) と言います。 X = <A, B, C, B, D, A, B> Y = <B, D, C, A, B, A> という二つの系列から得られる LCS は <B, C, B, A> で、その長さは 4 です。長さ 2 の<B, D> の長さ 3 の <A, B, A> なども共通部分列ですが、最長ではないのでこれらは LCS ではありません。また、LCS は最長であれば位置はどこでも良いので、この場合 <B, D, A, B> も LCS です。 LCS は動的計画法 (Dynamic Prog
文書比較（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
/0 » diff(3)
そんなわけでO(NP)のお話とか。 まず、処理を最適化するためにO(ND)の無駄を考えてみる。 O(ND)では編集回数Dを0…nと変化させて順次処理を行うわけだけど、仮に集合A(0…M)とB(0…N)の間で、M!=Nの関係が有る場合、D<|M-N|の間は決して終端にたどり着かない期間の計算となる。 また、編集回数Dの時に、零距離直線kを-D…0…Dまで計算するが、この際も実際には結構無駄な計算を行っている。 というのも、編集回数Dで終点にたどり着ける場合、実際に経路として使用されるkの範囲は-D…0…Dと一致しない。 集合Aと集合Bの関係をN>=Mと仮定して、Δ=N-Mとした場合、この未知の集合において最も少ない編集回数はΔとなるが、その場合のkの範囲は0…Δとなる（上図の緑色の範囲）。 以降Dが2増える毎(移動距離1の往復分)に-1…Δ+1、-2…Δ+2とkの範囲が広がっていくこ
/0 » diff(2)
diff続き。 今回はO(ND)アルゴリズムと一般的に呼ばれている方法のまとめ。 O(Nなんちゃら)とか表記する場合、本当は処理時間の指標の筈で、元々O(ND)もこのアルゴリズムにはO(ND)掛かりますよってダケの筈なんだけどなぁ・・・。 何処を覗いてもMyers氏のアルゴリズムをO(ND)アルゴリズムと呼ぶ不思議。 diff(1)と同様に 集合 A(0…M) = { a b d e f a b c e d } 集合 B(0…N) = { d a b a b c b c b a e d } のdiffを取る事を考える。 （エディットグラフは前回参照で） エディットグラフ上の最短距離を考えるにあたり、如何に効率よく斜線部分を通るかを考える（最短距離＝最も効率よく斜線部分を通過した経路）。 ここで、斜線斜線と呼ぶのも、原文diagonal直訳の対角線もちょっとアレなので、あえて
/0 ≫ diff(1)
仕事でdiffとる必要があって、とりあえず実装後に色々勉強して理解できたので、忘れないうちにどこかに文章化しておくテスト。 って、ここかよ＜文章化 （いや、ネット上に日本語で細かく解説してくれてるサイトが無かったので・・・） 取り合えず、予定としては diff(1) → 基本の考え方 diff(2) → アルゴリズム１：O(ND)アルゴリズム diff(3) → アルゴリズム２：O(NP)アルゴリズム の予定で。 ・・・まぁ、全部書ければいいな・・・と（遠い目） 集合 A(0…M) = { a b d e f a b c e d } 集合 B(0…N) = { d a b a b c b c b a e d } のdiffを取る事を考える。 diffの考え方の基本は、最も共通部分が長くなる組み合わせ（以降LCS = LargestCommonSubsequence)を見つ
バージョン管理システムの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
ウノウラボ Unoh Labs: diff with C++
ミートソーススパゲティを作るときは、ミートソースから作るのが信条のbokkoです。それはさておき、今日はdiffのお話です。 diff diffは指定した2つのファイルの差分を求めるコマンド、もしくはその差分そのものを指します。普段から何気なく使用しているコマンドですが、その中で使われているアルゴリズムは結構難しいです。 差分を計算するということ 差分を計算するというのは以下の3つを求めることに帰結します。 ・Levenshtein Distance(Edit Distance) ・LCS(Longest Common Subsequence) ・SES(Shortest Edit Script) 上から順に1つずつ説明していきます。 Levenshtein Distance Levenshtein Distanceは2つのシーケンスの違いを数値化したもので編集距離とも言います。これは後述
jpace - Overview
1 contribution on Sunday, April 24, 2022 No contributions on Monday, April 25, 2022 No contributions on Tuesday, April 26, 2022 1 contribution on Wednesday, April 27, 2022 No contributions on Thursday, April 28, 2022 No contributions on Friday, April 29, 2022 No contributions on Saturday, April 30, 2022 1 contribution on Sunday, May 1, 2022 No contributions on Monday, May 2, 2022 No contributions
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
差分のアルゴリズム - 忘れたときに備えた記録(2007-07-17)
http://www.xmailserver.org/diff2.pdf
GitHub - google/diff-match-patch: Diff Match Patch is a high-performance library in multiple languages that manipulates plain text.
jpace - Overview