Python的difflib SequenceMatcher加速

Question

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

这里的问题是，我收集了3000个txt文件(平均大小为75KB)，粗略估计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中使用。该库将在两个字符串之间执行fast差异并返回更改(添加行、相等行、删除行)。

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

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

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

Answer 2

cdifflib是difflib.SequenceMatcher的一个C实现。

替换SequenceMatcher，所有的difflib操作都会快4倍左右

from cdifflib import CSequenceMatcher
import difflib
difflib.SequenceMatcher = CSequenceMatcher

Answer 3

您可以使用pypy获得较小的加速比

http://pypy.org/