Python中高效模糊字符串比较，使用Levenshtein或difflib

Question

我正在进行临床信息的标准化（类似拼写检查），也就是要把每个给定的单词和一个包含90万个医学单词的字典进行对比。我最关心的是这个过程的时间复杂度和性能。

我想进行模糊字符串比较，但不太确定该用哪个库。

选项1：

import Levenshtein
Levenshtein.ratio('hello world', 'hello')

Result: 0.625

选项2：

import difflib
difflib.SequenceMatcher(None, 'hello world', 'hello').ratio()

Result: 0.625

在这个例子中，两者的结果是一样的。你觉得在这种情况下，两者的性能相似吗？

Answer 1

• difflib.SequenceMatcher使用的是一种叫做Ratcliff/Obershelp的算法，它通过计算两个字符串中匹配字符的数量的两倍，再除以这两个字符串的总字符数来得出结果。

• Levenshtein使用的是Levenshtein算法，它计算的是将一个字符串变成另一个字符串所需的最少编辑次数。

复杂度

SequenceMatcher在最坏情况下的时间复杂度是平方级别的，而它的实际表现又复杂地依赖于两个序列中有多少元素是相同的。 (来源)

Levenshtein的复杂度是O(m*n)，其中n和m分别是两个输入字符串的长度。

性能

根据Levenshtein模块的源代码，Levenshtein和difflib（SequenceMatcher）有一些重叠的地方。它只支持字符串，而不支持其他类型的序列，但另一方面，它的速度要快得多。

Answer 2

如果你对Levenshtein和Difflib相似度的快速视觉比较感兴趣，我计算了大约230万本书名的相似度：

import codecs, difflib, Levenshtein, distance

with codecs.open("titles.tsv","r","utf-8") as f:
    title_list = f.read().split("\n")[:-1]

    for row in title_list:

        sr      = row.lower().split("\t")

        diffl   = difflib.SequenceMatcher(None, sr[3], sr[4]).ratio()
        lev     = Levenshtein.ratio(sr[3], sr[4]) 
        sor     = 1 - distance.sorensen(sr[3], sr[4])
        jac     = 1 - distance.jaccard(sr[3], sr[4])

        print diffl, lev, sor, jac

然后我用R语言把结果画了出来：

为了满足好奇心，我还比较了Difflib、Levenshtein、Sørensen和Jaccard的相似度值：

library(ggplot2)
require(GGally)

difflib <- read.table("similarity_measures.txt", sep = " ")
colnames(difflib) <- c("difflib", "levenshtein", "sorensen", "jaccard")

ggpairs(difflib)

结果是：

Difflib和Levenshtein的相似度确实很有意思。

2018年更新：如果你正在研究识别相似字符串的工作，可以看看minhashing——这里有一个很好的概述。Minhashing在大文本集合中寻找相似性方面非常出色，速度很快。我的实验室还开发了一个应用，使用minhashing来检测和可视化文本重用，链接在这里：https://github.com/YaleDHLab/intertext