例如，我有一个很长的字符串列表，每个字符串大约有 30-50 个字符，我想删除与该列表中的其他字符串相似的字符串（只留下一个重复项）。
我查看了各种字符串相似性算法，例如 Levenstein 距离和本文中介绍的方法。它们确实有效，但速度慢得令人痛苦——我想出的最佳算法具有 O(n^2) 复杂性，并且需要约 1.5 秒来处理包含 3000 个字符串的列表。
有没有一些快速的方法来删除这些列表？
问问题
2142 次
2 回答
2
如果您的相似性度量很强（例如 Levenshtein 距离 1），那么您可以按顺序处理您的字符串列表，为当前字符串生成所有可能的“关闭”字符串并在哈希表中查找该关闭字符串。如果存在，请跳过原始字符串。如果没有，则将其输出并将其添加到哈希表中。
该算法依赖于能够生成所有与字符串相近的字符串，并且不会太多。（这就是我上面所说的“强”的意思。）
作为一种可能的优化，您可以在哈希表中存储的不仅仅是原始字符串。例如，如果您想要 Levenshtein 距离 3，您可以将距离输出字符串的所有字符串距离 1 存储在哈希表中，然后在检查新字符串时查找距离 2 的字符串。
于 2013-04-06T18:40:31.087 回答
2
在匹配 DNA 字符串（或重新组装片段）时，经常会出现此问题。第一种方法是将字符串拆分为kmers 子字符串，例如4 个相邻的字母。所以
abcdefgh
会成为：
abcd + bcde + cdef + defg + efgh
对于完整的字典，这些子字符串可以输入到哈希表中，每个子字符串作为有效负载携带包含它们的原始字符串（它们的数字）的列表（可能还有可以找到它们的偏移量）
要进行搜索，请将待测字符串与字典一样对待，并在哈希表中查找其片段。现在，一次命中将导致找到所有五个片段，并具有正确的偏移量。部分命中将产生少于五个片段，但具有正确的偏移量。
当然，搜索会导致很多假阴性命中，但是通过组合（逻辑与）倒排索引列表，并且仅选择大约正确索引处的命中，事情会很快变得独特。
对于 OP 问题中的问题大小，运行时间可能是几（几十）毫秒。
顺便说一句：作为这种方法的副作用，替换的行为几乎与 indels 相同。在该示例中，他们将 1 个（在末端）到 4 个（在中间）kmer 匹配。对于较大的字符串，这不是问题，对于小字符串（就像在示例中一样（您可以使用较小的片段）
更新：我刚刚阅读了链接，看来他们也使用了 2-mers（并在其中提供了一些统计数据）
于 2013-04-06T19:18:34.117 回答