首页 爱情文章 亲情文章 友情文章 生活随笔 校园文章 经典文章 人生哲理 励志文章 搞笑文章 心情日记
  • 爱情文章
  • 亲情文章
  • 友情文章
  • 生活随笔
  • 校园文章
  • 经典文章
  • 人生哲理
  • 励志文章
  • 搞笑文章
  • 心情日记
  • 英语文章
  • 范文大全
  • 作文大全
  • 新闻阅读
    •
    当前位置: 山茶花美文网 > 范文大全 > 正文

    [Ruby实现的最短编辑距离计算方法]最短距离问题

    时间：2020-05-13来源：山茶花美文网 本文已影响 人 山茶花美文网手机站

    这篇文章主要介绍了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}"

    • [Ruby实现的最短编辑距离计算方法]最短距离问题 相关文章:
    • 爱情文章
    • 亲情文章
    • 友情文章
    • 随笔
    • 哲理
    • 励志
    • 范文大全

    最新文章

    热点文章

    推荐访问

    军训远足心得体会 军训爬山心得体会 大学军训徒步拉练感想 军训徒步作文 军训徒步10公里感想 军训徒步心得体会 5分钟演讲中秋节节日 中秋一分钟演讲 中秋节演讲稿4分钟 中秋节演讲稿一分钟 中秋节演讲稿五分钟 3-5分钟 中秋节短篇演讲稿 中秋节演讲稿两分钟 中秋节的演讲稿3分钟 关于中秋节的演讲稿三分钟 孩子体验军训的心得 参加孩子军训活动的感受与收获 家长对孩子军训后的收获和感悟 小孩军训的收获与感悟 学生军训的收获与感悟 孩子军训成长过程家长感悟 孩子军训感悟 孩子军训心得体会 孩子军训的收获与感悟 兵役前训练心得体会 部队当兵的心得 新兵役前教育训练心得体会 预备役军训心得体会 新兵军训感悟

    本文[Ruby实现的最短编辑距离计算方法]最短距离问题由山茶花美文网整理提供，版权归原作者、原出处所有。

    Copyright © 山茶花美文网 All Rights Reserved.