Efficient Compression of Inverted Files and Suffix Arrays

IPSJ Web Site Web Site Web Site 5 Citations 35 References

Bibliographic Information

Other Title
  • 転置ファイルおよび接尾辞配列の効率的圧縮法
  • テンチ ファイル オヨビ セツビジ ハイレツ ノ コウリツテキ アッシュクホウ

Search this article

Description

単語ブロックソート圧縮法を提案する.これは文書と全文検索のための索引を圧縮する方法であり 圧縮データから転置ファイルを高速に生成できる.文書は圧縮時に単語に区切られるため 復号時には形態素解析などの時間のかかる処理は必要ない.これにより 全文検索のための索引を保存する際のディスク容量やネットワークを介して転送する際の負荷を減らすことができる.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

Journal

Citations (5)*help

See more

References(35)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top