Python中的模糊字符串比较,混淆了使用哪个库

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (146)

我想做模糊字符串比较,但混淆了要使用哪个库。

备选案文1:

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

Result: 0.625

备选案文2:

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

Result: 0.625

在这个例子中,两者给出了相同的答案。但我更喜欢用difflib。谢谢。

提问于
用户回答回答于

如果您对Levenshtein和Difflib相似性的快速视觉比较感兴趣,我计算了二百三十万本书的标题:

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的相似性确实很有趣。

用户回答回答于
  • 顺序匹配器使用拉特克利夫/奥伯舍普算法计算匹配字符的加倍数除以两个字符串中的字符总数。
  • 莱文Levenshtein算法它计算将一个字符串转换为另一个字符串所需的最小编辑数。

复杂性

序列匹配是最坏情况下的二次时间,并且期望-情况行为以一种复杂的方式依赖于序列共有多少个元素。从这里开始)

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

性能

在Levenshtein模块中:Levenshtein与Difflib有一些重叠(SequenceMatcher)。它只支持字符串,不支持任意的序列类型,但另一方面它更快。

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励