| 大会名称 |
|---|
| 2009年 情報科学技術フォーラム(FIT) |
| 大会コ－ド |
| F |
| 開催年 |
| 2009 |
| 発行日 |
| 2009/8/20 |
| セッション番号 |
| 5A |
| セッション名 |
| 情報検索・論理・オートマトン |
| 講演日 |
| 2009/09/03 |
| 講演場所(会議室等) |
| A会場（9号館1F 911教室） |
| 講演番号 |
| RA-007 |
| タイトル |
| 高速復元可能な接尾辞配列圧縮法 |
| 著者名 |
| 田中 洋輔, 小野 廣隆, 定兼 邦彦, 山下 雅史, |
| キーワード |
| 文字列検索, 索引, 索引圧縮, 接尾辞配列 |
| 抄録 |
| 大規模データに対する高速な文字列検索は接尾辞配列 (SA) を用いて実現できるが, SAには多くの容量が必要になってしまう. SAを圧縮する様々な方法が提案されているが, 本論文では出現頻度の高いフレーズの検索が既存の圧縮法に比べて性能がよいような圧縮方法を提案する. 提案手法では, SAを大きさSのブロックに分割し, そのブロック内でソートを行い, 差分を取ったものを保存し, 検索時は差分からソート後のSAを取り戻し, 区間S内を全て逐次的に検索する. これで検索フレーズの全ての出現位置を得ることができる. 最終的には実験により特に検索フレーズの頻度が高い場合, 多くの入力データで提案手法の性能が既存の方法より優れていることを示す. |
| 本文pdf |
| PDF download (134.1KB) |