jieba分词原理整理_jieba 分段

一 工具简介

jieba 是一个基于Python的中文分词工具：https://github.com/fxsjy/jieba

对于一长段文字，其分词原理大体可分为三部：

1.首先用正则表达式将中文段落粗略的分成一个个句子。

2.将每个句子构造成有向无环图，之后寻找最佳切分方案。

3.最后对于连续的单字，采用HMM模型将其再次划分。

二 模式介绍

jieba分词分为“默认模式”（cut_all=False）,“全模式”(cut_all=True)以及搜索引擎模式（该篇博文未涉及该模式）。对于“默认模式”，又可以选择是否使用 HMM 模型（HMM=True，HMM=False）。下面是一段代码实例：

import jieba
 
seg_list = jieba.cut("单手补扣+8板阿联只是微微一笑，他已赢回主帅信任", cut_all=True)
print("Mode1: " + "/ ".join(seg_list))
 
seg_list = jieba.cut("单手补扣+8板阿联只是微微一笑，他已赢回主帅信任", cut_all=False, HMM=False)
print("Mode2: " + "/ ".join(seg_list))
 
seg_list = jieba.cut("单手补扣+8板阿联只是微微一笑，他已赢回主帅信任", cut_all=False, HMM=True)
print("Mode3: " + "/ ".join(seg_list))

 输出结果为：

Mode1: 单手/ 补/ 扣/ +8/ 板/ 阿联/ 只是/ 微微/ 微微一笑/ / / 他/ 已/ 赢回/ 主帅/ 信任
Mode2: 单手/ 补/ 扣/ +/ 8/ 板/ 阿联/ 只是/ 微微一笑/ ，/ 他/ 已/ 赢回/ 主帅/ 信任
Mode3: 单手/ 补扣/ +/ 8/ 板/ 阿联/ 只是/ 微微一笑/ ，/ 他/ 已/ 赢回/ 主帅/ 信任

首先从总体上看，都是将一个整句划分为了不同的词，但是细看有以下需要注意的地方：

1.全模式下，“微微”出现了两次，这意味着全模式是把所有的可能分词都列举了出来。

2.默认模式下，“+8”被分为了两个词"+"和"8"，这是由于两种模式在分割句子时采用的正则表达式不同，后面会详细说。

3.当采用HMM 模型时，“补扣”被当作是一个词。这是因为“补扣”在词典中不被认为是一个词，因此切分方案将”补”和“扣”分为两个词。采用HMM 模型后，会对连续单字进行检测，将单字”补”和“扣”合为了一个词。

        if cut_all:
            re_han = re_han_cut_all
            re_skip = re_skip_cut_all
        else:
            re_han = re_han_default
            re_skip = re_skip_default
        if cut_all:
            cut_block = self.__cut_all
        elif HMM:
            cut_block = self.__cut_DAG
        else:
            cut_block = self.__cut_DAG_NO_HMM

从上面的代码里可以看到主程序关于各种模式的分支处理。

第一个分支处理是根据模式选取了不同的正则表示式，re_han用来识别汉字，re_skip则是识别其他各种符合。

第二个分支处理是根据模式选取了不同切分方法，cut_block是一个函数指针，后续将通过cut_block去完成实际的切分。

三 正则表达式处理

正则表达式(regular expression)描述了一种字符串匹配的模式（pattern），可以用来检查一个串是否含有某种子串、将匹配的子串替换或者从某个串中取出符合某个条件的子串等。对应到程序里，主要是通过正则表示实现对长段文字的分割。假设现在用正则表达式“[\u4E00-\u9FD5]+”进行分割，\u4E00和\u9FD5这两个unicode值正好是Unicode表中的汉字的头和尾，因此该正则表达式表示任意一个或多个汉字。对应到原来的句子，就是用红色标注的部分：

单手补扣+8板阿联只是微微一笑，他已赢回主帅信任

那么我们将红色的作为单独的一块，剩余的黑色部分也作为一块，最终分割结果过：

['', '单手补扣', '+8', '板阿联只是微微一笑', '，', '他已赢回主帅信任', '']

以上是全模式下的将段落分割成小句的方案。而在默认模式下，正则表达式变为了“[ \u4E00-\u9FD5 a-z A-Z 0-9+#&\._]+”， a-z表示小写字母， A-Z表示大写 0-9字母，表示任意数字，后面黑色部分表示字符‘+’‘#’‘&’‘.’‘_’。全模式下只能识别汉字，而默认模式下还可以识别字母数字符号等等，其对应的分割结果如下。

单手补扣+8板阿联只是微微一笑，他已赢回主帅信任

['', '单手补扣+8板阿联只是微微一笑', '，', '他已赢回主帅信任', '']

四 默认模式

前面提到的原理三大步，第一步分割小句已经完成了，下一步就是根据小句构造有向无环图（DAG）了。假设当前要处理的句子是：“他已赢回主帅信任”，jieba中构造DAG的代码如下：

    def get_DAG(self, sentence):
        self.check_initialized()
        DAG = {}
        N = len(sentence)
        for k in xrange(N): # 遍历block中的每个字符
            tmplist = [] # 用于存储可能词
            i = k # 该字符所在位置
            frag = sentence[k]
            while i < N \
                    and frag in self.FREQ: # 从字符位置开始遍历，直至末尾或字符不在字典内
                if self.FREQ[frag]: # 如果次数大于0，就将该位加入
                    tmplist.append(i)
                i += 1
                frag = sentence[k:i + 1]
            if not tmplist:
                tmplist.append(k)
            DAG[k] = tmplist
        return DAG

上述代码最终得到DAG（return DAG）：{0: [0], 1: [1], 2: [2, 3], 3: [3], 4: [4, 5], 5: [5], 6: [6, 7], 7: [7]}

可以看出该DAG就是一个key-value表，key值是一个坐标，value是一个列表。可以用下面的图形象化表示：

上述get_DAG函数的执行过程，就是沿着橘黄色的箭头遍历每个字符，当遍历到某个字符时，从该字符开始不断往后拓展，如果能成为一个词（通过查看字典），那么就在节点间连一个蓝色的箭头。比如对于“主”（key：2）来说，它自己本身（2-2）可以构成一个词，“主帅”（2-3）也能构成一个词。

有了图以后，我们要找最好的整体划分方案，也就是说“主”和“主帅”之间我们只能选一种，而具体的选择要从整体看，找到一个全局最佳方案，实现代码如下：

    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])

上面的代码是使用route存储最佳分词位置及分数，分数越大越好。使用动态规划计算最好的分词方式， 其实就是从末尾开始遍历，遍历到某个节点时，计算以该节点为起始位置，以最后一个节点为结束位置，这之间那段字符串的最佳分词方案。

当我们得到最佳分词方案后，就可以输出了，代码如下：

    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 # 若是单字先存入buf
            else:
                if buf:
                    if len(buf) == 1:
                        yield buf 
                        buf = ''# 若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

上述代码就是根据得到的分词方案去将每个词输出，只是处理上有些小细节。如果当前要输出的是单字，不会马上输出，而是存入一个buf里，直至下一个词不是单字时，将会对buf内的所有单字组成的句子处理，其实也就是利用HMM识别未登录词。若不采用HMM模式，那么这里不需要对单字进行处理，而是直接输出。

利用HMM识别未登录词需要了解的知识请看这篇：https://blog.csdn.net/liujianfei526/article/details/50640176

最终目标是用{B,M,E,S}为连续的单字字符进行标注，标注完成后就得到了分词方案。

jieba中关于HMM的代码如下：

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])

上述代码就是viterbi算法了，将观测字符存入obs，V是一个二维数组，第一维表示第几个字符，第二维表示第几个状态，数组中存储的值V[pos][status]可以理解为第pos位字符是status状态的概率。

首先对第一个字符单独特殊处理，因为之后都是状态->状态，而第一个是起始->状态。我们需要计算每个状态产生该字符的概率P(字符|状态)，还要计算由起始状态转为每个状态的概率P(状态|起始)，两者相乘既得到V(字符，状态)=P(状态|起始)*P(字符|状态)。

之后就是遍历剩余的字符，处理每个位置字符时，从所有可能的前置状态中找一个使V(上个字符，前置状态)*P(状态|前置状态)*P(字符|状态)最大，并将该最大值作为V(字符，状态)。同时用path记录一个序列，每次把新确定的状态放到末尾。计算完最后一个字符后，我们去找以E或S结尾且概率最大的状态序列。

五 全模式

    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

上述代码就是全模式下的算法，与默认模式的区别在于需要将所有的分词都输出。所以可以不必去理最佳分词方案，而是把所有的分词都输出。即从头开始遍历DAG，在每次遍历时都得到一个（k，L），其中k代表每个字符，L是一个列表，里面存储了一些坐标，从k位到L中的每个坐标可以构成一个词，所以每次遍历时，就把这些词都输出。唯一需要注意的是通过old_j防止重复输出。