Module: CLI::Kit::Levenshtein

Extended by:
T::Sig
Defined in:
lib/cli/kit/levenshtein.rb

Class Method Summary collapse

Methods included from T::Sig

sig

Class Method Details

.distance(str1, str2) ⇒ Object 



38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
 
# File 'lib/cli/kit/levenshtein.rb', line 38

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 = 0

  # to avoid duplicating an enumerable object, create it outside of the loop
  str2_codepoints = str2.codepoints

  str1.each_codepoint.with_index(1) do |char1, i|
    j = 0
    while j < m
      cost = char1 == str2_codepoints[j] ? 0 : 1
      x = min3(
        T.must(d[j + 1]) + 1, # insertion
        i + 1, # deletion
        T.must(d[j]) + cost, # substitution
      )
      d[j] = i
      i = x

      j += 1
    end
    d[m] = x
  end

  x
end

.min3(a, b, c) ⇒ Object 



78
79
80
81
82
83
84
85
86
 
# File 'lib/cli/kit/levenshtein.rb', line 78

def min3(a, b, c)
  if a < b && a < c
    a
  elsif b < c
    b
  else
    c
  end
end