From: "David A. Black" <dblack@...>
Date: 2008-04-30T10:39:27+09:00
Subject: Re: Levenshtein_distance and recreate the string

Hi --

On Wed, 30 Apr 2008, Phillip Gawlowski wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Ams Lo wrote:
> | Hi -
> |
> | A general computer science question-
> |
> | Given the levenshtein distance between two strings and one of the
> | strings S1, is it possible to re-create the second string.
> |
> | For example -
> |
> | S1 = "RUBY"
> |
> | S2 = "BRUY"
> |
> | lev_distance = 3
> |
> | Given 3 and S2, is it possible to recreate S1??
>
> I see no reason why it shouldn't.
>
> Looking at the Wikiality for the algorithm[0], the algorithm works,
> essentially, on a matrix for the strings. Juxtaposing the axes should
> solve that, in a naive, uneducated way, anyway.
>
> After all, the Levenshtein distance is the same for RUBY -> BRUBY and
> BRUBY -> RUBY.

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.


David

-- 
Rails training from David A. Black and Ruby Power and Light:
   INTRO TO RAILS         June 9-12            Berlin
   ADVANCING WITH RAILS   June 16-19           Berlin
   INTRO TO RAILS         June 24-27           London (Skills Matter)
See http://www.rubypal.com for details and updates!