相似集合分组算法

Question

我有一个搜索引擎。当搜索关键字时，搜索引擎会生成结果。我需要找到所有生成类似结果的其他关键字。

例如，关键字k1给出结果集R1 = { 1,2,3,4,5,...40 }，其中包含最多40个文档ID。我需要获取所有其他关键字K1的列表，这些关键字生成的结果类似于k1生成的结果。

两个结果集R1和R2之间的相似度S(R1, R2)计算如下：
2 * (在_R1_和_R2_中相同元素的数量) / ((_R1_中的元素总数) + (_R2_中的元素总数))。例如：R1 = {1,2,3}，R2 = {2,3,4,5}，则S(R1, R2) = (2*|{2,3}|) / |{1,2,3}| + |{2,3,4,5}| = (2*2)/(3+4) = 4/7 = 0.57。

由于关键字超过100,000个，因此结果集也有100,000个以上。到目前为止，我只能通过O(N^2)的复杂方式解决这个问题，其中每个结果集都与其他所有集合进行比较。这需要很长时间。

有没有更好的想法？

以下是一些类似但并未完全解决问题的帖子：

• 如何存储集合以快速查找相似模式?
• 比较数字集合相似性的高效算法是什么?

- ddofborg

---

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.110.3089 - sclv

Answer 1

一个问题是结果按排序顺序排列吗？

有一个想法，将两个集合合并，进行排序并查找重复项。它可以缩减到O(nlogn)。

- NirmalGeo

---

你仍然需要将每个集合与另一个集合相结合，这会产生n*(n-1)种组合，对吗？ - ddofborg

Answer 2

为了简化问题，假设所有关键词都有10个结果，k1是要比较的关键词。您从每个关键词的集合中删除9个结果。现在将最后一个结果与k1的结果进行比较，并且具有相同最后一个结果的关键词就是您想要的。如果一个关键词与k1有1个共同结果，则只有1%的概率它会保留下来。一个与k1有5个共同结果的关键词将有25%的概率保留下来。也许您会认为1%太大了，那么您可以重复上述过程n次，与k1有1个共同结果的关键词将有1%^n的概率保留下来。时间复杂度为O(N)。

- jerry_sjtu

Answer 3

你的相似度准则是否固定不变？或者我们可以采用一些变化来实现更快的搜索引擎？

另一种选择：

我想到的一个替代方案是：

针对你的结果集R1，你可以遍历文档，并创建一个直方图，可用于与这些文档匹配的其他关键字。然后，如果给定的备选关键字获得了至少#R1/2次点击，则将其列为“相似”。

最大的区别在于，您不考虑R1中根本不存在的文档。

---

精确？

如果您需要一个完全符合您要求的解决方案，我相信只计算满足上述“替代”标准的关键字的R2集将足够。我认为（需要数学证明！）如果不满足“替代”标准，则没有机会满足您的标准。

- CygnusX1