分词-Jieba分词DAG方法

前言

分词是自然语言处理中最基础的任务之一，也是必须掌握的算法之一。

虽然在深度网络中，分词起到的作用越来越小（有研究表明深度网络中“字”级别的表现一般会优于“词”级别的表现^[1]），且属于已经解决的问题^[2]。

但在实际应用中，面对需要标注的任务，如关键词抽取，实体识别等。在数据集小时难以训练深度模型，使用无监督模型与不进行fine-tuning的两阶段模型与统计模型的效果待分析（这里留个疑问，在后面写实体识别的时候我做个试验看看效果），且目前在公司的场景中好多任务还是以词为单位。

由于我们目前采用的是JieBa分词^[3]，这里对照jieba分词源码对Jieba分词做一个详细的总结（本篇主要讲Jieba分词在未启用HMM解决未登录词时的分词方法）。

中文分词

3个典型的分词方式：

基于词典匹配

正向最大匹配法、逆向最大匹配法和双向匹配分词法等
基于统计

HMM、CRF等
基于深度学习

基于标注的深度模型，如LSTM、BERT-NER等

Jieba 分词DAG

jieba分词提供四种模式（paddle模式、全模式、精确模式、搜索引擎模式）的分词，本文关注默认的精确模式且不开启基于HMM的新词发现。

基于Trie树结构实现高效的词图扫描，生成句子中汉字所有可能成词情况所构成的有向无环图（DAG）
采用了动态规划查找最大概率路径, 找出基于词频的最大得分切分组合
基于词频的得分是采用了unigram的语言模型，公式如下：

$P(s) = P(w_1,w_2,w_3,...,w_n) = \prod_{i=1}^{n}P(w_i)$

1	如对句子-----“去北京大学玩” 进行分词，步骤及源码分析如下

根据离线统计词典进行前缀词典的构建

相关词的Jieba离线词典如下所示（Jieba的词典是根据1998人民日报的切分语料还有一个msr的切分语料。另一个是作者收集的一些txt小说，用ictclas把他们切分（可能有一定误差）。然后用python脚本统计词频）：

词	词频	词性
北	17860	ns
北京	34488	ns
北京大学	2053	nt
京	6583	ns
大	144099	a
大学	20025	n
学	17482	n
去	123402	v
玩	4207	v

对每个字都是通过在文本中的位置来标记的，因此可以构建一个以位置为key，相应划分的末尾位置构成的列表为value的映射，例子中的前缀表如下所示:

DAG {0: [0], 1: [1, 2, 4], 2: [2], 3: [3, 4], 4: [4], 5: [5]}
然后基于前缀词典，对输入文本进行切分，对于“去”，没有前缀，那么就只有一种划分方式；对于“北”，则有“北”、“北京”、“北京大学”三种划分方式……然后基于前缀词典实现高效的词图扫描，生成句子中汉字所有可能成词情况所构成的有向无环图。

#代码如下：
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

采用维特比算法查找最大概率路径, 找出基于词频的最大切分组合

Jieba分词中使用了基于unigram的语言模型来计算分词的得分。这里为了便于计算且防止溢出,单个词的概率为

$P(w) = log(freq(w)/total)$

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

我们对第6行做下拆解：

for idx in xrange(N - 1, -1, -1):
    tmp = []
    for x in DAG[idx]:
        freqCount = self.FREQ.get(sentence[idx:x + 1]) or 1)
        #如果字典get没有找到这个key，那么我们就使用最后的frequency来做  
        prob = (log(freqCount) - logtotal + route[x + 1][0], x) 
        #以（频度得分值，词语最后一个字的位置）这样的tuple保存在route中
        tmp.append(prob)
        route[idx] = max(tmp)
        #route[N]存储以N开头，最优分词的结果末尾字符的下标，即sentence[N:route[N][1]]即为单词。

这里加了些打印，便于理解这个函数

1 2	import jieba print(jieba.lcut("去北京大学玩",HMM=False))

route初始化为 {6: (0, 0)}
logtotal值为17.911553
构建完成的DAG为 {0: [0], 1: [1, 2, 4], 2: [2], 3: [3, 4], 4: [4], 5: [5]}
计算字符串”玩“的route值
计算：本词**玩**的词频取对数=log(4207) - 全部词频取对数=log(60101970) + 下一个词的概率值route=0.000000
从集合[(-9.567048094079867, 5)]中选取route值最大的词语进行分隔,其值为(-9.567048094079867, 5)
计算字符串”学“的route值
计算：本词**学**的词频取对数=log(17482) - 全部词频取对数=log(60101970) + 下一个词的概率值route=-9.567048
从集合[(-17.709674212609823, 4)]中选取route值最大的词语进行分隔,其值为(-17.709674212609823, 4)
计算字符串”大“的route值
计算：本词**大**的词频取对数=log(144099) - 全部词频取对数=log(60101970) + 下一个词的概率值route=-17.709674
计算字符串”大学“的route值
计算：本词**大学**的词频取对数=log(20025) - 全部词频取对数=log(60101970) + 下一个词的概率值route=-9.567048
从集合[(-23.742971547941938, 3), (-17.573864499813695, 4)]中选取route值最大的词语进行分隔,其值为(-17.573864499813695, 4)
计算字符串”京“的route值
计算：本词**京**的词频取对数=log(6583) - 全部词频取对数=log(60101970) + 下一个词的概率值route=-17.573864
从集合[(-26.693171830016205, 2)]中选取route值最大的词语进行分隔,其值为(-26.693171830016205, 2)
计算字符串”北“的route值
计算：本词**北**的词频取对数=log(17860) - 全部词频取对数=log(60101970) + 下一个词的概率值route=-26.693172
计算字符串”北京“的route值
计算：本词**北京**的词频取对数=log(34488) - 全部词频取对数=log(60101970) + 下一个词的概率值route=-17.573864
计算字符串”北京大学“的route值
计算：本词**北京大学**的词频取对数=log(2053) - 全部词频取对数=log(60101970) + 下一个词的概率值route=-9.567048
从集合[(-34.8144061532561, 1), (-25.037050961057112, 2), (-19.85154385473132, 4)]中选取route值最大的词语进行分隔,其值为(-19.85154385473132, 4)
计算字符串”去“的route值
计算：本词**去**的词频取对数=log(123402) - 全部词频取对数=log(60101970) + 下一个词的概率值route=-19.851544
从集合[(-26.039894434624195, 0)]中选取route值最大的词语进行分隔,其值为(-26.039894434624195, 0)
route最终为 {6: (0, 0), 5: (-9.567048094079867, 5), 4: (-17.709674212609823, 4), 3: (-17.573864499813695, 4), 2: (-26.693171830016205, 2), 1: (-19.85154385473132, 4), 0: (-26.039894434624195, 0)}
['去', '北京大学', '玩']

最后，根据得分对句子进行分词。

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 = ''