Trie树

概述

在Google中随意搜索,如下所示:

img

他会自动显示相关的搜索,不知道有没有想过这个功能是如何实现的呢?面对海量的数据,它怎么能在我输入的同时,如此快速的检索到相关内容呢?当我查找资料后,就遇到了它,Trie树。

What?

Trie树是个什么玩意呢?为啥他能快速进行检索?Trie树也叫字典树。因为它的结构和我们用到的字典基本差不多。

想想,你在字典中差“how”这个单词的动作是怎样的?先找到h,然后在h的基础上找o,再找w。用树来存储这个过程就是这样的:

img

没毛病。如果存储:how, hello, kan, know这几个单词,如下所示:

img

简单易懂。在其中查找字符,就跟查字典一样,一级一级往下找就行了。

比如查找单词,“ho”,当找到o时,发现o不是叶子节点,说明“ho”是某个单词的前缀,并不是完整的单词。

看到有人拿Trie树和红黑树、哈希表做对比,红黑树我还没整明白,但是哈希表我知道啊。这俩有可比性么?我觉得没有,完全就是两种数据结构,打眼一看,就知道他们的侧重点不同。很明显Trie树适合进行前缀匹配,而哈希表适合进行精确匹配啊。哦,还有一个,哈希表很多语言都有现成的实现,如HashMap,但Trie树貌似没有。

How

Trie树看着挺厉害的。那如何实现呢?刚才说了,哈希表很多有现成的实现,但Trie树没有,所以要想使用,就得自己来实现。

Trie树说到底还是树结构。其结构体如下:

struct TrieNode{
    char  data; // 保存字符
    TrieNode children[26]; // 子节点
}

使用Python写一个简单实现,其他语言也大同小异吧。都需要实现什么功能呢?

  1. 将字符串加入
  2. 匹配字符串

class Trie:

    class TrieNode:
        """
        树的节点
        """
        def __init__(self, data):
            self.data = data
            self.children = {}

    def __init__(self):
        self.root = self.TrieNode(None)

    def insert_str(self, string):
        """
        讲字符串添加进trie树中
        :param string: 字符串
        """
        tmp_trie_node = self.root
        for c in list(string):
            # 这里使用字母的顺序作为key,方便查找
            index = ord(c) - ord('a')
            if not tmp_trie_node.children.get(index):
                tmp_trie_node.children[index] = self.TrieNode(c)
            tmp_trie_node = tmp_trie_node.children[index]

    def is_match_str(self, string):
        """
        查询字符串是否在树中
        :param string:
        :return:
        """
        tmp_trie_node = self.root
        for c in list(string):
            index = ord(c) - ord('a')
            if not tmp_trie_node.children.get(index):
                return False
            tmp_trie_node = tmp_trie_node.children[index]
        return True

if __name__ == '__main__':
    trie = Trie()
    for string in ['how', 'hello', 'kan', 'know']:
        trie.insert_str(string)
    print(trie.is_match_str('hello'))
    print(trie.is_match_str('hess'))

很简单的一个小demo

可以看的出来,Trie树在构建的时候,需要扫描所有字符串,但是在查找的时候就很快速了。

why

说了半天,Trie树算是简单的说完了。回到开篇的问题上,使用Trie树是如何进行搜索的?

比如我们输入“h”,就可以把“h”为前缀的单词展示出来,再输入“he”,就把“he”为前缀的单词展示出来。

输入单词后,展示相关的搜索句子,也是同样的道理。当然,搜索引擎会对其进行优化,比如匹配的相关内容有很多,从中选择哪些?等等。以上只是一个雏形的雏形。

Trie树不光可以用在搜索上,类似的场景有很多,比如输入法的自动补全、IDE的自动补全等等。怎么都是自动补全,应该还是有其他场景的,只是我只想到了这些。

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

原文地址 https://hujingnb.com/archives/278

转载请保留原文连接: Trie树 | 烟草的香味

guest
0 评论
内联反馈
查看所有评论
0
希望看到您的想法,请发表评论。x