Mailing-List: contact java-user-help@lucene.apache.org; run by ezmlm
Precedence: bulk
Reply-To: java-user@lucene.apache.org
Received-SPF: pass (nike.apache.org: local policy)
Content-Type: text/plain; charset=iso-8859-1
Mime-Version: 1.0 (Apple Message framework v1251.1)
Subject: Re: Building FST-like automaton queries
From: Alan Woodward <alan.woodward@romseysoftware.co.uk>
In-Reply-To: 
 <CAL8PwkZJRBFY+6bCxa56VtCKvmAE2_u7VdKZrf4SK8o25OATtA@mail.gmail.com>
Date: Tue, 28 Feb 2012 13:42:42 +0000
Content-Transfer-Encoding: quoted-printable
Message-Id: <F3406419-AECF-4365-849A-99ABADEF39B6@romseysoftware.co.uk>
References: <FCE483F7-8BB1-4344-9CD1-3CE1EF129C7A@romseysoftware.co.uk>
 <CAL8PwkZJRBFY+6bCxa56VtCKvmAE2_u7VdKZrf4SK8o25OATtA@mail.gmail.com>
To: java-user@lucene.apache.org


On 28 Feb 2012, at 13:31, Michael McCandless wrote:

> Neat :)  It's like a FuzzyQuery w/ a custom (binary?) cost matrix for
> the insert/delete/transposition changes...
>=20
> Is the number of edits smallish?  Ie you're not concerned about
> combinatoric explosion of step 1?

We're only allowing expansions within an edit distance of 1, which =
should keep the numbers of terms down.=20

>=20
> For steps 2 and 3 you shouldn't use FST at all.  Instead, for 2) use
> BasicAutomata.makeString(String) on each of your expanded terms, then
> BasicOperations.union on all of those automata to make a single
> automaton accepting all your expanded terms, then likely call
> .determinize() on the resulting automaton (maybe also .minimize() but
> I think that may not help).  Then pass that automaton to AQ.

Excellent, thanks for your help.  I'll give that a go.

>=20
> We don't yet have a way to drive a query from an FST, but that would
> be an interesting addition.  EG you could then support weights as
> well, to decide how the terms are scored (if certain OCR errors are
> more likely than others).
>=20
> Mike McCandless
>=20
> http://blog.mikemccandless.com
>=20
> On Tue, Feb 28, 2012 at 7:33 AM, Alan Woodward
> <alan.woodward@romseysoftware.co.uk> wrote:
>> Hello,
>>=20
>> I'm trying to create a Lucene Query that will take a term and expand =
it to include common OCR errors (for example, 'cl' is often misread as =
'd', so a search for 'clog' should also hit 'dog').  My plan is to do =
this by generating all the possible variants of a term, using an =
existing list of errors, and then somehow mapping this into an =
AutomatonQuery.  I've been looking around the o.a.l.util.automaton and =
o.a.l.util.fst packages on trunk, and I *think* that this is possible, =
but I'm so far failing to work out how to put the various bits together.
>>=20
>> I'm thinking it should work like this:
>> 1) expand query term to sorted list of possible matches
>> 2) create an FST over those matches
>> 3) plug this FST into an AutomatonQuery subclass.
>>=20
>> 1) is easy.  It's 2) and 3) I'm having trouble with.
>>=20
>> All help gratefully received!
>>=20
>> Thanks,
>>=20
>> Alan Woodward
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
>> For additional commands, e-mail: java-user-help@lucene.apache.org
>>=20
>=20
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-user-help@lucene.apache.org
>=20


---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org