字典树（trie）/前缀树（Prefix Tree）实例讲解

92923 阅读 0 评论 0 点赞

对于字典树/前缀树可能大部分情况很难直观或者有接触的体验，尤其是对前缀这个玩意没啥概念，可能做题遇到前缀问题也是使用暴力匹配蒙混过关，如果字符串比较少使用哈希表等结构可能也能蒙混过关，但如果字符串比较长、相同前缀较多那么使用字典树可以大大减少内存的使用和效率。

一个字典树的应用场景：在搜索框输入部分单词下面会有一些神关联的搜索内容，你有时候都很神奇是怎么做到的，这其实就是字典树的一个思想。

一、字典树trie树

Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树，是一种多叉树结构。

字典树trie树

二、trie树的作用

Trie树的核心思想是空间换时间，利用字符串的公共前缀来减少无谓的字符串比较以达到提高查询效率的目的。

（1）核心应用

1. 字符串检索；

2. 词频统计；

3. 字符串排序；

4. 前缀匹配。

（2）trie树节点

每个字母都占用一个trie树节点，根节点与子节点没有本质的区别，主要有这几个属性：

1. root: 是否为根节点

2. dict: 装子节点的hash表

3. flag: 是否为一个单词的结尾

4. value: 该单词的完整内容（只有在flag为True时才有）

5. count: 该单词出现的次数（只有在flag为True时才有）

6. list: 是一个字典，用于遍历储存东西的(只有root节点才有)

class Trie(object):

    def __init__(self, root=None,flag=False,count=None,value=None):
        self.root = root  # root 节点用于装内容
        self.count = count  # count 用于计数，可以统计词频
        self.dict = {}  # dict 用于装子节点，子节点还是trie树
        self.flag = flag  # flag用于判断是否结束
        self.value = value # value就表示这个单词是什么
        self.list = {}

（3）常规操作

先来实现最基础的四个操作：

1. insert: 增,注意最后一个字母的判断以及处理即可

2. search: 查

3. delete: 删

4. startsWith: 判断前缀是否存在

①增

def insert(self, word):
        """
        :type word: str
        :rtype: None
        """
        trie = self
        for j,i in enumerate(word):
            # 如果是不是最后一个字母就遍历(或添加)
            if j != len(word) - 1:
                if i not in trie.dict:
                    trie.dict[i] = Trie(root=i)
                trie = trie.dict[i]
            else:
                # 是最后一个字母且flag为true就加计数
                if i in trie.dict and trie.dict[i].flag:
                    trie = trie.dict[i]
                    trie.count += 1
                # 是最后一个字母但flag为false就修改flag将计数改为1
                elif i in trie.dict and not trie.dict[i].flag:
                    trie = trie.dict[i]
                    trie.flag = True
                    trie.count = 1
                    trie.value = word
                # 如果trie.dict中没有就新增
                else:
                    trie.dict[i] = Trie(root=i,flag=True,count=1,value=word)

②查

def search(self, word):
        """
        :type word: str
        :rtype: bool
        """
        trie = self
        for i in word:
            if i in trie.dict:
                trie = trie.dict[i]
            else:
                return False
        return trie.flag

③删

def delete(self, word):
        '''
        :type word: str
        :rtype: None
        '''
        if self.search(word):
            trie = self
            for i in word:
                if len(trie.dict) == 1:
                    trie.dict.pop(i)
                    break
                else:
                    trie = trie.dict[i]
        else:
            print('该单词不在trie树中')

④判断前缀是否存在

def startsWith(self, prefix):
        """
        :type prefix: str
        :rtype: bool
        """
        trie = self
        for i in prefix:
            if i in trie.dict:
                trie = trie.dict[i]
            else:
                return False
        return True

（4）遍历操作

遍历操作就首选DFS深度优先搜索,参数中加入prefix的目的是为了后面的联想操作，如果只做遍历可以不加；值得一提的是，我对子节点的储存采用的是字典的形式，遍历出来的结果排序刚刚好就是字典序，也就实现了前面说的字符串字典序的处理（其实真要排字典序，直接sorted就好了，没必要用trie树）

def dfs(self,path,trie,prefix=''):
        # 如果为真说明走到了一个单词的结尾
        if trie.flag:
            self.list[prefix + ''.join(path)] = trie.count
            if trie.dict == {}:
                return
        
        for i in trie.dict:
            path.append(i)
            self.dfs(path,trie.dict[i],prefix)
            path.pop()

给trie树创建可迭代方法

def __iter__(self):
        self.list = {}  # 重置self.list
        self.dfs([],self)
        return iter(self.list)

（5）联想操作

联想业务应该是这样的：用户输入前几个字母，然后匹配出完整的单词，使用频率越高的单词理应放在最前面；

所以整体思路是这样的：根据前缀找到前缀最后一个字母所在的trie树节点，从那个节点开始进行DFS遍历，然后在遍历结果前加上一个前缀，最后将结果按照count进行排序最后以列表形式输出结果；

先实现排序算法，这里用的是快速排序,注意比较的值是count，最后留下的是单词；

def quick_sorted(self,dict):
        '''
        :type dict: dict
        :rtype: list
        '''
        if len(dict) >= 2:
            nums = list(dict.keys())
            mid = nums[len(nums) // 2]
            left, right = {}, {}
            nums.remove(mid)
            for d in nums:
                if dict[d] < dict[mid]:
                    left[d] = dict[d]
                else:
                    right[d] = dict[d]
            return self.quick_sorted(right) + [mid] + self.quick_sorted(left)
        return list(dict.keys())

再实现联想操作

def dream(self,prefix):
        '''
        :type prefix: str
        :rtype: list
        '''
        trie = self
        for i in prefix:
            if i in trie.dict:
                trie = trie.dict[i]
            elif dict[d] == dict[mid]:
                if d > mid:
                    right[d] = dict[d]
                else:
                    left[d] = dict[d]
            else:
                return []
        self.list = {}  # 重置self.list
        self.dfs([],trie,prefix)
        return self.quick_sorted(self.list)