From: Eleanor McHugh <eleanor@...>
Date: 2008-04-30T20:01:47+09:00
Subject: Re: Levenshtein_distance and recreate the string

On 30 Apr 2008, at 02:13, 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??
>
> Many thanks,

Simple answer: no.

Each step that exists between S1 and S2 represents the choosing of one  
change out of a set of changes the same size as your token space (so  
for uppercase letters only that would be 26) and therefore to reverse  
that change you would generate that many valid words. Selecting which  
of those is the S1 word is impossible without additional constraints.

For the S1 -> S3 -> S1 case the actual search space (still assuming  
capital letters only) is therefore 26 ** 3, or 17576 equally plausible  
S1 candidates. Of course that assumes a naive search strategy, whereas  
it's quite possible the space could be restricted based upon known  
dictionary characteristics: certain tokens may be impossible at  
certain locations; genetic algorithms may grow 'good' solutions faster  
than exhaustive search; etc.

Ellie

Eleanor McHugh
Games With Brains
http://slides.games-with-brains.net
----
raise ArgumentError unless @reality.responds_to? :reason