Diff algorithm - 枕を欹てて聴く

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

[vowrumme]

今のところ一番わかりやすい解説！

[hiratara]

ふむ。 「> Diff algorithm ... 計算量O(ND) / O(NP)のalgorithmなどがある」

[kurumigi]

JavaScriptによるレーベンシュタイン距離(編集距離)の計算。

[marblejenka]

[c/c++]

[Ctrans]

Diff algorithm

[cn_syan]

diff

[snaka72]

あとでよむ

[ytoku]

三種類解説。基本となるアルゴリズムと、距離や「損失」で反復深化する改良アルゴリズム。/よくある左上から右下までの最短経路を探すDPの問題ってこういう所に応用できるのかー

[Gemma]

levenshtein距離 O(ND) / O(NP)

[mooz]

これはすごい。じっくり読まないと。

[smoking186]

「O(ND)」とか「O(NP)」とかはアルゴリズムの名前じゃない... / 開発者が名前付けるのが一番良いんですけどねぇ。アルゴリズムとか暗号とかネットワーク系とか。

[edvakf]

ビットパラレル法という高度な技もあるらしいですよ。ビット演算に疎い自分には理解するのがそもそも無理でした。http://handasse.blogspot.com/2009/04/c_29.html

[efcl]

Javascriptで書くDiffアルゴリズム