文本比较算法

我们在项目中有一个要求，我们必须比较两个文本（update1，update2），并提出一个算法来定义有多少单词和多少句子已经改变。文本比较算法

是否有任何算法可以使用它？我甚至不在寻找代码。如果我知道算法，我可以用java编写它。谢谢。

2012-01-30 java_mouse

http://stackoverflow.com/questions/65199/ c-sharp-comparison-algorithms – 2012-01-30 14:41:49

http://neil.fraser.name/software/diff_match_patch/myers.pdf – 2012-01-30 14:42:16

典型地，这通过寻找Longest Common Subsequence完成（通常称为LCS问题）。这就是diff这样的工具的工作原理。当然，diff是一个面向行的工具，听起来你的需求有所不同。但是，我假设你已经构建了一些方法来比较单词和句子。

2012-01-30 14:40:52 FatalError

某种类型的差异变型的可能会有所帮助，如wdiff

如果你决定设计自己的算法，你将必须解决其中的一句话已经插入的情况。例如，对于以下两个文件：

The men are bad. I hate the men

和

The men are bad. John likes the men. I hate the men

你的工具应该能够向前看认识到，在第二，I hate the men还没有被替换John likes the men但而不是被触动，并在它之前插入一个新的句子。即它应该报告插入一个句子，而不是改变一个新句子后面的四个单词。

2012-01-30 14:44:20 Howard

由diff和大多数其他比较实用程序的使用的具体算法是尤金Myer百货公司An O(ND) Difference Algorithm and Its Variations。在java-diff-utils包中有一个Java实现。

2012-01-30 15:37:19

为了您的信息，也有在下面GitHub上的页面通过自己各种编程语言实现。

2012-01-31 11:05:14 cubicdaiya

困难来自效率，以良好的业绩比较大的文件时。因此，我实施迈尔斯O（ND）的diff算法的变化 - 这表现相当好，准确的（与支持基于滤波正则表达式）：

2015-09-09 21:23:18

下面是描述其他文本比较算法，一般应输出“更好”（例如两个文件：主页上的更多信息更小，更有意义的）差异：

第一文件引用所述第二和提及本绕其算法：

赫克尔[3]指出相似LCS技术存在的问题，并提出了线性石灰算法来检测块移动。如果字符串中没有重复的符号，算法会充分执行。但是，该算法在其他情况下给出的结果不佳。例如，给定两个字符串aabb和bbaa, Heckel的算法无法发现任何常见的子字符串。

第一纸在this answer提到和第二在this answer，既类似SO问题：

2017-01-12 17:30:18

回答