Python 的 difflib SequenceMatcher 加速

Question

我正在使用 difflib SequenceMatcher（ratio() 方法）来定义文本文件之间的相似性。虽然 difflib 比较一小组文本文件的速度相对较快，例如 10 个 70 kb 的文件平均相互比较（46 次比较）需要大约 80 秒。

这里的问题是我收集了 3000 个 txt 文件（平均 75 kb），对 SequenceMatcher 完成比较工作需要多长时间的原始估计是 80 天！

我尝试了“real_quick_ratio()”和“quick_ratio()”方法，但它们不适合我们的需求。

有没有办法加快比较过程？如果没有，有没有其他更快的方法来完成这样的任务？即使它不在 Python 中。

Answer 1

有一个 cdifflib 的difflib.SequenceMatcherC实现。

替换 SequenceMatcher，所有 difflib 操作将快 4 倍左右

from cdifflib import CSequenceMatcher
import difflib
difflib.SequenceMatcher = CSequenceMatcher

Answer 2

您发现的问题很常见，因为difflib没有优化。以下是我多年来在开发比较 HTML 文档的工具时发现的一些技巧。

适合内存的文件

创建两个列表，包含每个文件中的行。然后difflib.SequenceMatcher使用列表作为参数调用。该SequenceMatcher知道如何处理列表和进程将会更快，因为它是由炭上线完成由线的基础上，而不是字符。这可能会降低精度。

看看fuzzy_string_cmp.py和diff.py，看看我是如何做到这一点的。

选择

pypi 中有一个名为diff_match_patch的很棒的库。该库将在两个字符串之间执行快速差异并返回更改（添加行、行相等、删除行）。

通过利用diff_match_patch，您应该能够创建自己的dmp_quick_ratio函数。

在diff.py 中，您可以看到我如何使用该库来获得创建dmp_quick_ratio.

我的测试表明，使用diff_match_patch比 Python 的difflib.

Answer 3

您可以使用 pypy 获得小幅加速

http://pypy.org/