Stack Pub

AC自动机：Aho-Corasick automation，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法之一。要搞懂AC自动机，先得有模式树（字典树）Trie、广度优先策略和KMP模式匹配算法的基础知识。

位图法就是利用位数组来存储数据状态，其优点就是节省数据存储空间。

布隆过滤器(Bloom Filter)是一种空间效率高的概率数据结构，由 Burton·Howar·Bloom 于1970年构思，用于测试元素是否是一组元素的成员。它实际上就是由一个很长的二进制向量(bitmap)和一系列随机映射函数(哈希函数)组成，将一系列数据通过一组哈希函数映射到位图数组中，以表示该数据存在。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

KMP算法是一种改进的字符串匹配算法, 由D.E.Knuth, J.H.Morris和V.R.Pratt提出, 无论是基于确定有限状态自动机机(Determinstic Finite Automata, DFA)的KMP实现还是基于部分匹配表(Parital Match Table, PMT)的KMP实现,其核心思想都是利用匹配失败后的信息,尽可能的减少模式串与主串的匹配次数以达到快速匹配的目的。

Skip lists are a data structure that can be used in place of balanced trees. Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.
–William Pugh

Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较。

图(graph)由顶点(vertex)与边(edge)的构成，研究元素间多对多的关系。

平衡二叉树(balance binary tree)是二叉排序树的进化体，由G.M.Adelson-Velsky和E.M. Landis提出的，所以又叫AVL树。

平衡二叉树是指它除了具备二叉排序树的基本特征之外，还具有一个重要的特定：它的左子树与右子树的深度之差(平衡因子)的绝对值不超过1，且都是平衡二叉树。

二叉排序树(Binary Sort Tree,BST)又称为二叉查找树,二叉搜索树,具有以下性质:

1. 如果左子树不为空,则左子树上所有结点的值都小于根结点的值.
2. 如果右子树不为空,则右子树上所有结点的值均大于根结点的值.
3. 左右子树也分别为二叉排序树.
4. 树中没有相同的结点.

如果用中序遍历二叉排序树,则遍历结果是一个递增序列.