最高效的字符串相似度度量函数

Question

最高效的字符串相似度度量函数

pythonstringpython-3.xlevenshtein-distance

4

我正在寻找一种在Python中实现字符串相似度度量函数的高效方法（或提供Python绑定的库）。

我想比较大小为10kb的字符串，不能采取逐行比较等捷径，需要比较整个字符串。我并不关心使用哪种确切的度量标准，只要结果合理且计算速度快即可。以下是我迄今为止尝试过的内容：

- 标准库中的difflib.SequenceMatcher。ratio（）可以得到良好的结果，但对于10kb文本需要100ms以上。quick_ratio（）只需一半的时间，但结果有时偏离真实值。 - python-Levenshtein：Levenshtein是我的用例中可以接受的指标，但Levenshtein.ratio('foo', 'bar')与SequenceMatcher相比并不更快。

在我开始对pypi上提供字符串相似度测量函数的每个库进行基准测试之前，也许你可以给我指点方向？如果可能的话，我希望将单个比较的时间缩短到不到10毫秒（在常规硬件上）。

- klamann

我认为二次复杂度会使这个问题变得非常困难。这里提到了一些替代方案（例如固定参数算法+近似算法），但是你的问题似乎有点宽泛，不足以评估这些替代方案（我并不关心确切的指标和未知的数据）。 - sascha

如果你对细节感兴趣的话，我正在开发一套用于近似重复检测的系统，该系统使用MinHashes进行可能重复项的识别。有时候会出现大量的可能重复项，而我需要找到最佳匹配。所以，我不在乎使用什么精确指标，只要它在数学意义上是一个指标即可。此外，我也不关心数据，它应该适用于任何类型的字符串。对于相对较小的输入，甚至具有二次复杂度的算法都应该比我到目前为止审查过的算法表现更好（至少我希望如此…）。 - klamann

我不能提供更多（这不是我的专业领域），你需要决定那些替代方案是否值得尝试（需要编码）。但是，仅仅通过一些相当愚蠢的计算（假设字节=字符）来取得你的数字+二次复杂度，例如：10kB = 10240 B -> 10240^2 = 104.857.600, 对我来说100ms看起来非常快。 - sascha

好吧，如果我必须将每个字符与另一个字符进行比较，那么速度确实会非常慢。但是我认为这里有优化的空间。此外，我不需要最佳解决方案，只要能够以合理的近似值作出答案，并且误差在3％以内，我就完全满意。 - klamann

3个回答

1

我在使用RapidFuzz时运气不错，虽然我不知道它与其他工具相比如何，但它比thefuzz/fuzzywuzzy快得多。

不知道它是否适用于您的用例，但这是您在谷歌搜索“快速字符串相似性python”时找到的第一件事。

- Danferno

1

当我提出这个问题时，这还不存在，看起来很有前途！ - klamann

0

基于我所做的大量阅读，像tfidf_matcher这样的东西对我很有效。返回最佳的k个匹配项。而且，它比Fuzzywuzzy快1000倍。

- Upasana Parashar

1

目前你的回答不够清晰，请编辑并添加更多细节，以帮助其他人理解它如何回答问题。你可以在帮助中心找到有关如何编写好答案的更多信息。 - Community

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- klamann · Accepted Answer

edlib 似乎对我的使用情况足够快。它是一个带有Python绑定的C++库，可以在我的计算机上为小于100kb的文本计算Levehnstein距离，每个文本不到10毫秒。10kb的文本仅需约1毫秒，比difflib.SequenceMatcher快100倍。