class DynarexLevenshtein
Attributes
distance[R]
to_dynarex[R]
Public Class Methods
new(a,b)
click to toggle source
# File lib/dynarexlevenshtein.rb, line 11 def initialize(a,b) @distance = levenshtein(a,b) end
Public Instance Methods
levenshtein(a,b)
click to toggle source
# File lib/dynarexlevenshtein.rb, line 15 def levenshtein(a,b) a, b = [a, b].sort_by(&:length) n, m = a.length, b.length schema = 'table[title,string1,string2, distance]/rows(' + \ (['line','label'] + (0..n).map{|x| "col%s" % x}).join(',') + ')' @to_dynarex = Dynarex.new(schema) @to_dynarex.summary[:title] = 'Calculates the Levenshtein distance between a and b.' @to_dynarex.summary[:string1] = a @to_dynarex.summary[:string2] = b current = (n+1).times.to_a top_label = ['0','',''] + a.split('') label = [''] + b.split('') h = Hash[([:line, :label] + (0..n).map{|x| ("col%s" % x).to_sym})\ .zip(top_label)] @to_dynarex.create h (1..m).each do |i| previous, current = current, [i]+[0]*n h = Hash[([:line, :label] + (0..n).map{|x| ("col%s" % x).to_sym}).zip([i.to_s, \ label[i-1]] + previous)] @to_dynarex.create h (1..n).each do |j| delete, change, add = current[j-1], previous[j-1], previous[j] change += 1 if a[j-1] != b[i-1] current[j] = [add+1, delete+1, change].min end end h = Hash[([:line, :label] + (0..n).map{|x| ("col%s" % x).to_sym}).zip([(m+1).to_s, label[-1]] + current)] @to_dynarex.create h @to_dynarex.summary[:distance] = current[n].to_s current[n] end