ruby - 按相似度对字符串进行分组

Question

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

这些字符串通常是无意义的，并且彼此不同。但在一组字符串中，可能有 300 个字符串中的 5 个，有很大的相似性。实际上它们是同一个字符串，不同的是格式、标点和几个单词。

我怎样才能算出那组字符串？

顺便说一句，我正在用 ruby​​ 编写，但如果没有别的，伪代码中的算法就可以了。

谢谢

Answer 1

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

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

然后你可以计算两个字符串之间的编辑距离，或者你想要的任何其他度量。这样可以避免将每个字符串与其他字符串进行比较的 O(n^2) 复杂性。