From: Rick DeNatale Date: 2008-04-30T21:47:38+09:00 Subject: Re: Levenshtein_distance and recreate the string On Wed, Apr 30, 2008 at 8:25 AM, Vidar Hokstad wrote: > 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. Another thing to consider is why it's called a distance rather than, say, a difference. Consider this analogy. Given that the highway distance between Raleigh, NC, and Washington, DC is 250 miles. Given Washington, DC, and 250 miles, can I uniquely identify Raleigh, NC. No since the highway distance between Washington, DC and New York, NY (as well as many other places) is also 250 miles. -- Rick DeNatale My blog on Ruby http://talklikeaduck.denhaven2.com/