文本差异算法

Question

我需要一种算法,可以比较两个文本文件并突出显示它们的差异(甚至更好!)可以以有意义的方式计算它们的差异(比如两个相似的文件应该具有高于两个不同文件的相似性得分,单词"相似"以正常术语定义).它听起来很容易实现,但事实并非如此.

实现可以在c#或python中.

谢谢.

Answer 1

我可以推荐看看Neil Fraser的代码和文章:

谷歌的Diff-比赛补丁

目前提供Java,JavaScript,C++和Python.无论语言如何,每个库都具有相同的API和相同的功能.所有版本都有全面的测试工具.

Neil Fraser:差异策略 - 用于理论和实施说明

Answer 2

在Python中,有difflib,正如其他人所建议的那样.

difflib提供SequenceMatcher类,可用于为您提供相似比.功能示例:

def text_compare(text1, text2, isjunk=None):
    return difflib.SequenceMatcher(isjunk, text1, text2).ratio()

Answer 3

看看difflib.(蟒蛇)

这将以各种格式计算差异.然后,您可以使用上下文差异的大小来衡量两个文档的不同之处？

Answer 4

Bazaar包含另一种差异算法,称为耐心差异(在该页面的评论中有更多信息),据称它比传统的差异算法更好.集市发行版中的'patiencediff.py'文件是一个简单的命令行前端.

Answer 5

我目前的理解是,最短编辑脚本(SES)问题的最佳解决方案是使用Hirschberg线性空间细化的Myers"中蛇"方法.

迈尔斯算法描述于:

E.Myers,"一种O(ND)差分算法及其变化",
Algorithmica 1,2(1986),251-266.

GNU diff实用程序使用Myers算法.

您所说的"相似性得分"在文献中称为"编辑距离",即将一个序列转换为另一个序列所需的插入或删除的数量.

请注意,许多人引用了Levenshtein距离算法,但是虽然很容易实现,但不是最佳解决方案,因为它效率低(需要使用可能很大的n*m矩阵)并且不提供"编辑脚本" "这是可用于将一个序列转换为另一个序列的编辑序列,反之亦然.

有关Myers/Hirschberg的良好实施,请查看:

http://www.ioplex.com/~miallen/libmba/dl/src/diff.c

它所包含的特定库不再被维护,但据我所知,diff.c模块本身仍然是正确的.

麦克风

Answer 6

如果您需要比线条更精细的粒度,则可以使用Levenshtein距离.Levenshtein距离是关于如何将两个文本相似的直接衡量标准.
您还可以使用它来提取编辑日志,并且可以使用非常精细的差异,类似于SO的编辑历史页面上的差异.但要注意Levenshtein距离可能是CPU和内存密集型计算的,所以使用difflib,正如Douglas Leder建议的那样,很可能会更快.

参看 也是这个答案.