python - 最有效的字符串相似度度量函数

Question

我正在寻找 Python 中字符串相似度度量函数的有效实现(或提供 Python 绑定(bind)的库)。

我想比较平均大小为 10kb 的字符串，但我不能采取任何捷径，比如逐行比较，我需要比较整个字符串。我并不关心具体使用什么指标，只要结果合理且计算速度快即可。这是我到目前为止所尝试过的:

来自标准库的
• difflib.SequenceMatcher。 ratio() 给出了良好的结果，但对于 10kb 文本需要 >100ms。 quick_ratio()只需要一半的时间，但结果有时与真实值相差甚远。
• python-Levenshtein :对于我的用例来说，levenshtein 是一个可接受的指标，但 Levenshtein.ratio('foo', 'bar') 并不比 SequenceMatcher 快。

在我开始对 pypi 上提供测量字符串相似性的函数的每个库进行基准测试之前，也许您可​​以为我指出正确的方向？如果可能的话，我希望将单次比较的时间减少到 10 毫秒以下(在商用硬件上)。

Answer 1

edlib对于我的用例来说似乎足够快。

它是一个带有 Python 绑定(bind)的 C++ 库，可以在每个不到 10 毫秒的时间内计算 <100kb 的文本的 Levehnstein 距离(在我的机器上)。 10kb 文本在约 1 毫秒内完成，比 difflib.SequenceMatcher 快 100 倍。