lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Robert Muir (JIRA)" <>
Subject [jira] Commented: (LUCENE-1606) Automaton Query/Filter (scalable regex)
Date Mon, 23 Nov 2009 19:51:43 GMT


Robert Muir commented on LUCENE-1606:

I think i have a workaround for this enum that will not hurt performance as well.
There are two problems, one exists with the existing api, one will become a problem with the
flex API if we move to byte[] TermRef, which, from performance numbers, it seems we almost
certainly should.

* problem 1 is the fact that this enum depends upon 'sorted transitions' where each transition
is an interval of UTF-16 characters. 
To fix this, two things are required:
# splitting intervals that overlap between the BMP and surrogate range into separate intervals
# sorting intervals in codepoint order, which means ordering the surrogate range intervals
after any BMP intervals.

* problem 2 is the fact the enum works on UTF-16 characters again, and we can try to seek
in the enumerator to a place ending with a lead surrogate.
# In this case, we should just tack on U+DC00 (the lowest of trail surrogates), which is functionally
# for the "common prefix" we just remove any trail surrogates, although this common prefix
is currently not even used at all, so we should get rid of it, if the first state is not a
loop we are in smart mode anyway!

I'll fix these problems, by providing a new "codepoint-order" comparator for transitions behind
the scenes in automaton, along with a getSortedTransitionsCodepointOrder() or something similar
to make the whole thing work.

it might seem at a glance that using 'int' (UTF-32 intervals) instead is a better fix, but
this is not true, because it would cause a RunAutomaton to use 1MB memory where it currently
uses 64KB, only for these stupid rare cases.

> Automaton Query/Filter (scalable regex)
> ---------------------------------------
>                 Key: LUCENE-1606
>                 URL:
>             Project: Lucene - Java
>          Issue Type: New Feature
>          Components: Search
>            Reporter: Robert Muir
>            Assignee: Robert Muir
>            Priority: Minor
>             Fix For: 3.1
>         Attachments: automaton.patch, automatonMultiQuery.patch, automatonmultiqueryfuzzy.patch,
automatonMultiQuerySmart.patch, automatonWithWildCard.patch, automatonWithWildCard2.patch,, LUCENE-1606-flex.patch, LUCENE-1606-flex.patch, LUCENE-1606.patch, LUCENE-1606.patch,
LUCENE-1606.patch, LUCENE-1606.patch, LUCENE-1606.patch, LUCENE-1606.patch, LUCENE-1606.patch,
LUCENE-1606.patch, LUCENE-1606_nodep.patch
> Attached is a patch for an AutomatonQuery/Filter (name can change if its not suitable).
> Whereas the out-of-box contrib RegexQuery is nice, I have some very large indexes (100M+
unique tokens) where queries are quite slow, 2 minutes, etc. Additionally all of the existing
RegexQuery implementations in Lucene are really slow if there is no constant prefix. This
implementation does not depend upon constant prefix, and runs the same query in 640ms.
> Some use cases I envision:
>  1. lexicography/etc on large text corpora
>  2. looking for things such as urls where the prefix is not constant (http:// or ftp://)
> The Filter uses the BRICS package ( to convert regular
expressions into a DFA. Then, the filter "enumerates" terms in a special way, by using the
underlying state machine. Here is my short description from the comments:
>      The algorithm here is pretty basic. Enumerate terms but instead of a binary accept/reject
>      1. Look at the portion that is OK (did not enter a reject state in the DFA)
>      2. Generate the next possible String and seek to that.
> the Query simply wraps the filter with ConstantScoreQuery.
> I did not include the automaton.jar inside the patch but it can be downloaded from
and is BSD-licensed.

This message is automatically generated by JIRA.
You can reply to this email to add a comment to the issue online.

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message