転置ファイルおよび接尾辞配列の効率的圧縮法

定兼, 邦彦, Kunihiko, Sadakane

転置ファイルおよび接尾辞配列の効率的圧縮法

情報処理学会 Web Site Web Site Web Site 被引用文献5件参考文献35件

書誌事項

タイトル別名

Efficient Compression of Inverted Files and Suffix Arrays
テンチファイルオヨビセツビジハイレツノコウリツテキアッシュクホウ

この論文をさがす

説明

単語ブロックソート圧縮法を提案する.これは文書と全文検索のための索引を圧縮する方法であり圧縮データから転置ファイルを高速に生成できる.文書は圧縮時に単語に区切られるため復号時には形態素解析などの時間のかかる処理は必要ない.これにより全文検索のための索引を保存する際のディスク容量やネットワークを介して転送する際の負荷を減らすことができる.htmlに対する実験から圧縮率はgzipよりも良く圧縮データから転置ファイルを生成する時間は転置ファイルを0から作るよりも短く形態素解析にかかる時間を含めると5倍以上速いことを確認した.また単語ブロックソート圧縮法よりも圧縮率の良い通常のブロックソート圧縮法で圧縮された文書から単語を切り出し転置ファイルを生成するアルゴリズムも提案する.

We propose word-based block sorting, which is used for compressing both texts and their full-text indexes, inverted files. Since texts are separated into words, morphological analysis, which is time consuming, is not necessary in the decoder. By using the proposed compression scheme, we can reduce space for storing full-text indexes and a load for transferring them via network. We confirmed by experiments that our compression scheme has better compression ratio than gzip and creating the inverted file from compressed data is faster than creating it from scratch. Furthermore, this is more than five times faster if time for morphological analysis is included. We also propose an algorithm for creating an inverted file from a compressed file by the ordinary block sorting which has better compression ratio than the word-based block sorting