文本差异算法

Question

我需要一个算法，可以比较两个文本文件，并突出显示它们的不同之处。更好的是，这个算法还能以有意义的方式计算它们的差异，比如两个相似的文件应该有一个比两个不相似的文件更高的相似度评分，而“相似”这个词的定义是按照常规的理解来进行的。听起来好像很简单，但实际上并不是。

这个算法可以用C#或Python来实现。

谢谢。

Answer 1

看看这个difflib模块吧。（这是Python的一个模块）

这个模块可以计算出两个文档之间的差异，并以不同的格式展示出来。你可以用上下文差异的大小来衡量这两个文档有多不同。

Answer 2

我推荐你看看Neil Fraser的代码和文章：

google-diff-match-patch

这个库目前支持Java、JavaScript、C++和Python等多种编程语言。不管你用哪种语言，这些库的接口和功能都是一样的。所有版本都有详细的测试工具。

Neil Fraser: Diff Strategies - 这里有关于理论和实现的笔记

Answer 3

在Python中，有一个叫做 difflib 的库，其他人也提到了这个。

difflib 提供了一个 SequenceMatcher 类，可以用来计算两个字符串之间的相似度。下面是一个示例函数：

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