时间戳

首页 > 解决方案 > 测试 2 个字符串 75%+ 相似度的最快算法？

algorithm - 测试 2 个字符串 75%+ 相似度的最快算法？

问题描述

我需要一个函数，它接收 2 个字符串并在它们相似度超过 75% 时返回一个布尔值。Levenshtein 有效，但我发现它对于我正在处理的数据量来说太慢了。

如果我能以某种方式首先确定 75%+ 的相似性，然后我可以运行 Levenshtein 进行精确的相似性匹配。

编辑

以下是我所说的相似性的一些例子：

isSimilar75("texts", "txts") //TRUE, 85% similar
isSimilar75("hello world", "hello word") //TRUE, 91% similar
isSimilar75("this is an example of longer text", "this is an example of a longer txt") //TRUE, 92% similar
isSimilar75("this is a test", "test what") //FALSE, 29% similar

该函数计算相似度类似于 levenshtein。我只需要一个更简单的 levenshtein 版本，它只根据字符操作（加、减和替换字符）的数量返回字符串是否“大约”75% 相似。该函数不需要返回百分比或进行任何精确计算，我只会对从该函数返回 true 的结果运行昂贵的 levenshtein。

标签： algorithmsorting

解决方案

两个词之间的 Levenshtein 距离的下限是它们的频率向量之间的 L1 距离。所以我们可以做类似的事情

import collections
def possiblySimilar75(s1, s2):
    c1 = collections.Counter(s1)
    c2 = collections.Counter(s2)
    return sum(abs(c1[x] - c2[x]) for x in set(c1.keys()) | set(c2.keys())) <= max(len(s1), len(s2)) / 4

推荐阅读