# Levenshtein function issue **URL:** \ **Category:** Ruby\ **Created:** [September 24, 2010, 3:13am UTC](https://www.ruby-forum.com/t/levenshtein-function-issue/195510 "2010-09-24T03:13:37Z")\ **Posts on this page:** 8\ **Page:** 1
**Author:** ![jsimone](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/2bfe46/32.png) [@jsimone](https://www.ruby-forum.com/u/jsimone)\ **Post date:** [September 24, 2010, 3:13am UTC](https://www.ruby-forum.com/t/levenshtein-function-issue/195510/1 "2010-09-24T03:13:37Z")
well, I’m trying to get the levenshtein function to work, and it’s close, but it’s not quite giving me the right answer and i have no idea why. here’s the code: class Array2D def initialize(width, height) @data = Array.new(width) { Array.new(height) } end def [](x, y) @data[x][y] end def []=(x, y, value) @data[x][y] = value end end def levenshtein(s, t) #include cost? m = s.size n = t.size d = Array2D.new(m+1,n-1) for i in 0…m d[i,0]=i end ``` for j in 0..n d[0,j]=j ``` end for j in 1…n for i in 1…m if(s[i].eql?(t[i])) then d[i,j]=d[i-1,j-1] end ``` if not (s[i].eql?(t[i])) then d[i,j] = [(d[i-1,j]+1), (d[i,j-1]+1), (d[i-1,j-1]+1) ``` ].min end end end puts “After:”+ d.inspect # puts "Ans: " return d[m,n] end #end func # when I call it: puts “Call to levenshtein():” puts levenshtein(“string1”,“2strings”) # and the output… here’s the output: Call to levenshtein(): After:#\ Ans: 8 If you check those two strings I tested with at this URL, my resulting matrix is wrong (no idea why), and the answer should be 2… check it here: [http://www.miislita.com/searchito/levenshtein-edit-distance.html](http://www.miislita.com/searchito/levenshtein-edit-distance.html) = THANK YOU SO MUCH FOR ANY HELP! ---
**Author:** ![jsimone](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/2bfe46/32.png) [@jsimone](https://www.ruby-forum.com/u/jsimone)\ **Post date:** [September 24, 2010, 6:25pm UTC](https://www.ruby-forum.com/t/levenshtein-function-issue/195510/2 "2010-09-24T18:25:38Z")
… > d = Array2D.new(m+1,n-1) You have ‘n-1’ here, but subsequently use indexes up to n. cheers ---
**Author:** ![jsimone](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/2bfe46/32.png) [@jsimone](https://www.ruby-forum.com/u/jsimone)\ **Post date:** [September 26, 2010, 6:43am UTC](https://www.ruby-forum.com/t/levenshtein-function-issue/195510/3 "2010-09-26T06:43:39Z")
Chris H. wrote: > … > > > � d = Array2D.new(m+1,n-1) > > You have ‘n-1’ here, but subsequently use indexes up to n. > > cheers Thanks for the reply. Yes, but when I change that, I just get an error… (that’s why I had originally changed it) ---
**Author:** ![jsimone](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/2bfe46/32.png) [@jsimone](https://www.ruby-forum.com/u/jsimone)\ **Post date:** [September 27, 2010, 6:25pm UTC](https://www.ruby-forum.com/t/levenshtein-function-issue/195510/4 "2010-09-27T18:25:54Z")
On Sep 26, 12:43 am, Joe S. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > ## error… (that’s why I had originally changed it) > > Posted viahttp://www.ruby-forum.com/. Looking at the description at [http://www.levenshtein.net/](http://www.levenshtein.net/) it appears that both m and n should be +1 The strings are then offset to allow indexing from 1. Guess you either need to add a character (blank?) to the beginning of both strings, or adjust your indexes into s and t (the 1st char is the 0th index) I’m totally pulling this out of my head, as I don’t have Ruby on my work computer ---
**Author:** ![jsimone](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/2bfe46/32.png) [@jsimone](https://www.ruby-forum.com/u/jsimone)\ **Post date:** [September 28, 2010, 8:10pm UTC](https://www.ruby-forum.com/t/levenshtein-function-issue/195510/5 "2010-09-28T20:10:51Z")
On Sep 27, 3:37 pm, Joe S. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > > to the beginning of both strings, or adjust your indexes into s and t > > (the 1st char is the 0th index) > > > I’m totally pulling this out of my head, as I don’t have Ruby on my > > work computer > > ## Thank you for the reply. Unfortunately, I get the same error when I try this ☹ > > Posted viahttp://www.ruby-forum.com/. This was bugging me so I installed Ruby and gave it a go. You do need to change that ‘n-1’ to be ‘n+1’ Then in the nested loop you need to use both indexes: for j in 1…n for i in 1…m if(s[i].eql?(t[i])) then ^this ‘i’ should be ‘j’ But you still need to adjust the indexes into the strings (i-1 and j-1 seems to work here) cheers ---
**Author:** ![jsimone](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/2bfe46/32.png) [@jsimone](https://www.ruby-forum.com/u/jsimone)\ **Post date:** [September 27, 2010, 9:36pm UTC](https://www.ruby-forum.com/t/levenshtein-function-issue/195510/6 "2010-09-27T21:36:22Z")
Chris H. wrote: > On Sep 26, 12:43�am, Joe S. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > > > ## error… (that’s why I had originally changed it) > > > > Posted viahttp://www.ruby-forum.com/. > > Looking at the description at [http://www.levenshtein.net/](http://www.levenshtein.net/) it appears > that both m and n should be +1 > The strings are then offset to allow indexing from 1. Guess you > either need to add a character (blank?) > to the beginning of both strings, or adjust your indexes into s and t > (the 1st char is the 0th index) > > I’m totally pulling this out of my head, as I don’t have Ruby on my > work computer Thank you for the reply. Unfortunately, I get the same error when I try this ☹ ---
**Author:** ![jsimone](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/2bfe46/32.png) [@jsimone](https://www.ruby-forum.com/u/jsimone)\ **Post date:** [September 28, 2010, 11:05pm UTC](https://www.ruby-forum.com/t/levenshtein-function-issue/195510/7 "2010-09-28T23:05:54Z")
On 09/28/2010 08:10 PM, Chris H. wrote: > On Sep 27, 3:37 pm, Joe S. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > > > Chris H. wrote: > > > > > On Sep 26, 12:43 am, Joe S. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > > > > > > > ## error… (that’s why I had originally changed it) […] > Now, that bugged me too, and I had a go (using more idiomatic ruby ranges and Enumerable methods, and “enhancing” the String class): > Notes: When first going through the matrix, I fill the initial values in the first column and row, and set the rest to nil. When traversing the matrix a second time, I start at index ‘1’ and end at the index calculated from the size, but the strings actually use zero-based indexes. To illustrate that: S T R I N G ← This is the string - spaced out f. visibility 0 1 2 3 4 5 ← These are the corresponding index numbers ``` ^ This is the last index, but the size is returned as 6. ``` So, when I am traversing the matrix, I use 1…6, but the corresponding letters are at 0…5. That is the reason that I have to use cost = (self[s-1] == other[t-1]) ? 0 : 1 so I really do compare the strings letter by letter. Hope that helps a bit, t. ---
**Author:** ![jsimone](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/2bfe46/32.png) [@jsimone](https://www.ruby-forum.com/u/jsimone)\ **Post date:** [September 29, 2010, 4:19am UTC](https://www.ruby-forum.com/t/levenshtein-function-issue/195510/8 "2010-09-29T04:19:03Z")
Seems to be working after some minor changes, thank you everyone!!!