Trie原理以及应用于搜索提示

╰半夏微凉° 2022-09-28 11:59 153阅读 0赞

## 背景 ##

今天看到这样一篇文章：[坑：缓存 + 哈希 = 高并发？][_ _ _]

有一段如下内容：

举个例子来说吧，搜索提示功能大家都知道吧，就是下面这个图的东西。

![搜索][SouthEast]

如果是google,baidu这种大型搜索系统，或者京东淘宝这种电商系统，搜索提示的调用量是搜索服务本身调用量的几倍，因为你每输入一个键盘，就要调用一次搜索提示服务，这算得上是个标准的高并发系统吧？那么它是怎么实现的呢？

可能很多人脑子里立刻出现了缓存+哈希的系统，把搜索的搜索提示词存在redis集群中，每次来了请求直接redis集群中查找key，然后返回相应的value值就行了，完美解决，虽然耗费点内存，但是空间换时间嘛，也能接受，这么做行不行？恩，我觉得是可以的，但有人这么做吗？没有。

了解的人应该知道，没有人会这么来实现，这种搜索提示的功能一般用trie树来做，耗费的内存不多，查找速度为O(k)，其中k为字符串的长度，虽然看上去没有哈希表的O(1)好，但是少了网络开销，节约了很多内存，并且实际查找时间还要不比缓存+哈希慢多少，一种合适当前场景的核心数据结构才是高并发系统的关键，缓存+哈希如果也看成一种数据结构，但这种数据结构并不适用于所有的高并发场景，所以高并发系统的设计，关键在合理的数据结构的设计，而不在架构的套用。

所以就来温习一下trie树，并来做个记录。

## Trie ##

### 知识简介 ###

字典树（Trie）可以保存一些字符串->值的对应关系。基本上，它跟 Java 的 HashMap 功能相同，都是 key-value 映射，只不过 Trie 的 key 只能是字符串。

Trie 的强大之处就在于它的时间复杂度。它的插入和查询时间复杂度都为 O(k) ，其中 k 为 key 的长度，与 Trie 中保存了多少个元素无关。Hash 表号称是 O(1) 的，但在计算 hash 的时候就肯定会是 O(k) ，而且还有碰撞之类的问题；Trie 的缺点是空间消耗很高。

至于Trie树的实现，可以用数组，也可以用指针动态分配。

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

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

Trie树的基本性质可以归纳为：

1.  根节点不包含字符，除根节点意外每个节点只包含一个字符。
2.  从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
3.  每个节点的所有子节点包含的字符串不相同。

Trie树有一些特性：

1.  根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2.  从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3.  每个节点的所有子节点包含的字符都不相同。
4.  如果字符的种数为n，则每个结点的出度为n，这也是空间换时间的体现，浪费了很多的空间。
5.  插入查找的复杂度为O(n)，n为字符串长度。

基本思想（以字母树为例）：

1.  插入过程
    
    对于一个单词，从根开始，沿着单词的各个字母所对应的树中的节点分支向下走，直到单词遍历完，将最后的节点标记为红色，表示该单词已插入Trie树。
2.  查询过程
    
    同样的，从根开始按照单词的字母顺序向下遍历trie树，一旦发现某个节点标记不存在或者单词遍历完成而最后的节点未标记为红色，则表示该单词不存在，若最后的节点标记为红色，表示该单词存在。

### 字典树的数据结构： ###

利用串构建一个字典树，这个字典树保存了串的公共前缀信息，因此可以降低查询操作的复杂度。

下面以英文单词构建的字典树为例，这棵Trie树中每个结点包括26个孩子结点，因为总共有26个英文字母(假设单词都是小写字母组成)。则可声明包含Trie树的结点信息的结构体:

typedef struct Trie_node  
    {  
        int count;                    // 统计单词前缀出现的次数 
        struct Trie_node* next[26];   // 指向各个子树的指针 
        bool exist;                   // 标记该结点处是否构成单词 
    }TrieNode , *Trie;

其中next是一个指针数组，存放着指向各个孩子结点的指针。

已知n个由小写字母构成的平均长度为10的单词，判断其中是否存在某个串为另一个串的前缀子串。下面对比3种方法：

1.  最容易想到的：即从字符串集中从头往后搜，看每个字符串是否为字符串集中某个字符串的前缀，复杂度为O(n^2)。
2.  使用hash：我们用hash存下所有字符串的所有的前缀子串。建立存有子串hash的复杂度为`O(n*len)`。查询的复杂度为`O(n)* O(1)= O(n)`。
3.  使用Trie：因为当查询如字符串abc是否为某个字符串的前缀时，显然以b、c、d….等不是以a开头的字符串就不用查找了，这样迅速缩小查找的范围和提高查找的针对性。所以建立Trie的复杂度为`O(n*len)`，而建立+查询在trie中是可以同时执行的，建立的过程也就可以成为查询的过程，hash就不能实现这个功能。所以总的复杂度为`O(n*len)`，实际查询的复杂度只是O(len)。

### Trie树的操作 ###

在Trie树中主要有3个操作，插入、查找和删除。一般情况下Trie树中很少存在删除单独某个结点的情况，因此只考虑删除整棵树。

1.  插入
    
    假设存在字符串str，Trie树的根结点为root。i=0，p=root。
    
    1.  取str\[i\]，判断p->next\[str\[i\]-97\]是否为空，若为空，则建立结点temp，并将p->next\[str\[i\]-97\]指向temp，然后p指向temp；  
        若不为空，则p=p->next\[str\[i\]-97\]；
    2.  i++，继续取str\[i\]，循环1)中的操作，直到遇到结束符’\\0’，此时将当前结点p中的 exist置为true。
2.  查找
    
    假设要查找的字符串为str，Trie树的根结点为root，i=0，p=root
    
    1.  取str\[i\]，判断判断p->next\[str\[i\]-97\]是否为空，若为空，则返回false；若不为空，则p=p->next\[str\[i\]-97\]，继续取字符。
    2.  重复1)中的操作直到遇到结束符’\\0’，若当前结点p不为空并且 exist 为true，则返回true，否则返回false。
3.  删除（二选其一）
    
    1.  删除可以以递归的形式进行删除。
    2.  先搜索后删除

## lintcode ##

Question: [implement-trie/][implement-trie]

Java:

package cc.wsyw126.java.lintCode.implement_trie;
    
    public class Trie { 
        private TrieNode root;
    
        public Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        public void insert(String word) {
            TrieNode node = root;
            int length = word.length();
            int position ;
            char c;
            for (int i = 0; i < length; i++) {
                c = word.charAt(i);
                position = c-'a';
                if (node.trieNodes[position] == null) {
                    node.trieNodes[position] = new TrieNode();
                }
                node = node.trieNodes[position];
                node.setCount(node.getCount()+1);
            }
            node.setExist(true);
        }
    
        // Returns if the word is in the trie.
        public boolean search(String word) {
            boolean result = false;
            TrieNode node = root;
            int length = word.length();
            int position ;
            char c;
            for (int i = 0; i < length; i++) {
                c = word.charAt(i);
                position = c - 'a';
                node = node.trieNodes[position];
                if (node == null) {
                    break;
                }
            }
            if (node != null && node.getExist()) {
                result = true;
            }
            return result;
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        public boolean startsWith(String prefix) {
            TrieNode node = root;
            int length = prefix.length();
            int position ;
            char c;
            for (int i = 0; i < length; i++) {
                c = prefix.charAt(i);
                position = c - 'a';
                node = node.trieNodes[position];
                if (node == null) {
                    return false;
                }
            }
            return true;
        }
    
        // delete if the word is in the trie.
        public boolean doDelete(String word, TrieNode node) {
            //树中已匹配的字符串比传入字符串短
            if (node == null) {
                return false;
            }
    
            //树中已匹配的字符串比传入字符串不短
            if (word.length()  > 1){
                char c = word.charAt(0);
                int position = c - 'a';
                TrieNode trieNode = node.trieNodes[position];
                boolean b = doDelete(word.substring(1), trieNode);
                if (b) {
                    node.setCount(node.getCount() - 1);
                    if (trieNode.getCount() == 0) {
                        node.trieNodes[position] = null;
                    }
                    return true;
                }
            }
    
            if (word.length() == 1) {
                char c = word.charAt(0);
                int position = c - 'a';
                TrieNode trieNode = node.trieNodes[position];
                //只删除单词 如果是前缀不删除
                if (trieNode != null && trieNode.getExist()) {
                    return true;
                }
            }
            return false;
        }
    
        // delete if the word is in the trie.
        public boolean delete(String word) {
            return this.doDelete(word,root);
        }
    
        class TrieNode {
            // Initialize your data structure here.
            int count = 0;
            TrieNode[] trieNodes = new TrieNode[26];
            Boolean exist = false;
            public TrieNode() {
            }
    
            public TrieNode(int count, Boolean exist) {
                this.count = count;
                this.exist = exist;
            }
    
            public int getCount() {
                return count;
            }
    
            public void setCount(int count) {
                this.count = count;
            }
    
            public TrieNode[] getTrieNodes() {
                return trieNodes;
            }
    
            public void setTrieNodes(TrieNode[] trieNodes) {
                this.trieNodes = trieNodes;
            }
    
            public Boolean getExist() {
                return exist;
            }
    
            public void setExist(Boolean exist) {
                this.exist = exist;
            }
        }
    
        public static void main(String[] args) {
            Trie trie = new Trie();
            trie.search("lintcode");
            trie.startsWith("lint");
            trie.insert("lint");
            trie.startsWith("lint");
    
            boolean lint = trie.delete("lin");
            System.out.println("lint = " + lint);
            lint = trie.delete("lint");
            System.out.println("lint = " + lint);
        }
    }

#include <stdbool.h>
    #include <stdlib.h>
    #include <string.h>
    #include "stdio.h"
    
    typedef struct Trie_node {
        int count;                    // 统计单词前缀出现的次数
        struct Trie_node *next[26];   // 指向各个子树的指针
        bool exist;                   // 标记该结点处是否构成单词
    } TrieNode, *Trie;
    
    
    TrieNode *createTrieNode() {
        TrieNode *node = (TrieNode *) malloc(sizeof(TrieNode));
        node->count = 0;
        node->exist = false;
        memset(node->next, 0, sizeof(node->next));    // 初始化为空指针
        return node;
    }
    
    
    void Trie_insert(Trie root, char *word) {
        Trie node = root;
        char *p = word;
        int id;
        while (*p) {
            id = *p - 'a';
            if (node->next[id] == NULL) {
                node->next[id] = createTrieNode();
            }
            node = node->next[id];  // 每插入一步，相当于有一个新串经过，指针向下移动
            ++p;
            node->count += 1;      // 这行代码用于统计每个单词前缀出现的次数（也包括统计每个单词出现的次数）
        }
        node->exist = true;        // 单词结束的地方标记此处可以构成一个单词
    }
    
    int Trie_search(Trie root, char *word) {
        Trie node = root;
        char *p = word;
        int id;
        while (*p) {
            id = *p - 'a';
            node = node->next[id];
            ++p;
            if (node == NULL)
                return 0;
        }
        return node->count;
    }
    
    
    int main() {
        Trie root = createTrieNode();     // 初始化字典树的根节点
        char str[12];
        bool flag = false;
        while (gets(str)) {
            if (flag)
                printf("%d\n", Trie_search(root, str));
            else {
                if (strlen(str) != 0) {
                    Trie_insert(root, str);
                } else
                    flag = true;
            }
        }
    
        return 0;
    }

--------------------

参考资料：  
[坑：缓存 + 哈希 = 高并发？][_ _ _]  
[hackbuteer1][]  
备注：  
转载请注明出处：[http://blog.csdn.net/wsyw126/article/details/60468607][http_blog.csdn.net_wsyw126_article_details_60468607]  
作者：WSYW126

[_ _ _]: https://mp.weixin.qq.com/s?__biz=MzA5NTkwMzkwNQ==&mid=2650435286&idx=1&sn=b1763cba2a9a08e690a18ce1a77fc288&chksm=88b68718bfc10e0eae8437820db8b72e358c90fdbb9bb662783dc294cdc8237c583f1dac8e89&mpshare=1&scene=1&srcid=03099qDqXbYmD39VJdbuOIdd&key=d17593927da82b1157a8dd794674ff20d870771d131ed63c7aa855926b85ea2aaf2326145c408743b8fcd0fe3ee63d312eac44bd6107e22117076732d5faef35ba613775dfdec5a02b1c5e0de39ccc3a&ascene=0&uin=MjMxOTQ0MzY0MA%3D%3D&devicetype=iMac+MacBookPro11%2C1+OSX+OSX+10.11.6+build%2815G31%29&version=12020010&nettype=WIFI&fontScale=100&pass_ticket=xALSrJ3QO7o4NkxWCxCYC9ZIgf0xrx%2Bzfpt3tPOCpcyy%2Fpzsu7hwSQCleDvxgWhR
[SouthEast]: /images/20220708/c3eaf3f5c75841cab7a43345c4df42ee.png
[implement-trie]: http://www.lintcode.com/zh-cn/problem/implement-trie/
[hackbuteer1]: http://blog.csdn.net/hackbuteer1/article/details/7964147
[http_blog.csdn.net_wsyw126_article_details_60468607]: http://blog.csdn.net/wsyw126/article/details/60468607