红黑树:红黑树是一个二叉搜索树。在每个节点增加了一个存储位记录节点的颜色,可以是RED,也可以是BLACK,通过任意一条从根到叶子简单路径上颜色的约束,红黑树保证最长路径不超过最短路径的两倍,加以平衡。性质如下:
1.每个节点颜色不是黑色就是红色
2.对于每个节点,从该节点到其后代叶节点的简单路径上,均包含相同数目的黑色节点。
3.如果一个节点是红色,那么他的两个子节点就是黑色的,没有持续的红节点
4.根节点的颜色是黑色的
关键词过滤:
DFA全称为:Deterministic Finite Automaton,即确定有穷自动机。其特征为:有一个有限状态集合和一些从一个状态通向另一个状态的边,每条边上标记有一个符号,其中一个状态是初态,某些状态是终态。但不同于不确定的有限自动机,DFA中不会有从同一状态出发的两条边标志有相同的符号。
NFA全称为:Non-Deeterministic Finite State Automata,即不确定的有穷自动机: 对一个输入符号,有两种或两种以上可能对状态,所以是不确定的。
Trie tree算法
相同前缀的词组合成一个树形结构,不同前缀的词分属不同树形分支;只需要遍历一次待检测文本,然后在敏感词库中检索出有没有该字符对应的子树。