講演抄録/キーワード |
講演名 |
2012-09-03 10:05
Bit-Parallel Algorithms for Finding All Substrings Matching a Regular Expression ○Hiroaki Yamamoto(Shinshu Univ.)・Takashi Miyazaki(Nagano National College of Tech.) COMP2012-27 |
抄録 |
(和) |
本論文は,正規表現とテキストが与えられたとき,テキスト内で正規表現に一致するすべての文字列を
見つける問題を考える.そのとき,この問題に対し,コンパクトな有限オートマトンを使った
ビット並列アルゴリズを与える. |
(英) |
This paper is concerned with the following regular expression searching
problem which, given a regular expression $r$ and a text string $T$ of length $n$
over an alphabet $\Sigma$, is to find all substrings matching $r$.
We will give bit-parallel algorithms to solve the RE searching problem.
The time complexity of our algorithms depends on the number of substrings
matching $r$. Hence the smaller the number of matching substrings is, the faster
the algorithms run. Furthermore if the word-length of a computer
is large enough, then this algorithm runs fast. |
キーワード |
(和) |
正規表現 / ビット並列アルゴリズム / 有限オートマトン / パターンマッチング / / / / |
(英) |
regular expression / bit-parallelism / finite automaton / pattern matching / / / / |
文献情報 |
信学技報, vol. 112, no. 199, COMP2012-27, pp. 9-16, 2012年9月. |
資料番号 |
COMP2012-27 |
発行日 |
2012-08-27 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2012-27 |