基于三叉Trie树的中文分词 - wyz1989/Segment GitHub Wiki
1.前言
中文分词是自然语言处理基本技术， 一种简单的分词方法是基于词典的分词方法。本文介绍一种基于三叉Trie树（三叉搜索树）的中文分词方法。算法首先针对词典构造一棵三叉搜索树， 其次利用正向最大匹配原理，通过查找三叉搜索树对中文文本进行切分。
2.三叉搜索树
2.1 三叉搜索概念
三叉搜索树为标准Trie树（前缀树）和二叉搜索树的混合体， 它有和标准Trie树差不多的查找速度，但是和二叉搜索树一样只需要相对较小的内存空间。如下图所示：
上图为有序词典（as at be by he in is it of on or to），经过平衡化处理后构造出来的三叉搜索树，具体构造方法见下节"三叉搜索树构造"
2.3 三叉搜索树构造
平衡化
三叉搜索树查找效率和树的高度相关，词典输入顺序不同会得到完全不一样的搜索树，因此构造树的时候应该尽量使得树平衡。下面代码片段通过对词典进行排序和输入顺序调整， 来达到使得构造出来的三叉搜索树平衡的目的。
def outputBalancedDict(outputDict, sort_dict, offset, length):
if length < 1:
return
mid = length / 2
outputDict.append(sort_dict[mid + offset])
outputBalancedDict(outputDict, sort_dict, offset, mid)
outputBalancedDict(outputDict, sort_dict, offset + mid + 1, length - mid -1)
def sortDict(rawDict):
"""
中文排序
"""
import locale
return sorted(rawDict, cmp=locale.strcoll)
树的构造 下面代码片段完成了三叉搜索树构造。TSNode表示的是节点类， TernarySearchTrie为三叉搜索树类， 该类包含两个方法：getNode方法为查询word方法, addWord为将某个词典添加到搜索树中去的方法。
class TSNode(object):
def __init__(self, splitchar):
#左边、中间和右边节点
self.loNode = None
self.eqNode = None
self.hiNode = None
#保存的字符
self.splitchar = splitchar
#终止节点保存word
self.nodeValue = ""
def toString(self):
return self.splitchar
class TernarySearchTrie(object):
def __init__(self, root):
self.root = root
def getNode(self, key, startNode):
"""
查找词key
"""
if key == "" or key is None:
return None
length = len(key)
if length == 0:
return None
currentNode = startNode
charIndex = 0
cmpChar = key[charIndex]
cmpRes = -1
while 1:
if currentNode is None:
return None
cmpRes = cmp(cmpChar, currentNode.splitchar)
if cmpRes == 0:
####两个字符相等
charIndex += 1
if charIndex == length:
return currentNode
else:
cmpChar = key[charIndex]
currentNode = currentNode.eqNode
elif cmpRes < 0:
currentNode = currentNode.loNode
else:
currentNode = currentNode.hiNode
def addWord(self, key):
currentNode = self.root
charIndex = 0
cmpRes = -1
while 1:
cmpRes = cmp(key[charIndex], currentNode.splitchar)
if cmpRes == 0:
charIndex += 1
if charIndex == len(key):
return currentNode
if currentNode.eqNode is None:
currentNode.eqNode = TSNode(key[charIndex])
currentNode = currentNode.eqNode
elif cmpRes < 0:
if currentNode.loNode is None:
currentNode.loNode = TSNode(key[charIndex])
currentNode = currentNode.loNode
else:
if currentNode.hiNode is None:
currentNode.hiNode = TSNode(key[charIndex])
currentNode = currentNode.hiNode
3.中文切词
构造好三叉搜索树后我们就可以用搜索树进行中文切词。 切词的思想是通过正向最大长度匹配法，每次从三叉搜索树中查询出最长的匹配作为切词结果， 实现代码如下所示：
class Segment(object):
def __init__(self, root, text):
self.tst = root
##当前切分位置
self.offset = 0
self.text = text
def splitWordWithMaxMatch(self):
"""
搜索三叉树并每次返回最长匹配串
"""
word = ""
if self.text == "" or self.tst is None:
return word
if self.offset >= len(self.text):
return word
charIndex = self.offset
currentNode = self.tst
while 1:
if currentNode is None:
if word == "":
word = self.text[self.offset+1]
self.offset += 1
return word
cmpRes = cmp(self.text[charIndex], currentNode.splitchar)
if cmpRes == 0:
charIndex += 1
if currentNode.nodeValue != "":
word = currentNode.nodeValue
self.offset = charIndex
if charIndex == len(self.text):
return word
currentNode = currentNode.eqNode
elif cmpRes < 0:
currentNode = currentNode.loNode
else:
currentNode = currentNode.hiNode
4. 实验
输入：
[u"大", u"大学", u"大学生", u"活动", u"生活", u"中", u"中心", u"心"]
通过对输入进行排序，平衡化后构造出的三叉搜索树：
大
/ | \
中 学 活
| | / | \
心 生 心 动 生
|
活
切词输入： u"大学生活动中心" 切词结果： 大学生/活动/中心/