Re: DotStar regex package

"John R. Levine" <johnl@iecc.com> writes:


> The March issue of IEEE Computer has an article called "Tools for Very
> Fast Regular Expression Matching" which describes a regex package
> called DotStar, written by three guys at IBM.
...
> I don't know enough about the nitty-gritty of current DFA pattern matchers
> to know if this really is a signficant improvement. Anyone else have
> opinions?


I've read the article and although a few details are a little
fragmentary, the work is sound and is part of a new trend in trying to
develop better (i.e. faster) regular expression processors. Similar
results can be seen in the work of Michella Becchi, who worked with
Patrick Crowley at Washington University (and interned with me here at
Intel). The underlying trick is converting the NFA into a DFA (and
the obvious generalization of the Aho-Corasik algorithm is a good way
to do this) except where doing so causes a state explosion and using
"other techniques" for dealing with the transitions that would cause
the explosion.


Hope this helps,
-Chris


******************************************************************************
Chris Clark email: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. Web Site: http://world.std.com/~compres
23 Bailey Rd voice: (508) 435-5016
Berlin, MA 01503 USA twitter: @intel_chris
------------------------------------------------------------------------------

Return to the comp.compilers page.
Search the comp.compilers archives again.