Class: DamLev

Inherits:
Object
  • Object
show all
Defined in:
lib/dam_lev.rb,
lib/dam_lev/version.rb

Constant Summary collapse

VERSION = 
"1.0.1"

Class Method Summary collapse

Class Method Details

.distance(str1, str2) ⇒ Object 



2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
# File 'lib/dam_lev.rb', line 2

def self.distance(str1, str2)
  return str1.length if str2.empty?
  return str2.length if str1.empty?
  
  distance_matrix = build_matrix(str1, str2)
  
  (1..str1.length).each do |i|
    (1..str2.length).each do |j|
      sub_cost = str1[i-1] == str2[j-1] ? 0 : 1
      
      distance_matrix[i][j] = [
        distance_matrix[i-1][j] + 1,            # deletion
        distance_matrix[i][j-1] + 1,            # insertion
        distance_matrix[i-1][j-1] + sub_cost    # substitution
      ].min    
                                  
      if i > 1 && j > 1 && str1[i-1] == str2[j-2] && str1[i-2] == str2[j-1]
        distance_matrix[i][j] = [
          distance_matrix[i][j], 
          distance_matrix[i-2][j-2] + sub_cost  # transposition
        ].min
      end
    end
  end
  
  distance_matrix.last.last
end