jieba是一个开源的中文分词库，这几天看了下源码，就做下记录。
下载jieba后，tree得到主要部分的目录树结构如下：
├── jieba │ ├── analyse │ │ ├── analyzer.py │ │ ├── idf.txt │ │ ├── __init__.py │ │ ├── textrank.py │ │ └── tfidf.py │ ├── _compat.py │ ├── dict.txt │ ├── finalseg │ │ ├── __init__.py │ │ ├── prob_emit.p │ │ ├── prob_emit.py │ │ ├── prob_start.p │ │ ├── prob_start.py │ │ ├── prob_trans.p │ │ └── prob_trans.py │ ├── __init__.py │ ├── __main__.py │ └── posseg │ ├── char_state_tab.p │ ├── char_state_tab.py │ ├── __init__.py │ ├── prob_emit.p │ ├── prob_emit.py │ ├── prob_start.p │ ├── prob_start.py │ ├── prob_trans.p │ ├── prob_trans.py │ └── viterbi.py ├── LICENSE ├── MANIFEST.in ├── README.md ├── setup.py └── test analyse目录下是几个提取文本关键词的算法实现。dict.txt是总的词库，每行记录了一个词和这个词的词频及词性。
__init__.py是jieba的主要入口
finalseg是如果使用hmm，那么在初步分词之后还要调用这里的代码，主要是对hmm的实现。
然后介绍下主要接口__init__.py中的几个函数：
def gen_pfdict(self, f): 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 except ValueError: raise ValueError( 'invalid dictionary entry in %s at Line %s: %s' % (f_name, lineno, line)) f.close() return lfreq, ltotal gen_pfdict加载dict.txt生成字典树，lfreq存储dict.txt每个词出现了多少次，以及每个词的所有前缀，前缀的频数置为0，ltotal是所有词出现的总次数。得到的字典树存在self.FREQ中。例如对于词"不拘一格"，在字典树lfreq中是这样的{"不" : 0, "不拘" : ,"不拘一" , 0, "不拘一格" : freq} 其中的freq就是在dict.txt中记录的词频。
def get_DAG(self, sentence): self.check_initialized() DAG = {} N = len(sentence) for k in xrange(N): tmplist = [] i = k frag = sentence[k] while i < N and frag in self.FREQ: if self.FREQ[frag]: tmplist.append(i) i += 1 frag = sentence[k:i + 1] if not tmplist: tmplist.append(k) DAG[k] = tmplist return DAG FREQ是根据dict.txt生成的字典树，get_DAG函数是根据FREQ对于每个句子sentence生成一个有向无环图，图信息存在字典DAG中，其中DAG[pos]是一个列表[a, b, c...]，pos从0到len(sentence) - 1，表示sentence[pos : a + 1],sentence[pos, b + 1]...这些单词出现在了dict中。
例如以“但也并不是那么出乎意料或难以置信”这句话作为输入，生成的DAG如下，简单的讲就是把句子中词的位置标记出来 0 [0] 但 1 [1] 也 2 [2] 并 3 [3, 4] 不是 4 [4] 是 5 [5, 6] 那么 6 [6] 么 7 [7, 8, 10] 出乎意料 8 [8] 乎 9 [9, 10] 意料 10 [10] 料 11 [11] 或 12 [12, 13, 15] 难以置信 13 [13] 以 14 [14, 15] 置信 15 [15] 信
接下来就是对句子的切分，即jieba.cut。具体的分词流程概括起来如下: 1. 给定待分词的句子, 使用正则(re_han)获取匹配的中文字符(和英文字符)切分成的短语列表； 2. 利用get_DAG(sentence)函数获得待切分句子的DAG，首先检测(check_initialized)进程是否已经加载词库，若未初始化词库则调用initialize函数进行初始化，initialize中判断有无已经缓存的前缀词典cache_file文件，若有相应的cache文件则直接使用 marshal.load 方法加载前缀词典，若无则通过gen_pfdict对指定的词库dict.txt进行计算生成前缀词典，到jieba进程的初始化工作完成后就调用get_DAG获得句子的DAG； 3. 根据cut_block指定具体的方法(__cut_all,__cut_DAG,__cut_DAG_NO_HMM)对每个短语使用DAG进行分词 ，如cut_block=__cut_DAG时则使用DAG(查字典)和动态规划, 得到最大概率路径, 对DAG中那些没有在字典中查到的字, 组合成一个新的片段短语, 使用HMM模型进行分词, 也就是作者说的识别新词, 即识别字典外的新词； 4. 使用python的yield 语法生成一个词语生成器, 逐词语返回；
def __cut_all(self, sentence): 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: for j in L: if j > k: yield sentence[k:j + 1] old_j = j__cut_all是全模式切分，其实就是把DAG中的所有组合显示出来。对于上个句子得到的结果如下：但/也/并/不是/那么/出乎/出乎意料/意料/或/难以/难以置信/置信
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])calc函数根据出现的概率来计算最可能的切词结果，其中单词A的概率为A的出现次数除以所有单词出现的总次数。通过dp计算最大概率的切词方式，route[i][0]表示sentence[i : len]的最大概率，route[i][1]表示sentence[i : len]这个子串的第一个切分位置在哪。
def __cut_DAG_NO_HMM(self, sentence): DAG = self.get_DAG(sentence) route = {} self.calc(sentence, DAG, route) x = 0 N = len(sentence) buf = '' while x < N: y = route[x][1] + 1 l_word = sentence[x:y] if re_eng.match(l_word) and len(l_word) == 1: buf += l_word x = y else: if buf: yield buf buf = '' yield l_word x = y if buf: yield buf buf = '' __cut_DAG_NO_HMM是不使用hmm的精确模式，首先调用calc，得到的route[i][1]中保存的是切分的位置信息，然后遍历输出切分方式。
def __cut_DAG(self, sentence): DAG = self.get_DAG(sentence) route = {} self.calc(sentence, DAG, route) x = 0 buf = '' N = len(sentence) while x < N: y = route[x][1] + 1 l_word = sentence[x:y] if y - x == 1: buf += l_word else: if buf: if len(buf) == 1: yield buf buf = '' else: if not self.FREQ.get(buf): recognized = finalseg.cut(buf) for t in recognized: yield t else: for elem in buf: yield elem buf = '' yield l_word x = y if buf: if len(buf) == 1: yield buf elif not self.FREQ.get(buf): recognized = finalseg.cut(buf) for t in recognized: yield t else: for elem in buf: yield elem __cut_DAG同时使用最大概率路径和hmm，对于利用动态规划计算出的最大概率切分后，用buf将连续的单字收集以及未登录词收集起来，再调用finalseg.cut利用hmm进行分词。
然后是final_seg的__init__.py
def viterbi(obs, states, start_p, trans_p, emit_p): V = [{}] # tabular path = {} for y in states: # init V[0][y] = start_p[y] + emit_p[y].get(obs[0], MIN_FLOAT) path[y] = [y] for t in xrange(1, len(obs)): V.append({}) newpath = {} for y in states: em_p = emit_p[y].get(obs[t], MIN_FLOAT) (prob, state) = max( [(V[t - 1][y0] + trans_p[y0].get(y, MIN_FLOAT) + em_p, y0) for y0 in PrevStatus[y]]) V[t][y] = prob newpath[y] = path[state] + [y] path = newpath (prob, state) = max((V[len(obs) - 1][y], y) for y in 'ES') return (prob, path[state])HMM中的viterbi算法的实现函数，是viterbi算法给定了模型参数和观察序列之后求隐藏状态序列，其中对于分词，观察序列就是句子本身，而隐藏序列就是一个由{B, M, E, S}组成的序列，B表示词的开始，M表示词的中间，E表示词的结尾，S表示单字成词。 函数的输入参数中obs是输入的观察序列，即句子本身，states表示隐藏状态的集合，即{B, M, E, S}，start_p表示第一个字分别处于{B, M, E, S}这几个隐藏状态的概率，trans_p是状态转移矩阵，记录了隐藏状态之间的转化概率，例如trans_p[‘B’][‘E’]代表的含义就是从状态B转移到状态E的概率，emit_p是发射概率矩阵，表示从一个隐藏状态转移到一个观察状态的概率，例如P[‘B’][‘\u4e00’]代表的含义就是’B’状态下观测的字为’\u4e00’(对应的汉字为’一’)的概率大小。 V是一个列表，V[i][j]表示对于子观察序列obs[0 ~ i]，在第i个位置时隐藏状态为j的最大概率，其实就是个简单dp。 path是记录了状态转移的路径。
def __cut(sentence): global emit_P prob, pos_list = viterbi(sentence, 'BMES', start_P, trans_P, emit_P) begin, nexti = 0, 0 # print pos_list, sentence for i, char in enumerate(sentence): pos = pos_list[i] if pos == 'B': begin = i elif pos == 'E': yield sentence[begin:i + 1] nexti = i + 1 elif pos == 'S': yield char nexti = i + 1 if nexti < len(sentence): yield sentence[nexti:]通过调用viterbi算法得到概率和path之后，对sentence进行分词。
参考：
http://www.cnblogs.com/lrysjtu/p/4529325.html
http://blog.csdn.net/daniel_ustc/article/details/48195287
