module Levenshtein

Public Class Methods

distance(str1, str2) click to toggle source

This code is based directly on the Text gem implementation Returns a value representing the “cost” of transforming str1 into str2 taken from github.com/threedaymonk/text/blob/master/lib/text/levenshtein.rb

# File lib/feeling_lucky.rb, line 7
def distance(str1, str2)
  n = str1.length
  m = str2.length
  return m if n.zero?
  return n if m.zero?

  d = (0..m).to_a
  x = nil

  str1.each_char.with_index(1) do |char1, i|
    str2.each_char.with_index do |char2, j|
      cost = (char1 == char2) ? 0 : 1
      x = min3(
        d[j+1] + 1, # insertion
        i + 1,      # deletion
        d[j] + cost # substitution
      )
      d[j] = i
      i = x
    end
    d[m] = x
  end

  x
end

Private Instance Methods

distance(str1, str2) click to toggle source

This code is based directly on the Text gem implementation Returns a value representing the “cost” of transforming str1 into str2 taken from github.com/threedaymonk/text/blob/master/lib/text/levenshtein.rb

# File lib/feeling_lucky.rb, line 7
def distance(str1, str2)
  n = str1.length
  m = str2.length
  return m if n.zero?
  return n if m.zero?

  d = (0..m).to_a
  x = nil

  str1.each_char.with_index(1) do |char1, i|
    str2.each_char.with_index do |char2, j|
      cost = (char1 == char2) ? 0 : 1
      x = min3(
        d[j+1] + 1, # insertion
        i + 1,      # deletion
        d[j] + cost # substitution
      )
      d[j] = i
      i = x
    end
    d[m] = x
  end

  x
end