> For the complete documentation index, see [llms.txt](https://data-structure-and-algorithm.gitbook.io/project/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://data-structure-and-algorithm.gitbook.io/project/suan-fa-ji-ben-suan-fa-si-xiang/qi-ta-suan-fa.md).

# 其他算法

## 树

每当用户登录Facebook时，Facebook都必须在一个庞大的数组中 查找，核实其中是否包含指定的用户名。前面说过，在这种数组中查找时，最快的方式是二分查 找，但问题是每当有新用户注册时，都必须将其用户名插入该数组并重新排序，因为二分查找仅 在数组有序时才管用。如果能将用户名插入到数组的正确位置就好了，这样就无需在插入后再排 序。为此，有人设计了一种名为二叉查找树（binary search tree）的数据结构。

如果你对数据库或高级数据结构感兴趣，请研究如下数据结构：B树，红黑树，堆， 伸展树。

## 反向索引

这是一种很有用的数据结构：一个散 列表，将单词映射到包含它的页面。这种数据结构被称为反向索引（inverted index），常用于创 建搜索引擎。如果你对搜索感兴趣，从反向索引着手研究是不错的选择。

## 傅里叶变换

给定一首歌曲，傅里叶变换能够将其中的各种频 率分离出来。 这种理念虽然简单，应用却极其广泛。例如，如果能够将歌曲分解为不同的频率，就可强化 你关心的部分，如强化低音并隐藏高音。傅里叶变换非常适合用于处理信号，可使用它来压缩音 乐。为此，首先需要将音频文件分解为音符。

傅里叶变换能够准确地指出各个音符对整个歌曲的 贡献，让你能够将不重要的音符删除。这就是MP3格式的工作原理！ 数字信号并非只有音乐一种类型。JPG也是一种压缩格式，也采用了刚才说的工作原理。傅 里叶变换还被用来地震预测和DNA分析。 使用傅里叶变换可创建类似于Shazam这样的音乐识别软件。傅里叶变换的用途极其广泛，你 遇到它的可能性极高！

## 并行算法

有一种特殊的并行算法正越来越流行，它就是分布式算法。在并行算法只需两到四个内核时， 完全可以在笔记本电脑上运行它，但如果需要数百个内核呢？在这种情况下，可让算法在多台计 算机上运行。MapReduce是一种流行的分布式算法，你可通过流行的开源工具Apache Hadoop来 使用它。

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

映射是将一个数组转换为另一个数组。

![](https://3953159057-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-L_oS8XWzoA34pjHOQZS%2F-LblDHerLneCqvXOzx5k%2F-LblKR3U7Wz6MGH97Dld%2Fimage.png?alt=media\&token=5eca72f2-f79e-4f34-979c-9c4a3ca75ec5)

而归并是将一个数组转换为一个元素。

![](https://3953159057-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-L_oS8XWzoA34pjHOQZS%2F-LblDHerLneCqvXOzx5k%2F-LblKVwsLsxNhjlA8ICs%2Fimage.png?alt=media\&token=8828e75d-19de-418f-806a-2dc7d54a0ae7)

### 布隆过滤器和 HyperLogLog

假设你管理着网站Reddit。每当有人发布链接时，你都要检查它以前是否发布过，因为之前 未发布过的故事更有价值。 又假设你在Google负责搜集网页，但只想搜集新出现的网页，因此需要判断网页是否搜集过。 在假设你管理着提供网址缩短服务的bit.ly，要避免将用户重定向到恶意网站。你有一个清单，其中记录了恶意网站的URL。你需要确定要将用户重定向到的URL是否在这个清单中。 这些都是同一种类型的问题，涉及庞大的集合。

给定一个元素，你需要判断它是否包含在这个集合中。为快速做出这种判断，可使用散列表。 例如，Google可能有一个庞大的散列表，其中的键是已搜集的网页。

只是Google需要建立数万亿个网页的索引，因此这个散列表非常大，需要占用大量的存储空 间。Reddit和bit.ly也面临着这样的问题。面临海量数据，你需要创造性的解决方案！

#### 布隆过滤器

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

1. 可能出现错报的情况，即Google可能指出“这个网站已搜集”，但实际上并没有搜集。
2. 不可能出现漏报的情况，即如果布隆过滤器说“这个网站未搜集”，就肯定未搜集。

 布隆过滤器的优点在于占用的存储空间很少。使用散列表时，必须存储Google搜集过的所有 URL，但使用布隆过滤器时不用这样做。布隆过滤器非常适合用于不要求答案绝对准确的情况， 前面所有的示例都是这样的。对bit.ly而言，这样说完全可行：“我们认为这个网站可能是恶意的， 请倍加小心。

#### HyperLogLog

HyperLogLog是一种类似于布隆过滤器的算法。如果Google要计算用户执行的不同搜索的数 量，或者Amazon要计算当天用户浏览的不同商品的数量，要回答这些问题，需要耗用大量的空 间！对Google来说，必须有一个日志，其中包含用户执行的不同搜索。有用户执行搜索时，Google 必须判断该搜索是否包含在日志中：如果答案是否定的，就必须将其加入到日志中。即便只记录 一天的搜索，这种日志也大得不得了！ 

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

### SHA算法

安全散列算法（secure hash algorithm，SHA）函数。给定一个字符串，SHA 返回其散列值。

用于创建散列表的散列函数根据字符串生成数组索引，而SHA根据字符串生成另一个字符串。 对于每个不同的字符串，SHA生成的散列值都不同。

![](https://3953159057-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-L_oS8XWzoA34pjHOQZS%2F-LblDHerLneCqvXOzx5k%2F-LblMJuj3vWGDaQJAjbK%2Fimage.png?alt=media\&token=6bf2bd0d-6ec0-49f7-8fcf-d3d10614e422)

两个文件是否相同比较

你可使用SHA来判断两个文件是否相同，这在比较超大型文件时很有用。假设你有一个4 GB 的文件，并要检查朋友是否也有这个大型文件。为此，你不用通过电子邮件将这个大型文件发送 给朋友，而可计算它们的SHA散列值，再对结果进行比较。

密码检查

SHA还让你能在不知道原始字符串的情况下对其进行比较。例如，假设Gmail遭到攻击，攻 击者窃取了所有的密码！你的密码暴露了吗？没有，因为Google存储的并非密码，而是密码的 SHA散列值！你输入密码时，Google计算其散列值，并将结果同其数据库中的散列值进行比较。

你可以通过字符串计算出散列值，但却不能从散列值逆推出字符串；而且稍微修改一下字符串，计算出的散列值也很不相同；

### 局部敏感的散列算法Simhash

有时候，你希望结果相反，即希望散列函数是局部敏感的。在这种情况下，可使用Simhash。 

1. 如果你对字符串做细微的修改，Simhash生成的散列值也只存在细微的差别。这让你能够通过比 较散列值来判断两个字符串的相似程度，这很有用！ 
2. Google使用Simhash来判断网页是否已搜集。 
3. 老师可以使用Simhash来判断学生的论文是否是从网上抄的。 
4. Scribd允许用户上传文档或图书，以便与人分享，但不希望用户上传有版权的内容！这个 网站可使用Simhash来检查上传的内容是否与小说《哈利·波特》类似，如果类似，就自动拒绝。

### Diffie-Hellman密钥交换

这里有必要提一提Diffie-Hellman算法，它以优雅的方式解决了一个古老的问题：如何对消息 进行加密，以便只有收件人才能看懂呢？ 最简单的方式是设计一种加密算法，如将a转换为1，b转换为2，以此类推。

Diffie-Hellman使用两个密钥：公钥和私钥。顾名思义，公钥就是公开的，可将其发布到网站 上，通过电子邮件发送给朋友，或使用其他任何方式来发布。你不必将它藏着掖着。有人要向你 发送消息时，他使用公钥对其进行加密。加密后的消息只有使用私钥才能解密。只要只有你知道 私钥，就只有你才能解密消息！ 

Diffie-Hellman算法及其替代者RSA依然被广泛使用。如果你对加密感兴趣，先着手研究 Diffie-Hellman算法是不错的选择：它既优雅又不难理解。

### 线性规划

最好的东西留到最后介绍。线性规划是我知道的最酷的算法之一。 **线性规划用于在给定约束条件下最大限度地改善指定的指标。**

例如，假设你所在的公司生产 两种产品：衬衫和手提袋。衬衫每件利润2美元，需要消耗1米布料和5粒扣子；手提袋每个利润3 美元，需要消耗2米布料和2粒扣子。你有11米布料和20粒扣子，为最大限度地提高利润，该生产 多少件衬衫、多少个手提袋呢？ 在这个例子中，目标是利润最大化，而约束条件是拥有的原材料数量。 

再举一个例子。你是个政客，要尽可能多地获得支持票。你经过研究发现，平均而言，对于 每张支持票，在旧金山需要付出1小时的劳动（宣传、研究等）和2美元的开销，而在芝加哥需要 付出1.5小时的劳动和1美元的开销。在旧金山和芝加哥，你至少需要分别获得500和300张支持票。 你有50天的时间，总预算为1500美元。请问你最多可从这两个地方获得多少支持票？ 

这里的目标是支持票数最大化，而约束条件是时间和预算。 

你可能在想，本书花了很大的篇幅讨论最优化，这与线性规划有何关系？所有的图算法都可 使用线性规划来实现。线性规划是一个宽泛得多的框架，图问题只是其中的一个子集。但愿你听 到这一点后心潮澎湃！ 线性规划使用Simplex算法，这个算法很复杂，因此本书没有介绍。如果你对最优化感兴趣， 就研究研究线性规划吧！