欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Ruby实现的最短编辑距离计算方法

程序员文章站 2022-11-15 18:56:48
利用动态规划算法,实现最短编辑距离的计算。 复制代码 代码如下: #encoding: utf-8 #author: xu jin #date: nov 12, 2...

利用动态规划算法,实现最短编辑距离的计算。

复制代码 代码如下:

#encoding: utf-8
#author: xu jin
#date: nov 12, 2012
#editdistance
#to find the minimum cost by using editdistance algorithm
#example output:
#  "please input a string: "
#  exponential
#  "please input the other string: "
#  polynomial
#  "the expected cost is 6"
#  the result is :
#    ["e", "x", "p", "o", "n", "e", "n", "-", "t", "i", "a", "l"]
#    ["-", "-", "p", "o", "l", "y", "n", "o", "m", "i", "a", "l"]

p "please input a string: "
x = gets.chop.chars.map{|c| c}
p "please input the other string: "
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, and fit
 
def edit_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)}
  for i in(1..x.length - 1) do
    for j in(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
      if e[i][j] == e[i-1][j] + 1
        flag[i][j] = del
      elsif e[i][j] == e[i-1][j - 1] + 1
        flag[i][j] = cha
      elsif e[i][j] == e[i][j - 1] + 1
        flag[i][j] = ins      
      else flag[i][j] = fit
      end    
    end
  end 
end

out_x, out_y = [], []

def solution_structure(x, y, flag, i, j, out_x, out_y)
  case flag[i][j]
  when fit
    out_x.unshift(x[i])
    out_y.unshift(y[j]) 
    solution_structure(x, y, flag, i - 1, j - 1, out_x, out_y)
  when del
    out_x.unshift(x[i])
    out_y.unshift('-')
    solution_structure(x, y, flag, i - 1, j, out_x, out_y)
  when ins
    out_x.unshift('-')
    out_y.unshift(y[j])
    solution_structure(x, y, flag, i, j - 1, out_x, out_y)
  when cha
    out_x.unshift(x[i])
    out_y.unshift(y[j])
    solution_structure(x, y, flag, i - 1, j - 1, out_x, out_y)
  end
  #if flag[i][j] == nil ,go here
  return if i == 0 && j == 0   
  if j == 0
      out_y.unshift('-')
      out_x.unshift(x[i])
      solution_structure(x, y, flag, i - 1, j, out_x, out_y)
  elsif i == 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 "the expected edit distance is #{e[x.length - 1][y.length - 1]}"
solution_structure(x, y, flag, x.length - 1, y.length - 1, out_x, out_y)
puts "the result is : \n  #{out_x}\n  #{out_y}"