求一个可行方案：计算新用户和老用户通讯录的最高匹配度

[iblislsy]

需求： 对于每一个新用户，希望能计算出和老用户的通讯录最高匹配度，找到类似伪造通讯录的情况。

例子： 每一个用户的通讯录表结构如下

user_id phone

123 18721212111

123 18721212112

123 18721212113

124 18721212111

124 18721212112

124 18721212115

124 18721212116

假设 user_id:123 是一个新用户，可以发现用户 123 和用户 124 存有相同的联系人

用户 123 和 124 的匹配度为: 相同号码数量 /新用户的号码数量 = 2/3 = 0.67

需要遍历找到匹配度最高的用户，或者是大于某一阈值的用户群体。

各位大佬，这个复杂度似乎有点高，有没有可行的方案。

[owenliang]

什么叫钢筋

[iblislsy]

@owenliang 下午试了一下 ES，包括数据导入和查询，效率上挺快的，分布式还没有研究。 钢筋就是，任何时候都能抬杠，找存在感。

[owenliang]

@iblislsy es 很成熟的，你这个需求取决于召回阶段拥有相同号码的记录数量，肯定不会很大，所以参与聚合计算量也不大，选型 es 问题不大。

[sky101001]

个人觉得数据量较大时，利用 Bloom Filter 是最佳解决方案：
1. 首先设计几个不同的 hash 函数，这些 hash 函数可以把手机号映射到 256bit 的空间里，并具有“稀疏”的特点（就是说 1 的数量很少，几乎全是 0 ）比如手机号 A 可以在 hash 后得到 00100010，手机号 B 得到 00100001。
2. 然后对用户通讯录里的每个手机号进行 hash 操作，并将所得的结果按位相加，得到一个签名。比如手机号 AB 相加，得到 00100011。不同的 hash 算法可以得到不同的签名。记录这些签名。
3. 每当有新用户注册，对其通讯录进行以上处理，得到其签名（如 00100001 ）。将新用户的签名和老用户的签名进行与操作，记录 1 的个数，1 的个数最多的，就可能是最相似的。
这样初筛时间复杂度是 O(N)，之后再进行处理就快多了。

[Xs0ul]

你这个 Bloom Filter 有点问题，即使每个手机号 hash 之后稀疏，一堆手机号取或以后，1 还是很多的，就不洗漱了。Bloom Filter 概念上是检查一个元素在不在一个集合里的，而不是比较两个文档的相似度。估计文档相似度的算法是楼上说的 minHash 和 LSH。

@iblislsy #21 你这个例子不用分词，每个手机号就是一个单词，一个人的通讯录组成一篇“文档”。当然你可以用取前 N 位或 hash 之类的办法来降低“词汇量”。

[sky101001]

@Xs0ul 是的，这个不是 bloomfilter 的标准用法，在取或操作后摘要不再稀疏。 个人是觉得在文本长度不定的情况下，用局部敏感哈希按照（相同号码数量 /新用户的号码数量）计算相似度会比较麻烦，所以提了这个方法。本质上是就给号码归类以降低计算量。

最终要的就是这个不稀疏的结果，假设有三个签名，分别为 11000110，11000100，01100111，可以很容易地看出前两个数据集重合的可能性更大，这样就可以筛除海量数据中不相似的那部分。

当然，这是有误判的概率的，这个概率是和 hash 函数以及签名的长度有关的。这种 hash 函数，很好取，提一个不太好的函数--比如我希望 hash 函数要在 256bit 的空间里至多有 2 个 1，我可以把 md5 的最后 16 位分成两段 8 位的摘出来，决定这两个 1 的位置。

[xiaoxinshiwo]

楼主，redis 的 set 数据类型可以支持完成你的需求，求并集即可；
Redis Set 是 String 的无序排列。SADD 指令把新的元素添加到 set 中。对 set 也可做一些其他的操作，比如测试一个给定的元素是否存在，对不同 set 取交集，并集或差，等等。

[xiaoxinshiwo]

另外推荐看看：MapReduce 练习----求共同好友
https://blog.csdn.net/zyz_home/article/details/79659694

[xiaoxinshiwo]

@guyskk0x0 #24 用 redis 何不使用 set ？可以直接取交集

[guyskk0x0]

@xiaoxinshiwo 这里需求是在 N 个集合里找与目标交集最大的一个，不是简单的求交集

[xiaoxinshiwo]

@guyskk0x0 #50 知道啊，无非使用定时任务跑 N 次嘛