1. 前言
Jieba是由fxsjy大神开源的一款中文分词工具，一款属于工业界的分词工具——模型易用简单、代码清晰可读，推荐有志学习NLP或Python的读一下源码。与采用分词模型Bigram + HMM 的ICTCLAS 相类似，Jieba采用的是Unigram + HMM。Unigram假设每个词相互独立，则分词组合的联合概率：
在Unigram分词后用HMM做未登录词识别，以修正分词结果。
2. 分解
以下源码分析基于jieba-0.36版本。
分词模式
Jieba支持的三种分词模式：全模式、精确模式、搜索引擎模式。分词函数jieba.cut()中有两个模式调节参数cut_all、HMM，分别表示是否采用全模式（若否，则为精确模式）、是否使用HMM。这两个参数的组合对应于如下分词模式：
cut_all=True, HMM=_对应于全模式，即所有在词典中出现的词都会被切分出来，实现函数为__cut_all；cut_all=False, HMM=False对应于精确模式且不使用HMM；按Unigram语法模型找出联合概率最大的分词组合，实现函数为__cut_DAG；cut_all=False, HMM=True对应于精确模式且使用HMM；在联合概率最大的分词组合的基础上，HMM识别未登录词，实现函数为__cut_DAG_NO_HMM。
另一个分词函数jieba.cut_for_search()对应于搜索引擎模式，对长词进行更细粒度的切分：
def cut_for_search(sentence, HMM=True):
"""
Finer segmentation for search engines.
"""
words = cut(sentence, HMM=HMM)
for w in words:
if len(w) > 2:
for i in xrange(len(w) - 1):
gram2 = w[i:i + 2]
if FREQ.get(gram2):
yield gram2
if len(w) > 3:
for i in xrange(len(w) - 2):
gram3 = w[i:i + 3]
if FREQ.get(gram3):
yield gram3
yield w从上面的代码中，可以看出：对于长度大于2的词，依次循环滚动取出在前缀词典中的二元子词；对于长度大于3的词，依次循环滚动取出在前缀词典中的三元子词。至于前缀词典是什么，且看下一小节。
词典检索
为了检索词典中的词时，一般采取的思路是构建Trie树——利用了字符串的公共前缀，以缩短查询时间。作者当时也是这样做的，用了两个dict，trie dict用于保存trie树，lfreq dict用于存储词 -> 词频：
def gen_trie(f_name):
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
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
except ValueError, e:
logger.debug('%s at line %s %s' % (f_name, lineno, line))
raise ValueError, e
return trie, lfreq, ltotal何不将前缀信息也放到lfreq中呢？Pull request 187中便有人提出来并实现了，还给lfreq取了个好听的名字“前缀字典”。
分词DAG
一个句子所有的分词组合构成了有向无环图（Directed Acyclic Graph, DAG）G=(V,E)，一个词对应与DAG中的的一条边e∈E，边的起点为词的初始字符，边的结点为词的结束字符。jieba.get_DAG()函数实现切分句子得到DAG：
sentence = "印度报业托拉斯"
dag = jieba.get_DAG(sentence)
# {0: [0, 1, 6], 1: [1], 2: [2, 3], 3: [3], 4: [4, 5, 6], 5: [5, 6], 6: [6]}DAG是用dict表示的，key为边的起点，value为边的终点集合，比如：上述例子中4 -> 6表示词“托拉斯”。
求解Unigram模型
对于Unigram模型下的联合概率(1)求对数：
将词频的log值作为图G边的权值，从图论的角度出发，将最大概率问题变成了最大路径问题；是不是与ICTCLAS的处理思路有异曲同工之妙。在上面的DAG中，节点0表示源节点，节点m-1表示尾节点；则V={0,⋯,m−1}，且DAG满足如下性质：
即DAG顶点的序号的顺序与图流向是一致的。Jieba用动态规划（DP）来求解最大路径问题，假设用didi标记源节点到节点i的最大路径的值，则有
其中，w(j,i)表示词cijcji的词频log值，w(i,i)表示字符ci独立成词的词频log值。在求解上述式子时，需要知道所有节点i的前驱节点j；然后DAG中只有后继结点list。在这里，作者巧妙地用到了一个trick——从尾节点m-1往前推算的最优解等价于从源节点0往后推算的。那么，用ri标记节点i到尾节点的最大路径的值，则
def calc(sentence, DAG, route):
N = len(sentence)
route[N] = (0, 0)
logtotal = log(total)
for idx in xrange(N - 1, -1, -1):
# r[i] = max { log P(c_{i}^{x}) + r(x)}
route[idx] = max((log(FREQ.get(sentence[idx:x + 1]) or 1) -
logtotal + route[x + 1][0], x) for x in DAG[idx])关于HMM识别未登录词，可看我之前写的一篇《【中文分词】隐马尔可夫模型HMM》. 至此，Jieba完成了一个非常漂亮实用的分词模型。