講演抄録/キーワード |
講演名 |
2011-12-16 09:30
双対型positionオートマトンを用いたコンパクトなDFA表現 ○山本博章・中村彰吾(信州大) COMP2011-36 |
抄録 |
(和) |
正規表現のための照合アルゴリズムは,正規表現を決定性有限オートマトン(DFA)に
変換すれば,検索は高速に行うことができる.しかし,最悪の場合は,
DFAのサイズが元の正規表現の長さの指数的になってしまう.
長さ$m$の正規表現に対し,一般にDFAのサイズは$(m+1)2^{2m+1}|\Sigma|$ビット
必要とする.NavarroとRaffinotは,positionオートマトンを利用して,
$(\tilde{m}+1)2^{\tilde{m}}~(=(\tilde{m}+1)\prod_{a\in \Sigma}2^{m_a})$
ビットでDFAを表現する方法を示した.ここで,$\tilde{m}=\sum_{a\in\Sigma} m_a$, $m_a$は
与えられた正規表現に出現するアルファベット記号$a$の数である.
本論文は,双対型positionオートマトンというモデルを導入し,
$(\tilde{m}+1)(\sum_{a\in \Sigma}2^{m_a})$ビットのみを使ったDFAの表現方法を
示す.このDFA表現を使うと,通常のDFAと同様に,
高速に正規表現の照合を行うことができる. |
(英) |
This paper introduces an automaton model called {\em a dual position automaton}
(a dual PA), and then gives a bit-parallel algorithm for generating
a dual PA from a regular expression (RE).
For any RE $r$ over an alphabet $\Sigma$,
our translation algorithm generates a dual PA consisting of $\tilde{m}(\tilde{m}+1)$
bits in $O(\tilde{m}\lceil \tilde{m}/w\rceil)$ time and space,
where $w$ is the length of a computer word, $\tilde{m}=\sum_{a\in\Sigma} m_a$
and $m_a$ is the number of occurrences of an alphabet symbol $a$ in $r$.
Furthermore, we give a method to construct a compact DFA representation
from a dual PA. This DFA representation requires only
$(\tilde{m}+1)\sum_{a\in\Sigma}2^{m_a}$ bits.
Finally, we show RE matching algorithms using such a DFA representation. |
キーワード |
(和) |
双対型positionオートマトン / DFA / 正規表現 / パターンマッチング / / / / |
(英) |
dual position automaton / DFA / regular expression / pattern matching / / / / |
文献情報 |
信学技報, vol. 111, no. 360, COMP2011-36, pp. 1-7, 2011年12月. |
資料番号 |
COMP2011-36 |
発行日 |
2011-12-09 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2011-36 |