文本比较算法

Question

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

有没有可以使用的算法？

我甚至不需要代码。如果我知道算法，我可以用Java编写它。

- java_mouse

---

https://dev59.com/lnVD5IYBdhLWcg3wKoSH - Mitch Wheat

http://neil.fraser.name/software/diff_match_patch/myers.pdf - Mitch Wheat

Answer 1

通常这是通过找到最长公共子序列（通常称为LCS问题）来完成的。这就是像diff这样的工具的工作原理。当然，diff是一种面向行的工具，听起来您的需求有些不同。但是，我假设您已经构建了某种比较单词和句子的方法。

- FatalError

---

有一个名为wdiff(1)的diff(1)前端，它基于逐字逐句的方式工作。 - vonbrand

Answer 2

一个O（NP）序列比较算法被Subversion的差异引擎所使用。

提供一下信息，以下Github页面中我自己用各种编程语言实现了这个算法。

https://github.com/cubicdaiya/onp

- cubicdaiya

Answer 3

一些类似于diff的变体可能会有所帮助，例如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替换，而是保持不变，并在它之前插入了一个新的句子。也就是说，它应该报告插入了一句话，而不是报告更改了四个单词后跟着加了一句新的话。

- Howard

Answer 4

以下是两篇论文，介绍了其他文本比较算法，通常应输出“更好”的（例如更小、更有意义）差异:

• Tichy, Walter F., "The String-to-String Correction Problem with Block Moves" (1983). Computer Science Technical Reports. Paper 378.
• Paul Heckel, "A Technique for Isolating Differences Between Files", Communications of the ACM, April 1978, Volume 21, Number 4

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

Heckel[3]指出LCS技术存在类似的问题，并提出了一种线性算法来检测块移动。如果字符串中有很少的重复符号，该算法的表现是足够好的。然而，否则该算法的结果就很差。例如，给定两个字符串aabb和bbaa，Heckel的算法无法发现任何公共子字符串。

第一篇论文被提及在这个答案中，第二篇论文被提及在这个答案中，两篇论文都与类似的SO问题有关：

• Is there a diff-like algorithm that handles moving block of lines? - Stack Overflow

- Kenny Evitt

Answer 5

diff和大多数其他比较工具使用的特定算法是Eugene Myer的O(ND)差异算法及其变种。在java-diff-utils包中有它的Java实现。

- Zoë Peterson

Answer 6

困难在于如何高效、高性能地比较大文件。因此，我实现了一种变体的Myers O(ND) diff算法——它表现出色且准确（并支持基于正则表达式的过滤）：

算法可以在这里测试：becke.ch比较工具Web应用程序 主页上还有更多信息：becke.ch比较工具

- becke.ch

---

很棒的工具！但是下载页面不可用（404）。请问您能告诉我在哪里可以下载吗？ - Sam Sirry

Answer 7

最著名的算法是O(ND)差异算法，也被用于Notepad++比较插件（用C++编写）和GNU diff(1)。你可以在这里找到一个C#实现： http://www.mathertel.de/Diff/default.aspx

- ozanmut