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

Question

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

8

我知道近似字符串搜索和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)))))

然而，排序后的向量按以下顺序返回： "rat" "cat" "lion" "fish" "moose" "tiger" "mouse" 我认为这是次优的，因为我希望moose和mouse在彼此附近。我知道无论如何排序这些单词，都无法让所有单词都与它们最接近的对出现在一起。然而，我仍然愿意尝试其他解决方案。

- C_Z_

这是一个非常好的问题，我已经阅读了下面的答案。有很多不同的创意和想法。我想知道是否有一种方法可以在10,000个字符串列表中找到2个最接近的字符串，其中“距离”的度量不是内置于搜索算法中的，但可以注入（Levenstein或其他）。它能否在小于O（n平方）的时间内完成？ - Nick Perkins

这个问题可以通过使用度量树高效地解决。 - Anderson Green

3个回答

2

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

第二步，您需要迭代您的列表，并通过预先索引的列表进行快速查找以查找邻居。

关于模糊索引：

大约15年前，我编写了模糊搜索，可以找到N个最接近的邻居。这是对Wilbur的三字母算法的修改，这种修改被命名为“Wilbur-Khovayko算法”。

基本思路：通过三字母将字符串拆分，并搜索最大交集得分。

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

然后，针对每个三字母建立索引，其中包含它存在的术语。

因此，这是每个三字母的term_ID列表。

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

它工作得很快：我记得，在旧的Sun / Solaris上，256MB RAM，200MHZ CPU上，它在0.25秒内在500万个术语的字典中搜索了100个最接近的术语。

您可以从以下网址获取我的旧源代码：http://olegh.ftp.sh/wilbur-khovayko.tgz

- olegarch

感谢您的帮助。我不懂C语言，但我找到了一个名为Fuzzyset的Python模块，可以进行三元组匹配。该模块能够在大约5分钟内处理我的约13000个单词数据集。虽然不是最理想的，但已经可以接受了。感谢您指引我正确的方向。 - C_Z_

不客气。感谢您欣赏我的努力。此外，如果您需要提高代码的性能 - 您可以使用RADIX50代码将三字母组转换为16位值。您可以将该值直接用作包含termIDs列表的表中的索引。这项技术在我的模糊引擎中使用。详情请参见：http://en.wikipedia.org/wiki/DEC_Radix-50 - olegarch

1

简单的实现方法是建立一个布尔矩阵，以字符串为索引（即它们在排序列表中的位置），并比较每对字符串，如果它们根据您的标准“相似”，则将相应的矩阵元素设置为true。这将运行在O(n^2)时间复杂度。

您可以将字符串转换为字符频率元组（例如，“moose”->（0,0,0,0,1,0,0,0,0,0,0,0,1,0,2,0,0,0,1,0,0,0,0,0,0,0）其中第i个向量分量表示字母表中的第i个字母）。请注意，频率向量仅在“少数”组件中有所不同（例如，在至多2个组件中的D-L距离为1时，相应的差异为+1，-1）。

对转换后的数据进行排序。您想生成的成对候选项将在已转换值的排序列表中相邻或至少“接近”彼此。通过将列表条目与其后继者中最多的k个进行比较（当然是比较相应的字符串），可以检查候选项，其中k是小整数。此算法将以O(n log n)运行。

您必须在转换/排序（具有取决于频率向量表示形式所选择的复杂比较操作）的附加开销和减少的比较次数之间权衡。该方法不考虑字符的内部单词位置，而仅考虑它们的出现次数。根据实际字符串集，可能会有许多候选配对无法转化为实际“相似”的配对。

由于您的数据似乎由英语词汇组成，一个潜在的优化是定义字符类（例如元音/辅音，“e”/其他元音/音节辅音/非音节辅音），而不是单个字符。

额外的优化：

请注意，您数据集中那些互为排列的字符串对（例如[art,tar]）将在给定转换下产生相同的值。因此，如果您将D-L距离限制为1 并且如果您不将相邻字符的置换视为单个编辑步骤，则永远不要选择具有相同转换值的列表项作为候选项。

- collapsar

我应该按什么标准对字符频率进行排序？按照a的数量，然后是b的数量，然后是c的数量等分组似乎是武断和无信息的，但是没有其他更好的想法。 - C_Z_

非常感谢您的帮助，对于所有的问题我很抱歉。虽然我不确定这是否有效，因为当我运行那段代码时，它将示例单词排序为“rat，cat，lion，fish，moose，tiger，mouse”。老鼠和猫在一起，这很好，但是驼鹿和老鼠不在一起。尽管如此，它仍然应该有所帮助，因为我想我可以将每个单词与其四个最近的邻居进行比较，或者类似于此的操作，而不是将每个单词与所有其他单词进行比较。 - C_Z_

numpy.sign(numpy.sum(numpy.subtract(fv1, fv2)))将按字符串中的字符数进行排序，而不是按频率相似性进行排序。虽然我不知道更好的排序方法是什么。 - Ishamael

@Ishamael 不会的，因为当考虑具有相同特征向量的单词时，可以很容易地看到它们将被排序在一起，而不考虑单词的长度。 - collapsar

相同的特征向量总是意味着相同的长度。特征向量中元素的总和是字符串的长度，这些总和之间的差异就是长度的差异，因此使用该差异作为比较器进行排序就是按长度排序。此外，具有相同特征向量的字符串不一定保证彼此相邻。 - Ishamael

显示剩余3条评论

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

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

- Ishamael · Accepted Answer

一种将其实现的方法（时间复杂度为 O(n k^2)，其中 n 表示字符串数量，k 表示最长的字符串）是将每个字符串转换为以下形式的掩码集合：

rat => ?at, r?t, ra?, ?rat, r?at, ra?t, rat?

这样，如果两个单词在一个字母上不同，比如“rat”和“cat”，它们都将有一个掩码?at，而如果一个单词是另一个单词的子序列，比如“rat”和“rats”，它们都将有一个掩码“rat?”。

然后，您只需根据它们的掩码对字符串进行分组，并打印具有两个以上字符串的组。如果有重复，请先去重数组。

以下是一个示例代码，其中包含一个额外的cats字符串。

l = ["moose", "tiger", "lion", "mouse", "rat", "fish", "cat", "cats"]
d = {}

def add(mask, s):
    if mask not in d:
        d[mask] = []
    d[mask].append(s)

for s in l:
    for pos in range(len(s)):
        add(s[:pos] + '?' + s[pos + 1:], s)
        add(s[:pos] + '?' + s[pos:], s)
    add(s + '?', s)

for k, v in d.items():
    if len(v) > 1:
        print v

输出

['moose', 'mouse']
['rat', 'cat']
['cat', 'cats']