| 講演名 | 2010-05-19 非巡回正規表現に対する効率的なパターン照合 金田 悠作, 湊 真一, 有村 博紀, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 正規表現は,アルファべットΣの文字と,結合"・"と選択"|"だけから構成されるとき,非巡回正規表現(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. |
| キーワード(和) | パターン照合 / 正規表現 / ビット並列アルゴリズム |
| キーワード(英) | Pattern matching / Regular expression / Bit-Parallel algorithm |
| 資料番号 | COMP2010-11 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2010/5/12(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 非巡回正規表現に対する効率的なパターン照合 |
| サブタイトル（和） | |
| タイトル（英） | Efficient Pattern Matching for Acyclic Regular Expressions |
| サブタイトル（和） | |
| キーワード(1)（和/英） | パターン照合 / Pattern matching |
| キーワード(2)（和/英） | 正規表現 / Regular expression |
| キーワード(3)（和/英） | ビット並列アルゴリズム / Bit-Parallel algorithm |
| 第 1 著者 氏名（和/英） | 金田 悠作 / Yusaku KANETA |
| 第 1 著者 所属（和/英） | 北海道大学大学院情報科学研究科 Graduate School of Information Science and Technology, Hokkaido University |
| 第 2 著者 氏名（和/英） | 湊 真一 / Shin-ichi MINATO |
| 第 2 著者 所属（和/英） | 北海道大学大学院情報科学研究科 Graduate School of Information Science and Technology, Hokkaido University |
| 第 3 著者 氏名（和/英） | 有村 博紀 / Hiroki ARIMURA |
| 第 3 著者 所属（和/英） | 北海道大学大学院情報科学研究科 Graduate School of Information Science and Technology, Hokkaido University |
| 発表年月日 | 2010-05-19 |
| 資料番号 | COMP2010-11 |
| 巻番号（vol） | vol.110 |
| 号番号（no） | 37 |
| ページ範囲 | pp.- |
| ページ数 | 7 |
| 発行日 | |