Tag Archives: trie

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

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

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

1

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

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

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