本文主要是自己在阅读jieba源码的理解做一下分词算法的总结，分为工程和算法两部分进行。
算法
现在的中文分词以规则+统计为主要实现方式。所以大致分为：1、词典的存储方式。2、query表达。3、译码。4、对于单字序列用HMM发现新词。
- 词典的存储方式
- trier树
lfreq = {}
trie = {}
ltotal = 0.0
with open(f_name, 'rb') as f:
lineno = 0
for line in f.read().rstrip().decode('utf-8').split('\n'):
lineno += 1
print "lineno: ", lineno
print len(trie)
try:
word,freq,_ = line.split(' ')
freq = float(freq)
lfreq[word] = freq
ltotal+=freq
p = trie
for c in word:
if c not in p:
p[c] ={}
p = p[c]
p['']='' #ending flag
- 前缀数组
lfreq = {}
ltotal = 0
f_name = resolve_filename(f)
for lineno, line in enumerate(f, 1):
try:
line = line.strip().decode('utf-8')
word, freq = line.split(' ')[:2]
freq = int(freq)
lfreq[word] = freq
ltotal += freq
for ch in xrange(len(word)):
wfrag = word[:ch + 1]
if wfrag not in lfreq:
lfreq[wfrag] = 0
翻看结巴的发布历史，发现最开始用的trier树的方式，现在采用的是前缀数组的方式进行存储。这儿加一段自己的理解，为什么后来用前缀数组来表示，因为字典树的优势在于其查找的速度上，其复杂度为o（n）（n为query的长度，和树的深度没有关系）。但是python的dict是散列表实现其查找复杂度为O(1),trier树的优势不再存在，但是c++等语言中字典是红黑树实现的，其优势还是比较明显。而前缀数组相较于tier树不用保存单词间的依赖关系，因为其速度和所占用的内存上回更有优势。
- query表达
一般是将输入query转换成有向无环图
这一步的主要作用是将query根据第一步加载的词典生成有向无环图，有向无环图大概长这样：
DAG
0 [0]
1 [1]
2 [2, 4]
3 [3, 4]
4 [4]
5 [5]
6 [6]
7 [7]
8 [8]
即表示的是每一个输入query的token序列的所有成词的方式，后面的译码算法会根据这个图进行译码。常见的译码算法包括最大正向匹配算法，最大概率译码方式。jieba采用的最大概率译码。注意在表示
- 译码
根据query的有向无环图，这儿介绍最大概率译码和最大正向匹配译码
最大正向匹配算法
dag = self.get_DAG(sentence)
old_j = -1
for k, L in iteritems(dag):
if len(L) == 1 and k > old_j:
yield sentence[k:L[0] + 1]
old_j = L[0]
else:
if len(L) > 1 and k > old_j:
yield sentence[k:L[-1] + 1]
old_j = L[-1]
最大概率
def calc(self, sentence, DAG, route):
N = len(sentence)
route[N] = (0, 0)
logtotal = log(self.total)
for idx in xrange(N - 1, -1, -1):
route[idx] = max((log(self.FREQ.get(sentence[idx:x + 1]) or 1) -
logtotal + route[x + 1][0], x) for x in DAG[idx])
- HMM发现新词
对于译码出的单字序列使用HMM发现新词。HMM的原理和代码详见我的github：
HMM介绍及code实现
