Added edit distance to Label

[erd-marker.git] / lib / erd_handler / label.rb

diff --git a/lib/erd_handler/label.rb b/lib/erd_handler/label.rb
index cdeacb177eb24c56c7004995e4ab1130303e903d..a995432a3cf544240cc2a7d73984cb7c1259ddb7 100644 (file)
--- a/lib/erd_handler/label.rb
+++ b/lib/erd_handler/label.rb
@@ -2,7 +2,7 @@ class Label
   
   attr_reader :original, :processed
   
-  def initialize(original)
+  def initialize(original = "")
     @original = original
     @processed = [original]
   end
@@ -55,4 +55,33 @@ class Label
   def tidy
     self.split.downcase.stem
   end
+  
+  def levenshtein(other_object)
+    if other_object.class == Label
+      other = other_object.processed.join('')
+    else
+      other = other_object
+    end
+    s = @processed.join('')
+    n = s.length
+    m = other.length
+    return m if (0 == n)
+    return n if (0 == m)
+    
+    d = Array.new(m+1) {Array.new(n+1, 0)} # one row for each characer in other, one column for each charater in self
+    
+    (0..n).each {|i| d[0][i] = i}
+    (0..m).each {|j| d[j][0] = j}
+    (1..m).each do |i|
+      (1..n).each do |j|
+        d[i][j] = [d[i-1][j-1] + ((s[j-1] == other[i-1]) ? 0 : 1),  # substitution
+                   d[i-1][j] + 1, # deletion
+                   d[i][j-1] + 1  # addition
+                   ].min
+      end
+    end
+    d[-1][-1]
+  end
+  
+  alias :edit_distance :levenshtein
 end
\ No newline at end of file