开启辅助访问 切换到宽版

精易论坛

 找回密码
 注册

QQ登录

只需一步,快速开始

用微信号发送消息登录论坛

新人指南 邀请好友注册 - 我关注人的新帖 教你赚取精币 - 每日签到 - 下载易语言


求职/招聘- 论坛接单- 开发者大厅

论坛版规 总版规 - 建议/投诉 - 应聘版主 - 精华帖总集 积分说明 - 禁言标准 - 有奖举报

谨防被骗唯一飞机@bbs129谨防被骗唯一飞机@bbs129谨防被骗唯一飞机@bbs129谨防被骗唯一飞机@bbs129谨防被骗唯一飞机@bbs129谨防被骗唯一飞机@bbs129
谨防被骗唯一飞机@bbs129谨防被骗唯一飞机@bbs129谨防被骗唯一飞机@bbs129谨防被骗唯一飞机@bbs129谨防被骗唯一飞机@bbs129谨防被骗唯一飞机@bbs129
收神马搜gou广告资源+飞机@bbs129收海外谷ge代运营流量+飞机@bbs129长期大量收网站访客量+飞机@bbs129高价寻百du下载站流量+飞机@bbs129长期大量收网站访客量+飞机@bbs129长期大量收网站访客量+飞机@bbs129
收神马搜gou广告资源+飞机@bbs129收海外谷ge代运营流量+飞机@bbs129寻实力国内外短xin群fa+飞机@bbs129高价寻百du下载站流量+飞机@bbs129寻实力国内外短xin群fa+飞机@bbs129寻实力国内外短xin群fa+飞机@bbs129
收神马搜gou广告资源+飞机@bbs129收海外谷ge代运营流量+飞机@bbs129收国内国外协议群发粉+飞机@bbs129高价寻百du下载站流量+飞机@bbs129收国内国外协议群发粉+飞机@bbs129收国内国外协议群发粉+飞机@bbs129
收神马搜gou广告资源+飞机@bbs129收海外谷ge代运营流量+飞机@bbs129收海内外app上架流量+飞机@bbs129高价寻百du下载站流量+飞机@bbs129收海内外app上架流量+飞机@bbs129收海内外app上架流量+飞机@bbs129
收神马搜gou广告资源+飞机@bbs129收海外谷ge代运营流量+飞机@bbs129收百du搜gou广告资源+飞机@bbs129高价寻百du下载站流量+飞机@bbs129收百du搜gou广告资源+飞机@bbs129收百du搜gou广告资源+飞机@bbs129
收神马搜gou广告资源+飞机@bbs129收海外谷ge代运营流量+飞机@bbs129收海外谷gFB大搜流量+飞机@bbs129高价寻百du下载站流量+飞机@bbs129收海外谷gFB大搜流量+飞机@bbs129收海外谷gFB大搜流量+飞机@bbs129
收神马搜gou广告资源+飞机@bbs129收海外谷ge代运营流量+飞机@bbs129收越南zalo协yi群fa+飞机@bbs129高价寻百du下载站流量+飞机@bbs129收越南zalo协yi群fa+飞机@bbs129收越南zalo协yi群fa+飞机@bbs129
寻稳定短xin群fa+飞机@bbs129寻稳定短xin群fa+飞机@bbs129收巴西土耳其协yi群fa+飞机@bbs129高价收谷ge大搜流量+飞机@bbs129收巴西土耳其协yi群fa+飞机@bbs129收巴西土耳其协yi群fa+飞机@bbs129
寻稳定短xin群fa+飞机@bbs129寻稳定短xin群fa+飞机@bbs129收泰国line协yi群fa代发+飞机@bbs129高价收谷ge大搜流量+飞机@bbs129收泰国line协yi群fa代发+飞机@bbs129收泰国line协yi群fa代发+飞机@bbs129
寻稳定短xin群fa+飞机@bbs129寻稳定短xin群fa+飞机@bbs129收WhatsApp协yi群fa+飞机@bbs129高价收谷ge大搜流量+飞机@bbs129收WhatsApp协yi群fa+飞机@bbs129收WhatsApp协yi群fa+飞机@bbs129
寻稳定短xin群fa+飞机@bbs129寻稳定短xin群fa+飞机@bbs129收飞机协yi群fa+飞机@bbs129高价收谷ge大搜流量+飞机@bbs129收飞机协yi群fa+飞机@bbs129收飞机协yi群fa+飞机@bbs129
寻稳定短xin群fa+飞机@bbs129寻稳定短xin群fa+飞机@bbs129收印尼协yi群fa代发+飞机@bbs129高价收谷ge大搜流量+飞机@bbs129收印尼协yi群fa代发+飞机@bbs129收印尼协yi群fa代发+飞机@bbs129
寻稳定短xin群fa+飞机@bbs129寻稳定短xin群fa+飞机@bbs129收国内国外广告资源+飞机@bbs129高价收谷ge大搜流量+飞机@bbs129收国内国外广告资源+飞机@bbs129收国内国外广告资源+飞机@bbs129
寻稳定短xin群fa+飞机@bbs129寻稳定短xin群fa+飞机@bbs129大量收海外各种流量粉+飞机@bbs129高价收谷ge大搜流量+飞机@bbs129大量收海外各种流量粉+飞机@bbs129大量收海外各种流量粉+飞机@bbs129
没有飞机的加备用+飞机@bbs129没有飞机的加备用+飞机@bbs129没有飞机的加备用+飞机@bbs129没有飞机的加备用+飞机@bbs129没有飞机的加备用+飞机@bbs129没有飞机的加备用+飞机@bbs129
没有飞机的加备用+飞机@bbs129没有飞机的加备用+飞机@bbs129没有飞机的加备用+飞机@bbs129没有飞机的加备用+飞机@bbs129没有飞机的加备用+飞机@bbs129没有飞机的加备用+飞机@bbs129
谨防被骗唯一飞机@bbs129谨防被骗唯一飞机@bbs129谨防被骗唯一飞机@bbs129谨防被骗唯一飞机@bbs129谨防被骗唯一飞机@bbs129谨防被骗唯一飞机@bbs129
谨防被骗唯一飞机@bbs129谨防被骗唯一飞机@bbs129谨防被骗唯一飞机@bbs129谨防被骗唯一飞机@bbs129谨防被骗唯一飞机@bbs129广告招租
查看: 7412|回复: 270
收起左侧

[2022开源大赛(第七届)] 【首发】【Myers Diff】【差异纯算法】文章差异 劲爆算法

    [复制链接]

结帖率:100% (32/32)
发表于 2022-12-5 22:45:18 | 显示全部楼层 |阅读模式   江西省南昌市
分享源码
界面截图: -
是否带模块: -
备注说明: -
什么是直观的 diff
我们先简单定义一下,什么是 diff:diff 就是目标文本和源文本之间的区别,也就是将源文本变成目标文本所需要的操作。
Myers算法由Eugene W.Myers在1986年发表的一篇论文中提出,是一个能在大部分情况产生”最短的直观的“diff的一个算法。

20190508161434.png

diff 与图搜索
”寻找最短的直观的diff”是一个非常模糊的问题,首先,我们需要把这个问题抽象为一个具体的数学问题,然后再来寻找算法解决。抽象的过程交给算法科学家了,抽象的结果是:寻找diff的过程可以被表示为图搜索
什么意思呢?还是以两个字符串,src=ABCABBA,dst=CBABAC为例,根据这两个字符串我们可以构造下面一张图,横轴是src内容,纵轴是dst内容,那么图中每一条从左上角到右下角的路径,都表示一个diff。向右表示删除,向下表示新增,对角线则表示原内容保持不动
9b85365dgy1ffjxfo7r42j20lm0nudhx.jpg
根据图中形成的线路,我们可以选择一条路径看看它的效果
  • (0, 0) -> (1, 0)
  • (1, 0) -> (2, 0) -> (3, 1)
  • (3, 1) -> (3, 2) -> (4, 3) -> (5, 4)
  • (5, 4) -> (6, 4) -> (7, 5)
  • (7, 5) -> (7, 6)



这条路径代表的 diff 如下:
- A- B  C+ B  A  B- B  A+ C

  • 现在,“寻找 diff” 这件事,被抽象成了“寻找图的路径”了。那么,“最短的直观的” diff 对应的路径有什么特点呢?

    • 路径长度最短(对角线不算长度)
    • 先向右,再向下(先删除,后新增)






三个概念
根据 Myers 的论文,他提出了三个概念:
  • snake: 一条snake代表走一步。例如从(0,0)->(0,1) / (0,0)->(1,0) / (0,1)->(0,2)->(2,4) 这分别为三条snake,走对角线不计入步数
  • k line: 定义 k = x - y (我们可以写成 y = x - k,是相同斜率的平行斜线组成的一个集合)
  • d contour: 走一步算一个d

20190508092808.png


Myers 算法
Myers 算法就是一个能在大部分情况产生”最短的直观的“ diff 的一个算法,算法原理如下。


  • 首先,定义参数 d 和 k,d 代表路径的长度,k 代表当前坐标 x - y 的值。定义一个”最优坐标“的概念,最优坐标表示 d 和 k 值固定的情况下,x 值最大的坐标。x 大,表示向右走的多,表示优先删除。
  • 还是用上面那张图为例。我们从坐标 (0, 0) 开始,此时,d=0,k=0,然后逐步增加 d,计算每个 k 值下对应的最优坐标。
  • 因为每一步要么向右(x + 1),要么向下(y + 1),对角线不影响路径长度,所以,当 d=1 时,k 只可能有两个取值,要么是 1,要么是 -1。
  • 当 d=1,k=1 时,最优坐标是 (1, 0)。
  • 当 d=1,k=-1 时,最优坐标是 (0, 1)。
  • 因为 d=1 时,k 要么是 1,要么是 -1,当 d=2 时,表示在 d=1 的基础上再走一步,k 只有三个可能的取值,分别是 -2,0,2。
  • 当 d=2,k=-2 时,最优坐标是 (2, 4)。
  • 当 d=2,k=0 时,最优坐标是 (2, 2)。
  • 当 d=2,k=2 时,最优坐标是 (3, 1)。
  • 以此类推,直到我们找到一个 d 和 k 值,达到最终的目标坐标 (7, 6)。
  • 下图横轴代表 d,纵轴代表 k,中间是最优坐标,从这张图可以清晰的看出,当 d=5,k=1 时,我们到达了目标坐标 (7, 6),因此,”最短的直观的“路径就是 (0, 0) -> (1, 0) -> (3, 1) -> (5, 4) -> (7, 5) -> (7, 6),对应的 diff 如下。


9b85365dgy1ffjz1967znj20p20k9gmg.jpg
现在我们可以知道,其实 Myers 算法是一个典型的”动态规划“算法,也就是说,父问题的求解归结为子问题的求解。要知道 d=5 时所有 k 对应的最优坐标,必须先要知道 d=4 时所有 k 对应的最优坐标,要知道 d=4 时的答案,必须先求解 d=3,以此类推。

实现
算法原理知道以后,实现便是一件简单的事情了,基本流程如下:

  • 迭代 d,d 的取值范围为 0 到 n+m,其中 n 和 m 分别代表源文本和目标文本的长度(这里我们选择以行为单位)
  • 每个 d 内部,迭代 k,k 的取值范围为 -d 到 d,以 2 为步长,也就是 -d,-d + 2,-d + 2 + 2…
  • 使用一个字典 v,以 k 值为索引,存储最优坐标的 x 值
  • 将每个 d 对应的 v 字典存储起来,后面回溯的时候需要用
  • 当我们找到一个 d 和 k,到达目标坐标 (n, m) 时就跳出循环
  • 使用上面存储的 v 字典(每个 d 对应一个这样的字典),从终点反向得出路径


  • 最后补充一句,市面上使用的是标准 Myers 算法的一个变体。标准的算法有一个很大的缺点,就是空间消耗很大,因为我们需要存储每一个 d 对应的 v 字典。如果输入文件比较大,这样的空间开销是不能接受的。因此 Myers 在他的 论文 中,同时提供了一个算法变体,这个变体需要的空间开销要小得多。但是在某些情况下,变体产生的 diff 会和标准算法有所不同。也就是说,如果你按照上面的算法实现的程序,出来的结果和市面上的结果有所不同是正常的。



参考资料
The Myers diff algorithm: part 1


源码下载
两个版本:
版本1 无窗口: Myers diff 无窗口.e (24.2 KB, 下载次数: 127)

点评

算法很牛,希望有大神能优化下,字多会算很久。   四川省遂宁市  发表于 2022-12-9 18:38
我以为我在研究论文,提供的资料我还以为是文献   安徽省合肥市  发表于 2022-12-8 15:44
按理来说是不会越界的,,如果越界了,说明你自己改了那个方法:类-路径节点-导出文本型   江西省南昌市  发表于 2022-12-7 10:18
路径节点.取上一个节点,出现数组越界错误,局部变量buff是空数组,麻烦修复一下   辽宁省沈阳市  发表于 2022-12-7 08:23

评分

参与人数 37好评 +28 精币 +59 收起 理由
无尘666 + 1 感谢分享,很给力!~
MrSimple + 1 + 2 支持开源~!感谢分享
qiyuer + 1 感谢分享,很给力!~
mumulu + 1 感谢分享,很给力!~
苕皮哥哥 + 1 + 2 YYDS~!
单排练心态 + 1 + 1 YYDS~!
2015易语言 + 1 感谢分享,很给力!~
Arui + 1 感谢分享,很给力!~
深蓝浅蓝 + 1 感谢分享,很给力!~
闻v风 + 1 + 1 算法很不牛,可惜速度有点慢了,字数一多计算好久才结束
陽陽陽 + 1 牛逼牛逼,昨天没币了
易语言资源网 + 1 + 3 开源精神必须支持~
ku2017 + 1 支持开源~!感谢分享
Bszk + 1 + 3 感谢分享,很给力!~
风清云游 + 1 + 2 支持开源~!感谢分享
飞腾小子 + 1 + 2 YYDS~!
zhouzhanfan + 1 + 2 开源精神必须支持~
悟桐的深思 + 1 感谢分享,很给力!~
llxx123 + 1 + 2 支持开源~!感谢分享
StarAdmire + 1 + 2 YYDS~!
无艸忘居 + 1 + 2 YYDS~!
商亨人和 + 1 支持开源~!感谢分享
六先生 + 1 新技能已get√
794229345 + 1 + 1 YYDS~!
xxdahai + 1 + 1 看着就牛逼
benbenyw + 1 + 2 开源还讲原理!老哥诚意十足啊
国王软件 + 1 + 2 支持开源~!感谢分享
zg2600 + 1 + 2 支持开源~!感谢分享
sinewtec + 1 + 2 支持开源~!感谢分享
Orzlee + 1 + 2 新技能已get√
hrb011011 + 1 支持开源~!感谢分享
910265444 + 1 支持开源~!感谢分享
romantic + 1 + 2 支持开源~!感谢分享
冰点 + 1 + 3 感谢分享,很给力!~
凌哥 + 1 + 5 支持开源~!感谢分享
Onsxsen + 1 + 2 支持开源~!感谢分享
远赴 + 1 + 2 YYDS~!

查看全部评分


本帖被以下淘专辑推荐:

结帖率:0% (0/4)

签到天数: 1 天

发表于 3 天前 | 显示全部楼层   上海市上海市
感谢分享!
回复 支持 反对

使用道具 举报

签到天数: 1 天

发表于 3 天前 | 显示全部楼层   江苏省苏州市
牛逼。。。。。
回复 支持 反对

使用道具 举报

发表于 2023-1-15 02:30:37 | 显示全部楼层   广东省广州市
标准的算法有一个很大的
回复 支持 反对

使用道具 举报

发表于 2023-1-15 02:28:22 | 显示全部楼层   广东省广州市

感谢分享,很给力!~
回复 支持 反对

使用道具 举报

签到天数: 5 天

发表于 2023-1-13 10:00:27 | 显示全部楼层   浙江省杭州市

++

6666666666666666666
回复 支持 反对

使用道具 举报

结帖率:95% (314/332)

签到天数: 1 天

发表于 2023-1-2 14:49:05 | 显示全部楼层   福建省泉州市
支持开源!感谢分享,论坛有你更精彩~
回复 支持 反对

使用道具 举报

结帖率:95% (20/21)
发表于 2022-12-31 16:23:48 | 显示全部楼层   重庆市重庆市
能不能计算两段文本差异度的百分比

点评

分词。。我只知道python的jieba分词 然后简单的余弦相似度。。不简单吧   重庆市重庆市  发表于 2023-1-16 23:27
那个直接分词后简单的余弦相似度就好了   广东省东莞市  发表于 2023-1-15 19:03
回复 支持 反对

使用道具 举报

结帖率:95% (20/21)
发表于 2022-12-31 15:52:42 | 显示全部楼层   重庆市重庆市
算法原理知道以后,实现便是一件简单的事情了
回复 支持 反对

使用道具 举报

结帖率:100% (5/5)

签到天数: 1 天

发表于 2022-12-30 18:05:07 | 显示全部楼层   广东省肇庆市
差异纯算法】文章差异 劲爆算法
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则 致发广告者

发布主题 收藏帖子 返回列表

sitemap| 易语言源码| 易语言教程| 易语言论坛| 诚聘英才| 易语言模块| 手机版| 联系我们| 精易论坛
拒绝任何人以任何形式在本论坛发表与中华人民共和国法律相抵触的言论,本站内容均为会员发表,并不代表精易立场!
论坛帖子内容仅用于技术交流学习和研究的目的,严禁用于非法目的,否则造成一切后果自负!如帖子内容侵害到你的权益,请联系我们!
揭阳精易科技有限公司申明:我公司所有的培训课程版权归精易所有,任何人以任何方式翻录、盗版、破解本站培训课程,我们必将通过法律途径解决!
公司简介:揭阳市揭东区精易科技有限公司致力于易语言教学培训/易语言学习交流社区的建设与软件开发,多年来为中小企业编写过许许多多各式软件,并把多年积累的开发经验逐步录制成视频课程供学员学习,让学员全面系统化学习易语言编程,少走弯路,减少对相关技术的研究与摸索时间,从而加快了学习进度!
防范网络诈骗,远离网络犯罪 违法和不良信息举报电话0663-3422125,QQ: 800073686,邮箱:800073686@b.qq.com
Powered by Discuz! X3.4 揭阳市揭东区精易科技有限公司 ( 粤ICP备12094385号-1) 粤公网安备 44522102000125 增值电信业务经营许可证 粤B2-20192173

快速回复 返回顶部 返回列表