算法 044：一些领域算法知识体系

知识体系

在了解基础算法之后，我们还要学习和了解在不同专业领域有哪些特有的算法。这里不一定要求复杂度，而是要有知识面以及解决问题的思路。

A. 领域算法梳理

在了解基础算法之后，我们还要学习和了解在不同专业领域有哪些特有的算法。这里不一定要求复杂度，而是要有知识面以及解决问题的思路。

B. 领域算法之安全算法

主要包括摘要算法和加密算法两大类。

安全算法 - 摘要算法：消息摘要算法的主要特征是加密过程不需要密钥，并且经过加密的数据无法被解密，目前可以解密逆向的只有 CRC32 算法，只有输入相同的明文数据经过相同的消息摘要算法才能得到相同的密文。消息摘要算法不存在密钥的管理与分发问题，适合于分布式网络上使用。
安全算法 - 加密算法：数据加密的基本过程就是对原来为明文的文件或数据按某种算法进行处理，使其成为不可读的一段代码称为”密文”，使其只能在输入相应的密钥之后才能显示出原容，通过这样的途径来达到保护数据不被非法人窃取、阅读的目的。该过程的逆过程为解密，即将该编码信息转化为其原来数据的过程。
安全算法 - 国密算法：国密即国家密码局认定的国产密码算法，主要有 SM1、SM2、SM3、SM4、SM7、SM9。

安全算法的详细内容可参考安全系列：安全算法 - 摘要算法、安全算法 - 加密算法、安全算法 - 国密算法。

C. 领域算法之字符串匹配算法

字符串匹配（String Matching）也称字符串搜索（String Searching），是字符串算法中重要的一种，是指从一个大字符串或文本中找到模式串出现的位置。

朴素的字符串匹配算法（Naive String Matching Algorithm）：又称为暴力匹配算法（Brute Force Algorithm），最为简单的字符串匹配算法。
Knuth-Morris-Pratt 字符串匹配算法（即 KMP 算法）：最常用的字符串匹配算法之一。
Boyer-Moore 字符串匹配算法：各种文本编辑器的”查找”功能（Ctrl+F）大多采用 Boyer-Moore 算法，效率非常高。
字符串匹配 - 文本预处理：后缀树（Suffix Tree）：上述字符串匹配算法（朴素的字符串匹配算法、KMP 算法、Boyer-Moore 算法）均是通过对模式（Pattern）字符串进行预处理的方式来加快搜索速度。对 Pattern 进行预处理的最优复杂度为 O(m)，其中 m 为 Pattern 字符串的长度。对文本（Text）进行预处理的算法则是后缀树。

本系列字符串匹配部分的详细内容：字符串匹配 Overview。

D. 领域算法之大数据处理

这里其实想让大家理解的是大数据处理的常用思路，而不是算法本身。

大数据处理 - Overview：主要介绍大数据处理的一些思路。
大数据处理 - 分治/hash/排序：就是先映射，而后统计，最后排序。分而治之/hash 映射——针对数据太大、内存受限，只能是：把大文件化成（取模映射）小文件，即 16 字方针：大而化小，各个击破，缩小规模，逐个解决；hash_map 统计——当大文件转化了小文件，那么我们便可以采用常规的 hash_map(ip, value) 来进行频率统计；堆/快速排序——统计完了之后，便进行排序（可采取堆排序），得到次数最多的 IP。
大数据处理 - Bitmap & Bloom Filter：布隆过滤器有着广泛的应用，对于大量数据的”存不存在”的问题在空间上有明显优势，但是在判断存不存在是有一定的错误率（false positive），也就是说，有可能把不属于这个集合的元素误认为属于这个集合（False Positive），但不会把属于这个集合的元素误认为不属于这个集合（False Negative）。
大数据处理 - 双层桶划分：本质上还是分而治之的思想，重在”分”的技巧上。适用范围：第 k 大，中位数，不重复或重复的数字；基本原理及要点：因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。
大数据处理 - Trie 树/数据库/倒排索引：适用范围：数据量大，重复多，但是数据种类小可以放入内存；基本原理及要点：实现方式，节点孩子的表示方式；扩展：压缩实现。
大数据处理 - 外排序：适用范围：大数据的排序，去重；基本原理及要点：外排序的归并方法，置换选择败者树原理，最优归并树。
大数据处理 - Map & Reduce：MapReduce 是一种计算模型，简单的说就是将大批量的工作（数据）分解（MAP）执行，然后再将结果合并成最终结果（REDUCE）。这样做的好处是可以在任务被分解后，通过大量机器进行并行计算，减少整个操作的时间。但如果你要再通俗点介绍，那么，说白了，MapReduce 的原理就是一个归并排序。

本系列大数据处理部分的详细内容：大数据处理 Overview。

E. 领域算法之分布式算法

分布式算法包括一致性 Hash 算法、经典的 Paxos 算法、Raft 算法、ZAB 算法等；顺便也介绍经典用于全局 ID 生成的 Snowflake 算法。

分布式算法 - 一致性 Hash 算法：一致性 Hash 算法是个经典算法，Hash 环的引入是为解决单调性（Monotonicity）的问题；虚拟节点的引入是为了解决平衡性（Balance）问题。
分布式算法 - Paxos 算法：Paxos 算法是 Lamport 宗师提出的一种基于消息传递的分布式一致性算法，使其获得 2013 年图灵奖。自 Paxos 问世以来就持续垄断了分布式一致性算法，Paxos 这个名词几乎等同于分布式一致性，很多分布式一致性算法都由 Paxos 演变而来。
分布式算法 - Raft 算法：Paxos 是出了名的难懂，而 Raft 正是为了探索一种更易于理解的一致性算法而产生的。它的首要设计目的就是易于理解，所以在选主的冲突处理等方式上它都选择了非常简单明了的解决方案。
分布式算法 - ZAB 算法：ZAB 协议全称 Zookeeper Atomic Broadcast（Zookeeper 原子广播协议），它应该是所有一致性协议中生产环境中应用最多的了。为什么呢？因为它是为 Zookeeper 设计的分布式一致性协议。
分布式算法 - Snowflake 算法：Snowflake，雪花算法是由 Twitter 开源的分布式 ID 生成算法，以划分命名空间的方式将 64-bit 位分割成多个部分，每个部分代表不同的含义。这种就是将 64 位划分为不同的段，每段代表不同的涵义，基本就是时间戳、机器 ID 和序列数。为什么如此重要？因为它提供了一种 ID 生成及生成的思路，当然这种方案就是需要考虑时钟回拨的问题以及做一些 buffer 的缓冲设计提高性能。

F. 领域算法之其它算法汇总

最后概要性地了解常见的其它算法：负载均衡算法、推荐算法、数据挖掘或机器学习算法。因为有其专业性，一般总体上了解就够了。

负载均衡算法 - 汇总：常用的负载均衡算法和 Nginx 中支持的负载均衡算法：轮询法（Round Robin）、加权轮询法（Weight Round Robin）、平滑加权轮询法（Smooth Weight Round Robin）、随机法（Random）、加权随机法（Weight Random）、源地址哈希法（Hash）、最小连接数法（Least Connections）。
推荐算法 - 汇总：对推荐算法整体知识点做汇总，做到总体的理解；深入理解需要再看专业的材料。
数据挖掘 - 10 大算法汇总：国际权威的学术组织 the IEEE International Conference on Data Mining（ICDM）2006 年 12 月评选出了数据挖掘领域的十大经典算法：C4.5、k-Means、SVM、Apriori、EM、PageRank、AdaBoost、kNN、Naive Bayes、CART。

CHARLIE SAYS