« 本読み | Main | プログラミング »

2005.11.26

ミスマッチの実装

Suffix Arraysを使ってミスマッチ検索を実現する論文が出ていて、これをwavelet tree + FMindexでもできるのではということで実装。

ターゲット長n、ターゲットのk次エントロピーをH_k、パターン長m、アルファベット数A、が与えられた時、ミスマッチを最大k(ここでのミスマッチはedit distanceの意味。削除、置換、追加からなる)まで許す、ターゲット中のクエリーにマッチする全てのポジションをnH_k bit 作業領域を用いて((mA)^k *m * logn + occ * logn) もしくは ((mA)^k * log^2 n + occ * log n)時間で報告できる、ただしoccは報告個数。

やっているのは、最初にパターン中の全ての部分列に対応するsuffix arrays中の領域をwavelet treeを使って求める(O(m^2))。あとはそれらを組み合わせて、クエリーにミスマッチが加わった形の新しい候補を作って調べている。(明示的には作らずに端から順に作る。)
例えばクエリーに"missisippi"が与えられたら"m","mi","mis",...,"i","is","iss",...,"pi","i"と全ての部分列に対応するsuffix arrays中の領域[sp,ep]をそれぞれ求める。次にこれらを順に組み合わせる。例えば3文字目のsが無くなったものを探すフェーズでは"mi"に対応する[sp1,ep1]と"sisippi"に対応する[sp2,sp2]を表からとってきて"mi":"sisippi"に対応する領域[sp,ep]をlognかmの速い方で求める。

実用的には(mA)^kの部分は殆どが候補を作る途中でターゲット領域に無いことがわかって打ち切られるので、もっと小さい。

prefix-freeの正規表現もこの勢いでできないかなぁ。夏ごろやるぞと言ったまま。

|

« 本読み | Main | プログラミング »

Comments

Post a comment



(Not displayed with comment.)




TrackBack

TrackBack URL for this entry:
http://app.cocolog-nifty.com/t/trackback/3041/7320280

Listed below are links to weblogs that reference ミスマッチの実装:

« 本読み | Main | プログラミング »