aanpassen

Onze dagmethode #15: Kernel#levenshtein

Geplaatst door Michiel de Mare ma, 25 feb 2008 08:00:00 GMT

Allerminst door ons verzonnen, maar toch vreselijk nuttig en geen onderdeel van de standaard-library: de Levenshteinafstand

Wat berekent het? Hoeveel karakters je moet toevoegen, weghalen of omwisselen om van de ene naar de andere string te gaan. Ideaal voor het detecteren van typefouten.

# example: 
levenshtein('levenssteen', 'levenshtein') # => 2

Of wat dacht je voor in plaats van je LIKE-clause? Niet zo snel misschien (uche uche) maar wel heel goed.

# Vroeger:
User.find(:all, 
    :conditions => ['name like ?', params[:name] + '%']])

# Nu:
User.find(:all).
    sort_by {|u| levenshtein(params[:name], u.name)}.
    first

def levenshtein(s1, s2)
  d = {}
  (0..s1.size).each { |row| d[[row, 0]] = row }
  (0..s2.size).each { |col| d[[0, col]] = col }
  (1..s1.size).each do |i|
    (1..s2.size).each do |j|
      i1,j1 = i-1,j-1
      cost = s1[i1] != s2[j1] ? 1 : 0
      d[[i, j]] = [d[[i1, j1]] + cost,
                   d[[i1, j]] + 1,
                   d[[i, j1]] + 1].min
      if i1*j1 > 0 and s1[i1] == s2[j-2] and s1[i-2] == s2[j1]
        d[[i, j]] = [d[[i,j]] , d[[i-2, j-2]] + cost].min
      end
    end
  end
  d[[s1.size, s2.size]]
end