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

Geplaatst in ,  | 3 reacties

Reacties

  1. RemVee zei 35 minuten later:

    Wat een prachtig voorbeeld voor refactor my code! ;)

  2. Menno van der Sman zei 11 dagen later:

    Ik gebruik al een tijdje de versie uit de Text-gem (http://text.rubyforge.org/)

    Korte benchmark:
    
                user        system      total        real
    RubyEnRails 14.520000   0.060000  14.580000 ( 15.083743)
    Text        4.660000    0.020000   4.680000 (  4.839868)
    

    Evengoed mooi om eens zelf naar dit soort problemen te kijken.

  3. Michiel zei 11 dagen later:

    Ik weet niet of onze versie (die ik overigens niet zelf heb geschreven, maar ik kan de bron niet meer vinden) daarom zoveel langzamer is, maar die telt het omwisselen van twee letters als één punt. Dat doet de Text-gem niet.

    Voorbeeld:

    
    levenshtein('ruby','urby') # => 1
    distance('ruby','urby')    # => 2
    

(Laat url/e-mail achter »)

   Voorvertoning