Q

----- Original Message -----
From: java-dev-return-32502-michael.j.goddard=saic....@lucene.apache.org 
<java-dev-return-32502-michael.j.goddard=saic....@lucene.apache.org>
To: java-dev@lucene.apache.org <java-dev@lucene.apache.org>
Sent: Tue Apr 21 18:02:47 2009
Subject: [jira] Commented: (LUCENE-1606) Automaton Query/Filter (scalable regex)


    [ 
https://issues.apache.org/jira/browse/LUCENE-1606?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12701285#action_12701285
 ] 

Robert Muir commented on LUCENE-1606:
-------------------------------------

eks:

the AutomatonTermEnumerator in this patch does walk the term dictionary 
according to the transitions present in the DFA. Thats what this JIRA issue is 
all about to me, not iterating all the terms! So you do not need the complete 
dictionary as a DFA.

for example: a regexp query of (a|b)cdefg with this patch seeks to 'acdefg', 
then 'bcdefg', as opposed to the current regex support which exhaustively 
enumerates all terms.

slightly more complex example, query of (a|b)cd*efg first seeks to 'acd' 
(because of kleen star operator). suppose it then encounters term 'acda', it 
will next seek to 'acdd', etc. if it encounters 'acdf', then next it seeks to 
'bcd'.

this patch implements regex, wildcard, and fuzzy with n=1 in terms of this 
enumeration. what it doesnt do is fuzzy with arbitrary n!. 

I used the simplistic quadratic method to compute a DFA for fuzzy with n=1 for 
the FuzzyAutomatonQuery present in this patch, the paper has a more complicate 
but linear method to compute the DFA.


> Automaton Query/Filter (scalable regex)
> ---------------------------------------
>
>                 Key: LUCENE-1606
>                 URL: https://issues.apache.org/jira/browse/LUCENE-1606
>             Project: Lucene - Java
>          Issue Type: New Feature
>          Components: contrib/*
>            Reporter: Robert Muir
>            Priority: Minor
>             Fix For: 2.9
>
>         Attachments: automaton.patch, automatonMultiQuery.patch, 
> automatonmultiqueryfuzzy.patch, automatonMultiQuerySmart.patch, 
> automatonWithWildCard.patch, automatonWithWildCard2.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 (http://www.brics.dk/automaton/) 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 do:
>       
>      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 http://www.brics.dk/automaton/ 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: java-dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: java-dev-h...@lucene.apache.org

Reply via email to