https://stackoverflow.com/questions/145607
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我需要一种可以比较两个文本文件并突出显示它们的差异的算法，并且（甚至更好！）可以以有意义的方式计算它们的差异（比如两个相似的文件应该具有高于两个不同文件的相似性得分，用这个词“相似的”在正常术语中定义）。这听起来很容易实现，但事实并非如此。
实现可以是c＃或python。
感谢。
解决方案
在Python中，有 difflib ，正如其他人所建议的那样。
difflib 提供 SequenceMatcher 课程，可以用来给你一个相似比。示例功能：
def text_compare(text1, text2, isjunk=None):
return difflib.SequenceMatcher(isjunk, text1, text2).ratio()
其他提示
我可以推荐看看Neil Fraser的代码和文章：
目前提供Java版本， JavaScript，C ++和Python。而不管 语言，每个图书馆的特点 相同的API和相同的功能。 所有版本也都有全面的 测试线束。
Neil Fraser：Diff Strategies - 理论和实施说明
查看 difflib 。 （Python）的
这将以各种格式计算差异。然后，您可以使用上下文差异的大小来衡量两个文档的不同之处？
我目前的理解是，最短编辑脚本（SES）问题的最佳解决方案是Myers“middle-snake”。使用Hirschberg线性空间细化的方法。
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模块本身仍然是正确的。
麦克
如果您需要比线条更精细的粒度，则可以使用Levenshtein距离。 Levenshtein距离是关于如何将两个文本相似的直接衡量标准 您还可以使用它来提取编辑日志，并且可以使用非常精细的差异，类似于SO的编辑历史页面上的差异。 但要注意Levenshtein距离可以计算CPU和内存密集型，所以使用difflib，正如Douglas Leder建议的那样，很可能会更快。
比照。还此答案。
有很多距离指标，因为paradoja提到Levenshtein距离，但也有 NYSIIS 和 Soundex 。在Python实现方面，我使用了 py-editdist 和 ADVAS 。两者都很好，因为你得到一个数字作为分数。首先查看ADVAS，它实现了一堆算法。
如上所述，使用difflib。获得差异输出后，您可以找到不同字符串的 Levenshtein距离 “价值”它们有多么不同。
您可以使用解决最长公共子序列（LCS）问题。另请参阅有关优化此解决方案的可能方法的讨论。
我用于不同功能的一种方法，用于计算修改后的文件中新增的数据量，也可能对您有用。
我有一个差异/补丁实现C＃，它允许我获取两个文件，可能是相同文件的旧版本和新版本，并计算“差异”，但不是通常意义上的单词。基本上我计算了一组我可以在旧版本上执行的操作，以便将其更新为与新版本具有相同的内容。
要将此用于最初描述的功能，要查看新数据的数量，我简单地完成了操作，并且逐字地从旧文件复制的每个操作，具有0因子，并且每个操作都是插入新文本（作为补丁的一部分分发，因为它没有出现在旧文件中）有一个1因子。所有角色都给了这个工厂，这给了我一个很长的0和1的列表。
我所要做的就是计算0和1的结果。在你的情况下，通过我的实现，与0相比较少的1表示文件非常相似。
此实现还将处理修改后的文件无序地从旧文件中插入副本，或者甚至重复（即，您从文件的开头复制部件并将其粘贴到底部附近）的情况，因为它们将都是旧文件中相同原始部分的副本。
我试验了称重副本，以便第一个副本计为0，并且相同字符的后续副本具有逐渐更高的因子，以便给复制/粘贴操作一些“新因子”，但我从来没有在项目废弃时完成了它。
如果您有兴趣，可以从我的Subversion存储库获取我的差异/补丁代码。
查看模糊模块。它具有快速（用C语言编写）的soundex，NYSIIS和双metaphone算法。
可以在以下网址找到一个很好的介绍： http：//www.informit。 COM /物品/ article.aspx p = 1848528
