Basic Trie Tree

Trie Tree 实际上是一种前缀树。在自然语言处理中我们经常需要进行词的匹配、查询等等操作。Trie Tree 实际就是对所有单词的前缀进行合并。例如 banana 和ban 实际上其存在共同前缀ban。Trie Tree的首要就是合并这些前缀从而达到高效匹配与统计。

基本简介

如上所示Trie实际上是一个多路查找树，每个节点都有可能是一个潜在的单词。每个节点的定义我们可以简略定义如下：

 struct  Node 
  {
      Node* children[26]
  }

cnt 表示该单词出现次数，如果0表示在该节点没有单词。children为指向下一集节点的指针。

func insert(root, string, value):
    node = root
    index_last_char = None
    for index_char, char in enumerate(string):
        if char in node.children:
            node = node.children[char]
        else:
            index_last_char = index_char
            break
    if index_last_char is not None: 
        for char in string[index_last_char:]:
            node.children[char] = Node()
            node = node.children[char]
    node.value = value

func find(node, key):
    for char in key:
        if char in node.children:
            node = node.children[char]
        else:
            return None
    return node.value

如上为trie的插入和search的伪代码实现，很是简单。不过前面说过了，性能、空间、往往都是矛盾。上述实现也不例外，其也就停留在学习入门教学的程度。上图我们已经看到节点 at 和ate因为只有单个子节点实际上是可以合并为ate一个.这也就是所谓的路径压缩。有兴趣的可以看下radix Tree实际上就是一种路径压缩。

应用举例

字符串检索，词频统计，搜索引擎的热门查询
事先将已知的一些字符串（字典）的有关信息保存到trie树里，查找另外一些未知字符串是否出现过或者出现频率。

举例：

1、有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。

2、给出N 个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。

3、给出一个词典，其中的单词为不良单词。单词均为小写字母。再给出一段文本，文本的每一行也由小写字母构成。判断文本中是否含有任何不良单词。例如，若rob是不良单词，那么文本problem含有不良单词。

4、1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串。请怎么设计和实现？

5、一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。

6、寻找热门查询：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复读比较高，虽然总数是1千万，但是如果去除重复和，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G(京东笔试题简答题与此类似)。

(1) 请描述你解决这个问题的思路；

(2) 请给出主要的处理流程，算法，以及算法的复杂度。
字符串最长公共前缀
Trie树利用多个字符串的公共前缀来节省存储空间，反之，当我们把大量字符串存储到一棵trie树上时，我们可以快速得到某些字符串的公共前缀。举例：
1. 给出N 个小写英文字母串，以及Q 个询问，即询问某两个串的最长公共前缀的长度是多少. 解决方案：
  首先对所有的串建立其对应的字母树。此时发现，对于两个串的最长公共前缀的长度即它们所在结点的公共祖先个数，于是，问题就转化为了离线（Offline）的最近公共祖先（Least Common Ancestor，简称LCA）问题。
排序
Trie树是一棵多叉树，只要先序遍历整棵树，输出相应的字符串便是按字典序排序的结果。

举例：给你N 个互不相同的仅由一个单词构成的英文名，让你将它们按字典序从小到大排序输出。
作为其他数据结构和算法的辅助结构
如后缀树，AC自动机等。

上述问题一般都可以使用或者借助Trie来实现。具体怎么处理大家自己可以慢慢思考

Basic Trie Tree

基本简介

应用举例

推荐阅读更多精彩内容