Module: Kotoshu::Algorithms::EditDistance

Defined in:
lib/kotoshu/algorithms/edit_distance.rb

Overview

Damerau-Levenshtein edit distance.

Counts the minimum number of operations (insertion, deletion, substitution, or transposition of adjacent characters) needed to transform one string into another. The transposition extension distinguishes this from plain Levenshtein — a transposition (e.g. "teh" → "the") costs 1 instead of 2.

Extracted from EditDistanceStrategy so that the algorithm is reusable independent of the strategy pipeline and testable without send-to-private.

Class Method Summary collapse

Class Method Details

.distance(str1, str2) ⇒ Integer

Compute the Damerau-Levenshtein distance between two strings.

Parameters:

  • str1 (String) —

    First string

  • str2 (String) —

    Second string

Returns:

  • (Integer) —

    Edit distance (0 when str1 == str2)



24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
# File 'lib/kotoshu/algorithms/edit_distance.rb', line 24

def distance(str1, str2)
  return str2.length if str1.empty?
  return str1.length if str2.empty?

  len1 = str1.length
  len2 = str2.length

  d = Array.new(len1 + 1) { Array.new(len2 + 1, 0) }

  (0..len1).each { |i| d[i][0] = i }
  (0..len2).each { |j| d[0][j] = j }

  (1..len1).each do |i|
    (1..len2).each do |j|
      cost = str1[i - 1] == str2[j - 1] ? 0 : 1

      d[i][j] = [
        d[i - 1][j] + 1,      # deletion
        d[i][j - 1] + 1,      # insertion
        d[i - 1][j - 1] + cost # substitution
      ].min

      next unless i > 1 && j > 1 &&
        str1[i - 1] == str2[j - 2] &&
        str1[i - 2] == str2[j - 1]

      d[i][j] = [d[i][j], d[i - 2][j - 2] + 1].min
    end
  end

  d[len1][len2]
end

.distance_with_threshold(str1, str2, threshold) ⇒ Integer?

Compute edit distance with early-exit threshold.

Returns nil when the true distance exceeds threshold. Uses the row-minimum early-termination technique: after each DP row is computed, if every cell in the row exceeds threshold, the final distance must exceed threshold (the last-row cell is bounded below by the row minimum) — so we bail without computing the rest.

Combined with the length pre-filter (|len1-len2| > threshold implies distance > threshold), this prunes clearly-different pairs in O(threshold * min(len1, len2)) instead of the full O(len1 * len2) Damerau-Levenshtein DP.

Note: the full matrix is kept (not 2-row DP) because the Damerau transposition step needs d[j-2] which a 2-row implementation doesn't retain. The early termination is the primary win, not memory reduction.

Parameters:

  • str1 (String) —

    First string

  • str2 (String) —

    Second string

  • threshold (Integer) —

    Maximum distance to report (assumed >= 0)

Returns:

  • (Integer, nil) —

    Distance if ≤ threshold, else nil



80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
 
# File 'lib/kotoshu/algorithms/edit_distance.rb', line 80

def distance_with_threshold(str1, str2, threshold)
  return 0 if str1 == str2
  # The length filter must run before the empty-string shortcuts:
  # an empty str1 gives distance str2.length, which still has to
  # honor the nil-above-threshold contract.
  return nil if (str1.length - str2.length).abs > threshold
  return str2.length if str1.empty?
  return str1.length if str2.empty?

  len1 = str1.length
  len2 = str2.length

  d = Array.new(len1 + 1) { Array.new(len2 + 1, 0) }
  (0..len1).each { |i| d[i][0] = i }
  (0..len2).each { |j| d[0][j] = j }

  (1..len1).each do |i|
    row_min = Float::INFINITY

    (1..len2).each do |j|
      cost = str1[i - 1] == str2[j - 1] ? 0 : 1

      d[i][j] = [
        d[i - 1][j] + 1,      # deletion
        d[i][j - 1] + 1,      # insertion
        d[i - 1][j - 1] + cost # substitution
      ].min

      # Damerau transposition (needs d[i-2][j-2] which is why
      # we keep the full matrix).
      if i > 1 && j > 1 &&
          str1[i - 1] == str2[j - 2] &&
          str1[i - 2] == str2[j - 1]
        d[i][j] = [d[i][j], d[i - 2][j - 2] + 1].min
      end

      row_min = d[i][j] if d[i][j] < row_min
    end

    # Row minimum > threshold ⇒ final answer > threshold.
    return nil if row_min > threshold
  end

  result = d[len1][len2]
  result <= threshold ? result : nil
end