lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Mark Miller (JIRA)" <>
Subject [jira] Commented: (LUCENE-1606) Automaton Query/Filter (scalable regex)
Date Fri, 20 Nov 2009 16:28:39 GMT


Mark Miller commented on LUCENE-1606:

bq. I assume we should nuke the old WildcardQuery, rename AutomatonWildcardQuery to WildcardQuery?

Yes - I think so - but how to handle the fact that you fall back to it? We might either rename
it or incorporate it into the new WildcardQuery?

bq. but then what should AutomatonRegexQuery be called, we already have RegexQuery?

Shouldn't this one eventually make the old obsolete? I say we name it RegexQuery.

bq. Thoughts on the automaton src code? Should I reformat to our style... (I did not do this).

Yup - I think we should reformat and drop the author tags. We can mention that type of info
in the NOTICE file.

bq. should we rename the pkg?

I think so - perhaps util.brics?  No need for dk I don't think.

bq. sorry the patch is monster, if it makes it any easier i could split the automaton library
itself away from the lucene integration (queries, etc)?

One large patch is fine with me - my IDE will make short work of groking it :)

> 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_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