読者です 読者をやめる 読者になる 読者になる

省メモリなBWT(2)

NLP

頭文字D 5th Stageを見ていたら、何もせずに土曜日が終わりそうです。

絵がだいぶ変わっているが、ノリは変わってないので満足です。

さて、本題です。
以下の論文を読んだので、そのことについてちょっとだけ書いておきます。

文字列検索における圧縮インデックス構築の省メモリな並列化手法
林 伸也, 先進的計算基盤システムシンポジウム論文集, 2013.

https://ipsj.ixsq.nii.ac.jp/ej/?action=pages_view_main&active_action=repository_view_main_item_detail&item_id=92222&item_no=1&page_id=13&block_id=8

FM-Indexを利用する時に問題となるBWTの構築を省メモリ化しつつ、並列化しやすい方法の提案である。SAを介した方法だと元テキストの数倍のメモリが必要であるため、せっかく圧縮できるインデックスなのに使いにくい。なので、できるだけ省メモリで高速にBWTを行う方法が重要である。

この論文では、以下のような手順でSAを介さずに直接BWTを構築する(厳密には、小さいSAを作ってるけど)。

  1. テキストが一定のサイズ以下になるまで、繰り返し2分割していく。
  2. 一定のサイズ以下になったら、BWTを構築しつつ、サンプリングしたSAを保持しておき、LF-Mappingで位置を特定できるようにしておく(小さなFM-Index)。
  3. 2分割した左と右のBWTを順にマージしていく。

つまり、分割統治の考え方でBWTを構築する。

例えば、以下のような感じである。

テキスト:
aaaaaaaaaaab$

であり、一定のサイズ(閾値)が3であった場合は、

left:  aaaaaa
right: aaaaab

とし、3より大きいので、leftとrightをさらに分割する。

left-left:   aaa
left-right:  aaa
right-left:  aaa
right-right: aab

このように分割し、4つのテキストそれぞれで、BWTを構築し、以下のようにマージしていく。

  1. left-leftとleft-rightをマージする。
  2. right-leftとright-rightをマージする。
  3. leftとrightをマージする。

アルゴリズムはとてもシンプルで理解しやすい。再帰で簡単に記述できる。

さて、厄介なのは、マージの処理である。マージの処理は、Ferragina(FM-IndexのFの人)の定理を使って、右側のBWTの各文字が、左側のBWTの各文字の間のどこに挿入されるかを計算しなければならない。位置の特定自体は、Ferraginaの定理でできるが、LF-Mappingが以下の理由から正しく機能しない。

f:id:ryokkie:20130615220914p:plain

このため、各BWTの先頭に疑似的に文字を追加して、LF-Mappingが正しく機能するようにする。また、LF-Mappingの操作自体も修正する。

f:id:ryokkie:20130615221200p:plain

f:id:ryokkie:20130615221238p:plain

上記以外の位置のLF-Mappingは、定義通りで問題ない。

あと、論文を読んでいて思ったのだが、式(6)は、Tr[0,n] < Tr[i+1,n]となっているが、Tr[0,n] < Tr[t,n]ではないだろうか?

なかなかおもしろく読めたので、今後に期待したい。

広告を非表示にする