VF符号上における圧縮照合アルゴリズム Compressed Pattern Matching on VF Codes

この論文をさがす

著者

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

抄録

本稿では,VF符号で圧縮されたテキスト上でのパターン照合アルゴリズムについて論じる.まず,圧縮照合問題の形式的枠組みであるCollage systemを用いて,VF符号上でKMP型の圧縮照合を行う汎用的なアルゴリズムを導出する.そのアルゴリズムは,O(m^2+D)時間・領域の前処理の後,O(n+R)時間で圧縮テキストを走査できる.ここで,m,n,R,Dはそれぞれ,パターン長,テキスト長,パターンの出現回数,圧縮辞書のサイズである.ただし,ここでいう圧縮辞書のサイズとは,各符号語に対応する文字列すべてを連結した長さに等しい.本稿では,さらに,文節木上の各ラベルが相互に文字列を共有した形で表現されている場合に,効率良く前処理を行う改善アルゴリズムを提案する.各ラベルがある文字列Sの一部分として表現されているとすると,提案アルゴリズムはO(m^2+|S|+|Τ|)時間・領域で前処理を行う.ここで,Τは文節木の大きさである.

We discuss the problem of pattern matching on a VF coded text. We derive a KMP-type pattern matching algorithm from the collage system, which is a general framework to capture the essence of compressed pattern matching. The algorithm runs on a VF coded text directly in O(n+R) time after O(m^2+D) time and space preprocessing, where m, n, R, D are the pattern length, the compressed text length, the number of occurrences, and the size of the dictionary for the VF code. In this paper, we also present an improved algorithm which can preprocess more efficiently if each label on the parse tree of the VF code shares substrings mutually. For the pattern of length m and the parse tree of size |Τ|, it runs in O(m^2+|S|+|Τ|) time and space for preprocessing if each label is represented as a pointer to the string S.

収録刊行物

  • 電子情報通信学会技術研究報告. COMP, コンピュテーション

    電子情報通信学会技術研究報告. COMP, コンピュテーション 109(108), 1-8, 2009-06-22

    一般社団法人電子情報通信学会

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

被引用文献:  2件中 1-2件 を表示

各種コード

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