5 ms·

RE2/J: Linear time regular expression matching in Java

42 points by fmela 12y ago

mumrah 12y 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 https://gist.github.com/mumrah/6104234 Javadoc: https://lucene.apache.org/core/4_0_0/core/org/apache/lucene/util/automaton/RegExp.html https://lucene.apache.org/core/4_0_0/core/org/apache/lucene/... Source: https://github.com/apache/lucene-solr/blob/trunk/lucene/core/src/java/org/apache/lucene/util/automaton/RegExp.java https://github.com/apache/lucene-solr/blob/trunk/lucene/core...
- hcayless 12y ago
  Lucene's regexp querying is based on http://www.brics.dk/automaton/ http://www.brics.dk/automaton/ It's fast, but limited too: no word boundary matching for example.
- chrisconroy 12y ago
  Related: the dk.brics.automaton library (http://www.brics.dk/automaton/ 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 12y ago
Obligatory comment about how if you can't match it in linear time then it's not a regular expression.
- peterashford 12y ago
  So Perl and Python don't have regex then?
  - sanxiyn 12y ago
    No, they are not regular. See http://en.wikipedia.org/wiki/Regular_language http://en.wikipedia.org/wiki/Regular_language for more.
userbinator 12y 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/ http://swtch.com/~rsc/regexp/
_benedict 12y 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-text%2Fsrc%2Forg%2Fjjoost%2Ftext%2Fpattern https://code.google.com/p/jjoost/source/browse/#hg%2Fjjoost-...

42 points by fmela 12y 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 https://gist.github.com/mumrah/6104234 Javadoc: https://lucene.apache.org/core/4_0_0/core/org/apache/lucene/util/automaton/RegExp.html https://lucene.apache.org/core/4_0_0/core/org/apache/lucene/... Source: https://github.com/apache/lucene-solr/blob/trunk/lucene/core/src/java/org/apache/lucene/util/automaton/RegExp.java https://github.com/apache/lucene-solr/blob/trunk/lucene/core...

hcayless 12y ago
Lucene's regexp querying is based on http://www.brics.dk/automaton/ http://www.brics.dk/automaton/ It's fast, but limited too: no word boundary matching for example.
chrisconroy 12y ago
Related: the dk.brics.automaton library (http://www.brics.dk/automaton/ 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 12y ago

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

peterashford 12y ago
So Perl and Python don't have regex then?
- sanxiyn 12y ago
  No, they are not regular. See http://en.wikipedia.org/wiki/Regular_language http://en.wikipedia.org/wiki/Regular_language for more.

userbinator 12y 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/ http://swtch.com/~rsc/regexp/

_benedict 12y 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-text%2Fsrc%2Forg%2Fjjoost%2Ftext%2Fpattern https://code.google.com/p/jjoost/source/browse/#hg%2Fjjoost-...