From: Vidar Hokstad <vidar.hokstad@...>
Date: 2008-04-30T21:25:03+09:00
Subject: Re: Levenshtein_distance and recreate the string

On Apr 30, 2:13 am, Ams Lo <rgow...@gmail.com> wrote:
>
> S1 = "RUBY"
>
> S2 = "BRUY"
>
> lev_distance = 3
>
> Given 3 and S2, is it possible to recreate S1??

Several people have given great answers as to why this isn't possible,
but let me give you another reason why, just
because I feel like it, and it's a useful thing to keep in mind.

Whenever you get a problem like this, a good way of approaching it if
you don't understand the algorithm is to think:

- If it _was_ possible, would that allow you to make impossibly
efficient compression algorithms?

In this case, the answer is that yes it would: You could pick a fixed
S2, for example an empty string, calculate the
Levensthein distance from S1 to the fixed S2. The distance would be
proportional to the length of S1. In fact, if
you choose S2 to be the empty string, then the distance would be equal
to the length of S1 (it'd take one deletion
per position in S1 to end up with an empty string)

In other words, you'd "compress" your test string "BRUY" down to the
number 4, but more importantly that "compression"
method would compress any string of any length, which is obviously
impossible (the reason this is impossible is that
if it was possible you could apply it to it's own output over and over
until you had compressed an arbitrary input
down to a bit).

In this case it's not a very hard problem to solve, but I find that
for a large number of questions about data
transformations, it's helpful to think about it in terms of
compression because the answers often become blatantly
obvious once you restate them that way.

Vidar