| 講演名 | 2002/3/5 拡張正則表現に対する文字列照合アルゴリズムの実験的評価 市川 龍治, 山本 博章, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本論文では,拡張正則表現に対する文字列照合問題を扱う。すなわち,長さmの拡張正則表現rと長さnのテキストxが与えられたとき,xの中にrと一致する文字列が存在するかどうか判定する問題である。山本の認識アルゴリズムを利用することによってこの問題を簡単にO(mn^2 +kn^3)時間かつO(mn+kn^2)領域で解くことができる。ここでは,このアルゴリズムを非決定性有限オートマトンおよび決定性有限オートマトンを使って実装することにより,その効率さについて実験的に評価する。 |
| 抄録(英) | In this paper, we are concerned with a string matching problem for extended regular expressions: Given an extended regular expression r of length m and a text string x of length n, determine if there exists a substring y of x such that y∈L(r), where L(r) denotes the language denoted by r. By using Yamamoto's recognition algorithm, we can simply solve this problem in O(mn^2 +kn^3) time and O(mn+kn^2) space. We implement this algorithm by using nondeterminisitic finite automata and deterministic finite automata, and evaluate the efficiency. |
| キーワード(和) | 拡張正則表現 / 文字列照合アルゴリズム |
| キーワード(英) | extended regular expression / string matching algorithm |
| 資料番号 | COMP2001-98 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2002/3/5(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 拡張正則表現に対する文字列照合アルゴリズムの実験的評価 |
| サブタイトル（和） | |
| タイトル（英） | String Matching Algorithm for Extended Regular Expressions |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 拡張正則表現 / extended regular expression |
| キーワード(2)（和/英） | 文字列照合アルゴリズム / string matching algorithm |
| 第 1 著者 氏名（和/英） | 市川 龍治 / Ryuji ICHIKAWA |
| 第 1 著者 所属（和/英） | 信州大学大学院工学系研究科 Graduate School of Science and Technology, Shinshu University |
| 第 2 著者 氏名（和/英） | 山本 博章 / Hiroaki YAMAMOTO |
| 第 2 著者 所属（和/英） | 信州大学工学部 Faculty of Engineering, Shinshu University |
| 発表年月日 | 2002/3/5 |
| 資料番号 | COMP2001-98 |
| 巻番号（vol） | vol.101 |
| 号番号（no） | 708 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |