簡潔データ構造による全文検索のハードウェアを用いた高速化

摘要

接尾辞配列は高速な全文検索に適したアルゴリズムである.巨大なデータを処理するために，データ構造を情報理論的下限まで圧縮した簡潔データ構造の利用が注目されている.一方で，圧縮されたデータの解凍をする処理が必要であり，そのオーバヘッドが問題となっている.圧縮接尾辞配列は接尾辞配列に簡潔データ構造を応用したアルゴリズムである.データ構造の性質上，主要な操作においてビットベクトルに対する演算，メモリに対するランダムアクセスが大量に必要となる.我々は圧縮接尾辞配列による全文検索を高速化するためのFPGAを用いたハードウェアアクセラレータを提案する.ハードウェアの並列性を利用することにより，ビットベクトルに対する演算の高速化やオーバヘッドの無いメモリアクセス順の制御が可能である.ハードウェアアクセラレータによる全文検索，テキスト復元のシミュレーションを行い，ソフトウェア実装の性能と比較することにより評価を行ったところ，それぞれ7倍，3倍以上の性能向上が得られるという結果が得られた.%Full-text searches for massive data are important in Web search and genomic analysis. Suffix array is a fast full-text search algorithm. Succinct data structure is a data structure compressed to the information-theoretic bound and improves the amount of data processible on memory. Compressed suffix array is an algorithm applying the succinct data structure to suffix array. We propose a FPGA-based hardware accelerator for full-text search using compressed suffix array. We evaluated by simulations its performances of full-text search and decompression of compressed suffix array. We compared its performance with that of a software implementation.