From: Ken Bloom <kbloom@...>
Date: 2008-05-01T23:10:12+09:00
Subject: Re: Levenshtein_distance and recreate the string

On Tue, 29 Apr 2008 20:56:30 -0500, Phillip Gawlowski wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> David A. Black wrote:
> |
> | But isn't it the same for RUBY -> RUBE and RUBA -> RUBE ? In which |
> case, if you had RUBE and the L. distance, you could not recreate |
> RUBY; you'd have a whole set of strings that were exactly that |
> distance from RUBE.
> 
> Good point. I don't know if the L. distance is unique for each
> possibility or not.

It's not unique. Any single deletion has edit distance 1, any single 
insertion has edit distance 1.

Thus, the strings that have edit distance 1 from "RUBY" include (but are 
not limited to):

#delete a letter
RUB
RUY
RBY
UBY
#add the letter A
ARUBY
RAUBY
RUABY
RUBAY
RUBYA
#add the letter B
BRUBY
RBUBY
RUBBY
RUBYB
...

That's not to say there aren't reasons for recreating all of these. For 
Mengmeng Du[1], recreating all of these and checking for their existance 
in a Bloom filter was orders of magnitude faster than computing the edit 
distance between a query and every entry in a 200,000 entry list of last 
names. (Just a paper I happen to be reading this week.)

--Ken

[1] Du, Mengmeng (2005) "Approximate Name Matching" Master's Degree 
Project, Royal Institute of Technology, Stockholm, Sweden

-- 
Ken (Chanoch) Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/