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

Question

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

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

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

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

谢谢

Answer 1

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

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

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