SACHICA(類似文字列列挙アルゴリズム)

機械学習

SACHICA(類似文字列列挙アルゴリズム)のC++による実装を公開しました。
http://sites.google.com/site/yasuotabei/sachica

sachicaは、同じ長さの文字列集合を入力として、ハミング距離がある閾値以下のすべてのペアーを超高速に出力します。　アルゴリズムは、マルチソーティングという手法に基づきます。
詳しくは、ハミング距離がd以内で長さがmの文字列集合があったとします。初めに、各文字列をk (> d)の部分文字列のブロックに分割します。 今、ハミング距離がd以内の文字列のペアーを求めたいので、もし、ハミング距離がd以内の文字列のペアーが存在すれば、鳩の巣原理により、それらにはk - d個の完全一致するブロックが存在します。この原理に基づき、sachicaはcombination(k, k-d)のすべての組み合わせのブロックをラディックスソートにてソートして、ブロックが完全一致する文字列ペアーを発見します。次に後処理で、それらのペアーが本当にハミング距離がd以下かどうかをチェックします。ラディックスソートの処理は、すべての文字列をペアワイズで比較するより効率的です。応用としては、ゲノム処理やベクトルデーターの近傍探索などがあります。もっと詳しく知りたい方は、論文を参照してください。
http://www.springerlink.com/content/3g5316143gr25124/