Mailing-List: contact java-user-help@lucene.apache.org; run by ezmlm
Precedence: bulk
Reply-To: java-user@lucene.apache.org
Received-SPF: pass (athena.apache.org: local policy)
DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws;
  s=s1024; d=yahoo.com;
  h=X-YMail-OSG:Received:X-Mailer:References:Date:From:Subject:To:MIME-Version:Content-Type:Content-Transfer-Encoding:Message-ID;
  b=I/olRp7yxag0NBFvHrJZeGn7a+xpeoP8eDWmrDwQoFvKPUXVhPm9GsD1LvIF/OL8U/c8f1x20urQLY1DMAHWY2Wq+qlGc1/h5HokwJcjGaglLIVMwLZmOkYMOogYgd/Pu9p7f/i0tIz33YXXl286aZttuWnkqLqJtgOBZdQrbL4=;
References: <20505283.post@talk.nabble.com> <491DDF01.9080407@gmail.com>
 <535223.79139.qm@web50711.mail.re2.yahoo.com>
 <CAB3A74869088D4D97E016C9BE77F6BF013446B2F3@ex01.corp.attivio.com>
Date: Fri, 14 Nov 2008 16:53:35 -0800 (PST)
From: Aaron Schon <aaron_schon@yahoo.com>
Subject: Re: Extremely Large Strings Comparison (slightly off-topic)
To: java-user@lucene.apache.org
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: quoted-printable
Message-ID: <943297.20398.qm@web50712.mail.re2.yahoo.com>

Thanks for responding Jonathan. I will look into k-grams approach. =0A=0ATh=
e objects could differ by small local changes. To provide some business con=
text, the application requires indexing email messages and attachments. If =
the attachments differ by some threshold (users making edits/reviews), the =
attachment needs to be flagged and major/minor versioned.=0A=0AThanks=0AAS=
=0A=0A=0A----- Original Message ----=0AFrom: Jonathan Young <JYoung@attivio=
.com>=0ATo: Aaron Schon <Aaron_Schon@yahoo.com>=0ASent: Friday, November 14=
, 2008 5:52:17 PM=0ASubject: RE: Extremely Large Strings Comparison (slight=
ly off-topic)=0A=0AAaron - Although a na=EFve implementation of a Levenshte=
in distance metric takes O(n*m) time, if you are willing to bound the maxim=
um distance by k << n,m (e.g. if you aren't interested in distances greater=
 than k) then the distance calculation can take O(k*min(n,m)).=0A=0AAnother=
 approach would be to use shingles or k-grams from the original document.  =
I believe Lucene has some support for that.=0A=0AIt depends a lot on the wa=
ys in which you expect the two strings to differ.  The fact that it is Base=
64-encoded MIME content doesn't matter - are they actually objects which ar=
e going to have small local changes, or are there likely to be changes whic=
h cascade (e.g. if the data is compressed).=0A=0AI hope this helps,=0A=0A--=
- Jonathan=0A=0A-----Original Message-----=0AFrom: Aaron Schon [mailto:aaro=
n_schon@yahoo.com]=0ASent: Friday, November 14, 2008 5:00 PM=0ATo: java-use=
r@lucene.apache.org=0ASubject: Extremely Large Strings Comparison (slightly=
 off-topic)=0A=0Ahi I need to compare two Base64 representation strings of =
some MIME content that I am storing within a Lucene index. I need to effici=
ently compare them to find the closest match to a query Base64 string , pos=
t Lucene query.=0A=0AI am not sure of the best way to approach this, could =
I compare the hashes and compute their similarity? Levenshtein distance see=
ms hard because of the size of ths strings and seems inefficient? Is there =
any other method you could suggest?=0A=0An.b: The idea is to not to determi=
ne exact match or not, it is to compute a similarity metric. for example=0A=
=0AJohn & Johnson (closer)=0Avs,=0AJohn & Jimmy (farther)=0A=0Atia,=0AAaron=
=0A=0A=0A=0A=0A------------------------------------------------------------=
---------=0ATo unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org=
=0AFor additional commands, e-mail: java-user-help@lucene.apache.org=0A=0A=
=0A      

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