文本差异算法

Question

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

该实现可以在c＃或python中执行。

谢谢。

Answer 1

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

difflib提供了SequenceMatcher类，它可以用来给你一个相似比。实施例的功能：

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

Answer 2

看看difflib。 （Python）

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

Answer 3

如果您需要比线更细的粒度，您可以使用Levenshtein距离。 Levenshtein距离是关于如何类似两个文本的直接测量。
您也可以使用它来提取编辑日志，并且可以使用非常细致的差异，类似于SO的编辑历史记录页面上的差异。 虽然Levenshtein距离可能需要相当CPU和内存密集度来计算，但是正如Douglas Leder所说，使用difflib最有可能会更快。

参考也this answer。

Answer 4

如上所述，使用difflib。一旦你有了差异输出，你可以找到不同字符串的Levenshtein distance，以给出它们有多不同的“值”。

Answer 5

Bazaar包含一个替代差异算法，称为patience diff（在该页面的评论中有更多信息），声称它比传统的差异算法更好。 bazaar发行版中的文件“patiencediff.py”是一个简单的命令行前端。

Answer 6

我可以推荐给看看尼尔·弗雷泽的代码和文章：

google-diff-match-patch

目前在Java中可用， 的JavaScript，C++和Python。不管 的语言，每个库都具有相同的API和相同的功能 。 所有版本也有全面的 测试线束。

Neil Fraser: Diff Strategies - 对理论和实现指出

Answer 7

有一些距离度量，如paradoja提到存在Levenshtein距离，但也有NYSIIS和Soundex。在Python实现方面，我以前使用过py-editdist和ADVAS。两者都很好，因为你可以得到一个单数作为分数。先看看ADVAS，它实现了一堆算法。

Answer 8

我目前的理解是，最短编辑脚本（SES）的问题的最佳解决方案是Myers“中间蛇”方法与海森堡线性空间细化。

E.斯堡，``的O（ND）差分 算法及其变化， ''
Algorithmica 1，2（1986），251-266：

迈尔斯算法中所描述。

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

您所说的“相似性分数”在文献中被称为“编辑距离”，即将一个序列转换为另一个序列所需的插入或删除次数。

请注意，许多人引用了Levenshtein距离算法，但这虽然易于实现，但并不是最优解，因为它效率低下（需要使用可能很大的n * m矩阵），并且不提供“编辑脚本”是可用于将一个序列转换为另一个序列的编辑序列，反之亦然。

对于一个好的迈尔斯/海森堡实现看：

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

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

迈克

Answer 9

你可以使用solution to the Longest Common Subsequence (LCS) problem。另请参阅有关优化此解决方案的可能方法的讨论。

Answer 10

我为不同的功能采用了一种方法来计算在修改过的文件中有多少数据是新的，也许可以为您工作。

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

要将此功能用于最初描述的功能，要查看有多少数据是新的，我简单地运行操作，并逐字逐句复制每个操作，这些操作具有0因子，每个操作插入的新文本（作为补丁的一部分分发，因为它不在旧文件中发生）具有单因子。所有的角色都给了这个工厂，这给了我基本上一个0和1的长列表。

然后我所要做的就是统计0和1。在你的情况下，在我的实现中，与0相比，1的低数字意味着这些文件非常相似。

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

我对称量副本进行了实验，以便将第一个副本计为0，并且相同字符的后续副本具有逐渐更高的因子，以便为复制/粘贴操作提供某些“新因素”，但我从不在项目报废时完成。

如果你有兴趣，我的Subversion /补丁代码可以从我的Subversion版本库获得。

Answer 11

查看Fuzzy模块。它为soundex，NYSIIS和double-metaphone提供了快速（用C语言编写）的算法。 http://www.informit.com/articles/article.aspx?p=1848528