Mini quiz (Was: Detecting similar strings)

ruby-talk
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

Nuralanur@aol.com 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

···

On Wednesday, August 02, 2006, at 09:42AM, Hal Fulton <hal9000@hypermetrics.com> wrote:

Nuralanur@aol.com 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