专栏首页胖胖的专栏使用 trie 树实现简单的中文分词
原创

使用 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 作为开发语言,在 Linux 或 Ma...

    胖兔子兔胖
  • Android Jetpack - Room

    Room 持久化库提供了一个基于 SQLite 的抽象层,以便在利用 SQLite 的全部功能的同时实现更强大的数据库访问

    SkyRiN
  • Jquery validate remote 验证数据唯一

    Zero_xxl
  • Bytes 陷阱, Redis 数据类型的一个小坑

    在Python 3环境下,当我们把一个字符串写进 Redis 再读出来,会发现这个字符串变成了 bytes型的数据:

    青南
  • AutoLink用户指南

    AutoLink采用 Apache License 2.0 国际许可协议 进行许可. 传播此文档时请注意遵循以上许可协议. 关于本许可证的更多详情可参考 htt...

    苦叶子
  • [Leetcode][python]Text Justification/文本左右对齐

    来自:https://shenjie1993.gitbooks.io/leetcode-python/068%20Text%20Justification.ht...

    后端技术漫谈
  • 文本挖掘和情感分析的基础示例

    经过研究表明,在旅行者的决策过程中,TripAdvisor(猫途鹰,全球旅游点评网)正变得越来越重要。然而,了解TripAdvisor评分与数千个评论文本中的每...

    AiTechYun
  • 6个应当了解的Java比特币开源项目 原

    比特币是第一种被广泛认可并获得众多支持的数字加密货币,如果你考虑在自己的Java系统中增加对比特币的支持,那么相信下面这6个使用Java开发的比特币开源项目会对...

    用户1408045
  • 技术视角的比特币骗局

    比特币目前现价约13000美元,根据比特币算法,最终将会产生2100万个比特币,整个比特币的市值在2730亿美元,约1.8万亿人民币。 那么比特币到底是什么?为...

    企鹅号小编
  • springboot quartz定时任务调度

    在我们添加spring-boot-starter-quartz依赖后就不需要主动声明工厂类,因为spring-boot-starter-quartz已经为我们自...

    开发架构二三事

扫码关注云+社区

领取腾讯云代金券