非巡回正規表現に対する効率的なパターン照合 Efficient Pattern Matching for Acyclic Regular Expressions

この論文をさがす

著者

    • 金田 悠作 KANETA Yusaku
    • 北海道大学 大学院情報科学研究科 Graduate School of Information Science and Technology, Hokkaido University
    • 湊 真一 MINATO Shin-ichi
    • 北海道大学 大学院情報科学研究科 Graduate School of Information Science and Technology, Hokkaido University
    • 有村 博紀 ARIMURA Hiroki
    • 北海道大学 大学院情報科学研究科 Graduate School of Information Science and Technology, Hokkaido University

抄録

正規表現は,アルファべットΣの文字と,結合"・"と選択"|"だけから構成されるとき,非巡回正規表現(acyclic regular expression)と呼ばれる.本稿では,非巡回正規表現のクラスに対して,長さmと深さdをもつ非巡回正規表現と長さnをもつ入力テキストを入力として受け取り,O(md)の前処理時間とO(md/w)領域を用いて,O(nmd/w)時間で正規表現照合問題を解く効率よいアルゴリズムを与える.このために,正規表現と等価な非決定性有限オートマトン(NFA)の状態遷移計算をビット演算と加減算を用いて模倣する分配集積演算と呼ぶビット並列計算手法を開発し,WuとManberらのSHIFT-AND手法(CACM 35(10), 1992)を,非巡回正規表現パターンに拡張している.本結果は,定数深さの非巡回正規表現に対して,O(m/w)領域を達成しつつ,一般の正規表現照合に対するBilleのアルゴリズム(ICALP, 2006)のよりも時間計算量が小さい.

A regular expression is acyclic if it is over the basis in Σ, dot "・", and union "|". In this paper, for the subclass of acyclic regular expressions, we give an efficient algorithm that solves the regular expression matching problem for an acyclic regular expression of length m and depth d and an input text of length n in O(nmd/w) time using O(md) preprocessing and O(md/w) space in words on unit-cost RAM model with word length w. We introduce new bit-parallel techniques, called scatter and gather operations to simulate Thompson NFA for a given regular expression, and naturally extend SHIFT-AND approach by Wu and Manber (CACM 35(10), 1992) to the regular expression matching problem. For an acyclic regular expression with unbounded depth d=O(1), our approach is faster than Bille's approach for any regular expression keeping O(m/w) space.

収録刊行物

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

    電子情報通信学会技術研究報告. COMP, コンピュテーション 110(37), 23-29, 2010-05-12

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

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

各種コード

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