Sweet Snippet 之 字符串编辑距离

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/tkokof1/article/details/100709721

字符串编辑距离的简单实现

字符串编辑距离应该是动态规划中的代表问题了:

给定两个字符串 aaa 与 bbb,求解将 aaa 编辑至 bbb 的操作步数(距离),编辑包含以下两种操作:

  • 删除某一字符
  • 增加某一字符

(这里我们不允许变更某一字符,注意一下)

求解方法则是根据子问题的结果"递推"出原问题的结果:

设字符串 aaa 的长度为 mmm, 字符串 bbb 的长度为 nnn, 我们定义问题 C(i,j)C(i, j)C(i,j)

C(i,j)C(i, j)C(i,j) : aaa 的(前缀)子串(长度为 iii) 与 bbb 的(前缀)子串(长度为 jjj) 的字符串编辑距离.

接着就是 C(i,j)C(i, j)C(i,j) 的递推公式了(这里就不做细节的讲述了,不熟悉的朋友可以参考进一步的资料)

C(i,j)={i,if j=0j,if i=0C(i−1,j−1),if a[i]=b[j]min(C(i−1,j),C(i,j−1))+1,otherwise C(i, j) = \left\{ \begin{aligned} % & 0, & if \ i = 0\ and\ j = 0 \\ & i, & if \ j = 0 \\ & j, & if \ i = 0 \\ & C(i - 1, j - 1), & if\ a[i] = b[j] \\ & min(C(i - 1, j), C(i, j - 1)) + 1, & otherwise \end{aligned} \right. C(i,j)=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​​i,j,C(i−1,j−1),min(C(i−1,j),C(i,j−1))+1,​if j=0if i=0if a[i]=b[j]otherwise​

下面简单列份实现(Lua):

-- get key from two index
function get_key(m, n)
    return m .. "_" .. n
end

function edit_dist_iter(a, b, m, n)
    local edit_dist_buffer = {}
    
    edit_dist_buffer[get_key(0, 0)] = 0
    
    for i = 1, m do
        edit_dist_buffer[get_key(i, 0)] = i
    end
    
    for i = 1, n do
        edit_dist_buffer[get_key(0, i)] = i
    end
    
    for i = 1, m do
        for j = 1, n do
            local ac = a:sub(i, i)
            local bc = b:sub(j, j)
            if ac == bc then
                edit_dist_buffer[get_key(i, j)] = edit_dist_buffer[get_key(i - 1, j - 1)]
            else
                local d1 = edit_dist_buffer[get_key(i - 1, j)]
                local d2 = edit_dist_buffer[get_key(i, j - 1)]
                edit_dist_buffer[get_key(i, j)] = math.min(d1, d2) + 1
            end
        end
    end
    
    return edit_dist_buffer[get_key(m, n)]
end

function edit_dist(a, b)
    return edit_dist_iter(a, b, #a, #b)
end

以上的代码使用了迭代形式,我们也可以用递归形式(来编写代码),只是递归会引起不少的重复计算,所以(工程)实现上,我们需要使用缓存来记录计算过的子问题结果(迭代版本也使用了缓存,作用上和递归版本其实也是一致的,记录的也是子问题的结果):

-- get key from two index
function get_key(m, n)
    return m .. "_" .. n
end

function edit_dist_recur(a, b, m, n, buffer)
    if m <= 0 then
        -- result is trivial, do not need buffer
        return n
    elseif n <= 0 then
        -- result is trivial, do not need buffer
        return m
    else
        local ac = a:sub(m, m)
        local bc = b:sub(n, n)
        if ac == bc then
            local d = buffer[get_key(m - 1, n - 1)]
            if d then
                buffer[get_key(m, n)] = d
                return d
            else
                local d = edit_dist_recur(a, b, m - 1, n - 1, buffer)
                buffer[get_key(m, n)] = d
                return d
            end
        else
            local d1 = buffer[get_key(m - 1, n)]
            if not d1 then
                d1 = edit_dist_recur(a, b, m - 1, n, buffer)
            end
            
            local d2 = buffer[get_key(m, n - 1)]
            if not d2 then
                d2 = edit_dist_recur(a, b, m, n - 1, buffer)
            end
            
            local d = math.min(d1, d2) + 1
            buffer[get_key(m, n)] = d
            return d
        end
    end
end

function edit_dist(a, b)
    -- create buffer
    local edit_dist_buffer = {}
    return edit_dist_recur(a, b, #a, #b, edit_dist_buffer)
end

另外还看到一种基于编辑图(Edit Graph)的实现方式,不过思路上仍然和之前的讲述是一致的,实现上则会更复杂些,在此就不列代码了~

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏高性能服务器开发

C++ 如何进阶?如何准备 C++ 面试?

在大多数开发或者准开发人员的认识中,C/C++ 是一门非常难的编程语言,很多人知道它的强大,但因为认为“难”造成的恐惧让很多人放弃。

28620
来自专栏奇点大数据

AI换脸ZAO一晚,成本烧掉几百万

8月30日上午10点半左右,正在使用ZAO的用户发现,想要生成一段新的AI换脸视频,已经不是等待几秒、排队第几位的问题,而是——

57930
来自专栏AI科技大本营的专栏

经典不过时,回顾DeepCompression神经网络压缩

导读:本文作者为我们详细讲述了 ICLR 2016 的最佳论文 Deep Compression 中介绍的神经网络压缩方法。

19310
来自专栏前端自习课

【JS】336- 拆解 JavaScript 中的异步模式

JavaScript 中有很多种异步编程的方式。callback、promise、generator、async await 甚至 RxJS。我最初接触不同的异...

9930
来自专栏苦逼的码农

从外由内剖析一道腾讯面试算法题

前几天在网上看到一份鹅场的面试题,算法部分大半是动态规划,最后一题就是写一个计算编辑距离的函数,今天就专门写一篇文章来探讨一下这个经典问题。

16210
来自专栏数据云团

Django实战-小程序端注销和获取状态

Django网络应用开发的5项基础核心技术包括模型(Model)的设计,URL 的设计与配置,View(视图)的编写,Template(模板)的设计和Form(...

14120
来自专栏磐创AI技术团队的专栏

深度强化学习(DRL)专栏(一)

【磐创AI导读】:本篇文章是深度强化学习专栏的第一篇,讲了引言和强化学习基础知识,希望对大家有所帮助。查看上篇关于本专栏的介绍:深度强化学习(DRL)专栏开篇。...

19120
来自专栏数据云团

Django实战-服务端登录验证-下

Django网络应用开发的5项基础核心技术包括模型(Model)的设计,URL 的设计与配置,View(视图)的编写,Template(模板)的设计和Form(...

12520
来自专栏高性能服务器开发

一个 WebSocket 服务器是如何开发出来的?

WebSocket 协议是为了解决 http 协议的无状态、短连接(通常是)和服务端无法主动给客户端推送数据等问题而开发的新型协议,其通信基础也是基于 TCP。...

13620
来自专栏全栈者

「从源码中学习」面试官都不知道的Vue题目答案

当回答面试官问及的Vue问题,我们除了照本宣科的回答外,其实还可以根据少量的源码来秀一把,来体现出你对Vue的深度了解。

8810

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励