NLP——中文分词技术

一.中文分词简介

“词”这个概念一直是汉语语言学界纠缠不清而又绕不开的问题。“词是什么”（词的抽象定义）和“什么是词”（词的具体界定），这两个基本问题迄今为止也未能有一个权威、明确的表述，更无法拿出令大众认同的词表来。主要难点在于汉语结构与印欧体系语种差异甚大，对词的构成边界方面很难进行界定。比如，在英语中，单词本身就是“词”的表达，一篇英文文章就是“单词”加分隔符（空格）来表示的，而在汉语中，词以字为基本单位的，但是一篇文章的语义表达却仍然是以词来划分的。因此，在处理中文文本时，需要进行分词处理，将句子转化为词的表示。这个切词处理过程就是中文分词，它通过计算机自动识别出句子的词，在词间加入边界标记符，分隔出各个词汇。
整个过程看似简单，然而实践起来却很复杂，主要的困难在于分词歧义。以NLP分词的经典语句举例，“结婚的和尚未结婚的”，应该分词为“结婚/的/和/尚未/结婚/的”，还是“结婚/的/和尚/未/结婚/的”？这个由人来判定都是问题，机器就更难处理了。
此外，像未登录词、分词粒度粗细等都是影响分词效果的重要因素。
自中文自动分词被提出以来，历经将近30年的探索，提出了很多方法，可主要归纳为“规则分词”“统计分词”和“混合分词（规则+统计）”这三个主要流派：

• 规则分词是最早兴起的方法，主要是通过人工设立词库，按照一定方式进行匹配切分，其实现简单高效，但对新词很难进行处理。
• 随后统计机器学习技术的兴起，应用于分词任务上后，就有了统计分词，能够较好应对新词发现等特殊场景。
• 然而实践中，单纯的统计分词也有缺陷，那就是太过于依赖语料的质量，因此实践中多是采用这两种方法的结合，即混合分词。

二.规则分词

基于规则的分词是一种机械分词方法，主要是通过维护词典，在切分语句时，将语句的每个字符串与词表中的词进行逐一匹配，找到则切分，否则不予切分。按照匹配切分的方式，主要有正向最大匹配法、逆向最大匹配法以及双向最大匹配法三种方法。

1.正向最大匹配法

正向最大匹配（Maximum Match Method，MM法）的基本思想为：假定分词词典中的最长词有i个汉字字符，则用被处理文档的当前字串中的前i个字作为匹配字段，查找字典。若字典中存在这样的一个i字词，则匹配成功，匹配字段被作为一个词切分出来。如果词典中找不到这样的一个i字词，则匹配失败，将匹配字段中的最后一个字去掉，对剩下的字串重新进行匹配处理。
如此进行下去，直到匹配成功，即切分出一个词或剩余字串的长度为零为止。这样就完成了一轮匹配，然后取下一个i字字串进行匹配处理，直到文档被扫描完为止。

其算法描述如下：

1. 从左向右取待切分汉语句的m个字符作为匹配字段，m为机器词典中最长词条的字符数。
2. 查找机器词典并进行匹配。若匹配成功，则将这个匹配字段作为一个词切分出来。若匹配不成功，则将这个匹配字段的最后一个字去掉，剩下的字符串作为新的匹配字段，进行再次匹配，重复以上过程，直到切分出所有词为止。

比如我们现在有个词典，最长词的长度为5，词典中存在“南京市长”和“长江大桥”两个词。
现采用正向最大匹配对句子“南京市长江大桥”进行分词，那么首先从句子中取出前五个字“南京市长江”，发现词典中没有该词，于是缩小长度，取前4个字“南京市长”，词典中存在该词，于是该词被确认切分。再将剩下的“江大桥”按照同样方式切分，得到“江”“大桥”，最终分为“南京市长”“江”“大桥”3个词。显然，这种结果还不是我们想要的。

2.逆向最大匹配法

逆向最大匹配（Reverse Maximum Match Method，RMM法）的基本原理与MM法相同，不同的是分词切分的方向与MM法相反。逆向最大匹配法从被处理文档的末端开始匹配扫描，每次取最末端的i个字符（i为词典中最长词数）作为匹配字段，若匹配失败，则去掉匹配字段最前面的一个字，继续匹配。相应地，它使用的分词词典是逆序词典，其中的每个词条都将按逆序方式存放。
在实际处理时，先将文档进行倒排处理，生成逆序文档。然后，根据逆序词典，对逆序文档用正向最大匹配法处理即可。
由于汉语中偏正结构较多，若从后向前匹配，可以适当提高精确度。所以，逆向最大匹配法比正向最大匹配法的误差要小。统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245。
比如之前的“南京市长江大桥”，按照逆向最大匹配，最终得到“南京市”“长江大桥”。当然，如此切分并不代表完全正确，可能有个叫“江大桥”的“南京市长”也说不定。

#!/usr/bin/env python3
# encoding: utf-8
'''
@file: IMM.py
@time: 2020/7/12 0012 16:46
@author: Jack
@contact: jack18588951684@163.com
'''


## 逆向最大匹配
class IMM(object):
    def __init__(self, dic_path):
        self.dictionary = set()
        self.maxium = 0
        ## 读取词典
        with open(dic_path, 'r', encoding='utf-8') as f:
            for line in f:
                line = line.strip()
                if not line:
                    continue
                self.dictionary.add(line)
                self.maxium = len(line)

    def cut(self, text):
        result = []
        index = len(text)
        while index > 0:
            word = None
            for size in range(self.maxium, 0, -1):
                if index - size < 0:
                    continue
                piece = text[(index - size):index]
                if piece in self.dictionary:
                    word = piece
                    result.append(word)
                    index -= size
                    break
            if word is None:
                index -= 1
        return result[::-1]


def main():
    text = "南京市长江大桥"
    tokenizer = IMM('imm_dic.txt')
    print(tokenizer.cut(text))


if __name__ == '__main__':
    main()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

imm_dic.txt

南京市
南京市长
长江大桥

1
2
3
4
5
6

['南京市', '长江大桥']
1

3.双向最大匹配法

双向最大匹配法（Bi-directction Matching method）是将正向最大匹配法得到的分词结果和逆向最大匹配法得到的结果进行比较，然后按照最大匹配原则，选取词数切分最少的作为结果。
据SunM.S.和Benjamin K.T.（1995）的研究表明，中文中90.0%左右的句子，正向最大匹配法和逆向最大匹配法完全重合且正确，只有大概9.0%的句子两种切分方法得到的结果不一样，但其中必有一个是正确的（歧义检测成功），只有不到1.0%的句子，使用正向最大匹配法和逆向最大匹配法的切分虽重合却是错的，或者正向最大匹配法和逆向最大匹配法切分不同但两个都不对（歧义检测失败）。这正是双向最大匹配法在实用中文信息处理系统中得以广泛使用的原因。
前面举例的“南京市长江大桥”，采用该方法，中间产生“南京市/长江/大桥”和“南京市/长江大桥”两种结果，最终选取词数较少的“南京市/长江大桥”这一结果。

三.统计分词

基于规则的分词，一般都较为简单高效，但是词典的维护是一个很庞大的工程。在网络发达的今天，网络新词层出不穷，很难通过词典覆盖到所有词。随着大规模语料库的建立，统计机器学习方法的研究和发展，基于统计的中文分词算法渐渐成为主流。
其主要思想是把每个词看做是由词的最小单位的各个字组成的，如果相连的字在不同的文本中出现的次数越多，就证明这相连的字很可能就是一个词。因此我们就可以利用字与字相邻出现的频率来反应成词的可靠度，统计语料中相邻共现的各个字的组合的频度，当组合频度高于某一个临界值时，我们便可认为此字组可能会构成一个词语。
基于统计的分词，一般要做如下两步操作：

1. 建立统计语言模型
2. 对句子进行单词划分，然后对划分结果进行概率计算，获得概率最大的分词方式。这里就用到了统计学习算法，如隐含马尔可夫（HMM）、条件随机场（CRF）等。

1.语言模型

语言模型在信息检索、机器翻译、语音识别中承担着重要的任务。用概率论的专业术语描述语言模型就是：为长度为m的字符串确定其概率分布P(w1,w2,……，wm),其中w1到wm依次表示文本中 的各个词语。一般采用链式法则计算其概率值：

观察式3.1可知，当文本过长时，公式右部从第三项起的每一项计算难度都很大。为解决该问题，有人提出n元模型（n-gram model）降低该计算难度。所谓n元模型就是在估算条件概率时，忽略距离大于等于n的上文词的影响，因此P(w1,w2,……，wm)的计算可简化为：

当n=1时称为一元模型（unigram model），此时整个句子的概率可表示为：P(w1,w2,……，wm)=P(w1)P(w2)……P(wn)。在一元语言模型中，整个句子的概率等于各个词概率的乘积。言下之意就是各个词之间都是相互独立的，这无疑是完全损失了句中的词序信息，所以一元模型的效果并不理想。
当n=2时称为二元模型（bigram model），式3.2变为P(w1,w2,……，wm)=P(wi|wi-1)。当n=3时称为三元模型（trigram model）,式3.2变为P(w1,w2,……，wm)=P(wi|wi-2,wi-1)。显然当n>=2时，该模型是可以保留一定的词序信息的，而且n越大，保留的词序信息越丰富，但计算成本也呈指数级增长。

2.HMM模型

隐马尔可夫模型（HMM）是将分词作为字符串中的序列标注任务来实现的。其基本思路是：每个字在构造一个特定的词语时都占据着一个确定的构词位置（即词位），现规定每个字最多只有四个构词位置：即B（词首）、M（词中）、E（词尾）和S（单独成词），那么下面句子1）的分词结果就可以直接表示成如2）所示的逐字标注形式：
1）中文/分词/是/.文本处理/不可或缺/的/一步/！
2) 中/B文E分/B词/E是/S文/B本/M处/M理/E不/B可/M或/M缺/E的/S一/B步/E！/S
用数学抽象表示如下：用$\lambda =\lambda 1\lambda 2\dots \dots \lambda n$代表输入的句子，n为句子长度，$\lambda i$表示字，o=o1o2……on代表输出的标签，那么理想的输出即为：

在分词任务上，o即为B、M、E、S这四种标记，$\lambda$为诸如“中”“文”等句子中的每个字（包括标点等非中文字符）。
需要注意的是，$P(o|\lambda )$是关于2n个变量的条件概率，且不固定。因此，几乎无法对$P(o|\lambda )$进行精确计算。这里引入观测独立性假设，即每个字的输出仅仅与当前字有关，于是就能得到下式：

事实上，$P(ok|\lambda k)$的计算要容易很多。通过观测独立性假设，目标问题得到极大简化。然而该方法完全没有考虑上下文，且会出现不合理 的情况。比如按照之前设定的B、M、E和S标记，正常来说B后面只能是M或者E，然而基于观测独立性假设，我们很可能得到诸如BBB、BEM等的输出，显然是不合理的。
HMM就是用来解决该问题的一种方法。在上面的公式中，我们一直期望求解的是$P(o|\lambda )$,通过贝叶斯公式能够得到：

$\lambda$为给定的输入，因此$P(\lambda )$计算为常数，可以忽略，因此最大化$P(o|\lambda )$等价于最大化$P(o|\lambda )P(o)$。
针对$P(o|\lambda )P(o)$作马尔可夫假设，得到：

同时，对P(o)有：

这里HMM做了另外一个假设——齐次马尔可夫假设，每个输出仅仅与上一个输出有关，那么：

于是：

在HMM中，将$P(\lambda k|ok)$称为发射概率，$P(ok|ok-1)$称为转移概率。通过设置某些$P(ok|ok-1)=0$，可以排除类似BBB、EM等不合理的组合。
事实上，式3.9的马尔可夫假设就是一个二元语言模型，当将齐次马尔可夫假设改为每个输出与前两个有关时，就变成了三元语言模型。当然在实际分词应用中还是多采用二元语言模型，因为相比三元模型，其计算复杂度要小很多。
在HMM中，求解$maxP(\lambda |o)P(o)$的最常用方法是Veterbi算法。它是一种动态规划方法，核心思想是：如果最终的最优路径经过某个oi，那么从初始节点到oi-1点的路径必然也是一个最优路径——因为每一个节点oi只会影响前后两个$P(oi-1|oi)$和$P(oi|oi+1)$。
根据这个思想，可以通过递推的方法，在考虑每个oi时只需要求出所有经过各oi-1的候选点的最优路径，然后再与当前的oi结合比较。这样每步只需要算不超过l^2次，就可以逐步找出最优路径。Veterbi算法的效率是O（n*l2）,l是候选数目最多的节点oi的候选数目，它正比于n，这是非常高效率的。HMM的状态转移图如图3-1所示：

HMM的Python实现代码：

#!/usr/bin/env python3
# encoding: utf-8
'''
@file: HMM.py
@time: 2020/7/12 0012 20:00
@author: Jack
@contact: jack18588951684@163.com
'''


class HMM(object):
    def __init__(self):
        import os
        ## 存取算法中间结果，不用每次都训练模型
        self.model_file = 'data/hmm_model.pkl'
        ## 状态值集合
        self.state_list = ['B', 'M', 'E', 'S']
        ## 参数加载，用于判断是否需要重新加载model_file
        self.load_para = False

    def try_load_model(self, trained):
        if trained:
            import pickle
            with open(self.model_file, 'rb') as f:
                self.A_dic = pickle.load(f)
                self.B_dic = pickle.load(f)
                self.Pi_dic = pickle.load(f)
                self.load_para = True
        else:
            # 状态转移概率（状态——>状态的条件概率）
            self.A_dic = {}
            # 发射概率（状态——>词语的条件概率）
            self.B_dic = {}
            # 状态的初始概率
            self.Pi_dic = {}
            self.load_para = False

    def train(self, path):
        # 重置几个概率矩阵
        self.try_load_model(False)
        # 统计状态出现次数，求p(o)
        Count_dic = {}

        # 初始化参数
        def init_parameters():
            for state in self.state_list:
                self.A_dic[state] = {s: 0.0 for s in self.state_list}
                self.Pi_dic[state] = 0.0
                self.B_dic[state] = {}
                Count_dic = 0

        def makeLabel(text):
            out_text = []
            if len(text) == 1:
                out_text.append('S')
            else:
                out_text += ['B'] + ['M'] * (len(text) - 2) + ['E']
            return out_text

        init_parameters()
        line_num = -1
        # 观察者集合，主要是字以及标点等
        words = set()
        with open(path, encoding='utf-8') as f:
            for line in f:
                line_num += 1

                line = line.strip()
                if not line:
                    continue
                word_list = [i for i in line if i != '']
                words |= set(word_list)  # 更新字的集合
                linelist = line.split()

                line_state = []
                for w in linelist:
                    line_state.extend(makeLabel(w))

                assert len(word_list) == len(line_state)

                for k, v in enumerate(line_state):
                    Count_dic[V] += 1
                    if k == 0:
                        self.Pi_dic[v] += 1  # 每个句子的第一个字的状态，用于计算初始状态
                    else:
                        self.A_dic[line_state[k - 1][v]] += 1  # 计算转移概率
                        self.B_dic[line_state[k][word_list[k]]] = \
                            self.B_dic[line_state[k]].get(word_list[k], 0) + 1.0

            self.Pi_dic = {k: v * 1.0 / line_num for k, v in self.Pi_dic.items()}
            self.A_dic = {k: {k1: v1 / Count_dic[k] for k1, v1 in v.items()} for
                          k, v in self.A_dic.items()}

            # 加1平滑
            self.B_dic = {k: {k1: (v1 + 1) / Count_dic[k] for k1, v1 in v.items()}
                          for k, v in self.B_dic.items()}  # 序列化
            import pickle
            with open(self.model_file, 'wb') as f:
                pickle.dump(self.A_dic, f)
                pickle.dump(self.B_dic, f)
                pickle.dump(self.Pi_dic, f)
            return self

    def viterbi(self, text, states, start_p, trans_p, emit_p):
        V = [{}]
        path = {}
        for y in states:
            V[0][y] = start_p[y] * emit_p[y].get(text[0], 0)
            path[y] = [y]
        for t in range(1, len(text)):
            V.append({})
            newpath = {}

            # 检验训练的发射概率矩阵中是否有该字
            neverSeen = text[t] not in emit_p['S'].keys() and text[t] not in emit_p['M'].keys() and text[t] not in \
                        emit_p['E'].keys() and text[t] not in emit_p['B'].keys()
            for y in states:
                emitP = emit_p[y].get(text[t], 0) if not neverSeen else 1.0

                (prob, state) = max(
                    [(V[t - 1][y0] * trans_p[y0].get(y, 0) * emitP, y0) for y0 in states if V[t - 1][y0] > 0]
                )
                V[t][y] = prob
                newpath[y] = path[state] + [y]

                path = newpath

        if emit_p['M'].get(text[-1], 0) > emit_p['S'].get(text[-1], 0):
            (prob, state) = max([(V[len(text) - 1][y], y) for y in ('E', 'M')])
        else:
            (prob, state) = max([(V[len(text) - 1][y], y) for y in states])

        return (prob, path[state])

    def cut(self, text):
        import os
        if not self.load_para:
            self.try_load_model(os.path.exists(self.model_file))
            prob, pos_list = self.viterbi(text, self.state_list, self.Pi_dic, self.A_dic, self.B_dic)
            begin, next = 0, 0
            for i, char in enumerate(text):
                pos = pos_list[i]
                if pos == 'B':
                    begin = i
                elif pos == 'E':
                    yield text[begin:i + 1]
                    next = i + 1
                elif pos == 'S':
                    yield char
                    next = i + 1
            if next < len(text):
                yield text[next:]


hmm = HMM()
hmm.train('data/trainCorpus.txt_utf8')
text = '这是一个非常棒的方案！'
res = hmm.cut(text)
print(text)
print(str(list(res)))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161

3.其他统计分词算法

条件随机场（CRF）也是一种基于马尔可夫思想的统计模型。在隐马尔可夫中，有个很经典的假设，那就是每个状态只与它前面的状态有关。这样的假设显然是有偏差的，于是学者们提出了条件随机场算法，使得每个状态不止与他前面的状态有关，还与它后面的状态有关。
神经网络分词算法是深度学习方法在NLP上的应用。通常采用CNN、LSTM等深度学习网络自动发现一些模式和特征，然后结合CRF、softmax等分类算法进行分词预测。这一类称为基于深度学习的分词方法。
对比机械分词法，这些统计分词方法不需耗费人力维护词典，能较好地处理歧义和未登录词，是目前分词中非常主流的方法。但其分词的效果很依赖训练语料的质量，且计算量相较于机械分词要大得多。

四.混合分词

事实上，目前不管是基于规则的算法、还是基于HMM、CRF或者deep learning等的方法，其分词效果在具体任务中，其实差距并没有那么明显。在实际工程应用中，多是基于一种分词算法，然后用其他分词算法加以辅助。
最常用的方式就是先基于词典的方式进行分词，然后再用统计分词方法进行辅助。如此，能在保证词典分词准确率的基础上，对未登录词和歧义词有较好的识别。