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

• Item type: Trans(1)
• 公開日: 1999-11-15
• タイトル: 転置ファイルおよび接尾辞配列の効率的圧縮法
• タイトル / 言語: en
• タイトル: Efficient Compression of Inverted Files and Suffix Arrays
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 研究論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東京大学理学系研究科情報科学専攻
• 著者所属: 東京大学理学系研究科情報科学専攻
• 著者所属(英): en
• 著者所属(英): Department of Information Science, University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Information Science, University of Tokyo
• 著者名: 定兼, 邦彦; 今井, 浩
• 著者名(英): Kunihiko, Sadakane; Hiroshi, Imai
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 単語ブロックソート圧縮法を提案する.これは文書と全文検索のための索引を圧縮する方法であり 圧縮データから転置ファイルを高速に生成できる.文書は圧縮時に単語に区切られるため 復号時には形態素解析などの時間のかかる処理は必要ない.これにより 全文検索のための索引を保存する際のディスク容量やネットワークを介して転送する際の負荷を減らすことができる.htmlに対する実験から 圧縮率はgzipよりも良く 圧縮データから転置ファイルを生成する時間は転置ファイルを0から作るよりも短く 形態素解析にかかる時間を含めると5倍以上速いことを確認した.また 単語ブロックソート圧縮法よりも圧縮率の良い通常のブロックソート圧縮法で圧縮された文書から単語を切り出し転置ファイルを生成するアルゴリズムも提案する.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464847
• 書誌情報: 情報処理学会論文誌データベース（TOD）; 巻 40, 号 SIG08(TOD4), p. 85-94, 発行日 1999-11-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7799
• 出版者 / 言語: ja
• 出版者: 情報処理学会