2

我正在解决一个测验，需要一些建议。

测验摘要如下：

分析书签服务（如delicious、digg...）的数据并提取具有两个以上公共标签的url 组。

  1. 每个书签数据包含 1) 用户 ID、2) url 和 3) 一个标签数组。
  2. 与所有 url 相比，所有标签的大小都相对较小。也就是说，人们用有限的集合为网站添加书签
  3. 分配给 URL 的所有标签都不同
  4. 如果不同的用户为同一个 URL 添加了书签，你不应该将他们分成组。（但是，这是一个可选条件。你可以忽略 user_id 并假设所有 URL 都不同。）

例子：

siteA - [tag1, tag2, tag3]
siteB - [tag1, tag2, tag4]
siteC - [tag1, tag3, tag5]
siteD - [tag1, tag2, tag6]

以下两组 URL 将是结果

(siteA, siteB, siteD), (siteA, siteC)

因为 (siteA, siteB, siteD) 共享两个公共标签 (tag1, tag2) 并且 (siteA, siteC) 也共享两个公共标签 (tag1, tag3) 。

-- 条件 3,4 并添加了一个示例。谢谢@btilly。

我的问题是

  1. 如何解决（或可以应用哪种算法）并且实际上快速？
  2. 有没有可以用与这个问题类似的算法来解决的代表性问题？
4

1 回答 1

1

我将创建一个新的数据结构，即按标签，即具有该标签的 URL 的哈希值。

然后对于每一对标签，您可以获取 URL 较少的标签，遍历它们，并查找它是否在另一个标签中，生成共享该对标签的组。

如果您的n标签具有每个标签的平均murl，则需要O(n * m)生成新的数据结构并O(n * n * m)生成组。

于 2012-06-08T21:17:13.933 回答