【开源中文分词工具探析】系列&＃xff1a;

1. 开源中文分词工具探析&＃xff08;一&＃xff09;&＃xff1a;ICTCLAS (NLPIR)
2. 开源中文分词工具探析&＃xff08;二&＃xff09;&＃xff1a;Jieba
3. 开源中文分词工具探析&＃xff08;三&＃xff09;&＃xff1a;Ansj
4. 开源中文分词工具探析&＃xff08;四&＃xff09;&＃xff1a;THULAC
5. 开源中文分词工具探析&＃xff08;五&＃xff09;&＃xff1a;FNLP
6. 开源中文分词工具探析&＃xff08;六&＃xff09;&＃xff1a;Stanford CoreNLP
7. 开源中文分词工具探析&＃xff08;七&＃xff09;&＃xff1a;LTP

1. 前言

Jieba是由fxsjy大神开源的一款中文分词工具&＃xff0c;一款属于工业界的分词工具——模型易用简单、代码清晰可读&＃xff0c;推荐有志学习NLP或Python的读一下源码。与采用分词模型Bigram &＃43; HMM 的ICTCLAS 相类似&＃xff0c;Jieba采用的是Unigram &＃43; HMM。Unigram假设每个词相互独立&＃xff0c;则分词组合的联合概率&＃xff1a;

\begin{equation}
P(c_1^n) &＃61; P(w_1^m) &＃61; \prod_i P(w_{i})
\label{eq:unigram}
\end{equation}

在Unigram分词后用HMM做未登录词识别&＃xff0c;以修正分词结果。

2. 分解

以下源码分析基于jieba-0.36版本。

分词模式

Jieba支持的三种分词模式&＃xff1a;全模式、精确模式、搜索引擎模式。分词函数jieba.cut()中有两个模式调节参数cut_all、HMM&＃xff0c;分别表示是否采用全模式&＃xff08;若否&＃xff0c;则为精确模式&＃xff09;、是否使用HMM。这两个参数的组合对应于如下分词模式&＃xff1a;

• cut_all&＃61;True, HMM&＃61;_对应于全模式&＃xff0c;即所有在词典中出现的词都会被切分出来&＃xff0c;实现函数为__cut_all&＃xff1b;
• cut_all&＃61;False, HMM&＃61;False对应于精确模式且不使用HMM&＃xff1b;按Unigram语法模型找出联合概率最大的分词组合&＃xff0c;实现函数为__cut_DAG&＃xff1b;
• cut_all&＃61;False, HMM&＃61;True对应于精确模式且使用HMM&＃xff1b;在联合概率最大的分词组合的基础上&＃xff0c;HMM识别未登录词&＃xff0c;实现函数为__cut_DAG_NO_HMM。

另一个分词函数jieba.cut_for_search()对应于搜索引擎模式&＃xff0c;对长词进行更细粒度的切分&＃xff1a;

def cut_for_search(sentence, HMM&＃61;True):"""Finer segmentation for search engines."""words &＃61; cut(sentence, HMM&＃61;HMM)for w in words:if len(w) > 2:for i in xrange(len(w) - 1):gram2 &＃61; w[i:i &＃43; 2]if FREQ.get(gram2):yield gram2if len(w) > 3:for i in xrange(len(w) - 2):gram3 &＃61; w[i:i &＃43; 3]if FREQ.get(gram3):yield gram3yield w

从上面的代码中&＃xff0c;可以看出&＃xff1a;对于长度大于2的词&＃xff0c;依次循环滚动取出在前缀词典中的二元子词&＃xff1b;对于长度大于3的词&＃xff0c;依次循环滚动取出在前缀词典中的三元子词。至于前缀词典是什么&＃xff0c;且看下一小节。

词典检索

为了检索词典中的词时&＃xff0c;一般采取的思路是构建Trie树——利用了字符串的公共前缀&＃xff0c;以缩短查询时间。作者当时也是这样做的&＃xff0c;用了两个dict&＃xff0c;trie dict用于保存trie树&＃xff0c;lfreq dict用于存储词 -> 词频&＃xff1a;

def gen_trie(f_name): lfreq &＃61; {} trie &＃61; {} ltotal &＃61; 0.0 with open(f_name, &＃39;rb&＃39;) as f: lineno &＃61; 0 for line in f.read().rstrip().decode(&＃39;utf-8&＃39;).split(&＃39;\n&＃39;): lineno &＃43;&＃61; 1 try: word,freq,_ &＃61; line.split(&＃39; &＃39;) freq &＃61; float(freq) lfreq[word] &＃61; freq ltotal&＃43;&＃61;freq p &＃61; trie for c in word: if c not in p: p[c] &＃61;{} p &＃61; p[c] p[&＃39;&＃39;]&＃61;&＃39;&＃39; #ending flag except ValueError, e: logger.debug(&＃39;%s at line %s %s&＃39; % (f_name, lineno, line)) raise ValueError, e return trie, lfreq, ltotal

何不将前缀信息也放到lfreq中呢&＃xff1f;Pull request 187中便有人提出来并实现了&＃xff0c;还给lfreq取了个好听的名字“前缀字典”。

分词DAG

一个句子所有的分词组合构成了有向无环图&＃xff08;Directed Acyclic Graph, DAG&＃xff09;\(G&＃61;(V,E)\)&＃xff0c;一个词对应与DAG中的的一条边\(e \in E\)&＃xff0c;边的起点为词的初始字符&＃xff0c;边的结点为词的结束字符。jieba.get_DAG()函数实现切分句子得到DAG&＃xff1a;

sentence &＃61; "印度报业托拉斯"
dag &＃61; 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表示的&＃xff0c;key为边的起点&＃xff0c;value为边的终点集合&＃xff0c;比如&＃xff1a;上述例子中4 -> 6表示词“托拉斯”。

求解Unigram模型

对于Unigram模型下的联合概率\eqref{eq:unigram}求对数&＃xff1a;

\[ \begin{aligned} \arg \max \prod_i P(w_i) & &＃61; \arg \max \log \prod_i P(w_i)\\ & &＃61; \arg \max \sum_i \log P(w_i) \end{aligned} \]

将词频的log值作为图\(G\)边的权值&＃xff0c;从图论的角度出发&＃xff0c;将最大概率问题变成了最大路径问题&＃xff1b;是不是与ICTCLAS的处理思路有异曲同工之妙。在上面的DAG中&＃xff0c;节点0表示源节点&＃xff0c;节点m-1表示尾节点&＃xff1b;则\(V&＃61;\{0, \cdots , m-1 \}\)&＃xff0c;且DAG满足如下性质&＃xff1a;

\[ v > u, \quad \forall \ (u,v) \in E \]

即DAG顶点的序号的顺序与图流向是一致的。Jieba用动态规划&＃xff08;DP&＃xff09;来求解最大路径问题&＃xff0c;假设用\(d_i\)标记源节点到节点i的最大路径的值&＃xff0c;则有

\[ d_i &＃61; \max_{(j,i) \in E} \ \{ d_j&＃43;w(j,i) \} \]

其中&＃xff0c;\(w(j,i)\)表示词\(c_j^i\)的词频log值&＃xff0c;\(w(i,i)\)表示字符\(c_i\)独立成词的词频log值。在求解上述式子时&＃xff0c;需要知道所有节点i的前驱节点j&＃xff1b;然后DAG中只有后继结点list。在这里&＃xff0c;作者巧妙地用到了一个trick——从尾节点m-1往前推算的最优解等价于从源节点0往后推算的。那么&＃xff0c;用\(r_i\)标记节点i到尾节点的最大路径的值&＃xff0c;则

\[ r_i &＃61; \max_{(i,j) \in E} \ \{ r_j&＃43;w(i,j) \} \]

def calc(sentence, DAG, route):N &＃61; len(sentence)route[N] &＃61; (0, 0)logtotal &＃61; log(total)for idx in xrange(N - 1, -1, -1):# r[i] &＃61; max { log P(c_{i}^{x}) &＃43; r(x)}route[idx] &＃61; max((log(FREQ.get(sentence[idx:x &＃43; 1]) or 1) -logtotal &＃43; route[x &＃43; 1][0], x) for x in DAG[idx])

关于HMM识别未登录词&＃xff0c;可看我之前写的一篇《【中文分词】隐马尔可夫模型HMM》. 至此&＃xff0c;Jieba完成了一个非常漂亮实用的分词模型。