#!/usr/bin/ruby -w ################################################################################# # File : levenstein.rb # # Author : Jean-Eudes Duchesne (duchesnj@iro.umontreal.ca) # # Created : 30 janvier 2004 # # Last updated : 2 février 2004 # # Description : Implementation of Levenstein distance algorithm for finding # # the minimum number of operations to transform S into T. # # Allowed operations are : Substitution, insertion and deletion # # # # Usage : levenstein.rb S T # # S et T are the strings to be compared. The script is pretty # # basic, so try not to use extreme cases. For exemple, output # # formatting is pretty simple, using strings that are too long # # might give unexpected results ! # # # ################################################################################# ### Libs ### ### Globals ### ### Classes & Methods ### class Array2D def initialize @data = [[]] end def [](i,j) # Want i to be the rows and j the columns if @data[j] == nil || @data[j][i] == nil return nil else return @data[j][i] end end def []=(i,j,x) @data[j] = [] if @data[j] == nil @data[j][i] = x end end ### Main ### S = ARGV[0] T = ARGV[1] m = S.length + 1 n = T.length + 1 # Initialisation of array D = Array2D.new for i in 0 ... m D[i,0] = i end for j in 0 ... n D[0,j] = j end # calculate every other cell for i in 1 ... m for j in 1 ... n if(S[i-1] == T[j-1]) D[i,j] = D[i-1,j-1] else D[i,j] = D[i-1,j-1] + 1 end if(D[i,j] > D[i,j-1] + 1) D[i,j] = D[i,j-1] + 1 end if(D[i,j] > D[i-1,j] + 1) D[i,j] = D[i-1,j] + 1 end end end #Print dynamic table and minimal nb of operations printf("\n - ") for j in 0 ... n printf(" %s ", T[j..j]) end printf("\n- ") for i in 0 ... m for j in 0 ... n printf("%3d ", D[i,j]) end printf("\n%s ", S[i..i]) end printf("\nOperations : %d\n\n", D[m-1,n-1])