在许多字符串的列表中查找相似字符串的算法

Question

我知道近似字符串搜索和 Levenshtein 距离之类的东西，但我想要做的是获取大量字符串并快速挑选出任何彼此相似的匹配对（例如，相距 1 Damerau-Levenshtein 距离）。所以像这样

l = ["moose", "tiger", "lion", "mouse", "rat", "fish", "cat"]

matching_strings(l)

# Output
# [["moose","mouse"],["rat", "cat"]]

我只真正知道如何使用 R 和 Python，所以如果您的解决方案可以用其中一种语言轻松实现，则加分。

更新：

感谢 Collapsar 的帮助，这里是 Python 中的解决方案

import numpy
import functools
alphabet = {'a': 0, 'c': 2, 'b': 1, 'e': 4, 'd': 3, 'g': 6, 'f': 5, 'i': 8, 'h': 7, 'k': 10, 'j': 9, 'm': 12, 'l': 11, 'o': 14, 'n': 13, 'q': 16, 'p': 15, 's': 18, 'r': 17, 'u': 20, 't': 19, 'w': 22, 'v': 21, 'y': 24, 'x': 23, 'z': 25}


l = ["moose", "tiger", "lion", "mouse", "rat", "fish", "cat"]
fvlist=[]

for string in l:
    fv = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    for letter in string:
        fv[alphabet[letter]]+=1
    fvlist.append(fv)

fvlist.sort (key=functools.cmp_to_key(lambda fv1,fv2: numpy.sign(numpy.sum(numpy.subtract(fv1, fv2)))))

但是，已排序的向量按以下顺序返回：

“老鼠”“猫”“狮子”“鱼”“驼鹿”“老虎”“老鼠”

我认为这是次优的，因为我希望驼鹿和老鼠彼此相邻。我知道无论我如何对这些单词进行排序，都无法将所有单词放在所有最接近的单词对旁边。但是，我仍然对替代解决方案持开放态度

Answer 1

第一步，您必须使用任何模糊搜索索引来索引您的列表。

第二，您需要迭代列表并通过在预索引列表中快速查找来搜索邻居。

关于模糊索引：

大约 15 年前我写了模糊搜索，它可以找到 N 个近邻。这是我对 Wilbur trigram 算法的修改，这个修改被命名为“Wilbur-Khovayko 算法”。

基本思想：按三元组分割字符串，并搜索最大交集分数。

例如，让我们有字符串“hello world”。该字符串生成三元组：hel ell llo“lo”、“o_w”等；此外，为每个单词生成特殊的前缀/后缀三元组，例如 $he $wo lo$ ld$。

此后，为每个三元组构建索引，说明它出现在哪个术语中。

因此，这是每个三元组的 term_ID 列表。

当用户调用某个字符串时，它也会拆分为三元组，并程序搜索最大交集分数，并生成 N 大小的列表。

它工作得很快：我记得，在旧的 Sun/Solaris、256MB 内存、200MHZ CPU 上，它在 5,000,000 个术语的字典中搜索 100 个最接近的术语，只需 0.25 秒

您可以从以下位置获取我的旧来源：http://olegh.ftp.sh/wilbur-khovayko.tgz