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

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

文件适合内存

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

看看fuzzy_string_cmp.py和 diff.py看看我是怎么做到的。

备选

有一个很棒的图书馆叫diff_match_patch在 pypi 中可用。该库将在两个字符串之间执行快速 差异并返回更改(添加的行、相等的行、删除的行)。

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

在diff.py您可以看到我如何使用该库来获得创建 dmp_quick_ratio 的灵感。

我的测试表明使用 diff_match_patch比 Python 的 difflib 快 20 倍。