使用 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 树变种来解决,有兴趣可以自行尝试。

附件:

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程之旅

Python——搞定烦人的字符串编码

在学习Python之前,就听说过Python的版本圣战,最可怕的是有的写Py3的程序员觉得Py2是另一种语言....所以在刚开始学习的时候,我索性把Python...

10730
来自专栏java架构师

重构学习笔记

这里仅仅是做了个总结,相当于速查手册。 1、对集合封装 集合,比如List<XXX> ,如果做为返回值,那也就把其自身所拥有的Add,Remove等方法暴漏了...

321110
来自专栏青玉伏案

代码重构(一):函数重构规则

重构是项目做到一定程度后必然要做的事情。代码重构,可以改善既有的代码设计,增强既有工程的可扩充、可维护性。随着项目需求的不断迭代,需求的不断更新,我们在项目中所...

26550
来自专栏高性能服务器开发

API设计原则 – QT官网的设计实践总结

原文链接:API Design Principles – Qt Wiki 链接:(http://wiki.qt.io/API_Design_Principles...

33420
来自专栏抠抠空间

python常见模块之time模块

一、模块简介 在Python中,通常有这几种方式来表示时间: 时间戳(timestamp):通常来说,时间戳表示的是从1970年1月1日00:00:00开始按...

34670
来自专栏阮一峰的网络日志

12种不宜使用的Javascript语法

这几天,我在读《Javascript语言精粹》。 这本书很薄,100多页,正好假日里翻翻。 该书的作者是Douglas Crockford,他是目前世界上最精通...

34880
来自专栏aCloudDeveloper

python学习总结

最近经学长介绍学习python,为研究生做研究做准备,python对于科学计算有着很高的效率,对于科研人员当然是有着很强的诱惑,虽然我还没真正用它,但从整个学习...

31150
来自专栏owent

C++总是很神奇

很多时候看到C/C++的一些奇妙的应用,每次都是惊奇一点时间就随风飘过了 现在我还是决定记录一下这些有意思的东西。

10720
来自专栏Web行业观察

从JSON进化到BSON

自从MEAN引导的JSON数据格式取代传统JAVA推崇的XML以后, json的发展却停滞不前了, 当然这是好事, 因为稳定的结构是不需要向下兼...

41640
来自专栏Kotlin源码阅读

Kotlin源码阅读——Math

NaN其实在JVM上的语言,并不像JS一样,要特别地学习一下,但是NaN这个逻辑也确实存在。代码跟进去:

40340

扫码关注云+社区

领取腾讯云代金券