Module: Ruact::StringDistance

Defined in:
lib/ruact/string_distance.rb

Overview

Damerau-Levenshtein string distance + a "did you mean?" closest-match helper, factored out of ClientManifest (Story 7.4) so the Story 13.5 component-contract validator can reuse the SAME closest-match grain for typo'd prop/slot names ("did you mean postId?") without duplicating the algorithm.

Names are short (≤ 30 chars in practice) so the full O(m·n) DP table is fine — the readability win over the two-row trick is worth ~30 cells.

Class Method Summary collapse

Class Method Details

.closest_match(name, pool, max: 2) ⇒ String?

Returns the entry in pool within Damerau-Levenshtein distance max of name (case-insensitive), preferring the smallest distance. Returns nil when nothing qualifies.

Parameters:

  • name (String) —

    the typo'd name to match

  • pool (Array<String>) —

    candidate names

  • max (Integer) (defaults to: 2) —

    inclusive distance threshold (default 2)

Returns:

  • (String, nil) 


56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
# File 'lib/ruact/string_distance.rb', line 56

def self.closest_match(name, pool, max: 2)
  target = name.downcase
  best = nil
  best_distance = max + 1

  pool.each do |candidate|
    distance = damerau_levenshtein(target, candidate.downcase)
    next if distance > max || distance >= best_distance

    best_distance = distance
    best = candidate
  end

  best
end

.damerau_levenshtein(left, right) ⇒ Integer

Damerau-Levenshtein distance — like classic Levenshtein but treats an adjacent transposition (e.g. "ke"↔"ek") as a single edit.

rubocop:disable Metrics/AbcSize

Parameters:

  • left (String)
  • right (String)

Returns:

  • (Integer) —

    the edit distance



20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
# File 'lib/ruact/string_distance.rb', line 20

def self.damerau_levenshtein(left, right)
  return right.length if left.empty?
  return left.length if right.empty?

  m = left.length
  n = right.length
  d = Array.new(m + 1) { Array.new(n + 1, 0) }
  (0..m).each { |i| d[i][0] = i }
  (0..n).each { |j| d[0][j] = j }

  (1..m).each do |i|
    (1..n).each do |j|
      cost = left[i - 1] == right[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
      if i > 1 && j > 1 && left[i - 1] == right[j - 2] && left[i - 2] == right[j - 1]
        d[i][j] = [d[i][j], d[i - 2][j - 2] + cost].min
      end
    end
  end

  d[m][n]
end