数据结构与算法之美
王争
前Google工程师
立即订阅
71655 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?

王争 2019-01-11
上一节我们讲到,如何用位图、布隆过滤器,来过滤重复的数据。今天,我们再讲一个跟过滤相关的问题,如何过滤垃圾短信?
垃圾短信和骚扰电话,我想每个人都收到过吧?买房、贷款、投资理财、开发票,各种垃圾短信和骚扰电话,不胜其扰。如果你是一名手机应用开发工程师,让你实现一个简单的垃圾短信过滤功能以及骚扰电话拦截功能,该用什么样的数据结构和算法实现呢?

算法解析

实际上,解决这个问题并不会涉及很高深的算法。今天,我就带你一块看下,如何利用简单的数据结构和算法,解决这种看似非常复杂的问题。

1. 基于黑名单的过滤器

我们可以维护一个骚扰电话号码和垃圾短信发送号码的黑名单。这个黑名单的搜集,有很多途径,比如,我们可以从一些公开的网站上下载,也可以通过类似“360 骚扰电话拦截”的功能,通过用户自主标记骚扰电话来收集。对于被多个用户标记,并且标记个数超过一定阈值的号码,我们就可以定义为骚扰电话,并将它加入到我们的黑名单中。
如果黑名单中的电话号码不多的话,我们可以使用散列表、二叉树等动态数据结构来存储,对内存的消耗并不会很大。如果我们把每个号码看作一个字符串,并且假设平均长度是 16 个字节,那存储 50 万个电话号码,大约需要 10MB 的内存空间。即便是对于手机这样的内存有限的设备来说,这点内存的消耗也是可以接受的。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(27)

  • 木木匠
    我觉得这种分类过滤,最好的可能是机器学习,通过大量的垃圾短信样本来训练特征,最后可以达到过滤短信和邮件的目的,而且这种方法应该效果更好,至于电话拦截,实际上就是电话号码黑名单的问题,我觉得用布隆过滤器可以满足通用场景,一般实际场景中,对于这种电话是提示谨慎接听,但是我们可以本地和云端结合处理,解决部分的误报问题,当判断是黑名单的时候再去云端查,确认是否是真的黑名单。这样用布隆过滤器+云端也是一种方式
    2019-01-11
    1
    20
  • slvher
    对于短信文本,机器学习尤其是 NLP 方向的很多算法可用于 anti-spam。文本分类任务,特征工程做得稍用心的话,判别式模型(典型如 logistic regression)的效果通常好于生成式模型(典型如 naive-bayes)。

    对于电话号码数字,感觉用正则或定时拉取黑名单比 ml 模型简单可靠。
    2019-01-11
    16
  • C_love
    为啥P(W1W2...Wn|垃圾短信)是独立事件,能够拆成乘积,而P(W1W2...Wn)不是独立事件?

    作者回复: 也是也是。

    2019-01-14
    10
  • 纯洁的憎恶
    黑名单过滤法基于经验判断,难以确保及时性。基于内容规则的过滤法容易被针对,而且动态调整规则的成本较高。基于朴素贝叶斯算法的内容概率过滤法,既可以确保及时性,又能够较好的基于实际情况的变化而变化,具备初步智能特性。因为贝叶斯方法是基于先验判断,然后根据现实反馈动态调整判断的算法。

    当绝对值不好计算时,可以结合场景需要,合理使用相对值代替绝对值,以简化计算难度、消除无法计算的因子。
    2019-01-11
    5
  • 小新村小学扛霸子
    P(W1,W2...Wn同时出现在一条短信中) = P(W1出现在短信中) * P(W2出现在短信中) *....* P(Wn出现在短信中)这样计算应该就可以吧
    2019-04-25
    2
  • ldd
    请问,基于黑名单的过滤方式,用布隆过滤器只能存储Bool值,即是否存储,但是还要实现“标记次数来判断是否达到阈值”,就需要额外的散列表了,需要的内存空间依然很大,方案上还不如直接用散列表来的更好吧?

    作者回复: 你说的这是一种情况,大部分情况,都不会命中,也就说,都不是骚扰电话。

    2019-04-08
    2
  • loda
    朴素贝叶斯讲的很好
    2019-04-06
    2
  • Clement
    图片上的数据和公式使用什么软件画出来的?

    编辑回复: iPad Paper

    2019-01-21
    2
  • 墨禾
    其实这个问题就是个分类预测问题,传统的机器学习方法中的分类预测算法都可以用
    2019-01-11
    2
  • junjun
    以前把算法一直和程序联系起来,现在突然发现,算法存在我们生活的各个方面,任何地方都是算法,比如你今天准备吃啥,其实也是一个算法。
    2019-09-26
    1
  • lttzzlll
    上一节我们讲了,布隆过滤器最大的特点就是比较省存储空间,所以,用它来解决这个问题再合适不过了。如果我们要存储 500 万个手机号码,我们把位图大小设置为 10 倍数据大小,也就是 5000 万,那也只需要使用 5000 万个二进制位(5000 万 bits),换算成字节,也就是不到 7MB 的存储空间。比起散列表的解决方案,内存的消耗减少了很多。

    这段话中:对于需要使用的内存空间有疑问,按照上一节的处理方式,把手机号码转换为整数,使用的内存空间应该是整数的范围 * 10 bits, 而不是手机号的数量 * 10 bits? 或者,这里不把手机号码转化为整数,用其他的哈希方法,把这500w个手机号映射到[0, 500W)这个区间内?

    作者回复: 布隆过滤器本身就是解决位图消耗空间比较多的问题。位图的大小是数据的范围。而布隆过滤器的大小应该是小于位图大小的,所以肯定就是数据的范围了。

    2019-02-17
    1
  • 🐱您的好友William🐱
    1.为啥叫naive:因为假设了条件分布中各个feature是独立出现的,feature之间啥关系没有!所以很naive,很朴素,很“傻”,但是效果真的不一定差,而且在没开发出更好的模型之前直接进行统计计算就能得出结果,且可以做成online的,怎么看都不亏啊(反正你也得用统计数据做其他的事,顺道做了呗老弟)!

    2.如果概率为0了怎么办!可以使用laplacian smoothing,简单的来说就是在分子分母上面加数来保证不会有0的出现。直接使用很小的数是可以的(遵循频率学派频率为大),但更精确的在分母分子上加什么,这个其实是与贝叶斯学派所认为的先验分布有关,就是在不看sample时,我们的先验知识对这种情况的估计是多少(比如我在不统计工科学校男女比例的时候就有了一定的先验知识:7:1,之后我再统计其实是对我的先验估计的一种调整)。
    2019-01-21
    1
  • ban
    https://www.jianshu.com/p/5cf3a155b2f0
    找到另外一个相亲的例子
    2019-01-13
    1
  • Geek_477c02
    P( Wi出现在短信中 | 短信是垃圾短信)表示垃圾短信中包含 Wi这个单词的概率有多大。

    如果wi出现的概率是0怎么办,连乘导致结果是0了?
    2019-01-13
    1
  • Kudo
    朴素贝叶斯模型的一个基本假设是条件独立性,即假定w1, w2, ..., wn之间相互独立。这是一个较强的假设,正是这一假设,使朴素贝叶斯的学习与预测大为简化,且易于实现,其缺点是分类的准确率不一定高。
    2019-01-11
    1
  • wenxueliu
    深度学习的经典例子。吴恩达的课上就有。
    2019-10-26
  • 🇩 🇱 🇱
    那p1/p2到底是多少呢
    2019-09-19
  • 李冲
    思考题可以借鉴推荐系统的思路不?就是以近邻的方式推测最终评价结果。

    载体的内容的评分是一个维度,其他维度可以考虑历史联系次数占比,历史联系频度。如果结果偏向负面,有条件也可以在云端查询对方的近期行为的评分。

    其实常见的做法都能够解决问题,搞不定的反而是那些白名单。银行总机打电话推销保险谁能拦得住
    2019-09-16
  • Paul Shan
    现在基于有监督的深度学习的检测算法比较流行,也就是通过标注样本来检测。这种方法的好处是准确率高,而且可以与时俱进,动态调整。缺点是训练模型时间长,消耗运算量大,需要标注的样本多。
    2019-08-05
  • ferry
    将短信内容中的分词假设为完全独立是不是不太符合实际情况呢?是否应该使用多元文法,假设为分词与前若干个分词相关呢?

    作者回复: 你说的也没错,不过那样就复杂了。

    2019-06-11
收起评论
27
返回
顶部