Ruby實現的最短編輯距離計算方法

 　　這篇文章主要介紹了Ruby實現的最短編輯距離計算方法,本文直接給出實現代碼,需要的朋友可以參考下

　　利用動態規劃算法，實現最短編輯距離的計算。

　　 代碼如下:

　　#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}"