ブロックソート圧縮データの検索法

概要

論文の詳細を見る
BurrowsとWheelerによって1994年に報告された(元は1983年にWheelerによって提案された)ブロックソート圧縮アルゴリズムは, その圧縮率が, よく知られているLZ圧縮アルゴリズムに匹敵することから圧縮アルゴリズムの理論家のあいだで注目されている.本論文では, ブロックソート圧縮データに対してパターン検索する方法を提案する.そして, ブロックソート圧縮アルゴリズムはパターン検索しやすい効率的な圧縮法であることを指摘する.テキスト全体が巡回シフトの配列によって行が辞書式に順序付けられており, テキストの中で複数箇所に散在する検索パターンは, 配列の行の先頭から現れ, 連続する行に固まっている.検索パターンと効率的に照合するために, テキスト中で出現頻度の少ない検索パターン文字の位置から始めて一気に絞り込み, そのまわりに拡大する処理方式を提案する.そして, 元のブロックソート圧縮アルゴリズムを修正して, 配列の最後の例の文字列を圧縮符号化するかわりに, 整列させた連続する文字の出現開始位置をポイントし, 整列前の位置との対応付けを直接求められる圧縮符号化を提案する.
一般社団法人情報処理学会の論文
2001-01-19