新浪微博笔试题：找出共有2个以上标签的用户对

题目：给定sina微博的全部用户(1亿以上)和标签(uniq的标签30万左右)的关系， 系统找出共有2个或以上标签的用户对，并给出这些标签是哪些。

• input：userid,taglist

• output：userid,userid,con-taglist (sizeof(con_taglist)>=2)

数据示例

   输入

• AA，体育 新闻清华 百年校庆
• BB，娱乐 八卦清华 新闻
• CC，体育 娱乐新闻
• DD，八卦 新闻娱乐

   输出

• AA，BB 清华 新闻
• AA，CC 体育 新闻
• BB，CC 娱乐 新闻
• BB，DD 娱乐 八卦 新闻
• CC，DD 娱乐 新闻

接下来就一起来想办法解决上面的难题。基于对于新浪微博的了解，以下内容可能会在实现中起到一些作用：

• 目前新浪微博每个用户最多可设置标签10个；
• 目前有相当数量的用户是没有设置标签的。

   解决问题思路：(自己整理的笨办法，自己能力有限暂时想不到更好的方案)

• 删除没有标签的用户数据，这一操作可以先把一部分不需要纳入分析的数据给排除掉。具体数量未知。

• 建立标签到用户的倒排索引。从以上数据上来看，平均每个标签用户对应的用户ID链要小于10^8*10/30^4 = 3000，但同时要考虑热门标签的ID数量会非常的大。

• 去除倒排索引后只有一个用户数的标签，这个估计可以去除的量很少。

• 对于删除后没有标签的数据按ID大小进行排序。

• 对于用户依次取其标签，查找倒排索引，找到共有用户。(只查找倒排索引中比用户ID比自己大的用户)

   基于以上的想法，考虑的新浪微博应该采用了 NOSQL存储，我们先假定具体数据格式如下：

• {“userid”:123,”taglist”:[“体育”,”新闻”,”清华”,”百年校庆”]}

• {“userid”:124,”taglist”:[“娱乐”,”新闻”,”清华”,”八卦”]}

• {“userid”:125,”taglist”:[“娱乐”,”新闻”,”体育”]}

• {“userid”:126,”taglist”:[“娱乐”,”新闻”,”八卦”]}

   就上面的一些数据我尝试了下将上面的数据进行倒排索引。具体的Python实现方法(代码写的比较丑，对于python怎么使用MapReduce)：

# -*- coding: utf-8 -*-
tagDB = open('tag.txt','r')
list = [s.strip() for s in tagDB.readlines()]
result={}
for i in list:
    data = eval(i)
    userid = data['userid']
    taglist = data['taglist']
    for tag in taglist:
        if result.has_key(tag):
            result[tag].append(userid)
        else:
            result[tag] = [userid]
print result
tagDB.close()

   如果你有更好的解决方案，欢迎分享~