Class: Kotoshu::Suggestions::Strategies::EditDistanceStrategy

Inherits:
BaseStrategy
  • Object
show all
Defined in:
lib/kotoshu/suggestions/strategies/edit_distance_strategy.rb

Overview

Edit distance suggestion strategy with enhanced ranking. Generates suggestions by finding words with small edit distance, ranked by word frequency, keyboard proximity, and common typo patterns.

Multi-language support:

  • Automatically selects keyboard layout based on language_code
  • Loads frequency data from YAML files (Phase 1) or GitHub (Phase 2)
  • Supports language-specific typo patterns

This is MORE OOP than Spylls which uses standalone functions for edit distance operations.

Follows Open-Closed Principle: Extend by adding YAML files, NOT by modifying this class.

Instance Attribute Summary collapse

Attributes inherited from BaseStrategy

#config, #name

Instance Method Summary collapse

Methods inherited from BaseStrategy

#calculate_ngram_similarity, #create_suggestion, #create_suggestion_set, #enabled?, #generate_ngrams, #get_config, #has_config?, #max_results, #priority, #to_s

Constructor Details

#initialize(name: :edit_distance, language_code: 'en', keyboard_layout: nil, frequency_tiers: nil, **config) ⇒ EditDistanceStrategy

Returns a new instance of EditDistanceStrategy.

Parameters:

  • name (String, Symbol) (defaults to: :edit_distance) —

    Name of the strategy

  • config (Hash) —

    Configuration options

Options Hash (**config):

  • :language_code (String) —

    Language code for keyboard layout (default: 'en')

  • :keyboard_layout (Keyboard::Layout) —

    Custom keyboard layout (optional)

  • :frequency_tiers (Hash) —

    Custom frequency tiers (optional)

  • :max_distance (Integer) —

    Maximum edit distance (default: 2)

  • :max_results (Integer) —

    Maximum results to return (default: 10)



32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
# File 'lib/kotoshu/suggestions/strategies/edit_distance_strategy.rb', line 32

def initialize(name: :edit_distance, language_code: 'en', keyboard_layout: nil,
               frequency_tiers: nil, **config)
  super(name: name, **config)
  @language_code = language_code

  # Use OOP registry for keyboard layout lookup
  @keyboard_layout = resolve_keyboard_layout(keyboard_layout)

  # Use custom frequency tiers if provided, otherwise load from Kelly data
  if frequency_tiers
    @frequency_tiers = frequency_tiers
    @common_words = Set.new
  else
    # Load frequency data for the language from Kelly JSON
    # This sets @frequency_tiers internally
    load_frequency_data(language_code)
  end
end

Instance Attribute Details

#keyboard_layout ⇒ Object (readonly)

Returns the value of attribute keyboard_layout.



23
24
25
 
# File 'lib/kotoshu/suggestions/strategies/edit_distance_strategy.rb', line 23

def keyboard_layout
  @keyboard_layout
end

#language_code ⇒ Object (readonly)

Returns the value of attribute language_code.



23
24
25
 
# File 'lib/kotoshu/suggestions/strategies/edit_distance_strategy.rb', line 23

def language_code
  @language_code
end

Instance Method Details

#adjacent_key_typo?(char1, char2) ⇒ Boolean

Check if a substitution is a keyboard-adjacent typo

Parameters:

  • char1 (String) —

    First character

  • char2 (String) —

    Second character

Returns:

  • (Boolean) —

    True if keys are adjacent



70
71
72
 
# File 'lib/kotoshu/suggestions/strategies/edit_distance_strategy.rb', line 70

def adjacent_key_typo?(char1, char2)
  @keyboard_layout.adjacent_keys(char1).include?(char2)
end

#adjacent_keys(key) ⇒ Array<String>

Get adjacent keys for a given key

Parameters:

  • key (String) —

    The key to find adjacent keys for

Returns:

  • (Array<String>) —

    List of adjacent key characters



78
79
80
 
# File 'lib/kotoshu/suggestions/strategies/edit_distance_strategy.rb', line 78

def adjacent_keys(key)
  @keyboard_layout.adjacent_keys(key)
end

#calculate_enhanced_score(original, suggestion, distance) ⇒ Float

Calculate enhanced score combining multiple factors.

Lower score = better suggestion

Parameters:

  • original (String) —

    The original misspelled word

  • suggestion (String) —

    The suggested word

  • distance (Integer) —

    Edit distance

Returns:

  • (Float) —

    Enhanced score (lower is better)



300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
 
# File 'lib/kotoshu/suggestions/strategies/edit_distance_strategy.rb', line 300

def calculate_enhanced_score(original, suggestion, distance)
  score = distance * 1000.0 # Base score from edit distance

  # Factor 1: Word frequency bonus (common words get lower score)
  score -= frequency_bonus(suggestion)

  # Factor 2: Keyboard proximity penalty (typo-like patterns get lower score)
  score += keyboard_penalty(original, suggestion)

  # Factor 3: Common typo pattern bonus
  # Transposition (swap adjacent chars) is the MOST common typo
  trans_bonus = transposition_bonus(original, suggestion)
  score -= trans_bonus

  # Factor 4: Missing double letter bonus (helo -> hello)
  score -= typo_pattern_bonus(original, suggestion)

  # Factor 5: Length similarity bonus (similar length is better)
  length_diff = (original.length - suggestion.length).abs
  score += length_diff * 50

  score
end

#frequency_bonus(word) ⇒ Integer

Get frequency bonus for a word

Parameters:

  • word (String) —

    The word to check

Returns:

  • (Integer) —

    Frequency bonus (0-200)



86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
 
# File 'lib/kotoshu/suggestions/strategies/edit_distance_strategy.rb', line 86

def frequency_bonus(word)
  return 0 unless @frequency_tiers

  word_downcase = word.downcase

  # Top 50: 200 bonus
  return 200 if @frequency_tiers[:top_50]&.include?(word_downcase)

  # Top 200: 100 bonus
  return 100 if @frequency_tiers[:top_200]&.include?(word_downcase)

  # Top 1000: 50 bonus
  return 50 if @frequency_tiers[:top_1000]&.include?(word_downcase)

  # Not in common words: no bonus
  0
end

#generate(context) ⇒ SuggestionSet

Generate suggestions based on enhanced edit distance scoring.

Scoring factors:

  • Edit distance (primary factor)
  • Word frequency (common words rank higher)
  • Keyboard proximity (adjacent key typos rank higher)
  • Common typo patterns (missing double letters, etc.)

Parameters:

  • context (Context) —

    The suggestion context

Returns:



114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
 
# File 'lib/kotoshu/suggestions/strategies/edit_distance_strategy.rb', line 114

def generate(context)
  word = context.word
  max_dist = get_config(:max_distance, 2)
  min_confidence = get_config(:min_confidence, 0.75) # Higher threshold for quality
  min_similarity = get_config(:min_jaro_similarity, 0.70) # Minimum Jaro-Winkler similarity (0.0-1.0)
  min_results = get_config(:min_results, 3) # Always return at least 3 suggestions if available

  # When the dictionary is case-insensitive, normalize case before
  # edit-distance comparison — otherwise "HELO" can never match
  # "Hello" within distance 2 (case differences alone cost 4).
  # The original dictionary casing is preserved on the returned
  # suggestion (we only normalize for the comparison).
  case_insensitive = dictionary_case_insensitive?(context)
  compare_word = case_insensitive ? word.downcase : word

  # Get all dictionary words
  all_words = dictionary_words(context)

  # Calculate enhanced scores for all candidates
  candidates = []
  all_words.each do |dict_word|
    next if dict_word == word

    compare_dict = case_insensitive ? dict_word.downcase : dict_word
    dist = edit_distance(compare_word, compare_dict)
    next if dist > max_dist || dist <= 0

    # Calculate enhanced score (lower is better)
    score = calculate_enhanced_score(compare_word, compare_dict, dist)
    candidates << [dict_word, dist, score]
  end

  # Sort by enhanced score (lower is better)
  sorted_candidates = candidates.sort_by { |_, _, score| score }

  # Calculate confidence scores with threshold filtering
  if sorted_candidates.empty?
    return SuggestionSet.empty
  end

  max_score = sorted_candidates.map { |_, _, s| s.to_f }.max
  min_score = sorted_candidates.map { |_, _, s| s.to_f }.min
  score_range = (max_score - min_score).abs

  # Create suggestions with confidence-based filtering
  suggestions = []
  sorted_candidates.each do |dict_word, dist, score|
    # Normalize score to confidence (0.0 to 1.0)
    # Lower score = higher confidence
    if score_range > 0
      normalized = (score.to_f - min_score) / score_range # 0 to 1
      confidence = 1.0 - normalized # Invert: lower score = higher confidence
    else
      confidence = 1.0
    end

    # Calculate Jaro-Winkler similarity for additional filtering.
    # Use the same case normalization as the edit distance so the
    # similarity score is consistent with the distance threshold.
    compare_dict = case_insensitive ? dict_word.downcase : dict_word
    jaro_similarity = calculate_ngram_similarity(compare_word, compare_dict)

    # Skip low-confidence or low-similarity suggestions (unless we need more for min_results)
    if (confidence < min_confidence || jaro_similarity < min_similarity) && (suggestions.size >= min_results)
      next
    end

    suggestions << Suggestion.new(
      word: dict_word,
      distance: dist,
      confidence: confidence,
      source: @name,
      original_length: word.length,
      ngram_score: jaro_similarity, # Now stores Jaro-Winkler similarity (0.0-1.0)
      enhanced_score: score
    )

    # Stop when we have enough high-quality suggestions
    break if suggestions.size >= max_results
  end

  SuggestionSet.new(suggestions, max_size: max_results)
end

#handles?(context) ⇒ Boolean

Check if this strategy should handle the context.

Parameters:

  • context (Context) —

    The suggestion context

Returns:

  • (Boolean) —

    True if the word needs correction



202
203
204
205
206
207
 
# File 'lib/kotoshu/suggestions/strategies/edit_distance_strategy.rb', line 202

def handles?(context)
  return false unless enabled?

  # Only handle if the word is not in the dictionary
  !dictionary_lookup(context, context.word)
end

#keyboard ⇒ Keyboard::Layout

Public method to get current keyboard being used

Returns:



54
55
56
 
# File 'lib/kotoshu/suggestions/strategies/edit_distance_strategy.rb', line 54

def keyboard
  @keyboard_layout
end

#keyboard_name ⇒ String

Public method to get keyboard name

Returns:

  • (String) —

    Keyboard layout name



61
62
63
 
# File 'lib/kotoshu/suggestions/strategies/edit_distance_strategy.rb', line 61

def keyboard_name
  @keyboard_layout.name
end

#keyboard_penalty(original, suggestion) ⇒ Float

Calculate keyboard proximity penalty.

Substitutions between adjacent keys get lower penalty. Uses OOP keyboard layout for language-aware distance calculations.

Parameters:

  • original (String) —

    The original word

  • suggestion (String) —

    The suggested word

Returns:

  • (Float) —

    Keyboard penalty (0-200)



362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
 
# File 'lib/kotoshu/suggestions/strategies/edit_distance_strategy.rb', line 362

def keyboard_penalty(original, suggestion)
  penalty = 0

  # Find the edit script to see what changed
  o_chars = original.chars
  s_chars = suggestion.chars

  # Simple comparison for equal-length words (substitutions)
  if o_chars.length == s_chars.length
    o_chars.each_with_index do |c1, i|
      c2 = s_chars[i]
      next if c1 == c2

      # Use OOP keyboard layout for distance calculation
      key_dist = @keyboard_layout.distance(c1, c2)

      penalty += if key_dist == Float::INFINITY
                   # Symbol or unknown key - medium penalty
                   50
                 elsif key_dist == 1
                   10  # Very likely typo (adjacent keys)
                 elsif key_dist == 2
                   30  # Somewhat likely
                 else
                   100 # Unlikely to be typo (far keys)
                 end
    end
  end

  penalty
end

#transposition_bonus(original, suggestion) ⇒ Float

Calculate bonus for transposition (swap adjacent characters). This is the MOST common typing error, so it gets the highest bonus.

Parameters:

  • original (String) —

    The original word

  • suggestion (String) —

    The suggested word

Returns:

  • (Float) —

    Transposition bonus (0 or 200)



330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
 
# File 'lib/kotoshu/suggestions/strategies/edit_distance_strategy.rb', line 330

def transposition_bonus(original, suggestion)
  # Transposition only makes sense for same-length words
  return 0 unless original.length == suggestion.length

  o = original.downcase
  s = suggestion.downcase

  # Count transpositions needed
  transpositions = 0
  (0...o.length).each do |i|
    next if o[i] == s[i]

    # Find matching char in suggestion
    match_idx = s.index(o[i], i + 1)
    if match_idx && (match_idx == i + 1 || (match_idx > i + 1 && s[i] == o[match_idx]))
      # This is a simple adjacent swap
      transpositions += 1
    end
  end

  # Only give bonus for single transposition
  transpositions == 1 ? 200 : (transpositions * 100)
end

#typo_pattern_bonus(original, suggestion) ⇒ Float

Calculate bonus for common typo patterns.

Parameters:

  • original (String) —

    The original word

  • suggestion (String) —

    The suggested word

Returns:

  • (Float) —

    Pattern bonus (0-300)



399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
 
# File 'lib/kotoshu/suggestions/strategies/edit_distance_strategy.rb', line 399

def typo_pattern_bonus(original, suggestion)
  bonus = 0

  # Pattern 1: Missing double letter (helo -> hello)
  # This is the MOST COMMON typo after transposition, give it highest bonus
  if suggestion.length == original.length + 1
    # Check if suggestion has a double letter that original is missing
    suggestion.chars.each_cons(2).with_index do |pair, i|
      if pair[0] == pair[1] # Found double letter at positions i and i+1
        # Check if removing the second occurrence (at i+1) gives us the original word
        # For "hello" with "ll" at position 2, remove position 3: "hel" + "o" = "helo"
        expected = suggestion[0...i + 1] + suggestion[i + 2..-1]
        if expected == original
          bonus += 300 # Strong bonus for missing double letter (MORE than transposition!)
          break
        end
      end
    end
  end

  # Pattern 2: Extra double letter (helllo -> hello)
  if original.length == suggestion.length + 1
    # Check if original has a double letter that suggestion doesn't
    original.chars.each_cons(2).with_index do |pair, i|
      if pair[0] == pair[1] # Found double letter in original
        # Check if removing it gives the suggestion
        reconstructed = original[0...i + 1] + original[i + 1..-1]
        if reconstructed == suggestion
          bonus += 100 # Bonus for extra double letter
          break
        end
      end
    end
  end

  # Pattern 3: Common prefixes/suffixes
  if original.start_with?(suggestion[0...3]) && suggestion.length > original.length
    bonus += 30 # Suggestion extends common prefix
  end

  bonus
end