我需要一种算法，可以比较两个文本文件并突出显示它们之间的差异，并且(可以更好！)可以以有意义的方式计算它们的差异(例如两个相似的文件应比两个不同的文件具有更高的相似性得分，并使用"相似"一词以正常术语定义)。听起来很容易实现，但事实并非如此。

可以在cor python中实现。

谢谢。

解决方案

看difflib。 (Python)

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

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

cf.也是这个答案。

如前所述，使用difflib。获得差异输出后，我们可能会发现不同字符串的Levenshtein距离，以给出它们之间有多不同的"值"。

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

我建议我们看一下尼尔·弗雷泽(Neil Fraser)的代码和文章：

google-diff-match-patch

Currently available in Java,
  JavaScript, C++ and Python. Regardless
  of language, each library features the
  same API and the same functionality.
  All versions also have comprehensive
  test harnesses.

尼尔·弗雷泽(Neil Fraser)：理论与实施笔记的差异化策略

正如paradoja提到的那样，有许多距离度量标准，即Levenshtein距离，但也有NYSIIS和Soundex。在Python实现方面，我之前使用过py-editdist和ADVAS。两者都很好，因为我们会得到一个数字作为分数。首先检查ADVAS，它实现了一堆算法。

在Python中，有difflib，也有其他人建议。

difflib提供了SequenceMatcher类，可用于为我们提供相似率。示例功能：

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

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

Myers算法的描述如下：

E. Myers, ``An O(ND) Difference
  Algorithm and Its Variations,''

  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模块本身仍然是正确的。

麦克风

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

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

我有一个diff / patch实现C，它允许我获取两个文件(可能是同一个文件的旧版本和新版本)，并计算"差异"，但并非通常意义上的。基本上，我计算出可以在旧版本上执行的一组操作，以将其更新为具有与新版本相同的内容。

为了将此功能用于最初介绍的功能，查看有多少数据是新的，我简单地遍历了这些操作，以及从原文件逐字复制的，具有0因子的每个操作以及插入新文本的每个操作(由于未在旧文件中发生，因此作为补丁的一部分分发)具有1因子。所有字符都被赋予了这个工厂，这基本上给了我一长串0和1的列表。

然后，我要做的就是将0和1相加。在情况下，对于我的实现，将1与0相比要少一些就意味着文件非常相似。

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

我尝试过权衡副本，以使第一个副本计为0，并且随后相同字符的副本具有逐渐提高的因数，以便为复制/粘贴操作提供一些"新因数"，但我从未完成过项目被废弃。

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