Mailing-List: contact dev-help@lucene.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@lucene.apache.org
Received-SPF: neutral (nike.apache.org: local policy)
DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws;
  s=s1024; d=yahoo.co.uk;
  h=X-YMail-OSG:Received:X-Mailer:Message-ID:Date:From:Subject:To:MIME-Version:Content-Type;
  b=IH24UUktaga3UwqL6MaBR8mUdDf5qrLeqNABrp2+dPYQtBV87Vz44cPDl0ABbn7OYCig9I1zxYnzi2VUiGXJvbBeTIyYed4IuHT2eSA7xqY2cRPuo/2dUIvsZ1zQmZYWm3+wLv0xAm4ZhTyJFrEfRmu0tGepizdB/L4asDNJr40=;
Message-ID: <1312981390.85930.YahooMailRC@web27107.mail.ukl.yahoo.com>
Date: Wed, 10 Aug 2011 14:03:10 +0100 (BST)
From: eks dev <eksdev@yahoo.co.uk>
Subject: Re: LevenshteinAutomata challenge
To: dev@lucene.apache.org
MIME-Version: 1.0
Content-Type: multipart/alternative; boundary="0-132899840-1312981390=:85930"

--0-132899840-1312981390=:85930
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable

Hi Robert, =0Aindeed, transpositions can be embedded into Lev, Automaton. I=
 share my opinion =0Awith you, even stronger, I think transpositions are fu=
ndamental for spell-check =0Atype of apps. =0A=0A=0ABut, even if implemente=
d, it would not change the point from my example, only =0Aslightly. ("To su=
pport efficiently..." )=0A=0A<Lev("ABXYZ", 1)> // assuming transposition  c=
ounts as one, still has much more =0Ato do ( "bigger search space", or what=
ever is this called) =0A=0Athen this composition=0A<RegEx("(AB)|(BA)")><Lev=
("XYZ", 1)>=0A=0A=0ALev("CARIN", 1) =0Avs =0A<RegEx("[CK]")><Lev("ARIN", 1)=
>=0A=0AAnd so on and so on...=0A=0ASo yes, transpositions would be great, b=
ut they are orthogonal to "regular =0Acomposition of automata"  (Lev. and r=
egex and however one constructs them) . =0A=0A=0AThis composition of automa=
ta enables us to restrict space significantly, and add =0Aheuristics that h=
elp improve match quality (precision).=0AIn my experience, plain edit dista=
nce without heuristics is rarely useful, =0Aespecially on shorter than, say=
 7 chars, It generates a lot of candidates and =0Aone needs re-scoring phas=
e .... which is in turn slow, if too many candidates. =0ASo we come back to=
 this, "automata composition" ,  with it, you could push some =0Aof these "=
heuristics" back to candidate fetching phase to increase precision of =0Ath=
is "candidate fetching phase with Edit distance" ... =0A=0A=0ATheoretical a=
lternative, less flexible/clean, would be to somehow add parameters =0Ato L=
ev. automata builder, like "I want to have max distance =3D 1 from 3rd =0Ac=
haracter on, but only transposition without deletes/inserts on first two =
=0Acharacters".... looks ugly =0A=0A=0ABut Mike and Dawid said this is alre=
ady there, works... only some API sugar is =0Aneeded! =0A=0ALovely :)=0A=0A=
=0ARe "... though if you don't want to implement it, you could let him know=
 are =0Ainterested..."=0A=0AI would really live to, but to find that much t=
ime to understand this hairy code =0Ais at the moment impossible. =0A=0A=0A=
Thanks to all, it turned out that your answer to my challenge was simple,  =
=0A"done, we have it already!" ;)=0A=0A=0A=0A> in order to support transpos=
ition in the first two characters like in=0A> my example, you would need Le=
v. Automaton that has maxDistance 2,=0A=0AActually this isn't true: we can =
implement the variant where=0Atranspositions are a basic edit operation:=0A=
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=3D10.1.1.16.652 (Chapter 7=
)=0A=0AI think this transpositions variant would really be more ideal for=
=0Aspellchecking.=0AI think it would actually be best/easiest if this was i=
mplemented in=0Apython in moman: https://bitbucket.org/jpbarrette/moman/=0A=
=0AJean-Philippe Barrette-LaPierre has told me before he was interested=0Ai=
n implementing it, but I think his time is limited, though if you=0Adon't w=
ant to implement it, you could let him know are interested.
--0-132899840-1312981390=:85930
Content-Type: text/html; charset=utf-8
Content-Transfer-Encoding: quoted-printable

<html><head><style type=3D"text/css"><!-- DIV {margin:0px;} --></style></he=
ad><body><div style=3D"font-family:arial,helvetica,sans-serif;font-size:10p=
t;color:#00007f;"><div>Hi Robert, <br>indeed, transpositions can be embedde=
d into Lev, Automaton. I share my opinion with you, even stronger, I think =
transpositions are fundamental for spell-check type of apps. <br><br>But, e=
ven if implemented, it would not change the point from my example, only sli=
ghtly. ("To support efficiently..." )<br><br>&lt;Lev("ABXYZ", 1)&gt; // ass=
uming transposition&nbsp; counts as one, still has much more to do ( "bigge=
r search space", or whatever is this called) <br>then this composition<br>&=
lt;RegEx("(AB)|(BA)")&gt;&lt;Lev("XYZ", 1)&gt;<br><br><br>Lev("CARIN", 1) <=
br>vs <br>&lt;RegEx("[CK]")&gt;&lt;Lev("ARIN", 1)&gt;<br><br>And so on and =
so on...<br><br>So yes, transpositions would be great, but they are orthogo=
nal to "regular composition of automata"&nbsp; (Lev. and regex and
 however one constructs them) . <br><br>This composition of automata enable=
s us to restrict space significantly, and add heuristics that help improve =
match quality (precision).<br>In my experience, plain edit distance without=
 heuristics is rarely useful, especially on shorter than, say 7 chars, It g=
enerates a lot of candidates and one needs re-scoring phase .... which is i=
n turn slow, if too many candidates. So we come back to this, "automata com=
position" ,&nbsp; with it, you could push some of these "heuristics" back t=
o candidate fetching phase to increase precision of this "candidate fetchin=
g phase with Edit distance" ... <br><br>Theoretical alternative, less flexi=
ble/clean, would be to somehow add parameters to Lev. automata builder, lik=
e "I want to have max distance =3D 1 from 3rd character on, but only transp=
osition without deletes/inserts on first two characters".... looks ugly <br=
><br>But Mike and Dawid said this is already there, works... only some
 API sugar is needed! <br>Lovely :)<br><br><br>Re "... though if you don't =
want to implement it, you could let him know are interested..."<br><br>I wo=
uld really live to, but to find that much time to understand this hairy cod=
e is at the moment impossible. <br><br>Thanks to all, it turned out that yo=
ur answer to my challenge was simple,&nbsp; "done, we have it already!" ;)<=
br><br><br><br>&gt; in order to support transposition in the first two char=
acters like in<br>=0A&gt; my example, you would need Lev. Automaton that ha=
s maxDistance 2,<br>=0A<br>=0AActually this isn't true: we can implement th=
e variant where<br>=0Atranspositions are a basic edit operation:<br>=0A<a h=
ref=3D"http://citeseerx.ist.psu.edu/viewdoc/summary?doi=3D10.1.1.16.652" ta=
rget=3D"_blank">http://citeseerx.ist.psu.edu/<wbr>viewdoc/summary?doi=3D10.=
1.1.16.<wbr>652</a> (Chapter 7)<br>=0A<br>=0AI think this transpositions va=
riant would really be more ideal for<br>=0Aspellchecking.<br>=0AI think it =
would actually be best/easiest if this was implemented in<br>=0Apython in m=
oman: <a href=3D"https://bitbucket.org/jpbarrette/moman/" target=3D"_blank"=
>https://bitbucket.org/<wbr>jpbarrette/moman/</a><br>=0A<br>=0AJean-Philipp=
e Barrette-LaPierre has told me before he was interested<br>=0Ain implement=
ing it, but I think his time is limited, though if you<br>=0Adon't want to =
implement it, you could let him know are interested.</div>=0A=0A=0A=0A</div=
></body></html>
--0-132899840-1312981390=:85930--