文本差异算法

看一看 difflib . (Python)

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

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

迈尔斯算法的描述见。

E.Myers, `An O(ND) Difference 算法和它的变体,
Algorithmica 1, 2 (1986), 251-266.

GNU diff工具使用Myers算法。

你所说的 "相似性分数 "在文献中被称为 "编辑距离"，它是将一个序列转化为另一个序列所需的插入或删除的数量。

请注意，许多人引用了列文斯坦距离算法，但这虽然容易实现，但不是最佳解决方案，因为它效率低下（需要使用一个可能是巨大的n*m矩阵），而且没有提供 "编辑脚本"，即可以用来将一个序列转化为另一个序列的编辑序列，反之亦然。

对于一个好的Myers/Hirschberg实施，请看。

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

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

集市 包含一种替代性的差异算法，称为 耐心差异 (在该页面的评论中有更多信息），据称比传统的diff算法更好。bazaar发行版中的'patiencediff.py'文件是一个简单的命令行前端。

如果你需要比线条更细的颗粒度，你可以使用列文斯坦距离。列文施泰因距离是一个简单明了的测量方法，用于衡量两个文本的相似程度。
你也可以用它来提取编辑日志，并可以进行非常细化的比较，类似于SO的编辑历史页面上的比较。 但要注意的是，Levenshtein距离的计算可能相当耗费CPU和内存，所以使用difflib，如Douglas Leder建议的那样，很可能会更快。

因此，参看 这个答案 .

有很多距离度量，正如paradoja提到的，有列文斯坦距离，但也有 NYSIIS 和 Soundex . 在Python的实现方面，我已经使用了 py-editdist 和 ADVAS 之前。 两者都不错，因为你会得到一个单一的数字作为分数。 先看看ADVAS，它实现了一堆的算法。

如前所述，使用difflib。一旦你有了差异化的输出，你可能会发现 Levenshtein距离 不同的字符串的 "值"，以给出它们的不同程度。

You could use the solution to the Longest Common Subsequence (LCS) problem .另见关于优化这一解决方案的可能方法的讨论。

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

我有一个C#的diff/patch实现，允许我取两个文件，大概是同一个文件的新旧版本，并计算 "差异"，但不是通常意义上的差异。基本上，我计算了一组操作，我可以对旧版本进行更新，使其具有与新版本相同的内容。

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

然后我所要做的就是统计0和1的数量。在你的案例中，在我的实现中，1的数量比0的数量少，就意味着文件非常相似。

这种实现方式还可以处理这样的情况：修改后的文件不按顺序插入了旧文件的副本，甚至是重复的副本（即你从文件的开头复制了一个部分，然后粘贴到底部附近），因为它们都是旧文件中同一个原始部分的副本。

我曾尝试对副本进行称重，使第一份副本算作0，而相同字符的后续副本的系数逐渐增大，以便给复制/粘贴操作一些 "新的因素"，但我从未完成，因为这个项目被废止了。