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

省メモリなBWT

NLP

CSAやFM-Indexの構築時にボトルネックとなる省メモリなBWTの構築方法について調べた。実際、SAから構築する方法だとInduced Sortingを使うわけだが、最終的なCSAやFM-Indexの結果に比べてメモリを使いすぎる。これはちょっと嫌がられる。今はメモリが安いとはいえ、個人で買えるサイズは数十GBだろうし、かなり投資できる会社であっても数百GBだろう。価格とのトレードオフを考えるとこのあたりが妥当だと思う。

ってことで、ここ最近の悩みは、BWTを構築する時の中間メモリのサイズだった。というのも、仮に中間メモリが元のテキストの5倍必要であれば、メモリ的には、10GB使えても、テキストとしては、2GBしか扱えないことになる。これはかなり無駄だと思う。2GBずつ作って、5個のCSAやFM-Indexにして、メモリに上げておくという方法も考えられるが、この場合、検索性能は、1/5になる(直列的に検索するため)。

なので、テキストを一括でBWTしたいと思い、このあたりの知識を深めるために、以下の論文を読んでみた。

http://crpit.com/confpapers/CRPITV122Dhaliwal.pdf

よくまとまっていて読みやすい。例も豊富だ。特に、FGMがおもしろい。なんとなく現実的に使えそうな構築方法だ。処理手順としては以下のようになる。

  1. テキストを適当なパラメータ(M)でブロックに分ける。
  2. 最も右側のブロックのBWTを計算し、ディスク(HDD or SSD)に格納する。
  3. 次のブロックのBWTを計算し、ディスク上のBWTとマージする。

上記の操作をBWTが完成するまで繰り返す。この方法を使えば、一定のメモリ量でBWTを計算できる。しかも、ディスク(HDD or SSD)に出力する部分はシーケンシャルに可能なので、アーキテクチャにも合っている。もちろん、SSDはHDDよりもランダムI/Oには強いが、最速はシーケンシャルI/Oである。

FGMの原論文は以下にあります。

http://people.unipmn.it/manzini/bwtdisk/bwte.pdf

FGMは、ツールがあるようで、試すと外部ディスクをガリガリ使いながら、まぁまぁの速度でBWTを計算してくれる。ツールは、以下にあります。

http://people.unipmn.it/manzini/bwtdisk/

注意すべきは、テキストを逆転させてからBWTを計算するので、予想した結果とは異なるというところだろう。

さて、原論文をしっかり読みます。

広告を非表示にする