加速Python的difflib中SequenceMatcher
我正在使用difflib库里的SequenceMatcher（ratio()方法）来比较文本文件之间的相似度。对于小规模的文本文件，比如说10个平均大小为70KB的文件，相互之间比较（总共46次比较）大约需要80秒，这个速度还算可以。
问题是，我有3000个txt文件（平均75KB），粗略估计一下，SequenceMatcher完成这些比较工作需要80天！
我试过“real_quick_ratio()”和“quick_ratio()”这两个方法，但它们并不适合我们的需求。
有没有什么办法可以加快比较的速度？如果没有，是否有其他更快的方法来完成这样的任务？即使不是用Python也可以。
3 个回答
你可以通过使用pypy来获得一些小的速度提升。
有一个用C语言实现的 difflib.SequenceMatcher，叫做 cdifflib。
如果用这个SequenceMatcher替换掉原来的，所有的difflib操作速度会快大约4倍。
from cdifflib import CSequenceMatcher
import difflib
difflib.SequenceMatcher = CSequenceMatcher
你遇到的问题很常见，因为 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倍。