高级应用篇三

问题一：如果你是一名手机应用开发工程师，让你实现一个简单的垃圾短信过滤功能以及骚扰电话拦截功能，该用什么样的数据结构和算法实现呢？

解题思路：

1，基于黑名单的过滤器。可以维护一个骚扰电话号码和垃圾短信发送号码的黑名单。方法一，如果黑名单中的电话号码不多的话，我们可以使用散列表，二叉树等动态数据结构存储。方法二，如果黑名单中的电话号码很多的话，我们可以使用上节所说的布隆过滤器，其最大的特点就是节省内存空间。方法三，还有一种时间换空间的方法，可以将内存的消耗优化到极致。可以把黑名单存储在服务器端，把过滤和拦截的核心工作，交给服务器来做，手机端只负责将要检查的号码发送给服务端，服务器端通过查黑名单，判断这个号码是否应该被拦截，并将结果返回手机端。但是这种方法严重依赖于网络。而且方法二使用布隆过滤器会出现错判的情况

2，基于规则的过滤器。对于短信来说，我们可以通过短信的内容，来判断是否是垃圾短信。可以先预设一些规则，比如短信中包含特殊单词，短信发送的号码是群发号码，短信中包含回拨的联系方式，短信格式很花哨等。如果满足以上规则几条就设定为垃圾短信。同时对特殊单词统计时可以根据已有的垃圾短信，进行分词处理，然后得到较为常用的垃圾短信。

3，基于概率统计的过滤器。基于概率统计的过滤器，是基于短信内容来判定是否是垃圾短信。我们需要把短信抽象成一组计算机可以理解并且方便计算的特征项，用这一组特征项代替短信本身，来做垃圾短信过滤。

首先通过分词算法，把一个短信分割成n个单词。这n单词就是一组特征项，全权代表这个短信。那么判定一个短信是否是垃圾短信就变成：

P(短信是垃圾短信 | w1,w2,...,wn同时出现在一条短信中)

根据朴素贝叶斯算法：

P(短信是垃圾短信 | w1,w2,...,wn同时出现在一条短信中) = P(w1,w2,...,wn同时出现在一条短信中 | 短信是垃圾短信 ) * P(短信是垃圾短信) / P(w1,w2,...,wn同时出现在一条短信中)

---

问题二：各种音乐App的功能越来越强大，不仅可以自己选歌听，还可以根据你听歌的口味偏好，给你推荐可能会喜爱的音乐，而且有时候，推荐的音乐还非常适合你的口味，如此智能的一个功能，你知道它是怎么实现的吗？

问题分析：这个问题，并不需要特别高深的理论。解题思路的核心思想非常简单，直白。一是找到跟你口味偏好相似的用户，把他们爱听的歌曲推荐给你；二是找出跟你喜爱的歌曲特征相似的歌曲，把这些歌曲推荐给你。

基于相似用户做推荐：只需要遍历所有的用户，对比每个用户跟你共同喜爱的歌曲个数，并且设置一个阈值，如果你和某个用户共同喜爱的歌曲个数超过这个阈值，就可以把这个用户看作跟你口味相似的用户，从而把这个用户喜爱但你还没听过的歌曲，推荐给你。

但是这里还有一个问题是如何知道用户喜爱那首歌曲呢？需要用户对某首歌曲定义喜爱的程度。然后就可以列出用户对每首歌的喜爱程度，遍历所有用户后，利用欧几里德距离来判断两个用户是否口味相似。

基于相似歌曲做推荐：最容易想到的是，我们对歌曲定义一些特征项，比如伤感，愉快，摇滚，民谣，是柔和还是高亢等等。类似基于相似用户的推荐方法，我们给每个歌曲的每个特征项打一个分数，这样每个歌曲就都有对应的特征项向量。基于这个特征向量，来计算两个歌曲之间的欧几里德距离。距离越小，表示两个歌曲的相似度越大。

但是要实现这个方案，需要有一个前提，那就是我们能够找到足够多，并且能够全面代表歌曲特点的特征项，除此之外，我们还要人工给每首歌标注每个特征项的得分，这明显是一个非常大的工程，此外人工标注有很大的主观性，也影响推荐的准确性。

既然基于歌曲特征项计算相似度不行，换一种思路。对于两首歌，如果喜欢听的人群都是差不多的，那侧面就可以反映出，这两首歌比较相似。每个用户对歌曲有不同的喜爱程度，我们依旧可以通过上一个解决方案中定义得分的标准，来定义喜爱程度。基于相似用户的推荐方法中，针对每个用户，我们将对各个歌曲的喜爱程度作为向量。基于相似歌曲的推荐思路中，针对每个歌曲，我们将每个用户的打分作为向量。然后计算向量之间的欧几里得距离，来表示歌曲之间的相似度。