问题：Python中的高性能模糊字符串比较，使用Levenshtein或difflib
我正在进行临床消息标准化（拼写检查），其中我对照900,000个单词的医学词典检查每个给定的单词。我更关心时间的复杂性/性能。
我想进行模糊字符串比较，但是不确定使用哪个库。
选项1：
import Levenshtein
Levenshtein.ratio('hello world', 'hello')
Result: 0.625选项2：
import difflib
difflib.SequenceMatcher(None, 'hello world', 'hello').ratio()
Result: 0.625在此示例中，两者给出相同的答案。您是否认为在这种情况下两者表现都一样？
回答 0
如果您想对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
In case you’re interested in a quick visual comparison of Levenshtein and Difflib similarity, I calculated both for ~2.3 million book titles:
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
I then plotted the results with R:
Strictly for the curious, I also compared the Difflib, Levenshtein, Sørensen, and Jaccard similarity values:
library(ggplot2)
require(GGally)
difflib <- read.table("similarity_measures.txt", sep = " ")
colnames(difflib) <- c("difflib", "levenshtein", "sorensen", "jaccard")
ggpairs(difflib)
Result:
The Difflib / Levenshtein similarity really is quite interesting.
2018 edit: If you’re working on identifying similar strings, you could also check out minhashing–there’s a great overview here. Minhashing is amazing at finding similarities in large text collections in linear time. My lab put together an app that detects and visualizes text reuse using minhashing here: https://github.com/YaleDHLab/intertext
回答 1
difflib.SequenceMatcher使用Ratcliff / Obershelp算法，计算匹配字符的加倍数除以两个字符串中的字符总数。
Levenshtein使用Levenshtein算法，它计算将一个字符串转换为另一个字符串所需的最少编辑次数
复杂
SequenceMatcher是最坏情况下的二次时间，其预期情况下的行为以复杂的方式取决于序列共有多少个元素。（从这里）
Levenshtein为O（m * n），其中n和m是两个输入字符串的长度。
性能
根据Levenshtein模块的源代码：Levenshtein与difflib（SequenceMatcher）有一些重叠。它仅支持字符串，不支持任意序列类型，但另一方面，它要快得多。