首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。
上一节讲了如何用位图、布隆过滤器来过滤重复的数据。今天再讲一个与过滤相关的问题——如何过滤垃圾短信和骚扰电话。应该用什么样的数据结构和算法？
算法解析
基于黑名单的过滤器
可以维护一个骚扰电话号码和垃圾短信发送号码的黑名单。若黑名单中电话号码不多，可以用散列表、二叉树等动态数据结构来存储，对内存的消耗并不会很大。但是，若黑名单中的电话号码很多时，比如500万个，每个号码看作一个长度为16的字符串，那大概需要100MB的存储空间，有点大。
而上节讲的布隆过滤器最大的特点是比较省存储空间，比较适合解决这个问题。如果要存储 500 万个手机号码，把位图大小设置为 10 倍数据大小，也就是 5000 万个二进制位（5000 万 bits），不到 7MB 的存储空间。比起散列表的解决方案，内存的消耗减少了很多。
实际上，还有一种时间换空间的方法，可以将本地内存的消耗优化到极致。可以把黑名单存储在服务器上，手机只负责将检查的号码发送给服务器端，服务器端通过查找黑名单，判断这个号码是否应该被拦截，并将结果返回给手机端。这个思路不需要占用手机内存，但是因为存在网络延迟会导致处理速度降低。
但是，布隆过滤器会判错的——一个电话不在黑名单中，但是判定在黑名单中。这对用户无法接受。
基于规则的过滤器
对于基于黑名单的垃圾短信过滤方法，若号码不在黑名单中就无法进行拦截了。这时可以使用基于规则的过滤方法。例如若某条短信符合下面规则，则判定是垃圾短信：
- 短信中包含特殊单词（或词语），比如一些非法、淫秽、反动词语等；
- 短信发送号码是群发号码，非我们正常的手机号码，比如 +60389585；
- 短信中包含回拨的联系方式，比如手机号码、微信、QQ、网页链接等，因为群发短信的号码一般都是无法回拨的；
- 短信格式花哨、内容很长，比如包含各种表情、图片、网页链接等；
- 符合已知垃圾短信的模板。垃圾短信一般都是重复群发，对于已经判定为垃圾短信的短信，我们可以抽象成模板，将获取到的短信与模板匹配，一旦匹配，就可以判定为垃圾短信。
具体而言，我们可以综合多条规则判断是否为垃圾短信。或者每个规则对应一个不同的得分，当某条短信的得分超过某个阈值时，会被判定为垃圾短信。
上面规则中都隐藏着很多细节去处理。例如，如何定义第一个规则中的特殊单词呢？可以基于概率统计的方法，借助计算机强大计算能力，找出哪些单词最常出现在垃圾短信中，将其作为特殊单词。不过这种方法要求有大量标记好的短信样本。
假如有1000万条短信，对其进行分词处理（借助中文或者英文分词算法），去掉“的、和、是”等没有意义的停用词（Stop words），得到 n 个不同的单词。针对每个单词，求出其在垃圾短信中出现的概率与在非垃圾短信中出现的概率。若在一个单词在垃圾短信中出现的频率远高于在非垃圾短信中出现的概率，则把这单词作为特殊单词。比如：
基于概率统计的过滤器
基于规则的过滤器，有一定的局限性：
- 规则受人的思维方式局限，未免太过简单
- 垃圾短信设计者可以精心设计短信，绕过这些规则的拦截
针对这个，来看一种更加高级的过滤方式——基于概率统计的过滤方式，它的理论基础是朴素贝叶斯算法。所以首先介绍下什么是朴素贝叶斯算法？
假设事件A是“小明不去上学”，事件 B 是“下雨了”。统计下过去 10 天的下雨情况和小明上学的情况，作为样本数据。
分析数据，这10天中，下雨的概率为P(B)=4/10，小明不去上学的概率为P(A)=3/10。在4个下雨天中，小明有2天没去上学，所以下雨天不去上学的概率 P(A|B)=2/4。在小明没有去上学的 3 天中，有 2 天下雨了，所以小明因为下雨而不上学的概率是 P(B|A)=2/3。
实际上，这4个概率值之间，有一定的关系也就是朴素贝叶斯算法，公式表示如下：
如上，朴素贝叶斯算法用一个公式即可概括。那怎么用它来做垃圾短信的过滤呢？
基于概率统计的过滤器，是基于短信内容判定是否为垃圾短信。而计算机没法理解短信含义，所以需要把短信抽象成一组计算机可以理解并且方便计算的特征项，用这一组特征项代替短信本身，来做垃圾短信过滤。这同样可以借助分词算法，将短信分割成 n 个单词。这 n 个单词就是一组特征项，表示这个短信。因此，判定一个短信是否是垃圾短信这样一个问题，就变成了判定同时包含这几个单词的短信是否是垃圾短信。
不同于基于规则的过滤器，非黑即白。基于概率的方法使用概率表征一个短信是垃圾短信的可信程度。对应的公式如下：
若直接采用这个公式计算概率，则会出现因为样本数量有限，样本中不会有太多同时包含 $W_1，W_2，W_3，…，W_n$ 的短信的，导致计算出的概率不准。甚至很多时候，样本中根本不存在这样的短信，也就无法计算概率。
这时可以借助朴素贝叶斯公式，将这个概率的求解，分解为其他三个概率的求解。
$P（W_1，W_2，W_3，…，W_n 同时出现在一条短信中 | 短信是垃圾短信）$这个概率照样无法通过样本来统计得到。但是有下面一条著名公式：
独立事件发生的概率计算公式：$P(AB) = P(A)P(B)$。如果事件 A 和事件 B 是独立事件，两者的发生没有相关性，事件 A 发生的概率 P(A) 等于 p1，事件 B 发生的概率 P(B) 等于 p2，那两个同时发生的概率 $P(AB)$ 就等于 $P(A)P(B)$。
基于这条独立事件发生概率的计算公式，可以把$P（W_1，W_2，W_3，…，W_n 同时出现在一条短信中 | 短信是垃圾短信）$分解为下面这个公式：
对于公式中的另外两项，P（短信是垃圾短信）表示短信是垃圾短信的概率，很容易得到。不过，因为样本空间有限，$P（W_1，W_2，W_3，…，W_n 同时出现在一条短信中）$不好通过概率统计得到。
实际上，可以分别计算同时包含$W_1，W_2，W_3，…，W_n$ 这 n 个单词的短信，是垃圾短信和非垃圾短信的概率。假设它们分别是 p1 和 p2。我们并不需要单纯地基于 p1 值的大小来判断是否是垃圾短信，而是通过对比 p1 和 p2 值的大小，来判断一条短信是否是垃圾短信。
基于这两个概率的比值来判断是否为垃圾短信，求解 (p1/p2)时，$P（W_1，W_2，W_3，…，W_n 同时出现在一条短信中）$已经被抵消了。也就不用求解了。
总结引申
本节主要讲了基于黑名单、规则、概率统计三种垃圾短信的过滤方法。实际上，这三种方法还可以应用到很多类似的过滤、拦截领域，比如垃圾邮件的过滤。
在讲黑名单过滤时说到布隆过滤器可能会存在误判情况，可能会导致用户投诉。实际上，可以结合三种不同的过滤方式的结果，对同一个短信处理，如果三者都表明这个短信是垃圾短信，才把它当作垃圾短信拦截过滤，这样就会更精准。
实际过程中，我们要结合具体的场景，不断去调整策略，权衡垃圾短信判定的准确率（是否会把不是垃圾的短信错判为垃圾短信）和召回率（是否能把所有的垃圾短信都找到），来实现我们的需求。
