模糊字符串列表去重是否有高效算法？

Question

例如，我有一个字符串的长列表，每个字符串大约有30-50个字符，我想删除与该列表中其他某些字符串相似的字符串（仅保留重复项家族中的一个出现）。

我查看了 各种字符串相似性算法，例如Levenstein距离和这篇文章中介绍的方法。它们确实有效，但速度非常慢 - 我想出的最佳算法表现出O(n^2)的复杂度，并需要大约1.5秒来处理包含3000个字符串的列表。

是否有一种快速的方法来去重这些列表？

- Rogach

---

如果您不想应用任何特定的相似度测量，可以实现哈希函数来表示字符串内容。假设两个字符串包含相同数量的相同字母，则它们是相似的。编写一个哈希函数来表示此属性，并检查是否已经使用相同哈希编码了任何字符串，如果是，则可以将其排除。 - stuhlo

@stuhlo - 请考虑这两个字符串："apple tree" 和 "apple trees"。它们非常相似，但并不包含相同的字母。另一方面，它们的编辑距离为1。 - Rogach

Answer 1

如果您的相似度衡量很强（例如Levenshtein距离1），那么您可以按顺序处理字符串列表，生成所有可能与当前字符串“接近”的字符串，并在哈希表中查找该接近字符串。如果存在，则跳过原始字符串。如果不存在，则输出它并将其添加到哈希表中。

此算法依赖于能够生成一个字符串的所有相似字符串，并且它们不会太多。（这就是我上面所说的“强”之意）

作为可能的优化，您可以在哈希表中存储更多内容，而不仅仅是原始字符串。例如，如果您想要Levenshtein距离3，则可以在哈希表中存储所有距离输出字符串1个距离的字符串，然后在检查新字符串时查找2个距离的字符串。

- Keith Randall

Answer 2

在匹配DNA字符串（或重新组装片段）时，经常会出现这个问题。首先的方法是将字符串分成kmer，即由相邻的4个字母组成的子字符串。所以

abcdefgh

Would become:

abcd + bcde + cdef + defg + efgh

完整的字典可以将这些子字符串输入到哈希表中，每个子字符串都携带一个有效载荷，即包含它们的原始字符串列表（它们的编号）（以及可能的偏移量）。

要搜索，请将“测试字符串”与“字典”视为相同，并在哈希表中查找其片段。现在，如果命中，则会找到所有五个片段，并且具有正确的偏移量。部分命中将产生少于五个片段，但具有正确的偏移量。

当然，搜索会导致很多误报，但是通过组合（逻辑AND）反转索引列表，并仅选择大约正确索引处的命中结果，事情很快就会变得独特起来。

对于OP问题的问题规模，运行时间可能为几十毫秒。

顺便说一下：由于此方法的副作用，替换几乎与插入和删除相同。在示例中，它们将使一个匹配点变成四个匹配点（在中间）。（对于较大的字符串，这不是问题，对于小字符串（例如示例），它是问题（您可以使用较小的片段））

更新：我刚刚阅读了链接，似乎他们也使用2-mer（并将一些统计数据投射到其中）。

- wildplasser

---

似乎我做错了什么，因为我几乎尝试了完全相同的方法，但速度很慢。我会再试一次。 - Rogach