分类大数据、算法与AI 下的文章

树3：字典树（Trie树）

Trie 树，也叫“字典树”，它是一个树形结构，是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。是属于多模式匹配的一种解法。

BF、RK、BM和KMP都是单模式匹配算法，也就是一个主串只能匹配一个模式串。在很多时候我们还需要多模式匹配，也就是一个主串匹配多个模式串，比如聊天敏感词。敏感词是一个列表，一个主串可能包含了多个敏感词。

KMP 算法是根据三位作者（D.E.Knuth，J.H.Morris 和 V.R.Pratt）的名字来命名的，算法的全称是 Knuth Morris Pratt 算法，简称为 KMP 算法。

BM（Boyer-Moore）算法，是一种高效的单模式串匹配算法。高效的字符串匹配算法在文本编辑器这样的软件上应用是否广泛。BM算法比著名的KMP算法更加高效。

字符串匹配可分为单模式串匹配和多模式串匹配，单模式串匹配就是一个串和一个子串匹配，多模式串匹配可以一个串同时查找多个字串。