省メモリなBWT - 気ままなブログ

CSAやFM-Indexの構築時にボトルネックとなる省メモリなBWTの構築方法について調べた。実際、SAから構築する方法だとInduced Sortingを使うわけだが、最終的なCSAやFM-Indexの結果に比べてメモリを使いすぎる。これはちょっと嫌がられる。今はメモリが安いとはいえ、個人で買えるサイズは数十GBだろうし、かなり投資できる会社であっても数百GBだろう。価格とのトレードオフを考えるとこのあたりが妥当だと思う。 ってことで、ここ最近の悩みは、BWTを構築する時の中間メモリのサイズだった。というのも、仮に中間メモリが元のテキストの5倍必要であれば、メモリ的には、10GB使えても、テキストとしては、2GBしか扱えないことになる。これはかなり無駄だと思う。2GBずつ作って、5個のCSAやFM-Indexにして、メモリに上げておくという方法も考えられるが、この場合、検索性能は、1/5

[suffixarray]

bwt