Ruby实现的最短编辑距离计算方法
利用动态规划算法，实现最短编辑距离的计算。
#encoding:utf-8 #author:xujin #date:Nov12,2012 #EditDistance #tofindtheminimumcostbyusingEditDistancealgorithm #exampleoutput: # "Pleaseinputastring:" # exponential # "Pleaseinputtheotherstring:" # polynomial # "Theexpectedcostis6" # Theresultis: # ["e","x","p","o","n","e","n","-","t","i","a","l"] # ["-","-","p","o","l","y","n","o","m","i","a","l"]
p"Pleaseinputastring:" x=gets.chop.chars.map{|c|c} p"Pleaseinputtheotherstring:" y=gets.chop.chars.map{|c|c} x.unshift("") y.unshift("") e=Array.new(x.size){Array.new(y.size)} flag=Array.new(x.size){Array.new(y.size)} DEL,INS,CHA,FIT=(1..4).to_a #deleat,insert,change,andfit defedit_distance(x,y,e,flag) (0..x.length-1).each{|i|e[i][0]=i} (0..y.length-1).each{|j|e[0][j]=j} diff=Array.new(x.size){Array.new(y.size)} foriin(1..x.length-1)do forjin(1..y.length-1)do diff[i][j]=(x[i]==y[j])?0:1 e[i][j]=[e[i-1][j]+1,e[i][j-1]+1,e[i-1][j-1]+diff[i][j]].min ife[i][j]==e[i-1][j]+1 flag[i][j]=DEL elsife[i][j]==e[i-1][j-1]+1 flag[i][j]=CHA elsife[i][j]==e[i][j-1]+1 flag[i][j]=INS elseflag[i][j]=FIT end end end end
out_x,out_y=[],[]
defsolution_structure(x,y,flag,i,j,out_x,out_y) caseflag[i][j] whenFIT out_x.unshift(x[i]) out_y.unshift(y[j]) solution_structure(x,y,flag,i-1,j-1,out_x,out_y) whenDEL out_x.unshift(x[i]) out_y.unshift('-') solution_structure(x,y,flag,i-1,j,out_x,out_y) whenINS out_x.unshift('-') out_y.unshift(y[j]) solution_structure(x,y,flag,i,j-1,out_x,out_y) whenCHA out_x.unshift(x[i]) out_y.unshift(y[j]) solution_structure(x,y,flag,i-1,j-1,out_x,out_y) end #ifflag[i][j]==nil,gohere returnifi==0&&j==0 ifj==0 out_y.unshift('-') out_x.unshift(x[i]) solution_structure(x,y,flag,i-1,j,out_x,out_y) elsifi==0 out_x.unshift('-') out_y.unshift(y[j]) solution_structure(x,y,flag,i,j-1,out_x,out_y) end end
edit_distance(x,y,e,flag) p"Theexpectededitdistanceis#{e[x.length-1][y.length-1]}" solution_structure(x,y,flag,x.length-1,y.length-1,out_x,out_y) puts"Theresultis:\n #{out_x}\n #{out_y}"