From: benjohn@...
Date: 2006-08-01T22:19:32+09:00
Subject: Re: Mini quiz (Was: Detecting similar strings)

>>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 :)
>
> 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