2013 | OriginalPaper | Chapter
Online Matching of Multiple Regular Patterns with Gaps and Character Classes
Authors : Seppo Sippu, Eljas Soisalon-Soininen
Published in: Language and Automata Theory and Applications
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Given a dictionary
D
of regular expressions and a text
T
, the online regular-pattern-matching problem is to single out, for each text position
T
[
c
], those expressions in
D
that have a match ending at
T
[
c
], while processing
T
only once. This problem is considered in the context of regular patterns over bounded-length gaps and keywords, where the gaps are specified by wildcards and character classes and the keywords are strings over the input alphabet. Our algorithm is based on constructing the Aho–Corasick pattern-matching automaton for the set of keywords, and representing as a bit vector the set of keywords that can precede a given keyword in a regular-pattern instance. For a dictionary
D
with
r
patterns and with
k
i
keywords in pattern
i
, the preprocessing takes time
$O(|D| + \sum_{i=1}^r k_i^2 \log k_i / w)$
, where
w
denotes the number of bits in a memory word. When only fixed-length wildcard gaps without character classes are allowed, the time spent by our matching algorithm for each text character
T
[
c
] is at most
O
((log
r
+
k
/
w
) (
K
c
+ 1)), where
k
= max {
k
1
, …,
k
r
} and
K
c
is the number of keyword occurrences in
D
matched at text position
T
[
c
].