按相似性分组字符串。

Question

我有一个字符串数组，数量不多（可能只有几百个），但通常很长（几百个字符）。

这些字符串一般来说是无意义的，而且彼此不同。但在这些字符串中，大约 300 个中可能有 5 个非常相似。实际上，它们是相同的字符串，区别在于格式、标点和少量单词。

如何找出这组字符串？

顺便说一下，我是用 Ruby 写的，但如果没有其他方法，伪代码算法也可以。

谢谢！

- luca

Answer 1

假设您不担心每个单词的拼写错误或其他错误，您可以执行以下操作：

构建一个反向索引，其基本上是一个哈希表，由单词键入，指向包含该单词的字符串指针列表（如何处理重复出现取决于您）。要确定与给定查询字符串类似的字符串，请在索引中查找每个查询单词，并针对结果列表中的每个源字符串计算每个列表中源字符串出现的次数。具有最高计数的字符串是相似性的最佳候选项，因为它们包含最多的共同单词。

然后，您可以计算两个字符串之间的编辑距离或任何其他度量标准。这样，您就避免了将每个字符串与其他每个字符串进行比较的O（n ^ 2）复杂度。

- RyanHennig