Module: SmartBrain::Support::Levenshtein

Defined in:
lib/smart_brain/support/levenshtein.rb

Overview

Pure-Ruby Levenshtein edit distance (no native dep). Used by FactCheck for SimilarNameConflict detection.

Class Method Summary collapse

Class Method Details

.distance(a, b) ⇒ Object 



10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
# File 'lib/smart_brain/support/levenshtein.rb', line 10

def distance(a, b)
  a = a.to_s
  b = b.to_s
  return b.length if a.empty?
  return a.length if b.empty?

  # Iterative two-row DP.
  previous = (0..b.length).to_a
  current = Array.new(b.length + 1, 0)
  (1..a.length).each do |i|
    current[0] = i
    (1..b.length).each do |j|
      cost = a[i - 1] == b[j - 1] ? 0 : 1
      current[j] = [
        previous[j] + 1,       # deletion
        current[j - 1] + 1,    # insertion
        previous[j - 1] + cost # substitution
      ].min
    end
    previous, current = current, previous
  end
  previous[b.length]
end