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

赞 (0)

相关推荐

  • Ruby实现的合并排序算法

    算法课的作业,利用分治法,合并排序. #encoding: utf-8 #author: xu jin, 4100213 #date: Oct 27, 2012 #MergeSort #to sort an array by using MergeSort algorithm #example output: #The original array is:[4, 32, 84, 58, 49, 40, 75, 29, 82, 21, 70, 37, 70] #The sorted array i

  • Ruby一行代码实现的快速排序

    复制代码 代码如下: def quick_sort(a) return a if a.size < 2 (x = a.pop) ?  quick_sort(a.select{|i| i <=x }) + [x] + quick_sort(a.select{|i| i > x}) : [] end array = [72,6,57,88,60,42,83,73,42,48,85] p quick_sort(array)    #=> [6, 42, 42, 48, 57, 60, 7

  • Ruby实现的3种快速排序算法

    刚学Ruby,正巧算法老师鼓励用不熟悉的语言来写算法,我就用Ruby吧~~ 话说Ruby可真是超厉害,好多凭直觉的方法都可以用.....无限膜拜中.... 期间我遇到了invalid multibyte char (US-ASCII)的错误,解决办法是在开头加一个#encoding:utf-8 这个错误在stackoverflow上有人问到过,某人给出的回答是 Write # encoding: utf-8 on top of that file. That changes the defaul

  • ruby实现的插入排序和冒泡排序算法

    1.插入排序 复制代码 代码如下: seq = [3,4,9,0,2,5,9,7,1] 1.upto(seq.length-1) do |i|  if seq[i] < seq[i-1]    tmp = seq[i]    j = i-1    while(j>=0 && tmp<seq[j]) do      seq[j+1] = seq[j]      j=j-1    end    seq[j+1]=tmp  endend seq.each {|num| puts

  • Ruby实现的各种排序算法

    时间复杂度:Θ(n^2) Bubble sort 复制代码 代码如下: def bubble_sort(a)    (a.size-2).downto(0) do |i|      (0..i).each do |j|        a[j], a[j+1] = a[j+1], a[j] if a[j] > a[j+1]      end    end    return a  end Selection sort 复制代码 代码如下: def selection_sort(a)    b =

  • Ruby实现的最长公共子序列算法

    最长公共子序列,LCS,动态规划实现. #encoding: utf-8 #author: xu jin, 4100213 #date: Nov 01, 2012 #Longest-Commom-Subsequence #to find a longest commom subsequence of two given character arrays by using LCS algorithm #example output: #The random character arrays are

  • Ruby最简单的消息服务器代码

    ser.rb 复制代码 代码如下: require 'socket's = TCPServer.new 3333conn = s.acceptloop do    puts conn.getsend clt.rb 复制代码 代码如下: require 'socket's = TCPSocket.new 'localhost',3333loop do    sms=gets.chomp    s.puts smsend 作者:Hevienz

  • Ruby实现的最优二叉查找树算法

    算法导论上的伪码改写而成,加上导论的课后练习第一题的解的构造函数. 复制代码 代码如下: #encoding: utf-8 =begin author: xu jin date: Nov 11, 2012 Optimal Binary Search Tree to find by using EditDistance algorithm refer to <<introduction to algorithms>> example output: "k2 is the r

  • Ruby的字符串与数组求最大值的相关问题讨论

    max方法 b=[1,3,55,777,2,4,6,8,0] 对于数值型的数据,max会得到数组的最大值,min得到数组的最小值 b.max => 777 b.min => 0 而对于字符串型数组比较大小没有实际意义, ruby中给出的例子是 # enum.max -> obj # enum.max { |a, b| block } -> obj #a = %w(albatross dog horse) #a.max => "horse" # a.max

  • 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

  • Ruby入门介绍第1/5页

    一.方法 Ruby 的方法定义允许为参数设置默认值,不过在带有默认值的参数后面不能出现不带有默认值的参数(允许 * 和 &),也就是说下面的方法定义是不被允许的,解释时会出现 parse error. 还有一点与 C# 不同的是,方法定义不能出现在方法调用的后面. # parse error def Display(args1="proshea", args2) end # 允许 def Display(args1="proshea", *args2) en

  • ruby中并发并行与全局锁详解

    前言 本文主要给大家介绍了关于ruby并发并行和全局锁的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧. 并发和并行 在开发时,我们经常会接触到两个概念: 并发和并行,几乎所有谈到并发和并行的文章都会提到一点: 并发并不等于并行.那么如何理解这句话呢? 并发: 厨师同时接收到了2个客人点了的菜单需要处理. 顺序执行: 如果只有一个厨师,那么他只能一个菜单接着一个菜单的去完成. 并行执行: 如果有两个厨师,那么就可以并行,两个人一起做菜. 将这个例子扩展到我们的web开发

  • 如何利用Ruby简单模拟Lambda演算详解

    如何利用Ruby简单模拟Lambda演算详解

    前言 最近看一本叫做<计算的本质>的书,这本书主要说了一些底层计算方面的知识.可以说它刷新了我的三观,而当今天看到可以使用Y组合子来实现递归的时候我的世界观基本崩塌了.故借着七夕来写一篇文章总结一些关于计算的一些基本认识.以便后续可以更好地学习.也借着Ruby的语法来阐述一下关于Lambda的一些故事. 0. 题外话 为了庆祝一下这个七夕节日,我提前关掉了LOL,打开了Emacs,敲下如下代码(这里顺便推广一下Ruby的单件方法) subject = "情侣" object

  • win10下使用virtualbox + vagrant配置ruby开发机环境

    在写本文前,笔者已经尝试了多种其他的替代方法,例如wmware虚拟机安装kylin.然而发现总是还有各种问题.经大佬指点安装了virtualbox + vagrant.于是发现配置起来如此简单.接下来笔者将详细阐述. (注:笔者自己的服务器上的配置是centos7.2 + ruby2.3.4 + mariadb + redis,自己的笔记本为win10,另外,很多网上的类似文章都写于很长时间以前,很多内容现在已经不适用,甚至很多关键的环节还不讲清楚,导致笔者配置初期踩了很多的坑.所以写下此文,总

  • win7下从ruby源代码编译安装的方法

    工作中需要在c++代码中嵌入ruby c api,然而在vs工程中编译失败,所以现在通过手动从源代码编译ruby寻找原因(之前使用rubyinstaller安装). 先从官网下载ruby 2.4.1 版本,https://www.ruby-lang.org/en/downloads/ 从安装指导可以看到,官方只提供了linux平台下的编译安装步骤,https://www.ruby-lang.org/en/documentation/installation/#building-from-sour

  • ruby on rails中Model的关联详解

    前言: 在学习model关联之前,首先要牢记一下几点: 1.关联关系,两端都要写好,否则会出现初学者看不懂的错误.而且对于理解代码,非常有好处. 2.model的名字是单数,controller是复数. 3.blong_to后面必须是单数,而且必须是小写.has_many后面必须是复数. 一:一对多 例如: 王妈妈有两个孩子,小明和小亮.可以说,王妈妈,有多个孩子.也可以说:小明,有一个妈妈;小王,有一个妈妈.我们一般在设计表的时候,是这样设计的: mothers表中id和name sons表中

  • 使用RVM实现控制切换Ruby/Rails版本

    在学习Ruby on Rails的过程中,不同教程使用的Ruby和Rails版本不一样,为了保持和教程中使用的版本一致,我们可以用RVM(Ruby Version Manager)来控制当前的Ruby/Rails版本,方便切换. RVM的安装在这里不是重点,不懂的话可以参考: 如何快速正确的安装 Ruby, Rails 运行环境. 安装其他版本Ruby 安装当前最新版本2.4.1 $ rvm install 2.4.1 查看目前安装的Ruby版本 $ rvm list 切换到指定版本(前提是已安

  • 每个程序员都应该学习使用Python或Ruby

    每个程序员都应该学习使用Python或Ruby

    如果你是个学生,你应该会C,C++和Java.还会一些VB,或C#/.NET.多少你还可能开发过一些Web网页,你知道一些HTML,CSS和JavaScript知识.总体上说,我们很难发现会有学生显露出掌握超出这几种语言范围外的语言的才能.这真让人遗憾,因为还有很多种编程语言,它们能让你成为一个更好的程序员. 在这篇文章里,我将会告诉你,为什么你一定要学习Python或Ruby语言. 跟C/C++/Java相比 - Python/Ruby能让你用少的多的多的代码写出相同的程序.有人计算过,Pyt

  • Ruby 中的 module_function 和 extend self异同

    在阅读开源的 Ruby 代码和编写可维护性的代码经常遇到这两者的使用,那么他们两者的共同点和区别是什么呢? module_function Ruby 的 module 是 method 和 constants 的集合.module 中的method 又可分为 instance method 和 module method, 当一个 module 被 include 进一个 class ,那么 module 中的 method (注:没有被 module_function 标记的 method)就

随机推荐