分節木と共有文字列で表現される符号上での効率良い圧縮照合アルゴリズム An Efficient Compressed Pattern Matching Algorithm on Codes Represented by Parse Tree and Shared String
この論文にアクセスする
この論文をさがす
著者
抄録
本論文では，VF符号で圧縮されたテキスト上でのパターン照合アルゴリズムについて論じる.ここで扱うVF符号とは，テキストを分節木によって可変長の部分文字列に分割し，固定長の符号語を割り当てる形式の符号化手法である. 圧縮照合問題の形式的枠組みであるCollage systemを用いれば，VF符号上でKMP型の汎用的なアルゴリズムを組織的に導出でき， O(m2 + D)時間・領域の前処理の後，O(n + R)時間で圧縮テキストを走査できる. ここで， m， n， R， D はそれぞれ，パターン長，テキスト長，パターンの出現回数，圧縮辞書のサイズである. しかし，この圧縮辞書のサイズは，各符号語に対する文字列の長さの総和に等しい. そこで，分節木上で共有される文字列の構造を利用し，より効率良く前処理を行うアルゴリズムを提案する. 提案アルゴリズムは，大きさ|T|の分節木T上の各ラベル文字列が，長さ|S|である文字列Sの一部分として表現されている場合， O(m2 + |S| + |T|)時間・領域で前処理を行うことができる. ここで，|S|+|T|はもとのDよりも非常に小さいものである. 本結果は，Collage system上で示されており，同種の構造の圧縮法であればVF符号に限らず適用できる.
収録刊行物
-
- 電子情報通信学会論文誌. D, 情報・システム = The IEICE transactions on information and systems (Japanese edition)
-
電子情報通信学会論文誌. D, 情報・システム = The IEICE transactions on information and systems (Japanese edition) 93(6), 733-741, 2010-06-01
電子情報通信学会