Module: Synthra::Utils::StringDistance

Defined in:
lib/synthra/utils/string_distance.rb

Overview

String distance calculations for "did you mean" suggestions

Provides methods to calculate edit distance between strings and find similar strings from a collection.

Examples:

Find similar type names

StringDistance.similar_strings("strig", Synthra::Types::Registry.names)
# => ["string", "text"]

Class Method Summary collapse

Class Method Details

.format_suggestions(suggestions) ⇒ String?

Format "did you mean" suggestion text

Examples:

StringDistance.format_suggestions(["uuid", "ulid"])
# => "Did you mean: uuid, ulid?"

StringDistance.format_suggestions([])
# => nil

Parameters:

  • suggestions (Array<String>) —

    list of suggestions

Returns:

  • (String, nil) —

    formatted suggestion text or nil if empty



124
125
126
127
128
 
# File 'lib/synthra/utils/string_distance.rb', line 124

def format_suggestions(suggestions)
  return nil if suggestions.nil? || suggestions.empty?

  "Did you mean: #{suggestions.join(", ")}?"
end

.levenshtein(str1, str2) ⇒ Integer

Calculate Levenshtein distance between two strings

The Levenshtein distance is the minimum number of single-character edits (insertions, deletions, or substitutions) required to transform one string into another.

Examples:

StringDistance.levenshtein("uuid", "ulid")  # => 2
StringDistance.levenshtein("text", "text")  # => 0
StringDistance.levenshtein("", "abc")       # => 3

Parameters:

  • str1 (String) —

    first string

  • str2 (String) —

    second string

Returns:

  • (Integer) —

    the edit distance



49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 
# File 'lib/synthra/utils/string_distance.rb', line 49

def levenshtein(str1, str2)
  str1 = str1.to_s.downcase
  str2 = str2.to_s.downcase

  return str2.length if str1.empty?
  return str1.length if str2.empty?
  return 0 if str1 == str2

  # Create matrix
  m = str1.length
  n = str2.length
  d = Array.new(m + 1) { Array.new(n + 1) }

  # Initialize first column
  (0..m).each { |i| d[i][0] = i }

  # Initialize first row
  (0..n).each { |j| d[0][j] = j }

  # Fill in the rest of the matrix
  (1..m).each do |i|
    (1..n).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
    end
  end

  d[m][n]
end

.similar_strings(target, candidates, max_distance: 3, limit: 3) ⇒ Array<String>

Find strings similar to a target from a collection

Returns strings that are within the specified edit distance of the target, sorted by distance (closest first).

Examples:

StringDistance.similar_strings("uui", ["uuid", "ulid", "name"])
# => ["uuid"]

StringDistance.similar_strings("tex", ["text", "next", "email"], max_distance: 2)
# => ["text", "next"]

Parameters:

  • target (String) —

    the string to match

  • candidates (Array<String>) —

    collection to search

  • max_distance (Integer) (defaults to: 3) —

    maximum edit distance (default: 3)

  • limit (Integer) (defaults to: 3) —

    maximum number of results (default: 3)

Returns:

  • (Array<String>) —

    similar strings, sorted by distance



101
102
103
104
105
106
107
108
109
110
 
# File 'lib/synthra/utils/string_distance.rb', line 101

def similar_strings(target, candidates, max_distance: 3, limit: 3)
  target = target.to_s

  candidates
    .map { |c| [c, levenshtein(target, c)] }
    .select { |_, dist| dist <= max_distance }
    .sort_by { |_, dist| dist }
    .first(limit)
    .map(&:first)
end