アルゴリズムの名前
今回の内容は以前当ブログに書いた「diff with C++」の記事をもっと濃くした感じになっていて、編集距離やLCS、SESの解説に始まり、Subversionのdiffエンジンや拙作のdtlで使われているO(NP)という差分アルゴリズムについて解説しています。
O(NP)や、それによく似たO(ND)をはじめとするエディットグラフを使って差分を求めるアルゴリズムは普段何気なく使っているdiffコマンドや各種バージョン管理システムで使われていることからもわかるようにとても有用であり、アルゴリズム自体の美しさやスマートさにも目を見張るものがあります。興味がある方はぜひ手にとって読んでみてください。本記事を通してdiffのアルゴリズムのおもしろさが伝われば幸いです。
「O(NP)」や「O(ND)」というのは各々のアルゴリズムの計算量のことであって名前にするのはどうなんでしょう。
Wu, Manber, Myers, Millerのアブストにあるthe O(ND) algorithm of Myers
とかってのはMyersのO(ND) (計算量) アルゴリズムって意味であって、アルゴリズムの名前じゃありません。また、最近の編集距離関係の論文を見てもO(NP)でアルゴリズムを指している例は見当たりませんでした。
ということで「O(NP)差分アルゴリズム」ならセーフだけど「O(NP)という差分アルゴリズム」だとアウトじゃぁないでしょうか。
修正されたようです. よかったよかった( ´ー`)