[二]漫话中文分词:Trie前缀树

在上一篇文章当中,说到了一些匹配的算法,但是算法有了,还得需要一个高效的数据结构,不能只是通过[‘中国人’, ‘中东人’]等结构来进行存放,可以想象一下,如果有几十万的词,那么这个列表的占用的内存非常大。

Trie树,也被称为前缀树,该词源自单词retrieval,发音和try相同,Trie树可以为字典分词提供一种高效的分词数据结构,该结构本质上是一种树状数据结构,比如”中国人”、”中东人”三个字符串构造的Trie树为下图,图中能够很清楚的看见,Trie树结构能够很好的节省相同前缀单词所浪费的空间,因为这两个词都是以”中”开头,所以可以使用同一个父辈节点。

1

除此之外,Trie树还对查询的速度有一定的优化,如果以列表存放词来说,如果列表存放的词达到了20万个,那么最坏的情况是你需要匹配的词在存放于最后,那么就相当于要将这20万个词全部遍历,可想而知浪费了非常多的计算资源。

下图为基于同一份10万左右的词典,使用正向最大匹配算法在列表和Trie两种结构上进行分词的运行时间,从下图可以看出来差距非常大。

而Trie树的查找方式则是通过层层查询,而不是直接遍历词典,比如”中国人”,首先会查找第一层中是否有”中”这个字符,如果没有查询到则返回查询失败,如果有则继续查找”中”字符对应的下一层是否有”国”,如果没有则返回查询识别,如果有则继续查找”国”下一层是否有”人”,此时找到存在”人”这个节点,并且该节点标注为蓝色,表明是一个词,所以返回该字符串为一个词。

其实要实现这样的数据结构,大致的功能点为下面两点:

  1. 查询词
  2. 添加词

除此之外还需要考虑如果标记词的结束节点,首先可以约定,默认情况都返回”False”表示为未查询到或设置失败,而返回”True”则表示查询到或设置成功,每个节点为一个字符,而字典当中的__value表示是否为结束节点(即一个词的尾字符),如果是则为True,不是则为False,整体可以采用函数或者类来定义。

实现代码:

class Trie():  #定义一个Trie类型
    def __init__(self):  #为这个生成的实例定义一个名为_children的对象,用于存放词的Trie结构
        self._children = {}
    def _add_word(self, word):  # 定义一个添加词的实例方法
        child = self._children  # 首先会将_children的对象赋值给child
        for i,char in enumerate(word):  # 然后从头遍历添加词的每一个字符
            if char not in child:  # 查看当前字符是否存在Trie树上
                child[char] = {'__value': False} # 如果没有则新建一个对象,并设置特殊key__value为False,表明这不是一个结尾字符
            if i == (len(word) - 1):  # 判断是否为结尾字符
                child[char]['__value'] = True # 如果是则将特殊key:__value设为True,表明为结尾字符
            child = child[char]  # 如果还有字符,则将当前字符对象更新为child,那么下一次查找则是基于上一次对象下
        return True # 添加完成返回True
    def _get_word(self, word):  # 查找词
        child = self._children  # 同样设置一个child变量,用于控制当前的字符对象 
        for char in word:  
            child = child.get(char)
            if child is None :  # 只要其中一个没有查找到,那么说明匹配识别,则返回False
                return False 
        return child['__value']  # 如果没有匹配失败则返回特殊__value的值
    #回True表示词典中存在该词,返回False表示不存在或者传递进来的词不成词

将Trie实现后,就可以在正向或者反向等算法中来进行使用,从而提高运算的效率,但是使用Trie树的时候,可能无法动态的计算其词的长度,所以根据上一篇文章当中修改的最大正向匹配算法的长度计算我手动计算填写。

下面的代码是基于《[一]漫话中文分词:最大匹配,双向最大,最小词数》文章中的最大正向匹配算法,但其中的词典则是使用Trie结构,改动了两处:

trie = Trie()
trie._add_word('分词')

sentence = '中文分词算法' 
start = 0 
maxWidth = 2 # 改动1:手动填写最大长度
cut_result = [] 

while (start <= len(sentence)): 
    end = start + maxWidth     
    word = sentence[start: end] 
    while ( word ) :  
        if ( trie._get_word(word) ) :  # 改动2:利用Trie的查询函数,该返回查询到为词则返回True,否则False
            cut_result.append(word)
            start = start + len(word) - 1  
            break 
        if (len(word[:-1]) == 0):
            cut_result.append(word) 
            break
        word = word[:-1]  
    start = start + 1  

print(cut_result)
#['中', '文', '分词', '算', '法']

Leave a Reply

Your email address will not be published. Required fields are marked *