例如，我有一个很长的字符串列表，每个字符串大约有30-50个字符，并且我想删除与该列表中其他字符串相似的字符串(从重复项族中只留下一个出现)。
我研究了各种字符串相似度算法，例如，Levenstein距离和本文中介绍的方法。它们确实有效，但速度慢得令人痛苦——我提出的最好的算法显示出O(n^2)的复杂度，处理包含3000个字符串的列表需要1.5s。
是否有一些快速的方法去重复这些列表?
如果您的相似性度量很强(例如Levenshtein distance 1)，那么您可以按顺序处理字符串列表，生成当前字符串的所有可能的"close"字符串，并在哈希表中查找该close字符串。如果存在，则跳过原始字符串。如果不是，则输出它并将其添加到哈希表中。
该算法依赖于能够生成一个字符串的所有接近字符串，并且不会有太多。(这就是我上面所说的"强"。)
作为一种可能的优化，您可以在哈希表中存储的不仅仅是原始字符串。例如，如果您希望Levenshtein距离为3，则可以将输出字符串中距离为1的所有字符串存储在哈希表中，然后在检查新字符串时查找距离为2的字符串。
这个问题在匹配DNA字符串(或重新组装片段)时经常发生。第一种方法是将字符串拆分为kmer s，子字符串，其中表示 4个相邻的字母。所以
abcdefgh
将成为:
abcd + bcde + cdef + defg + efgh
对于完整的字典，这些子字符串可以输入到哈希表中，每个子字符串作为负载携带包含它们的原始字符串(它们的数字)的列表(以及可能找到它们的偏移量)
要进行搜索，请将测试下的字符串与字典相同，并在哈希表中查找其片段。现在一个点击将导致所有五个片段都被找到，并且有正确的偏移量。部分命中将产生少于5个碎片，但具有正确的偏移量。 当然，搜索会产生很多假阴性结果，但是通过对倒排索引列表进行组合(逻辑与)，并且只选择上关于正确索引的的命中，事情会变得非常独特。对于OP问题中的问题大小，运行时间可能是几(几十)毫秒。
BTW:作为这个方法的一个副作用，替换的行为几乎与索引相同。在这个例子中，他们会将一个(在两端)到四个(在中间)的kmer-match旋转。对于较大的字符串，这不是问题，对于较小的字符串(就像在示例中一样)
更新:我刚刚读了链接，似乎他们也使用2-mers(并抛出一些统计数据)