RE2/J: Linear time regular expression matching in Java

by fmela • 11 years ago

42 8 11 years ago

mumrah• 11 years ago

Lucene has had this capability for a while now. A regexp query (as defined by the RegExp class) is compiled into an automaton for quick comparison with the inverted index, also represented as an automaton. Automatons and FSTs are used extensively by Lucene these days. Out of curiosity, I did some playing around with Lucene's RegExp class when it first came out (or rather, when I first learned about it). It provides a really interesting way to build regular expressions: https://gist.github.com/mumrah/6104234

Javadoc: https://lucene.apache.org/core/4_0_0/core/org/apache/lucene/...

Source: https://github.com/apache/lucene-solr/blob/trunk/lucene/core...

hcayless• 11 years ago

Lucene's regexp querying is based on http://www.brics.dk/automaton/

It's fast, but limited too: no word boundary matching for example.

chrisconroy• 11 years ago

Related: the dk.brics.automaton library (http://www.brics.dk/automaton/) is excellent.

It's got a much different API than java.util.RegEx, but it let's you work with Automatons as first class things instead of operating just with regexes. Being able to compute intersections, unions, shortest match examples, from multiple automata etc.. can be really useful.

dsymonds• 11 years ago

Obligatory comment about how if you can't match it in linear time then it's not a regular expression.

peterashford• 11 years ago

So Perl and Python don't have regex then?

sanxiyn• 11 years ago

No, they are not regular.

See http://en.wikipedia.org/wiki/Regular_language for more.

userbinator• 11 years ago

In addition to writing RE2, Russ Cox has a set of very readable articles on implementing efficient regular expressions here: http://swtch.com/~rsc/regexp/

_benedict• 11 years ago

Something missing from all such libraries that I find a little disappointing, is the ability to compile multiple regular expressions into a single evaluation with a paired action on the result, so that the regexp becomes a general purpose map with string domain. At its most basic, each regexp could then be paired with a different replacement operation. Or an arbitrary more complex action.

With a DFA representation (linear time evaluation), this is pretty powerful. I've a regexp library that supports this, that I've been meaning to spruce up for wider release, but it's been several years and I've yet to do it.

https://code.google.com/p/jjoost/source/browse/#hg%2Fjjoost-...

RE2/J: Linear time regular expression matching in Java

Related Stories