Re: Mini quiz (Was: Detecting similar strings)

Ruby
1

It’s missing from wikipedia though.

Does wikipedia provide the code for the implementations it lists?
Maybe Hal would be so kind to add it then, if we ask him politely
to do so :slight_smile:

Best regards,

Axel

2

It’s missing from wikipedia though.

Does wikipedia provide the code for the implementations it lists?
Maybe Hal would be so kind to add it then, if we ask him politely
to do so :slight_smile:

Best regards,

Here’s my implementation anyway (not at all fast):

def lev(s1, s2)

A hash to build up the solution matrix in.

l = Hash.new do |h,k|
h = if k.member? 0
# Edge case for the top and left of the solution matrix.
k.max
else
# Otherwise, recursively find this cell based on the rest of
# the solution matrix.
i,j = *k
[ l[[i-1,j]]+1,
l[[i,j-1]]+1,
l[[i-1,j-1]] + (s1[i]==s2[j]?0:1)].min
end
end

The answer’s stored in the bottom right of the solution matrix.

l[[s1.size-1, s2.size-1]]
end

3

[email protected] wrote:

It’s missing from wikipedia though.

Does wikipedia provide the code for the implementations it lists?
Maybe Hal would be so kind to add it then, if we ask him politely
to do so :slight_smile:

Ping me in a week and I will…

Hal

4

A quick search on Google reveals a levenshtein ruby function has already
been created.
http://po-ru.com/projects/levenshtein/

To my untrained eye (I am new to Ruby) using the levenshtein distance to
calculate what someone might have meant to type mught be expensive. You
will need to calculate the distance for all values in the field to
compare it with the user input, then pick the small distances and
display them as options. As the list of values grows larger, your app
will bog down.

Perhaps a better way is to use an auto-complete ajax call on the input
field?

Andrew