1 过滤垃圾短信？
买房、贷款、投资理财、开发票，各种垃圾短信和骚扰电话。 实现垃圾短信过滤功能及骚扰电话拦截功能，用啥数据结构和算法？
2 基于黑名单的过滤器
可维护一个骚扰电话号码和垃圾短信发送号码的黑名单。
2.1 黑名单搜集途径
- 公开网站下载
- 类似“360骚扰电话拦截”的功能
- 用户自主标记骚扰电话
被多个用户标记&&标记个数超过一定阈值的号码，即可定义为骚扰电话，加入黑名单。
若黑名单号码不多，可用散列表、二叉树等动态数据结构存储，对内存占用不多。
把每个号码看作一个字符串，且假设平均长度16字节，则存储50万个电话号码，大约需10MB内存。对手机，这点内存消耗也可接受。
但若黑名单中的电话号码很多？如500万。再用散列表需约100MB。为实现一个拦截功能，耗费用户这些手机内存，不合理。
2.2 布隆过滤器
省存储空间，再合适不过。 存储500万个手机号码，把位图大小设为10倍数据大小，即5000万，则只需使用5000万个二进制位（5000万bits），换算成字节，7MB不到。
时间换空间，可将内存的消耗优化到极致。可将黑名单存储在服务器端，把过滤和拦截的核心工作，交给服务端：
- 手机端只负责将待检号码发给服务器端
- 服务端通过查黑名单，判断该号码是否该被拦截，并将结果返给手机端
用这解决思路完全不占用手机内存。但有利就有弊，网络通信较慢，所以，网络延迟就会导致处理速度降低。该方案还要求联网才能正常工作。
判错概率
若它把一个重要的电话或者短信，当成垃圾短信或者骚扰电话拦截了，对于用户来说，这是无法接受的。这是个大问题。
3 基于规则的过滤器
若某垃圾短信发送者的号码不在黑名单，上面方法就无法拦截。 还可通过短信内容，判断某条短信是否是垃圾短信。 预先设定一些规则，若某条短信符合这些规则，就可判定它是垃圾短信：
- 短信包含特殊单词（或词语），如一些非法、淫秽、反动词语
- 短信发送号码是群发号码，非正常手机号，如 60389585
- 短信中包含回拨的联系方式，如手机号码、微信、QQ、网页链接等，因为群发短信的号码一般都是无法回拨
- 短信格式花哨、内容很长，比如包含各种表情、图片、网页链接等
- 符合已知垃圾短信的模板。垃圾短信一般都是重复群发，对于已经判定为垃圾短信的短信，我们可以抽象成模板，将获取到的短信与模板匹配，一旦匹配，就可判定为垃圾短信。
当然，如果短信只是满足其中一条规则，如果就判定为垃圾短信，那会存在比较大的误判的情况。我们可以综合多条规则进行判断。比如，满足2条以上才会被判定为垃圾短信；或者每条规则对应一个不同的得分，满足哪条规则，我们就累加对应的分数，某条短信的总得分超过某个阈值，才会被判定为垃圾短信。
不过，我只是给出了一些制定规则的思路，具体落实到执行层面，其实还有很大的距离，还有很多细节需要处理。比如，第一条规则中，如何定义特殊单词；第二条规则中，我们该如何定义什么样的号码是群发号码等等。
如何定义特殊单词？
如果只是自己盘脑袋想，哪些单词属于特殊单词，那势必有比较大的主观性，也很容易漏掉某些单词。可基于概率统计方法，借助计算机强大的计算能力，找出哪些单词最常出现在垃圾短信中，将这些最常出现的单词，作为特殊单词，用来过滤短信。
不过这种方法的前提是，我们有大量的样本数据，也就是说，要有大量的短信（比如1000万条短信），并且我们还要求，每条短信都做好了标记，它是垃圾短信还是非垃圾短信。
我们对这1000万条短信，进行分词处理（借助中文或者英文分词算法），去掉“的、和、是”等没有意义的停用词（Stop words），得到n个不同的单词。针对每个单词，我们统计有多少个垃圾短信出现了这个单词，有多少个非垃圾短信会出现这个单词，进而求出每个单词出现在垃圾短信中的概率，以及出现在非垃圾短信中的概率。如果某个单词出现在垃圾短信中的概率，远大于出现在非垃圾短信中的概率，那我们就把这个单词作为特殊单词，用来过滤垃圾短信。
文字描述不好理解，我举个例子来解释一下。
4 基于概率统计的过滤器
基于规则的过滤器，看起来很直观，也很好理解，但有一定局限性：
- 这些规则受人的思维方式局限，规则过简单
- 垃圾短信发送者可能会针对规则，精心设计短信，绕过这些规则的拦截
再看种更高级过滤方式，基于概率统计。基础理论是基于朴素贝叶斯算法。
什么是朴素贝叶斯算法？
假设事件A是“小明不去上学”，事件B是“下雨了”。统计一下过去10天的下雨情况和小明上学的情况，作为样本数据。
我们来分析一下，这组样本有什么规律。在这10天中，有4天下雨，所以下雨的概率P(B)=4/10。10天中有3天，小明没有去上学，所以小明不去上学的概率P(A)=3/10。在4个下雨天中，小明有2天没去上学，所以下雨天不去上学的概率P(A|B)=2/4。在小明没有去上学的3天中，有2天下雨了，所以小明因为下雨而不上学的概率是P(B|A)=2/3。实际上，这4个概率值之间，有一定的关系，这个关系就是朴素贝叶斯算法，我们用公式表示出来，就是下面这个样子。
朴素贝叶斯算法是不是非常简单？我们用一个公式就可以将它概括。弄懂了朴素贝叶斯算法，我们再回到垃圾短信过滤这个问题上，看看如何利用朴素贝叶斯算法，来做垃圾短信的过滤。
基于概率统计的过滤器，是基于短信内容来判定是否是垃圾短信。而计算机没办法像人一样理解短信的含义。所以，我们需要把短信抽象成一组计算机可以理解并且方便计算的特征项，用这一组特征项代替短信本身，来做垃圾短信过滤。
我们可以通过分词算法，把一个短信分割成n个单词。这n个单词就是一组特征项，全权代表这个短信。因此，判定一个短信是否是垃圾短信这样一个问题，就变成了，判定同时包含这几个单词的短信是否是垃圾短信。
不过，这里我们并不像基于规则的过滤器那样，非黑即白，一个短信要么被判定为垃圾短信、要么被判定为非垃圾短息。我们使用概率，来表征一个短信是垃圾短信的可信程度。如果我们用公式将这个概率表示出来，就是下面这个样子：
5 总结
这三种方法，还可以应用到很多类似的过滤、拦截的领域，如垃圾邮件过滤。
布隆过滤器可能误判，可能会导致用户投诉。可结合三种不同的过滤方式的结果，对同一个短信处理，如果三者都表明这个短信是垃圾短信，我们才把它当作垃圾短信拦截过滤，就更精准。
实际还要结合具体场景，以及大量的实验，不断去调整策略，权衡垃圾短信判定的准确率（是否会把不是垃圾的短信错判为垃圾短信）和召回率（是否能把所有的垃圾短信都找到），来实现需求。
