java - 如何高效查找相似文档

Question

我有很多使用聚类算法聚类的文档。在聚类算法中，每个文档可能属于多个簇。我创建了一个存储 document-cluster 分配的表和另一个存储 cluster-document 信息的表。当我查找与给定文档相似的文档列表时(let's sat d_i)。我首先检索它所属的集群列表(从 document-cluster 表)然后对于 document-cluster 中的每个集群 c_j 我检索文档列表属于 cluster-document 表中的 c_j。 c_j不止一个，所以显然会有多个列表。每个列表都有很多文档，显然这些列表之间可能存在重叠。

在下一阶段，为了找到与 d_i 最相似的文档，我根据它们与 d_i 共有的簇数对相似文档进行排名。

我的问题是关于最后一个阶段的。一个天真的解决方案是创建一种排序的 HashMap，它将文档作为键，#common clusters 作为值。然而，由于每个列表可能包含许多文档，这可能不是最佳解决方案。有没有其他方法可以对相似的项目进行排名？任何预处理或..？

Answer 1

假设数组的数量与元素的数量相比相对较小(特别是，数组的数量在 o(logn) 中)，您可以通过修改一个bucket sort :

设m为数组的个数创建一个包含 m 个桶 buckets[] 的列表，其中每个 bucket[i] 都是一个哈希集

for each array arr:
   for each element x in arr:
      find if x is in any bucket, if so - let that bucket id be i:
          remove x from bucket i  
          i <- i + 1
      If no such bucket exist, set i=1
      add x to bucket i

for each bucket i=m,m-1,...,1 in descending order:
   for each element x in bucket[i]:
      yield x

上面的运行时间复杂度为 O(m^2*n):

• 遍历每个数组
• 遍历每个数组中的所有元素
• 找到相关的桶。

请注意，最后一个可以通过添加一个map:element->bucket_id来完成，并且使用哈希表在O(1)中完成，因此我们可以将其改进为O(m*n).

---

另一种方法是使用 HashMap 作为从元素映射到其出现次数的直方图，然后根据直方图对包含所有元素的数组进行排序。这种方法的好处:它可以用 map-reduce 很好地分发。 :

map(partial list of elements l):
    for each element x:
       emit(x,'1')
reduce(x, list<number>):
   s = sum{list}
   emit(x,s)
combine(x,list<number>):
   s = sum{list} //or size{list} for a combiner
   emit(x,s)