树结构之Trie 树（前缀树，字典树）

前言

最进在看分词源码，发现词库的存储是基于Trie树的数据结构，特此了解了下其原理。Trie树又叫前缀树，字典树。Trie树的用途：字典搜索，词频统计，前缀查询等等。原理也不复杂。

Trie 树结构。

假设有 '不问', '不只', '朝', '朝着','不问你'这些词，那么如何构建trie树呢？直接上图：

好处：

压缩数据，将例子中10个字压缩成6个字进行存储，节省空间。
查找前缀方便，假如要搜索‘不’开头的词不需要遍历整个字典。

代码实现：

树节点：

class TreeNode:
    
    def __init__(self, word, number = 1,isEndWord = False):
        self.word = word
        self.number = number#前缀次数
        
        self.prefix_terms = set() #记录包含此前缀的所有词
        self.child_nodes = {}
        self.isEndWord = isEndWord #判断是否是一个词的最后个字
        
        if isEndWord:
            self.end_number = 1#词频次数
        else:
            self.end_number = 0#词频次数
        
    
    def add_child(self, word, isEndWord, term = None):
        self.prefix_terms.add(term)
        
        if word in self.child_nodes.keys():
            sub_tree_node = self.child_nodes.get(word)
            sub_tree_node.prefix_terms.add(term)
            sub_tree_node.number += 1
            if isEndWord:
                sub_tree_node.end_number += 1
        
        else:
            self.child_nodes[word] = TreeNode(word, number= 1,isEndWord = isEndWord)
            self.child_nodes[word].prefix_terms.add(term)

总共包含5个成员变量，分别是当前字符word，统计的前缀次数number，包含此前缀的词汇prefix_terms，当前字符是否是词的结束字isEndWord，以及当前词的词频。

构建树

class Trie:
    
    def __init__(self): 
        self.root = TreeNode("root")
    
    
    def buildTree(self,term):
        term = term.strip()
        if len(term) == 0:
            return
        
        current_node = self.root
        iter_num = len(term)
        for i in range(iter_num):
            if i == (iter_num - 1):
                current_node.add_child(term[i], isEndWord = True, term = term)
            else:
                current_node.add_child(term[i], isEndWord = False, term = term)
            
            current_node = current_node.child_nodes.get(term[i])

树搜索：

#前缀树查找
    #前缀树查找
    def searchTree(self,term):
         
        term = term.strip()
        if len(term) == 0:
            return None,0,0
        
        current_node = self.root
        iter_num = len(term)
        for i in range(iter_num):
            
            if term[i] in current_node.child_nodes.keys():
                current_node = current_node.child_nodes.get(term[i])
                 
                if i == (iter_num - 1):
                    return current_node.prefix_terms,current_node.end_number,current_node.number
            else:
                return None,0,0
            
    #####递归，动态规划思想
    def searchTreeByRecursion(self, term, current_node = None):
        
        if current_node is None:
            current_node = self.root
            term = term.strip()
            if len(term) == 0:
                return None,0,0
        
        if term[0] in current_node.child_nodes.keys():
            current_node = current_node.child_nodes.get(term[0])
            if len(term) == 1:
                return current_node.prefix_terms, current_node.end_number, current_node.number
            
            return self.searchTreeByRecursion(term[1:], current_node)
        else:
            return None, 0, 0

写了两个方法，一个从上往下遍历，一个从下往上基于递归。

输出树：

def display_tree(self, current_node = None, display_content = None):
        display = ''
        if current_node is None:
            current_node = self.root
            print([current_node.word])
            display_content = ''
 
        if not current_node.child_nodes:
            print(display_content + current_node.word+'/'+str(current_node.number)+'/'+str(current_node.end_number)+'/'+str(current_node.isEndWord))
        else:
            for sub_node in current_node.child_nodes.values():
                self.display_tree(sub_node,display_content+ current_node.word+'/'+str(current_node.number)+'/'+str(current_node.end_number)+'/'+str(current_node.isEndWord)+"--->")

这里输出树的每条分支，已经各个树节点的变量。

代码已上传百度网盘：
链接:https://pan.baidu.com/s/1vYmhrcHAIS-3oT3tLN_91Q 密码:hsbw

最后编辑于：2018.12.14 15:22:03