圧縮接尾辞配列に関する考察

• Item type: SIG Technical Reports(1)
• 公開日: 2000-07-26
• タイトル: 圧縮接尾辞配列に関する考察
• タイトル / 言語: en
• タイトル: A Note on the Compressed Suffix Arrays
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東北大学大学院情報科学研究科システム情報科学専攻
• 著者所属(英): en
• 著者所属(英): Department of System Information Sciences Graduate School of Information Sciences, Tohoku University
• 著者名: 定兼, 邦彦
• 著者名(英): Kunihiko, Sadakane
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 全文検索のための索引である接尾辞配列は，他の全文検索索引と比較すると省スぺースであるが，転置ファイルのような単語索引と比較するとサイズが大きい．この問題を解決するために圧縮接尾辞配列が提案されたが，検索にはテキスト自身も必要であるため，索引サイズはテキストよりも小さくならない．本稿では圧縮接尾辞配列を用いた検索アルゴリズムを，テキスト自身が不要になるように変更する．また，テキスト全体やその一部を圧縮接尾辞配列から復元するアルゴリズムを提案する．これにより，テキストの圧縮と高速な検索の両立が可能となる．大規模な英文，和文，DNA配列に対する実験により，検索文字列の出現数が少ない場合に転置ファイルや逐次検索よりも有効であることがわかった．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The suffix arrays, a kind of full-text indices, is more space-efficient than other full-text indices; however it is still larger than word indices such as the inverted files. Through the recently proposed compressed suffix array solved the problem in part, its index size is always larger than the text because it uses the text itself for keyword queries. In this paper we extend the text search algorithm using the compressed suffix array in order to work without the text itself. We also propose an algorithm to recover the whole or in part of the text. By using the algorithms both text comression and fast queries can be achieved. Experimental results on a large collection of English and Japanese texts and DNA sequences show that the compressed suffix array is more effective than using the inverted files or sequential searches if the number of occurrences of keywords is not too large.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10112482
• 書誌情報: 情報処理学会研究報告データベースシステム（DBS）; 巻 2000, 号 69(2000-DBS-122), p. 49-56, 発行日 2000-07-26
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会