id:siokoshou:20080324 の類似文字列を求める処理をちょっと改良。かなり使えるかも。一文字も同じ文字がなければ捨てるようにしてみました。編集距離が比較する両方の文字列の長さの合計以上であれば、それは完全に文字列を置き換えたということなので、つ…

類似文字列を求める処理を書いてみました。文字列を与えると、候補文字列の配列中から近いもの順に返してくる関数です。あいまい検索などに応用できます。 書いてみましたと言っても、以前書いた Diff クラスの使い方の一例だったりします。これ書いてて思い…

.NET 高速 diff classを公開します。２つの文字列のdiffを取ります。行単位のdiff(UNIXのdiffコマンドのような)と、文字単位のdiffを取れます。 "An O(NP) Sequence Comparison Algorithm"(PDF), Sun Wu, Udi Manber, Gene Myers, (1989) のアルゴリズムを使…

前回は http://www.mathertel.de/Diff/ のコードの Hashtable を削除したら２倍速くなったところまで。今日はその続き。 このコードでは文字列を行ごとにばらしてハッシュ値にする前処理があって、その後にハッシュ値配列のdiffを調べる。この前処理とdiff処…

http://www.mathertel.de/Diff/ここのO(ND)なコード、「非常に早いコードです。diffのアルゴリズムに詳しくなければこれより早いコードは書けません。」と書いたばかりでなんだけど、ちょっといじったら２倍早くなった。前言撤回(^^; Hashtableいらなくね？…

(追記)この日の日記で紹介したO(ND)のdiffクラスより高速なO(NP)のdiffを書きました。id:siokoshou:20070315を参照。(追記終わり)コード中でdiffを取りたかったので.NETなdiffクラスがないかと探してみたら、とてもよいものを見つけました。http://www.mathe…