著者

定兼 邦彦

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2000, no.84, pp.73-80, 2000-09-21

---

全文検索のための索引である接尾辞配列は,他の全文検索索引と比較すると省スペースであるが,転置ファイルのような単語索引と比較するとサイズが大きい.この問題を解決するために圧縮接尾辞配列が提案されたが,検索にはテキスト自身も必要であるため,索引サイズはテキストよりも小さくならない.本稿では圧縮接尾辞配列を用いた検索アルゴリズムを,テキスト自身が不要になるように変更する.また,テキスト全体やその一部を圧縮接尾辞配列から復元するアルゴリズムを提案する.これにより,テキストの圧縮と高速な検索の両立が可能となる.A compressed text database based on the compressed suffix array is proposed. The compressed suffix array of Grossi and Vitter occupies only O(n) bits for a text of length n; however it also uses the text itself that occupies O(n log|Σ|) bits for the alphabet Σ. On the other hand, our data structure does not use the text itself, and supports important operations for text databases: inverse, search and decompress. Our algorithms can find occ occurrences of any substring P of the text in O(|P|log n + occ log^ε n) time and decompress a part of the text of length l in O(l+log^ε n) time for any fixed 1 > ε > 0. Our data structure occupies only 1/εnH_0 + n(6+3logH_0)<log^εn>/<log^εn-1>+2n+|Σ|log|Σ|+o(n) bits where H_0〓log|Σ| is the order-0 entropy of the text.