前言
最进在看分词源码，发现词库的存储是基于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
网友评论