42

我需要一种算法，可以比较两个文本文件并突出它们的差异，并且（甚至更好！）可以以有意义的方式计算它们的差异（比如两个相似文件的相似度分数应该高于两个不同的文件，用“相似”这个词以正常术语定义）。这听起来很容易实现，但事实并非如此。

实现可以在 c# 或 python 中。

谢谢。

4

11 回答 11

30

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

谷歌差异匹配补丁

目前可用于 Java、JavaScript、C++ 和 Python。无论使用哪种语言，每个库都具有相同的 API 和相同的功能。所有版本还具有全面的测试工具。

尼尔弗雷泽：差异策略- 理论和实施说明

于 2008-09-28T11:04:31.520 回答
26

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

difflib提供SequenceMatcher类，可用于为您提供相似率。示例函数：

def text_compare(text1, text2, isjunk=None):
    return difflib.SequenceMatcher(isjunk, text1, text2).ratio()
于 2008-09-28T23:02:33.917 回答
23

看看difflib。（Python）

这将计算各种格式的差异。然后，您可以使用上下文差异的大小来衡量两个文档的差异程度？

于 2008-09-28T10:14:43.793 回答
12

我目前的理解是，最短编辑脚本 (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 模块本身仍然是正确的。

麦克风

于 2009-01-26T00:44:40.810 回答
10

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

于 2008-09-28T10:35:02.603 回答
5

如果您需要比线条更细的粒度，则可以使用 Levenshtein 距离。Levenshtein 距离是关于如何相似两个文本的直接度量。
您还可以使用它来提取编辑日志，并且可以进行非常细粒度的差异，类似于 SO 的编辑历史页面上的差异。请注意，尽管 Levenshtein 距离计算起来可能会占用大量 CPU 和内存，因此正如 Douglas Leder 所建议的那样，使用 difflib 很可能会更快。

参照。也是这个答案。

于 2008-09-28T10:27:49.440 回答
3

有许多距离指标，正如 paradoja 提到的，有 Levenshtein 距离，但也有NYSIIS和Soundex。在 Python 实现方面，我之前使用过py-editdist和ADVAS。从某种意义上说，两者都很好，因为您可以将一个数字作为分数返回。先看看 ADVAS，它实现了一堆算法。

于 2008-09-28T19:21:45.303 回答
2

如前所述，使用 difflib。一旦你得到了不同的输出，你可能会发现不同字符串的Levenshtein 距离，以便给出它们之间差异程度的“值”。

于 2008-09-28T10:33:09.083 回答
1

您可以使用最长公共子序列 (LCS) 问题的解决方案。另请参阅有关优化此解决方案的可能方法的讨论。

于 2009-12-21T01:31:09.693 回答
0

我为不同的功能采用的一种方法是计算修改后的文件中有多少新数据，也许对您也有用。

我有一个差异/补丁实现 C#，它允许我获取两个文件，大概是同一文件的旧版本和新版本，并计算“差异”，但不是通常意义上的。基本上，我计算了一组可以在旧版本上执行的操作，以将其更新为与新版本具有相同的内容。

为了将它用于最初描述的功能，查看有多少新数据，我简单地运行了操作，并且对于从旧文件逐字复制的每个操作，具有 0 因子，以及插入新文本的每个操作（作为补丁的一部分分发，因为它没有出现在旧文件中）有一个 1 因素。所有字符都被赋予了这个工厂，它基本上给了我一长串 0 和 1 的列表。

然后我所要做的就是计算 0 和 1。在您的情况下，通过我的实现，与 0 相比，1 的数量较少意味着文件非常相似。

此实现还将处理修改后的文件从旧文件中插入副本的情况，甚至是重复的（即，您从文件开头复制一部分并将其粘贴到底部附近），因为它们都是旧文件中相同原始部分的副本。

我尝试了称重副本，以便第一个副本计为 0，并且相同字符的后续副本具有逐渐更高的因子，以便为复制/粘贴操作提供一些“新因子”，但我从未完成它作为项目被取消。

如果您有兴趣，可以从我的 Subversion 存储库中获得我的差异/补丁代码。

于 2009-12-21T01:39:30.260 回答
0

看看Fuzzy模块。它具有用于 soundex、NYSIIS 和双变音器的快速（用 C 语言编写）算法。

一个很好的介绍可以在：http ://www.informit.com/articles/article.aspx?p=1848528

于 2012-04-03T12:11:29.180 回答