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 Fri, 20 Nov 2009 22:51:39 GMT


Robert Muir commented on LUCENE-1606:

bq. We should simply add a test for this method and everything else is the WildCardEnum. The
good thing of subclassing it is, that one has a more performat class if it uses common prefixes
and so on than the version we currently have. The wildcardEquals method must stay, but it
is not used, so explicitely mark it as "dead code".

if we do this, there are lots of cases where it will perform better, yes (virtually anything
involving ? operator)
but if we do this, there are also some cases where it won't perform quite as well, really
bad wildcards where it is better to just do linear scan than skip around many many times.

This is why i have detection for these cases, in the getEnum() instead I return "DumbTermEnum"
aka LinearTermEnum in AutomatonQuery.
if you think this is no problem, we can subclass it anyway. excerpt below:

     * If the DFA has a leading kleene star, or something similar, it will
     * need to run against the entire term dictionary. In this case its much
     * better to do just that than to use fancy enumeration.
     * this heuristic looks for an initial loop, with a range of at least 1/3
     * of the unicode BMP.
    State state = automaton.getInitialState();
    for (Transition transition : state.getTransitions())
      if (transition.getDest() == state
          && (transition.getMax() - transition.getMin()) > (Character.MAX_VALUE
/ 3))
        return new LinearTermEnum(reader);

    return new AutomatonTermEnum(automaton, term, reader);

> Automaton Query/Filter (scalable regex)
> ---------------------------------------
>                 Key: LUCENE-1606
>                 URL:
>             Project: Lucene - Java
>          Issue Type: New Feature
>          Components: contrib/*
>            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.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