python - python 模糊 levenshtein 比率提前退出？

Question

我正在尝试相互比较 100k 个字符串。我无法进一步减少问题的大小（即集合中的#strings）。我正在使用 Levenshtein 比率进行比较。如果比率大于 0.9，我想将 2 个字符串存储在一个列表中。我的问题是关于运行时优化。由于 0.9 是我的标准，有没有办法将此值传递给 Levenshtein.ratio() 并期望在负面情况下提前退出？如果存在提前退出的方法，则可以节省一些运行时间。在 Levenshtein 算法中是否可以在计算完整距离之前尽早获得比率。

例如

import Levenshtein 
Levenshtein.ratio('lot of runtime','why not an early exit in this case by taking the intended ratio')

有没有类似的东西：

Levenshtein.ratio('lot of runtime','why not an early exit in this case by taking the intended ratio', 0.9)

Answer 1

是的，像您假设的那样提前退出是可能的。

该Levenshtein模块的源代码是免费提供的，因此您可以自己添加该功能。

您可能希望考虑另一种优化：三角不等式。如果字符串 A 与字符串 B 20% 相似，而字符串 B 与字符串 C 相似 90%，那么您知道字符串 A 不会与字符串 C 90% 相似。那是不可能的，所以您没有实际计算 AC Levenshtein 距离。