文本差异algorithm
我需要一个能够比较两个文本文件并突出显示其差异的algorithm（甚至更好！）能够以有意义的方式计算它们的差异（例如，两个相似文件应该具有高于两个不同文件的相似度分数，词“相似”按正常条款定义）。 这听起来很容易实现，但事实并非如此。
该实现可以在C＃或Python。
谢谢。
在Python中， difflib也是其他人所build议的。
difflib提供了SequenceMatcher类，它可以用来给你一个相似的比例。 function示例：
def text_compare(text1, text2, isjunk=None): return difflib.SequenceMatcher(isjunk, text1, text2).ratio()
我可以推荐看看Neil Fraser的代码和文章：
谷歌的Diff-比赛补丁
目前以Java，JavaScript，C ++和Python提供。 不pipe语言如何，每个库都具有相同的API和相同的function。 所有版本也有全面的testing线束。
Neil Fraser：差异策略 – 理论和实施笔记
看difflib 。 （python）
这将计算各种格式的差异。 那么你可以使用上下文差异的大小来衡量两个文档是如何不同的？
Bazaar包含另一种差异algorithm，称为耐心差异 （在该页面的评论中有更多的信息），据称比传统的差异algorithm更好。 bazaar发行版中的文件“patiencediff.py”是一个简单的命令行前端。
我目前的理解是，最短编辑脚本（SES）问题的最佳解决scheme是具有Hirschberg线性空间细化的Myers“中间蛇”方法。
Myersalgorithm描述如下：
E.Myers，“一种O（ND）差分algorithm及其变化”，“
Algorithmica 1,2（1986），251-266。
GNU diff实用程序使用Myersalgorithm。
您所说的“相似性分数”在文献中被称为“编辑距离”，即将一个序列转换为另一个序列所需的插入或删除次数。
请注意，许多人已经引用了Levenshtein距离algorithm，但是，虽然易于实现，但不是最佳的解决scheme，因为效率低下（需要使用可能巨大的n×mmatrix），并且不提供“编辑脚本“这是可以用来将一个序列转换成另一个序列的编辑序列，反之亦然。
对于一个好的Myers / Hirschberg实现来看看：
http://www.ioplex.com/~miallen/libmba/dl/src/diff.c
它所包含的特定库不再维护，但就我所知，diff.c模块本身仍然是正确的。
麦克风
如果您需要比线更细的粒度，则可以使用Levenshtein距离。 Levenshtein距离是如何相似两个文本是一个直接的措施。
您也可以使用它来提取编辑日志，并且可以使用非常细致的差异，类似于SO的编辑历史logging页面上的差异。 尽pipeLevenshtein距离可能需要CPU和内存密集计算，所以像Douglas Leder所说的那样使用difflib最有可能会更快。
参看 也是这个答案 。
有一些距离度量，因为Paradoja提到了Levenshtein距离，但也有NYSIIS和Soundex 。 就Python的实现而言，我之前使用过py-editdist和ADVAS 。 从这个意义上来说，两人都很好，你可以得到一个单一的数字作为分数。 先看看ADVAS，它实现了一堆algorithm。
如上所述，使用difflib。 一旦你有了不同的输出，你可能会发现不同弦的Levenshtein距离 ，以给出他们是如何不同的“价值”。
您可以使用最长的公共子序列（LCS）问题的解决scheme 。 另请参阅关于优化此解决scheme的可能方法的讨论。
我已经采用了一种不同的function来计算修改过的文件中有多less数据是新的，也许可以为你工作。
我有一个diff / patch实现C＃，允许我把两个文件，可能是同一个文件的新旧版本，并计算“差异”，但不是在通常意义上的单词。 基本上，我计算了一系列可以在旧版本上执行的操作，并将其更新为与新版本具有相同的内容。
为了将这个function用于最初描述的function，为了查看有多less数据是新的，我简单地运行了这些操作，并且逐字逐句复制了每个操作，这个操作具有0因子，并且每个操作都插入了新的文本（作为补丁的一部分分发，因为它不在旧文件中发生）具有单因子。 所有的angular色都给了这个工厂，这给了我基本上一个0和1的长列表。
我所要做的就是统计0和1。 在你的情况下，在我的实现中，与0相比，1的低数字意味着这些文件非常相似。
这个实现也可以处理修改后的文件从旧文件中乱序插入拷贝，甚至复制（即从文件开头复制一部分并粘贴到底部附近）的情况，因为它们都是旧文件中的相同原始部分的副本。
我尝试过称量副本，以便将第一个副本计为0，并且相同字符的后续副本具有逐渐更高的因子，以便为复制/粘贴操作提供一些“新因素”，但是我从来没有完成过项目被取消了。
如果你有兴趣，我的Subversion版本库可以使用我的diff / patch代码。
看看模糊模块。 它具有快速（用C语言编写）基于algorithm的soundex，NYSIIS和double-metaphone。
一个很好的介绍可以在http://www.informit.com/articles/article.aspx?p=1848528find
