3

我有 200,000 个字符串。我需要在该集合中找到相似的字符串。我希望集合中类似字符串的数量非常少。请帮助提供有效的数据结构。

如果我正在寻找完全匹配的字符串，我可以使用简单的哈希。但是，在我的情况下，“相似性”是自定义定义的：如果两个字符串中 80% 的字符相同，则两个字符串被视为相似，顺序无关紧要。

我不想调用查找“相似性”~(200k*100k) 次的函数。欢迎任何建议，例如预处理字符串的技术，高效的数据结构。谢谢。

4

1 回答 1

1

我了解到只有当两个字符串之间的字符串长度差 <=3 时，距离比才可能 >=0.85。这意味着，我们可以对长度差 <=3 的字符串进行分组。

这大大减少了每组中的字符串数量。因此，在我的数据集中，总体比较的数量减少到略低于 50%（200k*100k）。此外，将数据集分成多个小集有助于进行并行处理，从而进一步减少整体运行时间。

减少百分比可能随样本数据集而变化，即最坏的情况发生在所有字符串的长度差 <=3 时。

[感谢 Inbar Rose 激发了这个想法]

就我而言，直方图如下所示：

直方图

于 2013-01-07T08:54:30.780 回答