中文分词工具jieba分词原理解析
1.原理简介
jieba分词首先基于统计词典， 构造一个前缀词典进行词图扫描，然后利用前缀词典对输入句子进行切分，得到所有的切分可能，根据切分的位置，构造一个有向无环图，最后根据动态规划算法，计算得到最大概率路径，也就得到了最终切分形式。对于未登录词，jieba使用了基于汉字成词的HMM模型，采用了Viterbi算法进行推导。
2.源码分析
小标题的顺序也是求解步骤
（1）前缀词典的构建
以前一直以为jieba分词的前缀词典采用的是Trie树的格式，后来看源码才发现jieba的前缀词典仅仅是字典，据悉是为了减少内存加快速度，优化代码的细节。具体原因可参考jieba的issue。jieba构建前缀词典的入口函数是gen_pfdict(self, f), 其中f表示的是离线统计词典文本文件。下面将给出文本文件的格式及源码：
文件格式：
北京大学 2053 nt
大学 20025 n
去 123402 v
玩 4207 v
北京 34488 ns
北 17860 ns
京 6583 ns
大 144099 a
学 17482 n
源码分析：
def gen_pfdict(self, f):
# 初始化前缀词典
lfreq = {}
ltotal = 0
f_name = resolve_filename(f)
for lineno, line in enumerate(f, 1):
try:
# 解析离线词典文本文件，离线词典文件格式如第2章中所示
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]
# 如果某前缀词不在前缀词典中，则将对应词频设置为0，
# 如第2章中的例子“北京大”
if wfrag not in lfreq:
lfreq[wfrag] = 0
except ValueError:
raise ValueError(
'invalid dictionary entry in %s at Line %s: %s' % (f_name, lineno, line))
f.close()
return lfreq, ltotal
（2）构建有向无环图
jieba中有向无环图的构建函数返回类似如下格式的值，以"去北京大学玩"为例：
0: [0]
1: [1,2,4]
2: [2]
3: [3,4]
4: [4]
5: [5]
很明显，对于0: [0]，表示位置0对应的词，就是0 ~ 0，就是“去”；对于1: [1,2,4]，表示位置1开始，在1，2，4位置都是词，就是1 ~ 1，1 ~ 2，1 ~ 4，即“北”，“北京”，“北京大学”这三个词。对于每一种划分，都将相应的首尾位置相连，例如，对于位置1,可以将它与位置1、位置2、位置4相连接，最终构成一个有向无环图，如下所示，
源码分析：
# 有向无环图构建主函数
def get_DAG(self, sentence):
# 检查系统是否已经初始化
self.check_initialized()
# DAG存储向无环图的数据，数据结构是dict
DAG = {}
N = len(sentence)
# 依次遍历文本中的每个位置
for k in xrange(N):
tmplist = []
i = k
# 位置k形成的片段
frag = sentence[k]
# 判断片段是否在前缀词典中
# 如果片段不在前缀词典中，则跳出本循环
# 也即该片段已经超出统计词典中该词的长度
while i < N and frag in self.FREQ:
# 如果该片段的词频大于0
# 将该片段加入到有向无环图中
# 否则，继续循环
if self.FREQ[frag]:
tmplist.append(i)
# 片段末尾位置加1
i += 1
# 新的片段较旧的片段右边新增一个字
frag = sentence[k:i + 1]
if not tmplist:
tmplist.append(k)
DAG[k] = tmplist
return DAG
(3)最大概率路径计算
我们构建出来的有向无环图DAG的每个节点都是带权的，权重就是它的词频，我们最后要求得的路径r,必然是∑weight(wi) 最大。再结合DAG的特点，很明显我们可以通过状态转移方程来做：
Rmax = max{(Rmaxi,Rmaxj,Rmaxk,...) + weight(Wx)}
具体的算法思路:自底向上的动态规划问题，它从sentence的最后一个字（N-1）开始倒序遍历sentence的每个字（idx）的方式，计算子句sentence[idx ~ N-1]的概率对数得分。然后将概率对数得分最高的情况以（概率对数，词语最后一个位置）这样的元组保存在route中。
def calc(self, sentence, DAG, route):
N = len(sentence)
# 初始化末尾为0
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])
