# Edit Distance at Wikipedia **URL:** \ **Category:** Ruby\ **Created:** [October 16, 2006, 12:17pm UTC](https://www.ruby-forum.com/t/edit-distance-at-wikipedia/72316 "2006-10-16T12:17:47Z")\ **Posts on this page:** 8\ **Page:** 1
**Author:** ![pool007](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/3bc359/32.png) [@pool007](https://www.ruby-forum.com/u/pool007)\ **Post date:** [October 16, 2006, 12:17pm UTC](https://www.ruby-forum.com/t/edit-distance-at-wikipedia/72316/1 "2006-10-16T12:17:47Z")
Hi list. I read an article posted at Wikipedia about Levenshtein distance (aka edit distance). The location of the document is > **[Levenshtein distance](https://en.wikipedia.org/wiki/Levenshtein_distance)** > > In information theory, linguistics, and computer science, the Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other. It is named after the Soviet mathematician Vladimir Levenshtein, who considered this distance in 1965. > Levenshtein distance may also be referred to as edit di... In the document, a sample Ruby code goes like the following: class String def levenshtein(comparator) a, b = self.unpack(‘U\*’), comparator.unpack(‘U\*’) n, m = a.length, b.length a, b, n, m = b, a, m, n if n \> m current = [\*0…n] 1.upto(m) do |i| previous, current = current, [i]+[0]\*n 1.upto(n) do |j| add, delete = previous[j]+1, current[j-1]+1 change = previous[j-1] change += 1 if a[j-1] != b[i-1] current[j] = [add, delete, change].min end end current[n] end end In the code, there’s a parameter called comparator which seems to be used to decode given parameter. But, I can’t understand what exactly the comparator is doing. Does anybody know the detail? Sincerely, Minkoo S. ---
**Author:** ![pool007](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/3bc359/32.png) [@pool007](https://www.ruby-forum.com/u/pool007)\ **Post date:** [October 16, 2006, 12:25pm UTC](https://www.ruby-forum.com/t/edit-distance-at-wikipedia/72316/2 "2006-10-16T12:25:48Z")
On Mon, Oct 16, 2006 at 07:15:52PM +0900, Minkoo wrote: > def levenshtein(comparator) > current[j] = [add, delete, change].min > Does anybody know the detail? > It’s simply the string you’re comparing against; unpack(‘U\*’) just turns > the > UTF-8 characters into unsigned integers: ``` class String def levenshtein(comparator) a, b = self.unpack('U*'), comparator.unpack('U*') b # => [102, 111, 111, ``` 98, 97, 114] n, m = a.length, b.length a, b, n, m = b, a, m, n if n \> m current = [\*0…n] 1.upto(m) do |i| previous, current = current, [i]+[0]\*n 1.upto(n) do |j| add, delete = previous[j]+1, current[j-1]+1 change = previous[j-1] change += 1 if a[j-1] != b[i-1] current[j] = [add, delete, change].min end end current[n] end end ``` "foo".levenshtein("foobar") # => 3 ``` ---
**Author:** ![pool007](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/3bc359/32.png) [@pool007](https://www.ruby-forum.com/u/pool007)\ **Post date:** [October 16, 2006, 12:42pm UTC](https://www.ruby-forum.com/t/edit-distance-at-wikipedia/72316/3 "2006-10-16T12:42:12Z")
Minkoo wrote: > def levenshtein(comparator) > […] > In the code, there’s a parameter called comparator which seems to be > used to > decode given parameter. But, I can’t understand what exactly the comparator > is doing. I didn’t examine the code, but I’d guess… you want the L. distance between two strings. One is self, and the other is the parameter named “comparator”. Good luck. ---
**Author:** ![pool007](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/3bc359/32.png) [@pool007](https://www.ruby-forum.com/u/pool007)\ **Post date:** [October 16, 2006, 3:45pm UTC](https://www.ruby-forum.com/t/edit-distance-at-wikipedia/72316/4 "2006-10-16T15:45:38Z")
On Mon, 16 Oct 2006 19:40:07 +0900, Carlos wrote: > > > > “comparator”. > I have now renamed the variable to “other” for clarity. ---
**Author:** ![pool007](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/3bc359/32.png) [@pool007](https://www.ruby-forum.com/u/pool007)\ **Post date:** [October 16, 2006, 3:12pm UTC](https://www.ruby-forum.com/t/edit-distance-at-wikipedia/72316/5 "2006-10-16T15:12:36Z")
On 10/16/06, Mauricio F. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > > In the document, a sample Ruby code goes like the following: > > add, delete = previous[j]+1, current[j-1]+1 > > used to > > class String > > add, delete = previous[j]+1, current[j-1]+1 > > – > Mauricio F. - [http://eigenclass.org](http://eigenclass.org) - singular Ruby I’m afraid that I’m not used to character encodings. Does Ruby use UTF-8 by default? In other words, suppose that I’ve launched irb and fired “foo”.levenshtein(“foobar”). In that case, is the string “foo” encoded as utf-8? Do I always have to unpack the string like the code shown above? Sincerely, Minkoo S. ---
**Author:** ![pool007](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/3bc359/32.png) [@pool007](https://www.ruby-forum.com/u/pool007)\ **Post date:** [October 16, 2006, 11:05pm UTC](https://www.ruby-forum.com/t/edit-distance-at-wikipedia/72316/6 "2006-10-16T23:05:26Z")
On Mon, Oct 16, 2006 at 10:11:51PM +0900, Minkoo wrote: > On 10/16/06, Mauricio F. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > > > It’s simply the string you’re comparing against; unpack(‘U\*’) just turns > > the UTF-8 characters into unsigned integers: > > > > class String > > def levenshtein(comparator) > > a, b = self.unpack(‘U\*’), comparator.unpack(‘U\*’) > > b # =\> [102, 111, > > 111, 98, 97, 114] > > […] > > > > “foo”.levenshtein(“foobar”) # =\> 3 > > I’m afraid that I’m not used to character encodings. Does Ruby use UTF-8 by > default? Ruby’s Strings as of 1.8 are just a sequence of bytes. If a String happens to hold a UTF-8 sequence, some operations will work properly when you set $KCODE=“u”, e.g. s = “\303\241” # “á” == acute s.scan(/\w/) # =\> [] $KCODE=“u” s.scan(/\w/) # =\> [“á”] Some other methods are covered by jcode.rb. > In other words, suppose that I’ve launched irb and fired > “foo”.levenshtein(“foobar”). > In that case, is the string “foo” encoded as utf-8? This depends on your locale; Ruby’s Strings do not know about encodings in 1.8 (they will very soon in 1.9 according to matz’ latest messages in ruby-core; search the ruby-talk archives for extensive discussions of the upcoming M17N). > Do I always have to unpack the string like the code shown above? In this particular case, it depends on two things: - the encoding you’re using - whether the Levenshtein should be relative to characters or bytes In general, it’s up to you to keep track of the encodings and handle Strings appropriately. ---
**Author:** ![pool007](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/3bc359/32.png) [@pool007](https://www.ruby-forum.com/u/pool007)\ **Post date:** [October 17, 2006, 8:45am UTC](https://www.ruby-forum.com/t/edit-distance-at-wikipedia/72316/7 "2006-10-17T08:45:24Z")
On 10/16/06, Minkoo [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > I’m afraid that I’m not used to character encodings. Does Ruby use UTF-8 by > default? As of Ruby 1.8, it doesn’t, but see the other responses. > In other words, suppose that I’ve launched irb and fired > “foo”.levenshtein(“foobar”). > In that case, is the string “foo” encoded as utf-8? The code makes that assumption, correct or not. If you’re one of those ignorant yokels who believes that characters are bytes, it’s also a safe assumption. 😉 Now, if you’re one of those people who does i18n, l10n, and m17n before breakfast, you’ll have alarm bells going off inside your head immediately, as such assumptions are in general very dangerous to make. A cardinal rule in this kind of programming is that strings are meaningless without an attached encoding. > Do I always have to > unpack the string like > the code shown above? It would be better, at least that keeps your options open when you attempt to internationalize your program. You wind up supporting Unicode at the very least, and that makes the transition to internationalization a bit easier, as Unicode is a reasonable choice as a character set if one wishes to do internationalization. ---
**Author:** ![pool007](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/3bc359/32.png) [@pool007](https://www.ruby-forum.com/u/pool007)\ **Post date:** [October 17, 2006, 10:59am UTC](https://www.ruby-forum.com/t/edit-distance-at-wikipedia/72316/8 "2006-10-17T10:59:52Z")
On 17/10/06, Dido S. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > The code makes that assumption, correct or not. If you’re one of those > ignorant yokels who believes that characters are bytes, it’s also a > safe assumption. 😉 Now, if you’re one of those people who does i18n, > l10n, and m17n before breakfast, you’ll have alarm bells going off > inside your head immediately, as such assumptions are in general very > dangerous to make. A cardinal rule in this kind of programming is that > strings are meaningless without an attached encoding. The version of Levenshtein in the Text project ([http://rubyforge.org/projects/text](http://rubyforge.org/projects/text)) will work on either UTF-8 codepoints or bytes depending on the value of $KCODE. It’s the best we can do for now; in the future, of course, we will be able to decide based on the strings’ encodings themselves. \ Paul.