文本比较算法

Question

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

有没有我可以使用的算法？我甚至没有找代码.如果我知道算法,我可以用java编写代码.谢谢.

Answer 1

通常,这是通过找到最长公共子序列(通常称为LCS问题)来完成的.这就是工具的diff工作方式.当然,这diff是一个面向行的工具,听起来你的需求有些不同.但是,我假设你已经构建了一些比较单词和句子的方法.

Answer 2

Subversion的diff引擎使用O(NP)序列比较算法.

为了您的信息,我自己在github的后续页面中有各种编程语言的实现.

https://github.com/cubicdaiya/onp

Answer 3

某种差异变体可能会有所帮助,例如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而是未被触及,并在它之前插入一个新句子.即它应该报告插入一个句子,而不是改变四个单词后跟一个新句子.

Answer 4

diff和大多数其他比较工具使用的特定算法是Eugene Myer的An O(ND)差分算法及其变化.java-diff-utils包中提供了Java实现.

Answer 5

以下是两篇描述其他文本比较算法的论文，这些算法通常应输出“更好”（例如，更小，更有意义）的差异：

• Tichy，Walter F.，“带有块移动的字符串到字符串校正问题”（1983）。计算机科学技术报告。论文378。
• Paul Heckel，“隔离文件之间差异的技术”，ACM通讯，1978年4月，第21卷，第4期

第一篇论文引用了第二篇，并提到了它的算法：

Heckel [3]指出了与LCS技术类似的问题，并提出了一种线性石灰算法来检测块运动。如果字符串中几乎没有重复的符号，则该算法将充分执行。但是，否则该算法将给出较差的结果。例如，给定两个字符串aabb和bbaa，Heckel的算法无法发现任何公共子字符串。

在第一篇论文中提到的这个答案，并在第二个这样的回答，既类似SO问题：

• 是否有类似diff的算法来处理移动的线段？- 堆栈溢出