Return-Path: Delivered-To: apmail-lucene-java-dev-archive@www.apache.org Received: (qmail 4373 invoked from network); 19 Apr 2009 21:37:17 -0000 Received: from hermes.apache.org (HELO mail.apache.org) (140.211.11.3) by minotaur.apache.org with SMTP; 19 Apr 2009 21:37:17 -0000 Received: (qmail 26266 invoked by uid 500); 19 Apr 2009 21:37:15 -0000 Delivered-To: apmail-lucene-java-dev-archive@lucene.apache.org Received: (qmail 26194 invoked by uid 500); 19 Apr 2009 21:37:15 -0000 Mailing-List: contact java-dev-help@lucene.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: java-dev@lucene.apache.org Delivered-To: mailing list java-dev@lucene.apache.org Received: (qmail 26186 invoked by uid 99); 19 Apr 2009 21:37:15 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Sun, 19 Apr 2009 21:37:15 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=10.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.140] (HELO brutus.apache.org) (140.211.11.140) by apache.org (qpsmtpd/0.29) with ESMTP; Sun, 19 Apr 2009 21:37:08 +0000 Received: from brutus (localhost [127.0.0.1]) by brutus.apache.org (Postfix) with ESMTP id 73798234C004 for ; Sun, 19 Apr 2009 14:36:47 -0700 (PDT) Message-ID: <683682711.1240177007453.JavaMail.jira@brutus> Date: Sun, 19 Apr 2009 14:36:47 -0700 (PDT) From: "Robert Muir (JIRA)" To: java-dev@lucene.apache.org Subject: [jira] Updated: (LUCENE-1606) Automaton Query/Filter (scalable regex) In-Reply-To: <1392250321.1239871695357.JavaMail.jira@brutus> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit X-JIRA-FingerPrint: 30527f35849b9dde25b450d4833f0394 X-Virus-Checked: Checked by ClamAV on apache.org [ https://issues.apache.org/jira/browse/LUCENE-1606?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Robert Muir updated LUCENE-1606: -------------------------------- Attachment: automatonmultiqueryfuzzy.patch this includes an alternative for another slow linear query, fuzzy query. automatonfuzzyquery creates a DFA that accepts all strings within an edit distance of 1. on my 100M term index this works pretty well: fuzzy: 251,219 ms automatonfuzzy: 172 ms while its true its limited to edit distance of one, on the other hand it supports transposition and is fast. > 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-unsubscribe@lucene.apache.org For additional commands, e-mail: java-dev-help@lucene.apache.org