分節木と共有文字列で表現される符号上での効率良い圧縮照合アルゴリズム An Efficient Compressed Pattern Matching Algorithm on Codes Represented by Parse Tree and Shared String

この論文にアクセスする

この論文をさがす

著者

    • 喜田 拓也 KIDA Takuya
    • 北海道大学大学院情報科学研究科 Graduate School of Information Science and Technology, Hokkaido University

抄録

本論文では,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

    電子情報通信学会

参考文献:  9件中 1-9件 を表示

各種コード

  • NII論文ID(NAID)
    110007618348
  • NII書誌ID(NCID)
    AA12099634
  • 本文言語コード
    JPN
  • 資料種別
    ART
  • ISSN
    18804535
  • NDL 記事登録ID
    10727390
  • NDL 雑誌分類
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL 請求記号
    Z16-779
  • データ提供元
    CJP書誌  NDL  NII-ELS  IR 
ページトップへ