算法图解-备忘

看了算法图解，除了上两篇讲的快速排序和动态规划，了解到几点知识点记录下：

1. K最近邻算法
   用于分类和回归，需要已最近的邻居作为衡量；可用来预测用户偏好，做成推荐系统，或者机器学习OCR识别文字、垃圾邮件过滤器；K最近邻算法使用的是计算用户间的距离来计算用户相似度，还有一种是余弦相似度；

2. 反向索引
   可用于搜索引擎；原理是抽取网页的关键字，将这些内容创建一个散列表，这个散列表的键为单词，值为包含指定单词的页面。现在假设有用户搜索hi, 在这种情况下，搜索引擎需要检查哪些页面包含hi, 那去查散列表就简单多了。
   将单词映射到包含它的页面，这种数据结构被称为反向索引。

3. 傅里叶变换
   绝妙、优雅且应用广泛的算法少之又少，傅里叶变换算是一个。Better Explained是一个杰出
   的网站，致力于以通俗易懂的语言阐释数学，它就傅里叶变换做了一个绝佳的比喻:给它一杯冰沙，它能告诉你其中包含哪些成分1。换言之，给定一首歌曲，傅里叶变换能够将其中的各种频
   率分离出来。
   傅里叶变换能够准确地指出各个音符对整个歌曲的 贡献，让你能够将不重要的音符删除。这就是MP3格式的工作原理!
   使用傅里叶变换可创建类似于Shazam这样的音乐识别软件。
   原来网易云音乐听歌识曲就是这个算法。

4. MapReduce 分布式算法
   分布式算法非常适合用于在短时间内完成海量工作，其中的MapReduce基于两个简单的理 念:映射(map)函数和归并(reduce)函数。

5. 布隆过滤器和HyperLogLog

布隆过滤器是一种概率型数据结构，它提供的答案有可能不对， 但很可能是正确的。为判断网页以前是否已搜集，可不使用散列表，而使用布隆过滤器。使用散 列表时，答案绝对可靠，而使用布隆过滤器时，答案却是很可能是正确的。

假设你在Google负责搜集网页，但只想搜集新出现的网页，因此需要判断网页是否搜集过。
使用布隆过滤器 就有两种情况：
可能出现错报的情况，即Google可能指出“这个网站已搜集”，但实际上并没有搜集。
不可能出现漏报的情况，即如果布隆过滤器说“这个网站未搜集”，就肯定未搜集。

HyperLogLog近似地计算集合中不同的元素数，与布隆过滤器一样，它不能给出准确的答案， 但也八九不离十，而占用的内存空间却少得多。
面临海量数据且只要求答案八九不离十时，可考虑使用概率型算法!

6. SHA加密算法和SimHash算法

散列表有几部分构成：
(1) 散列表容量大小
(2) 散列函数
(3) 填充因子 (大于填充因子 就要考虑扩容)
(4) 冲突
(5) 冲突解决方案

SHA加密算法： 散列表局部不敏感，假设你有一个字符串并计算了其散列值。
dog ----> cd6357
此时你修改其中的一个字符，再计算其散列值，结果将截然不同：
dot ----> e392da
这样攻击者不能通过比较散列值是否类似来破解密码

Simhash:
但有时你希望散列函数是局部敏感的，那就使用Simhash算法。如果你对字符串做细微的修改，Simhash生成的散列值也只存在细微的差别。这对你通过比较散列值来判断两字符川的相似度很有用。
那它的应用场景就有：
(1) Google使用Simhash来判断网页是否已搜集。
(2) 老师可以使用Simhash来判断学生的论文是否是从网上抄的。
(3) Scribd允许用户上传文档或图书，以便与人分享，但不希望用户上传有版权的内容！这个网站可使用Simhash来检查上传的内容是否与小说《哈利.波特》类似，类似则自动拒绝。
(4) 需要检查两项内容的相似度，Simhash很有用。