精华内容
下载资源
问答
  • ajax动态加载关键词提示
  • 当你在搜索引擎中输入想要搜索的一部分内容时,搜索引擎就会自动弹出下拉框,里面是各种关键词提示,这个功能是怎么实现的呢?其实底层最基本的就是 Trie 树这种数据结构。 1. 什么是 “Trie” 树 Trie 树也叫 ...
        
    当你在搜索引擎中输入想要搜索的一部分内容时,搜索引擎就会自动弹出下拉框,里面是各种关键词提示,这个功能是怎么实现的呢?其实底层最基本的就是 Trie 树这种数据结构。

    1. 什么是 “Trie” 树

    Trie 树也叫 “字典树”。顾名思义,它是一个树形结构,专门用来处理在一组字符串集合中快速查找某个字符串的问题。

    假设我们有 6 个字符串,它们分别是:how,hi,her,hello,so,see。我们希望在这里面多次查找某个字符串是否存在,如果每次都拿要查找的字符串和这六个字符串依次进行匹配,那效率就会比较低。

    如果我们可以对这六个字符串做一下预处理,组织成 Trie 树的结构,那之后每次查找,都只要在 Trie 树中进行匹配即可。Trie 树的本质,就是利用字符串之间的公共前缀,将重复的前缀合并在一起

    其中,根节点不包含任何信息,每个节点代表字符串中的一个字符,从根节点到红色节点的一条路径表示一个字符串。注意红色节点并不都是叶子节点,比如有两个词 how 和 however,那么 w 和 r 都是红色节点。一个 Trie 树的构造过程如下所示。


    当我们要在构建好的 Trie 树中查找一个字符串的时候,那就要将查找的字符串分割成单个的字符,然后从根节点开始匹配。如下面的例子所示,绿色路径就是 “her” 的匹配路径,而 “he” 的最后一个匹配节点并不是红色节点,所以其并不能完全匹配任何字符串。


    2. 如何实现一棵 Trie 树

    从上面我们可以看到,Trie 树主要有两个操作:一个是将字符串集合构建成 Trie 树,另一个是在 Trie 树中查询一个字符串

    Trie 树是一个多叉树结构,其子节点个数事先未知,但我们可以借助散列表的思想,在下标与字符之间建立一个一一映射,来存储子节点的指针。

    假设我们的字符串只有 a 到 z 这 26 个字母,那么数组下标为 0 的元素就存储指向子节点 a 的指针,下标为 1 的元素就存储指向子节点 b 的指针,以此类推,下标为 25 的元素就存储指向子节点 z 的指针。如果某个字符的子节点不存在,那对应该下标位置的元素就为 NULL。当我们在 Trie 树中进行查找的时候,就可以拿字符的 ASCII 码减去 'a' 的 ASCII 码来获取其子节点的指针。

    #include <iostream>
    #include <cstring>
    
    using namespace std;
    
    class TrieNode
    {
    public:
    
        char data;
        bool is_ending_char;
        TrieNode *children[26];
    
        TrieNode(char ch)
        {
            data = ch;
            is_ending_char = false;
            for (int i = 0; i < 26; i++)
                children[i] = NULL;
        }
    };
    
    class Trie
    {
    private:
    
        TrieNode *root;
    
    public:
    
        // 构造函数,根节点存储无意义字符 '/'
        Trie()
        {
            root = new TrieNode('/');
        }
    
        // 向 Trie 树中添加一个字符串
        void insert_string(const char str[])
        {
            TrieNode *cur = root;
            for (unsigned int i = 0; i < strlen(str); i++)
            {
                int index = int(str[i] - 'a');
                if (cur->children[index] == NULL)
                {
                    TrieNode *temp = new TrieNode(str[i]);
                    cur->children[index] = temp;
                }
                cur = cur->children[index];
            }
            cur->is_ending_char = true;
        }
    
        // 在 Trie 树中查找一个字符串
        bool search_string(const char str[])
        {
            TrieNode *cur = root;
            for (unsigned int i = 0; i < strlen(str); i++)
            {
                int index = int(str[i] - 'a');
                if (cur->children[index] == NULL)
                {
                    return false;
                }
                cur = cur->children[index];
            }
            if (cur->is_ending_char == true) return true;
            else return false;
        }
    };
    
    int main()
    {
        char str[][8] = {"how", "hi", "her", "hello", "so", "see", "however"};
    
        Trie test;
        for (int i = 0; i < 7; i++)
        {
            test.insert_string(str[i]);
        }
    
        cout << "Finding \'her\': " << test.search_string("her") << endl;
        cout << "Finding \'he\': " << test.search_string("he") << endl;
        cout << "Finding \'how\': " << test.search_string("how") << endl;
        cout << "Finding \'however\': " << test.search_string("however") << endl;
    
        return 0;
    }

    在构建 Trie 树的过程中,需要扫描所有的字符串,时间复杂度为 O(n),其中 n 表示所有字符串的长度之和。而在 Trie 树中进行查找的话,如果待查找字符串的长度为 k 的话,那最多只需要对比 k 个节点即可,时间复杂度为 O(k)。

    3. Trie 树的内存消耗

    在上面的例子中,Trie 树的每个节点都要存储 26 个指针,尽管某些节点的子节点很少,我们依然要维护这么一个长度的数组。另外,如果字符串中不仅包含小写字母,而且包含大写字母、数字甚至是中文等,那就会需要更多的存储空间。也就是说,在某些情况下,Trie 树并不一定会节省内存空间,尤其是在重复前缀不多的时候。

    当然,尽管 Trie 树可能会很浪费内存,但是确实非常高效,这也是一种空间换时间的折中。如果我们可以稍微牺牲一点查询的效率,那就可以选用数组、散列表、红黑树等其他数据结构来存储一个节点的子节点指针。

    假设我们使用数组,数组中的指针按照所指向子节点的字符大小顺序排列。这样,在查找的时候,我们可以通过二分算法来快速找到指向子节点的指针。但是,在往 Trie 树中插入字符串的话,为了维护数组的有序性,就会稍微慢了点。

    另外,还可以采用缩点优化,将只有一个子节点而且不是结束节点的节点与其子节点进行合并,来节省空间,但这也增加了编码难度。

    4. Trie 树与散列表、红黑树的比较

    在字符串匹配或者说查找问题上,Trie 树对要处理的字符串有极其严格的要求。

    • 字符串中包含的字符集不能太大;
    • 字符串的前缀重合比较多;
    • 从零开始实现一个 Trie 树,比较复杂,不便于维护;
    • Trie 树中利用指针来存储数据,不利用利用缓存。

    因此,在工程中,我们更倾向于使用散列表或者红黑树,它们都不需要自己去实现,直接利用编程语言中提供的线程类库就行。实际上,Trie 树不适合这种精确查找,更适合的是查找前缀匹配的字符串,也就是搜索时的关键词提示功能。

    5. 搜索关键词提示功能的实现

    假设关键词库由用户的热门搜索关键词组成,我们将这个词库构建成一个 Trie 树。当用户输入其中某个单词的时候,把这个词作为一个前缀子串在 Trie 树中匹配。还以上面为例,当用户输入 'h' 时,我们就可以将以 'h' 为前缀的单词 hello,her,hi,how 展示在搜索提示框,当用户输入 'he' 时,我们就可以将以 'h' 为前缀的单词 hello,her 展示在搜索提示框。这就是搜索关键词提示的最基本的算法原理。

    另外,Trie 树还可以扩展到更加广泛的应用上,比如输入法、代码编辑器和浏览器的自动输入补全功能。

    参考资料-极客时间专栏《数据结构与算法之美》

    获取更多精彩,请关注「seniusen」!

    展开全文
  • 当你在搜索引擎中输入想要搜索的一部分内容时,搜索引擎就会自动弹出下拉框,里面是各种关键词提示,这个功能是怎么实现的呢?其实底层最基本的就是Trie 树这种数据结构。 1. 什么是 “Trie” 树 Trie 树也叫 ...

    当你在搜索引擎中输入想要搜索的一部分内容时,搜索引擎就会自动弹出下拉框,里面是各种关键词提示,这个功能是怎么实现的呢?其实底层最基本的就是 Trie 树这种数据结构。

    1. 什么是 “Trie” 树

    Trie 树也叫 “字典树”。顾名思义,它是一个树形结构,专门用来处理在一组字符串集合中快速查找某个字符串的问题。

    假设我们有 6 个字符串,它们分别是:how,hi,her,hello,so,see。我们希望在这里面多次查找某个字符串是否存在,如果每次都拿要查找的字符串和这六个字符串依次进行匹配,那效率就会比较低。

    如果我们可以对这六个字符串做一下预处理,组织成 Trie 树的结构,那之后每次查找,都只要在 Trie 树中进行匹配即可。Trie 树的本质,就是利用字符串之间的公共前缀,将重复的前缀合并在一起。

    其中,根节点不包含任何信息,每个节点代表字符串中的一个字符,从根节点到红色节点的一条路径表示一个字符串。注意红色节点并不都是叶子节点,比如有两个词 how 和 however,那么 w 和 r 都是红色节点。一个 Trie 树的构造过程如下所示。

     

     

     

    当我们要在构建好的 Trie 树中查找一个字符串的时候,那就要将查找的字符串分割成单个的字符,然后从根节点开始匹配。如下面的例子所示,绿色路径就是 “her” 的匹配路径,而 “he” 的最后一个匹配节点并不是红色节点,所以其并不能完全匹配任何字符串。

     

     

     

     

    2. 如何实现一棵 Trie 树

    从上面我们可以看到,Trie 树主要有两个操作:一个是将字符串集合构建成 Trie 树,另一个是在 Trie 树中查询一个字符串。

    Trie 树是一个多叉树结构,其子节点个数事先未知,但我们可以借助散列表的思想,在下标与字符之间建立一个一一映射,来存储子节点的指针。

    假设我们的字符串只有 a 到 z 这 26 个字母,那么数组下标为 0 的元素就存储指向子节点 a 的指针,下标为 1 的元素就存储指向子节点 b 的指针,以此类推,下标为 25 的元素就存储指向子节点 z 的指针。如果某个字符的子节点不存在,那对应该下标位置的元素就为 NULL。当我们在 Trie 树中进行查找的时候,就可以拿字符的 ASCII 码减去 'a' 的 ASCII 码来获取其子节点的指针。

    #include <iostream>
    #include <cstring>
    
    using namespace std;
    
    class TrieNode
    {
    public:
    
        char data;
        bool is_ending_char;
        TrieNode *children[26];
    
        TrieNode(char ch)
        {
            data = ch;
            is_ending_char = false;
            for (int i = 0; i < 26; i++)
                children[i] = NULL;
        }
    };
    
    class Trie
    {
    private:
    
        TrieNode *root;
    
    public:
    
        // 构造函数,根节点存储无意义字符 '/'
        Trie()
        {
            root = new TrieNode('/');
        }
    
        // 向 Trie 树中添加一个字符串
        void insert_string(const char str[])
        {
            TrieNode *cur = root;
            for (unsigned int i = 0; i < strlen(str); i++)
            {
                int index = int(str[i] - 'a');
                if (cur->children[index] == NULL)
                {
                    TrieNode *temp = new TrieNode(str[i]);
                    cur->children[index] = temp;
                }
                cur = cur->children[index];
            }
            cur->is_ending_char = true;
        }
    
        // 在 Trie 树中查找一个字符串
        bool search_string(const char str[])
        {
            TrieNode *cur = root;
            for (unsigned int i = 0; i < strlen(str); i++)
            {
                int index = int(str[i] - 'a');
                if (cur->children[index] == NULL)
                {
                    return false;
                }
                cur = cur->children[index];
            }
            if (cur->is_ending_char == true) return true;
            else return false;
        }
    };
    
    int main()
    {
        char str[][8] = {"how", "hi", "her", "hello", "so", "see", "however"};
    
        Trie test;
        for (int i = 0; i < 7; i++)
        {
            test.insert_string(str[i]);
        }
    
        cout << "Finding \'her\': " << test.search_string("her") << endl;
        cout << "Finding \'he\': " << test.search_string("he") << endl;
        cout << "Finding \'how\': " << test.search_string("how") << endl;
        cout << "Finding \'however\': " << test.search_string("however") << endl;
    
        return 0;
    }
    

    在构建 Trie 树的过程中,需要扫描所有的字符串,时间复杂度为 O(n),其中 n 表示所有字符串的长度之和。而在 Trie 树中进行查找的话,如果待查找字符串的长度为 k 的话,那最多只需要对比 k 个节点即可,时间复杂度为 O(k)。

     

    3. Trie 树的内存消耗

    在上面的例子中,Trie 树的每个节点都要存储 26 个指针,尽管某些节点的子节点很少,我们依然要维护这么一个长度的数组。另外,如果字符串中不仅包含小写字母,而且包含大写字母、数字甚至是中文等,那就会需要更多的存储空间。也就是说,在某些情况下,Trie 树并不一定会节省内存空间,尤其是在重复前缀不多的时候。

    当然,尽管 Trie 树可能会很浪费内存,但是确实非常高效,这也是一种空间换时间的折中。如果我们可以稍微牺牲一点查询的效率,那就可以选用数组、散列表、红黑树等其他数据结构来存储一个节点的子节点指针。

    假设我们使用数组,数组中的指针按照所指向子节点的字符大小顺序排列。这样,在查找的时候,我们可以通过二分算法来快速找到指向子节点的指针。但是,在往 Trie 树中插入字符串的话,为了维护数组的有序性,就会稍微慢了点。

    另外,还可以采用缩点优化,将只有一个子节点而且不是结束节点的节点与其子节点进行合并,来节省空间,但这也增加了编码难度。

     

    4. Trie 树与散列表、红黑树的比较

    在字符串匹配或者说查找问题上,Trie 树对要处理的字符串有极其严格的要求。

    • 字符串中包含的字符集不能太大;

    • 字符串的前缀重合比较多;

    • 从零开始实现一个 Trie 树,比较复杂,不便于维护;

    • Trie 树中利用指针来存储数据,不利用利用缓存。

    因此,在工程中,我们更倾向于使用散列表或者红黑树,它们都不需要自己去实现,直接利用编程语言中提供的线程类库就行。实际上,Trie 树不适合这种精确查找,更适合的是查找前缀匹配的字符串,也就是搜索时的关键词提示功能。

     

    5. 搜索关键词提示功能的实现

    假设关键词库由用户的热门搜索关键词组成,我们将这个词库构建成一个 Trie 树。当用户输入其中某个单词的时候,把这个词作为一个前缀子串在 Trie 树中匹配。还以上面为例,当用户输入 'h' 时,我们就可以将以 'h' 为前缀的单词 hello,her,hi,how 展示在搜索提示框,当用户输入 'he' 时,我们就可以将以 'h' 为前缀的单词 hello,her 展示在搜索提示框。这就是搜索关键词提示的最基本的算法原理。

    另外,Trie 树还可以扩展到更加广泛的应用上,比如输入法、代码编辑器和浏览器的自动输入补全功能。

    展开全文
  • 搜索引擎的搜索关键词提示功能,我想你应该不陌生吧?为了方便快速输入,当你在搜索引擎的搜索框中,输入要搜索的文字的某一部分的时候,搜索引擎就会自动弹出下拉框,里面是各种关键词提示。你可以直接从下拉框中...

    搜索引擎的搜索关键词提示功能,我想你应该不陌生吧?为了方便快速输入,当你在搜索引擎的搜索框中,输入要搜索的文字的某一部分的时候,搜索引擎就会自动弹出下拉框,里面是各种关键词提示。你可以直接从下拉框中选择你要搜索的东西,而不用把所有内容都输入进去,一定程度上节省了我们的搜索时间。
    在这里插入图片描述
    尽管这个功能我们几乎天天在用,作为一名工程师,你是否思考过,它是怎么实现的呢?它底层使用的是哪种数据结构和算法呢?像 Google、百度这样的搜索引擎,它们的关键词提示功能非常全面和精准,肯定做了很多优化,但万变不离其宗,底层最基本的原理就是Trie 树。

    1.什么是Trie树?

    Trie 树,也叫“字典树”。顾名思义,它是一个树形结构。它是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串的问题。
    当然,这样一个问题可以有多种解决方法,比如散列表、红黑树,或者我们前面几节讲到的一些字符串匹配算法,但是,Trie 树在这个问题的解决上,有它特有的优点。不仅如此,Trie 树能解决的问题也不限于此,我们一会儿慢慢分析。
    现在,我们先来看下,Trie 树到底长什么样子。
    我举个简单的例子来说明一下。我们有 6 个字符串,它们分别是:how,hi,her,hello,so,see。我们希望在里面多次查找某个字符串是否存在。如果每次查找,都是拿要查找的字符串跟这 6 个字符串依次进行字符串匹配,那效率就比较低,有没有更高效的方法呢?
    这个时候,我们就可以先对这 6 个字符串做一下预处理,组织成 Trie 树的结构,之后每次查找,都是在 Trie 树中进行匹配查找。Trie 树的本质,就是利用字符串之间的公共前缀,将重复的前缀合并在一起。最后构造出来的就是下面这个图中的样子。
    在这里插入图片描述
    其中,根节点不包含任何信息。每个节点表示一个字符串中的字符,从根节点到红色节点的一条路径表示一个字符串(注意:红色节点并不都是叶子节点)。为了让你更容易理解 Trie 树是怎么构造出来的,我画了一个 Trie 树构造的分解过程。构造过程的每一步,都相当于往 Trie 树中插入一个字符串。当所有字符串都插入完成之后,Trie 树就构造好了。
    在这里插入图片描述
    在这里插入图片描述
    当我们在 Trie 树中查找一个字符串的时候,比如查找字符串“her”,那我们将要查找的字符串分割成单个的字符 h,e,r,然后从 Trie 树的根节点开始匹配。如图所示,绿色的路径就是在 Trie 树中匹配的路径。
    在这里插入图片描述
    如果我们要查找的是字符串“he”呢?我们还用上面同样的方法,从根节点开始,沿着某条路径来匹配,如图所示,绿色的路径,是字符串“he”匹配的路径。但是,路径的最后一个节点“e”并不是红色的。也就是说,“he”是某个字符串的前缀子串,但并不能完全匹配任何字符串。
    在这里插入图片描述

    2.如何实现一棵Trie树?

    从刚刚 Trie 树的介绍来看,Trie 树主要有两个操作,一个是将字符串集合构造成 Trie 树。这个过程分解开来的话,就是一个将字符串插入到 Trie 树的过程。另一个是在 Trie 树中查询一个字符串。
    了解了 Trie 树的两个主要操作之后,我们再来看下,如何存储一个 Trie 树?
    从前面的图中,我们可以看出,Trie 树是一个多叉树。我们知道,二叉树中,一个节点的左右子节点是通过两个指针来存储的,如下所示 Java 代码。那对于多叉树来说,我们怎么存储一个节点的所有子节点的指针呢?

    class BinaryTreeNode{//二叉树节点
    	char data;
    	BinaryTreeNode left;
    	BinaryTreeNode right;
    }
    

    我先介绍其中一种存储方式,也是经典的存储方式,大部分数据结构和算法书籍中都是这么讲的。还记得我们前面讲到的散列表吗?借助散列表的思想,我们通过一个下标与字符一一映射的数组,来存储子节点的指针。这句话稍微有点抽象,不怎么好懂,我画了一张图你可以看看。
    在这里插入图片描述
    假设我们的字符串中只有从 a 到 z 这 26 个小写字母,我们在数组中下标为 0 的位置,存储指向子节点 a 的指针,下标为 1 的位置存储指向子节点 b 的指针,以此类推,下标为 25 的位置,存储的是指向的子节点 z 的指针。如果某个字符的子节点不存在,我们就在对应的下标的位置存储 null。即每个节点都维持着一个大小为26的数组用于存储其子节点的指针地址
    我们在 Trie 树中查找字符串的时候,我们就可以通过字符的 ASCII 码减去“a”的 ASCII 码,迅速找到匹配的子节点的指针。比如,d 的 ASCII 码减去 a 的 ASCII 码就是 3,那子节点 d 的指针就存储在数组中下标为 3 的位置中。
    描述了这么多,有可能你还是有点懵,我把上面的描述翻译成了代码,你可以结合着一块看下,应该有助于你理解。

    public class Trie {//字典树
    	private TrieNode root=new TrieNode('/');//根节点存储无意义字符
    	public void insert(char[] text){
    		TrieNode p=root;
    		for(int i=0;i<text.length;i++){
    			int index=text[i]-'a';
    			if(p.children[index]==null){
    				TrieNode newNode=new TrieNode(text[i]);
    				p.children[index]=newNode;
    			}
    			p=p.children[index];
    		}
    		p.isEndingChar=true;
    	}
    	public boolean find(char[] pattern){
    		TrieNode p=root;
    		for(int i=0;i<pattern.length;++i){
    			int index=pattern[i]='a';
    			if(p.children[index]==null){
    				return false;
    			}
    			p=p.children[index];
    		}
    		if(p.isEndingChar==false){
    			return false;
    		}else return true;
    	}
    }
    class TrieNode{
    	public char data;
    	public TrieNode[] children=new TrieNode[26];
    	public boolean isEndingChar=false;
    	public TrieNode(char data){
    		this.data=data;
    	}
    }
    

    3.Trie树的时间复杂度和空间复杂度分析

    3.1 时间复杂度分析

    如果要在一组字符串中,频繁地查询某些字符串,用 Trie 树会非常高效。构建 Trie 树的过程,需要扫描所有的字符串,时间复杂度是 O(n)(n 表示所有字符串的长度和)。但是一旦构建成功之后,后续的查询操作会非常高效。每次查询时,如果要查询的字符串长度是 k,那我们只需要比对大约 k 个节点,就能完成查询操作。跟原本那组字符串的长度和个数没有任何关系。所以说,构建好 Trie 树后,在其中查找字符串的时间复杂度是 O(k),k 表示要查找的字符串的长度。

    3.2 空间复杂度分析

    刚刚我们在讲 Trie 树的实现的时候,讲到用数组来存储一个节点的子节点的指针。如果字符串中包含从 a 到 z 这 26 个字符,那每个节点都要存储一个长度为 26 的数组,并且每个数组元素要存储一个 8 字节指针(或者是 4 字节,这个大小跟 CPU、操作系统、编译器等有关)。而且,即便一个节点只有很少的子节点,远小于 26 个,比如 3、4 个,我们也要维护一个长度为 26 的数组。
    如果字符串中不仅包含小写字母,还包含大写字母、数字、甚至是中文,那需要的存储空间就更多了。所以,也就是说,在某些情况下,Trie 树不一定会节省存储空间。在重复的前缀并不多的情况下,Trie 树不但不能节省内存,还有可能会浪费更多的内存。
    当然,我们不可否认,Trie 树尽管有可能很浪费内存,但是确实非常高效。那为了解决这个内存问题,我们是否有其他办法呢?
    我们可以稍微牺牲一点查询的效率,将每个节点中的数组换成其他数据结构,来存储一个节点的子节点指针。用哪种数据结构呢?我们的选择其实有很多,比如有序数组、跳表、散列表、红黑树等。
    假设我们用有序数组,数组中的指针按照所指向的子节点中的字符的大小顺序排列。查询的时候,我们可以通过二分查找的方法,快速查找到某个字符应该匹配的子节点的指针。但是,在往 Trie 树中插入一个字符串的时候,我们为了维护数组中数据的有序性,就会稍微慢了点。
    实际上,Trie 树的变体有很多,都可以在一定程度上解决内存消耗的问题。比如,缩点优化,就是对只有一个子节点的节点,而且此节点不是一个串的结束节点,可以将此节点与子节点合并。这样可以节省空间,但却增加了编码难度。这里我就不展开详细讲解了,你如果感兴趣,可以自行研究下。
    在这里插入图片描述

    4.Trie树与散列表、红黑树的比较

    实际上,字符串的匹配问题,笼统上讲,其实就是数据的查找问题。对于支持动态数据高效操作的数据结构,我们前面已经讲过好多了,比如散列表、红黑树、跳表等等。实际上,这些数据结构也可以实现在一组字符串中查找字符串的功能。我们选了两种数据结构,散列表和红黑树,跟 Trie 树比较一下,看看它们各自的优缺点和应用场景。
    在刚刚讲的这个场景,在一组字符串中查找字符串,Trie 树实际上表现得并不好。它对要处理的字符串有及其严苛的要求。
    第一,字符串中包含的字符集不能太大。我们前面讲到,如果字符集太大,那存储空间可能就会浪费很多。即便可以优化,但也要付出牺牲查询、插入效率的代价。
    第二,要求字符串的前缀重合比较多,不然空间消耗会变大很多
    第三,如果要用 Trie 树解决问题,那我们就要自己从零开始实现一个 Trie 树,还要保证没有 bug,这个在工程上是将简单问题复杂化,除非必须,一般不建议这样做。
    第四,我们知道,通过指针串起来的数据块是不连续的,而 Trie 树中用到了指针,所以,对缓存并不友好,性能上会打个折扣。
    综合这几点,针对在一组字符串中查找字符串的问题,我们在工程中,更倾向于用散列表或者红黑树。因为这两种数据结构,我们都不需要自己去实现,直接利用编程语言中提供的现成类库就行了。
    讲到这里,你可能要疑惑了,讲了半天,我对 Trie 树一通否定,还让你用红黑树或者散列表,那 Trie 树是不是就没用了呢?是不是今天的内容就白学了呢?实际上,Trie 树只是不适合精确匹配查找,这种问题更适合用散列表或者红黑树来解决。Trie 树比较适合的是查找前缀匹配的字符串,也就是类似开篇问题的那种场景——即实现搜索引擎的搜索关键词提示功能

    5.字典树的优化——AC自动机

    很多支持用户发表文本内容的网站,比如 BBS,大都会有敏感词过滤功能,用来过滤掉用户输入的一些淫秽、反动、谩骂等内容。你有没有想过,这个功能是怎么实现的呢?
    实际上,这些功能最基本的原理就是字符串匹配算法,也就是通过维护一个敏感词的字典,当用户输入一段文字内容之后,通过字符串匹配算法,来查找用户输入的这段文字,是否包含敏感词。如果有,就用“*XXX”把它替代掉。
    我们前面讲过好几种字符串匹配算法了,它们都可以处理这个问题。但是,对于访问量巨大的网站来说,比如淘宝,用户每天的评论数有几亿、甚至几十亿。这时候,我们对敏感词过滤系统的性能要求就要很高。毕竟,我们也不想,用户输入内容之后,要等几秒才能发送出去吧?我们也不想,为了这个功能耗费过多的机器吧?那如何才能实现一个高性能的敏感词过滤系统呢?这就要用到今天的多模式串匹配算法
    我们前面几节讲了好几种字符串匹配算法,有 BF 算法、RK 算法、BM 算法、KMP 算法,还有 Trie 树。前面四种算法都是单模式串匹配算法,只有 Trie 树是多模式串匹配算法。我说过,单模式串匹配算法,是在一个模式串和一个主串之间进行匹配,也就是说,在一个主串中查找一个模式串。多模式串匹配算法,就是在多个模式串和一个主串之间做匹配,也就是说,在一个主串中查找多个模式串。
    尽管,单模式串匹配算法也能完成多模式串的匹配工作。例如开篇的思考题,我们可以针对每个敏感词,通过单模式串匹配算法(比如 KMP 算法)与用户输入的文字内容进行匹配。但是,这样做的话,每个匹配过程都需要扫描一遍用户输入的内容。整个过程下来就要扫描很多遍用户输入的内容。如果敏感词很多,比如几千个,并且用户输入的内容很长,假如有上千个字符,那我们就需要扫描几千遍这样的输入内容。很显然,这种处理思路比较低效。
    与单模式匹配算法相比,多模式匹配算法在这个问题的处理上就很高效了。它只需要扫描一遍主串,就能在主串中一次性查找多个模式串是否存在,从而大大提高匹配效率。我们知道,Trie 树就是一种多模式串匹配算法。那如何用 Trie 树实现敏感词过滤功能呢?
    我们可以对敏感词字典进行预处理,构建成 Trie 树结构。这个预处理的操作只需要做一次,如果敏感词字典动态更新了,比如删除、添加了一个敏感词,那我们只需要动态更新一下 Trie 树就可以了。
    当用户输入一个文本内容后,我们把用户输入的内容作为主串,从第一个字符(假设是字符 C)开始,在 Trie 树中匹配。当匹配到 Trie 树的叶子节点,或者中途遇到不匹配字符的时候,我们将主串的开始匹配位置后移一位,也就是从字符 C 的下一个字符开始,重新在 Trie 树中匹配。基于 Trie 树的这种处理方法,有点类似单模式串匹配的 BF 算法。我们知道,单模式串匹配算法中,KMP 算法对 BF 算法进行改进,引入了 next 数组,让匹配失败时,尽可能将模式串往后多滑动几位。借鉴单模式串的优化改进方法,能否对多模式串 Trie 树进行改进,进一步提高 Trie 树的效率呢?这就要用到 AC 自动机算法了。
    AC自动机的具体原理不需要掌握,我们只需要知道其应用与其和字典树的关系即可。

    展开全文
  • 搜索引擎的搜索关键词提示功能,我先你应该不陌生吧 ?为了方便舒服,当你在搜索框,输入文字的某一部分的时候,搜索引擎会自动弹出下拉框,里面有各种关键词提示。 你可以从下拉框中选中你要搜索的东西。 二、Trie...

    一、场景

    搜索引擎的搜索关键词提示功能,我先你应该不陌生吧 ?为了方便舒服,当你在搜索框,输入文字的某一部分的时候,搜索引擎会自动弹出下拉框,里面有各种关键词提示。 你可以从下拉框中选中你要搜索的东西。
    在这里插入图片描述

    二、Trie 树定义

    现在主流的搜索引擎,他们的关键词提示功能非常全面和精确,肯定做了很多优化,但最基本的原理是用了数据结构:Trie 树。
    Trie 树 ,也叫“字典树”。顾名思义,它是一个树形结构,它是一种专门处理字符串匹配的数据结构,用来解决在一组字符串中快速查找某个字符的问题。

    三、Trie 树实现搜索关键词原理

    1 )我们先看一下,Trie 树长什么样子。
    举一个简单的例子。我们有6个字符串,分别是:how,hi,her,hello,so,see。我们洗碗在里面多次查找某个字符串是否存在。如果每次查找,都是拿要查找的字符串跟这6个字符串依次进行字符串匹配,效率比较低。
    我们可以先对6个字符串做一下预处理,组织成一个Trie树的结构,字后每次查找,都在Trie树中匹配查找。
    Trie树的本质,就是利用字符串之间的公共前缀,将重复的前缀合并在一起。最后构造出如图的样子。
    在这里插入图片描述
    其中,根节点不包含任何信息。每个节点表示一个字符串中的字符,从根节点到红色节点的一条路径表示一个字符串(注意:红色节点并不都是叶子节点)。
    2)看一下怎么构造Trie 树
    构造过程的每一步,相当于往Trie 树中插入一个字符串。当所有字符串都插入完成后,Trie 树就构造好了。
    在这里插入图片描述
    3 )Trie 树中匹配字符串
    在Trie 树中查找一个字符串的时候,比如查找字符串“her”,那会将字符串分割成单个字符h,e,r,然后从Trie 树的根节点开始匹配。如下图,绿色的路径就是在Trie 树中匹配的路径。
    在这里插入图片描述

    四、Trie 树与红黑树、散列表算法对比

    1)字符串中包含的字符集不能太大。如果字符集太大,那存储空间可能就会浪费很多。
    2)字符串的前缀重合比较多,不然空间消耗会很大。
    3)如果要用Trie 树解决问题,那我们就需要从零实现一个Trie 树,还要保证没bug,这可能会导致问题复杂化,一般不建议这么做。
    4)Trie 树是通过指针串起来的数据块是不连续的,所以对指针并不友好,性能上会打折扣。

    综合这几点,针对一组字符串中查找字符串的问题,在工程中,更倾向于用散列表或红黑树。因为这两种数据结构,可以直接用现成类库就行。

    转载:https://time.geekbang.org/column/article/72414

    展开全文
  • 搜索引擎的搜索关键词提示功能,你应该不陌生吧!当你在搜索引擎的搜索框上,输入要搜索的文字的某一部分的时候,搜索引擎就会自动弹出下拉框,里面是各种关键词提示。你可以直接从下拉框中选择你要搜索的东西。 ...
  • 文章目录搜索中的关键词提示Trie树的介绍Trie树的实现Trie树的优缺点 搜索中的关键词提示 当我们在搜索引擎中进行搜索时,有时仅仅输入了搜索内容的一部分,搜索引擎就会提示我们可能的一些选择,这样我们就不再...
  • 搜索引擎的搜索关键词提示功能不用讲了吧,相信大家都用过.那么他是如何实现的呐?今天就来说一说它底层最基本的原理:Trie 树 什么是“Trie 树”? Trie 树,也叫“字典树”。顾名思义,它是一个树形结构。它是一...
  • Trie 树是一种解决字符串快速匹配问题的数据结构。如果用来构建 Trie 树的这一组字符串中,前缀重复的情况不是很多,那 Trie 树...Trie 树最有优势的是查找前缀匹配的字符串,比如搜索引擎中的关键词提示功能这个场景;
  • 输入学校名称,调用腾讯地图的关键词提示服务选择学校的地址,项目需要学校地址的坐标。 腾讯地图服务官网api 二,实现: (一)使用axios请求接口: schoolNameChange(e){ constthat=this; constschoolName=e...
  • 数据结构与算法之美 - 35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?什么是“Trie 树”?如何实现一棵 Trie 树?Trie 树真的很耗内存吗?Trie 树与散列表、红黑树的比较解答开篇内容小结课后思考 搜索引擎的...
  • vscode设置backbone关键词提示 打开 File - Preferences - User Snippets javascript.json // An highlighted block { "Backbone": { "prefix": "Ba", "body": [ "Backbone" ], "description": ...
  • 搜索引擎的搜索关键词提示功能,我想你应该不陌生吧?为了方便快速输入,当你在搜索引擎的搜索框中,输入要搜索的文字的某一部分的时候,搜索引擎就会自动弹出下拉框,里面是各种关键词提示。你可以直接从下拉框中...
  • Trie树Ⅰ 前言Ⅱ Trie 树的原理Ⅲ Trie 树的实现Ⅳ Trie 树的执行效率Ⅴ Trie 树与散列表、红黑树的比较Ⅵ 如何实现搜索引擎的关键词提示功能 Ⅰ 前言 大家肯定都用过搜索引擎,应该对下面的情形很熟悉了???? 我们...
  • c#模仿百度关键词提示

    千次阅读 2014-07-30 17:27:26
    1:from窗体环境:TextBox(关键词文本框)、ListBox(提示框) 2:实现思路:  2.1:以输入的关键词为条件查询 数据库(在查询中以点击率排序就加一个order by 点击率 desc)返回多行单列数据结果集合。再一一赋值到...
  • 搜索引擎的搜索关键词提示功能,我想你应该不陌生吧?为了方便快速输入,当你在搜索引擎的搜索框中,输入要搜索的文字的某一部分的时候,搜索引擎就会自动弹出下拉框,里面是各种关键词提示。你可以直接从下拉框中...
  • 2019独角兽企业重金招聘Python工程师标准>>> ...
  • 什么是 Trie 树 Trie 树的实现 如何实现搜索字符串自动提示 再谈 Trie 树 相信大家看了肯定有收获 什么是 Trie 树 Trie 树,又称前缀树,字典树,或单词查找树,是一种树形结构,也是哈希表的变种,它是一种专门...
  • 什么是 Trie 树 Trie 树的实现 如何实现搜索字符串自动提示 再谈 Trie 树 相信大家看了肯定有收获 什么是 Trie 树 Trie 树,又称前缀树,字典树,或单词查找树,是一种树形结构,也是哈希表的变种,它是一种专门...
  • 快速查找某个字符串的功能。 比如,我们有6个字符串,它们分别是:how,hi,her,hello,so,see。我们希望在里面多次查找某个字符是否存在。我们可以先对这6个字符串做一下预处理,组织成Trie树的结构,之后每次查找,都...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,179
精华内容 871
关键字:

关键词提示