Python 中的高性能模糊字符串比较，可以使用 Levenshtein 或 ddlib

我正在做临床信息标准化(拼写检查) ，我检查每个给定的单词对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

在这个例子中，两者给出了相同的答案。您认为在这种情况下两者的表现相同吗？

90998 次浏览
小开

  • 艰难。SequenceMatcher 使用 拉特克利夫/上级算法计算匹配字符的倍数除以两个字符串中的字符总数。

  • Levenshtein 使用 Levenshtein 算法计算将一个字符串转换为另一个字符串所需的最小编辑次数

复杂性

SequenceMatcher 是最坏情况下的二次时间，其预期情况行为以一种复杂的方式依赖于序列中有多少元素是相同的。(从这里)

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

表演

根据 Levenshtein 舱的 源代码: Levenshtein 与 Dillib 有一些重叠(SequenceMatcher)。它只支持字符串，而不支持任意的序列类型，但另一方面，它的速度要快得多。

小开

如果你有兴趣快速直观地比较一下 Levenshtein 和迪夫利布的相似之处，我计算了大约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 绘制结果:

enter image description here

为了满足好奇心，我还比较了迪夫利布、 Levenshtein、 Sørensen 和雅卡德的相似度值:

library(ggplot2)
require(GGally)


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


ggpairs(difflib)

结果: enter image description here

Diflib 和 Levenshtein 的相似性确实很有趣。

2018年编辑: 如果您正在识别类似的字符串，您还可以查看 minhash ——有一个 很好的概述。在线性时间内发现大型文本集合中的相似性方面，Minhash 令人惊讶。我的实验室开发了一个应用程序，可以通过 minhashhere 检测和可视化文本重用: https://github.com/YaleDHLab/intertext


提交答案