On Apr 30, 2:13 am, Ams Lo [email protected] 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