使用 trie 树实现简单的中文分词
原创
导语：工作中偶尔遇到需要对中文进行分词的情况，不要求非常高的精确度和语境符合度，仅是为了统计某些词出现的热度。本文提供了一种简单易行的中文分词方法。
工作中，偶尔会遇到需要进行中文分词统计的情况，但是并不需要做到高精度时，我们可以使用 trie 树，也就是 前缀树 来实现这个功能。
trie 树，可以叫前缀树，有时也称字典树，是字符串算法中比较常用的一种结构。关于 trie 树的概念及其扩展的其他更高效的数据结构，自行百度，这里不再占篇幅。
如果使用 trie 树来实现英文单词的查找，那么最终形成的结构，如下图所示(来自百度)：
同样，如果我们要实现中文的分词，也是同样的原理，将词库中出现的字，依次形成如上图查询树的方式，下边附上 Python 实现的代码和搜集的词库，以供大家直接 复制粘贴使用。
中文字符串切割：
#*******************************************************************************
# 函数名称: Logic_split_to_char, Logic_split_to_char_ex
# 功能描述: 将字符串切分为一个个的字符, 汉字为一个字符
# 输入参数: 待切割的字符串, 支持 GB18030 编码
# 输出参数:
# 返回值 : 字符列表
# 其他说明:
# 作 者: Logiczhang
# 创建日期: 2017-03-05 19:36
#*******************************************************************************
#对于标准 gb18030 编码可用
def Logic_split_to_char( txt ):
ret = []
for char in txt.decode( "gb18030" ):
ret.append( char.encode("gb18030") )
return ret
#对于可能混杂有 gb18030 编码无法解析的字符的字符串可用
def Logic_split_to_char_ex( txt ):
ret = []
end_pos = len( txt )
pos = 0
while pos < end_pos:
#ascii 字符
if ord(txt[pos]) < 0x80:
ret.append( txt[pos] )
pos = 1
else:
if pos 1 < end_pos:
ret.append(txt[pos] txt[pos 1])
pos = 2
return ret中文分词包装的类，加了详尽的注释，方便理解，文件用到的汉语词库、停用词库都是网络搜集，可在附件中下载，另外需用到上文的拆字接口。
# coding=gb18030
import string
from collections import Counter
class Logic_NLP:
trie_tree = {}
# 初始化: 根据词库建立 trie 树, 需要配合词库文件
def __init__( self, word_lib_filename = "../config/ChineseWordsLib.txt", unused_word_filename = "../config/ChineseUselessWordsLib.txt" ):
ifp = open( word_lib_filename )
word_list = sorted( ifp.readlines() )
ifp.close()
for word in word_list:
cn_chars = Logic_split_to_char_ex( word )
if len(cn_chars) <= 1:
print "Error for word:%s"%word
continue
ref = self.trie_tree
for cn_char in cn_chars:
ref[ cn_char ] = ref.has_key( cn_char ) and ref[ cn_char ] or {}
ref = ref[ cn_char ]
ref[ 'end' ] = True
# 保存停用词
self.unused_word_list = []
for word in file( unused_word_filename ):
self.unused_word_list.append( string.strip(word) )
# 分词函数, 不去停用词
def split_to_words(self, content ):
cn_chars = Logic_split_to_char_ex( content )
word_list = []
while len( cn_chars ) > 0:
word_tree = self.trie_tree
current_word = "" # 当前词
index = 0
cn_char = ""
for (index, cn_char) in enumerate(cn_chars):
current_word = cn_char
if word_tree.has_key( cn_char ):
# 词结束
if word_tree[ cn_char ].has_key( 'end' ):
word_list.append( current_word ) # 保存当前词
break # 结束本次搜索
# 词未结束
else:
word_tree = word_tree[ cn_char ] # 继续深搜
# 没有这个字开头的词, 或者这个字与前一个字不能组成词
else:
if len( current_word ) > len( cn_char ):
current_word = current_word[:0-len(cn_char)]
word_list.append( current_word ) # 保存当前的字
break
# 遍历完毕未被 break, 则剩余的部分被当作一个词
else:
word_list.append( current_word )
break
# 第一个字退出, 表示没有以第一个字开头的词
if index == 0:
cn_chars = cn_chars[1:]
continue
# 如果不是第一个字, 且因为词语不包含这个字而中断, 则以这个字作为第一个字再搜索一次
if not word_tree.has_key( cn_char ):
cn_chars = cn_chars[ index: ]
continue
# 如果不是因为上述原因, 则从下一个字符开始搜索
if index 1 < len( cn_chars ):
cn_chars = cn_chars[index 1:]
continue
return word_list
# 分词函数，去除停用词和单字
def split_to_words_ex( self, content ):
word_list = self.split_to_words( content )
ret_list = []
for word in word_list:
if len( word ) >= 2 and word not in self.unused_word_list:
ret_list.append( word )
return ret_list
# 返回指定内容内的热词，count 为只取前多少个词，-1 表示全部，默认为 10
def hot_words(self, content, count=10 ):
print "IN hotwords"
word_list = self.split_to_words_ex( content )
print word_list
if count == -1:
sort_words = Counter( word_list ).most_common( len( word_list) )
else:
sort_words = Counter( word_list ).most_common( count )
sort_words = sorted( sort_words, key=lambda a:a[1], reverse=True )
print sort_words
return sort_words[:count]如果需要对 UTF-8 编码进行支持，只需要对词库编码进行转换，对 拆字接口进行适配即可。
再次说明的是，本文的方法只能用以简单的分词，其中查找的规则为最长词匹配，类似于 "中华人民共和国" 这种王者级词语，若词库中有 "中华人民共和国"，同时又有"中华""人民""共和国"，那么只会匹配到 "中华人民共和国"，需要最短词匹配的话，可以在代码中更改。
另外，对 trie 树有了解的同学，以及对空间比较敏感的同学一定会发现，这种存储的方式，是比较浪费空间的，就比如文初的英文字典树结构图，每个字母 a 都存储了很多份，针对该问题，已经有比较多的 trie 树变种来解决，有兴趣可以自行尝试。
附件：
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。