1 Trie简介

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

在本文中，对于输入的进行序列化，比如输入“单词查找树”，序列化为“单/词/查/找/树”，这样可以进行任何一种自定义的数据插入和查询。序列化输入可以根据自己的需要进行相应的改动，这样可以把Trie树结构应用到很多其他的语言和领域。

本Trie树结构的优点在于：

1 不限制子节点的数量；

2 自定义的输入序列化，突破了具体语言、应用的限制，成为一个通用的框架；

3 可以进行最大Tokens序列长度的限制；

4 根据已定阈值输出重复的字符串；

5 提供单个字符串频度查找功能；

6 速度快，在两分钟内完成1998年1月份人民日报（19056行）的重复字符串抽取工作。

3 实现代码

Trie.h