高速復元可能な接尾辞配列圧縮法

田中 洋輔  小野 廣隆  定兼 邦彦  山下 雅史  
(FIT2009推薦論文)

誌名
電子情報通信学会論文誌 D   Vol.J93-D   No.8   pp.1567-1575
発行日: 2010/08/01
Online ISSN: 1881-0225
Print ISSN: 1880-4535
論文種別: 論文
専門分野: 情報・システム基礎
キーワード: 
全文検索,  接尾辞配列,  索引圧縮,  

本文: PDF(731.8KB)
>>論文を購入


あらまし: 
大規模文字列データに対する高速な文字列検索は接尾辞配列(SA)を用いて実現できるが,SAには多くの容量が必要になってしまう.SAを圧縮する様々な方法が提案されているが,本論文では出現頻度の高いフレーズの検索が既存の圧縮法に比べて高速な圧縮法を提案する.提案手法では,SAをブロックに分割し,そのブロック内でソートを行い,差分をとったものを保存し,検索時は差分からソート後のSAを取り戻し,区間内をすべて逐次的に検索する.これで検索フレーズのすべての出現位置を得ることができる.実験により,特に検索フレーズの頻度が高い場合,多くの入力データで提案手法の性能が既存の方法より優れていることを示す.