分词（一）：规则分词方法-FlyAI

分词（一）：规则分词方法

自然语言处理

最后更新 2021-06-23 10:59 阅读 2758

最后更新 2021-06-23 10:59

阅读 2758

自然语言处理

# 分词简介

中文word_seg是指将一个汉字序列切分成一个一个单独的词，与英文以空格作为天然的分隔符不同，中文字符在语义识别时，需要把数个字符组合成词，才能表达出真正的含义。word_seg通常应用于自然语言处理、搜索引擎、智能推荐等领域。

word_seg根据其核心思想主要分为两种，第一种是基于词典的分词，先把句子按照字典切分成词，再寻找词的最佳组合方式；第二种是基于字的分词，即由字构词，先把句子分成一个个字，再将字组合成词，寻找最优的切分策略，同时也可以转化成序列标注问题。

其分类大致可分为：

1. 基于匹配规则的方法
	* 正向最大匹配法(forward maximum matching method, FMM)
	* 逆向最大匹配法(backward maximum matching method, BMM)
	* 最短路径

2. 基于统计以及机器学习的分词方法
	* 基于N-gram语言模型的分词方法
	* 基于HMM的分词方法
	* 基于CRF的分词方法
	* 基于词感知机的分词方法
	* 基于深度学习的端到端的分词方法

基于规则匹配的分词通常会加入一些启发式规则，比如“正向/反向最大匹配”，“长词优先”等。

基于统计以及机器学习的分词方法，它们基于人工标注的词性和统计特征，对中文进行建模，即根据观测到的数据(标注好的语料)对模型参数进行训练，在分词阶段再通过模型计算各种分词出现的概率，将概率最大的分词结果作为最终结果。这类word_seg能很好处理歧义和未登录词问题，效果比基于规则匹配的方法效果好，但是需要大量的人工标注数据，以及较慢的分词速度。

[代码及数据](https://github.com/jeffery0628/chinese_word_seg)

## 中文分词的应用

目前在自然语言处理技术中，中文处理技术比西文处理技术要落后很大一段距离，许多西文的处理方法中文不能直接采用，就是因为中文必需有分词这道工序。中文分词是其他中文信息处理的基础，搜索引擎只是中文分词的一个应用。其他的比如机器翻译（MT）、语音合成、自动分类、自动摘要、自动校对等等，都需要用到分词。因为中文需要分词，可能会影响一些研究，但同时也为一些企业带来机会，因为国外的计算机处理技术要想进入中国市场，首先也是要解决中文分词问题。在中文研究方面，相比外国人来说，中国人有十分明显的优势。

分词准确性对搜索引擎来说十分重要，但如果分词速度太慢，即使准确性再高，对于搜索引擎来说也是不可用的，因为搜索引擎需要处理数以亿计的网页，如果分词耗用的时间过长，会严重影响搜索引擎内容更新的速度。因此对于搜索引擎来说，分词的准确性和速度，二者都需要达到很高的要求。目前研究中文分词的大多是科研院校，清华、北大、中科院、北京语言学院、东北大学、IBM研究院、微软中国研究院等都有自己的研究队伍，而真正专业研究中文分词的商业公司除了海量科技以外，几乎没有。

# 基于匹配规则的方法

主要是人工建立词库也叫做词典，通过词典匹配的方式对句子进行划分。其实现简单高效，但是对未登陆词很难进行处理。主要有前向最大匹配法，后向最大匹配法以及双向最大匹配法。

## 前向最大匹配算法

前向最大匹配算法，是从待分词句子的左边向右边搜索，寻找词的最大匹配。规定一个词的最大长度，每次扫描的时候寻找当前开始的这个长度的词来和字典中的词匹配，如果没有找到，就缩短长度继续寻找，直到找到字典中的词或者成为单字。

### 算法流程

1. 从前向后扫描字典，测试读入的子串是否在字典中
2. 如果存在，则从输入中删除掉该子串，重新按照规则取子串，重复1
3. 如果不存在于字典中，则从右向左减少子串长度，重复1

### 分词实例：

比如说输入 “北京大学生前来应聘”，假设词典中最长的单词为 5 个（MAX_LENGTH）。

1. 第一轮：取子串 “北京大学生”，正向取词，如果匹配失败，**每次去掉匹配字段最后面的一个字** 
   “北京大学生”，扫描 5 字词典，没有匹配，子串长度减 1 变为“北京大学”
   “北京大学”，扫描 4 字词典，有匹配，输出“北京大学”，输入变为“生前来应聘”
2. 第二轮：取子串“生前来应聘” 
   “生前来应聘”，扫描 5 字词典，没有匹配，子串长度减 1 变为“生前来应”
   “生前来应”，扫描 4 字词典，没有匹配，子串长度减 1 变为“生前来”
   “生前来”，扫描 3 字词典，没有匹配，子串长度减 1 变为“生前”
   “生前”，扫描 2 字词典，有匹配，输出“生前”，输入变为“来应聘””
3. 第三轮：取子串“来应聘” 
   “来应聘”，扫描 3 字词典，没有匹配，子串长度减 1 变为“来应”
   “来应”，扫描 2 字词典，没有匹配，子串长度减 1 变为“来”
   颗粒度最小为 1，直接输出“来”，输入变为“应聘”
4. 第四轮：取子串“应聘” 
   “应聘”，扫描 2 字词典，有匹配，输出“应聘”，输入变为“”
   输入长度为0，扫描终止

数据准备：词库

```python

def forward_max_match(sentence, window_size, word_dict):
    """
    前向最大匹配算法：
    （1）扫描字典，测试读入的子串是否在字典中
    （2）如果存在，则从输入中删除掉该子串，重新按照规则取子串，重复（1）
    （3）如果不存在于字典中，则从右向左减少子串长度，重复（1）

:param sentence: 待分词的句子
    :param window_size: 词的最大长度
    :param word_dict: 词典
    :return:
    """
    seg_words = []  # 存放分词结果

while sentence:
        for word_len in range(window_size, 0, -1):
            if sentence[:word_len] in word_dict:
                # 如果该词再字典中，将该词保存到分词结果中,并将其从句中切出来
                seg_words.append(sentence[:word_len])
                sentence = sentence[word_len:]
                break
        else:
            # 如果窗口中的词不在字典中，将第一个字切分出来
            seg_words.append(sentence[:word_len])
            sentence = sentence[word_len:]

return '/'.join(seg_words)
```

## 后向最大匹配算法

在词典中从句尾向句首进行扫描，尽可能地选择与词典中最长单词匹配的词作为目标分词，然后进行下一次匹配。

在实践中，逆向最大匹配算法性能优于正向最大匹配算法。

### 算法流程

1. 从后向前扫描字典，测试读入的子串是否在字典中
2. 如果存在，则从输入中删除掉该子串，重新按照规则取子串，重复1
3. 如果不存在于字典中，则从左向右减少子串长度，重复1

### 分词实例

输入 “北京大学生前来应聘”，假设词典中最长的单词为 5 个（MAX_LENGTH）。

1. 第一轮：取子串 “生前来应聘”，逆向取词，如果匹配失败，**每次去掉匹配字段最前面的一个字** 
   “生前来应聘”，扫描 5 字词典，没有匹配，字串长度减 1 变为“前来应聘”
   “前来应聘”，扫描 4 字词典，没有匹配，字串长度减 1 变为“来应聘”
   “来应聘”，扫描 3 字词典，没有匹配，字串长度减 1 变为“应聘”
   “应聘”，扫描 2 字词典，有匹配，输出“应聘”，输入变为“大学生前来”
2. 第二轮：取子串“大学生前来” 
   “大学生前来”，扫描 5 字词典，没有匹配，字串长度减 1 变为“学生前来”
   “学生前来”，扫描 4 字词典，没有匹配，字串长度减 1 变为“生前来”
   “生前来”，扫描 3 字词典，没有匹配，字串长度减 1 变为“前来”
   “前来”，扫描 2 字词典，有匹配，输出“前来”，输入变为“北京大学生”
3. 第三轮：取子串“北京大学生” 
   “北京大学生”，扫描 5 字词典，没有匹配，字串长度减 1 变为“京大学生”
   “京大学生”，扫描 4 字词典，没有匹配，字串长度减 1 变为“大学生”
   “大学生”，扫描 3 字词典，有匹配，输出“大学生”，输入变为“北京”
4. 第四轮：取子串“北京” 
   “北京”，扫描 2 字词典，有匹配，输出“北京”，输入变为“”
   输入长度为0，扫描终止

数据准备：词库

```python
def backward_max_match(sentence, window_size, word_dict):
    """
    后向最大匹配算法：
    （1）从后向前扫描字典，测试读入的子串是否在字典中
    （2）如果存在，则从输入中删除掉该子串，重新按照规则取子串，重复（1）
    （3）如果不存在于字典中，则从右向左减少子串长度，重复（1）

:param sentence: 待分词的句子
    :param window_size: 词的最大长度
    :param word_dict: 词典
    :return:
    """
    seg_words = []
    while sentence:
        for word_len in range(window_size, 0, -1):  # 每次去掉匹配字段最前面的一个字

if sentence[len(sentence) - word_len:] in word_dict:
                # 如果该词再字典中，将该词保存到分词结果中,并将其从句中切出来
                seg_words.append(sentence[len(sentence) - word_len:])
                sentence = sentence[:len(sentence) - word_len]
                break
        else:
            # 如果窗口中的词不在字典中，将最后一个字切分出来
            seg_words.append(sentence[-1:])
            sentence = sentence[:-1]
    seg_words.reverse()
    return '/'.join(seg_words)
```

## 双向最大匹配法

因为同一个句子，在机械分词中经常会出现多种分词的组合，因此需要进行歧义消除，来得到最优的分词结果。

以很常见的MMSEG机械word_seg为例，MMSEG在搜索引擎Solr中经常使用到，是一种非常可靠高效的word_seg。MMSEG消除歧义的规则有四个，它在使用中依次用这四个规则进行过滤，直到只有一种结果或者第四个规则使用完毕。这个四个规则分别是：

1. 最大匹配。选择“词组长度最大的”那个词组，然后选择这个词组的第一个词，作为切分出的第一个词，如对于“中国人民万岁”，匹配结果分别为：

* 中/国/人
	* 中国/人/民
	* 中国/人民/万岁
	* 中国人/民/万岁

在这个例子“词组长度最长的”词组为后两个，因此选择了“中国人/民/万岁”中的“中国人”，或者“中国/人民/万岁”中的“中国”。

2. 最大平均词语长度。经过规则1过滤后，如果剩余的词组超过1个，那就选择平均词语长度最大的那个(平均词长=词组总字数/词语数量)。比如“生活水平”，可能得到如下词组：

* 生/活水/平 (4/3=1.33)
	* 生活/水/平 (4/3=1.33)
	* 生活/水平 (4/2=2)

根据此规则，就可以确定选择“生活/水平”这个词组

3. 词语长度的最小变化率。这个变化率一般可以由标准差来决定。比如对于“中国人民万岁”这个短语，可以计算：

* 中国/人民/万岁(标准差=sqrt(((2-2)^2+(2-2)^2+(2-2^2))/3)=0)
	* 中国人/民/万岁(标准差=sqrt(((2-3)^2+(2-1)^2+(2-2)^2)/3)=0.8165)

于是选择“中国/人民/万岁”这个词组。

4. 计算词组中的所有单字词词频的自然对数，然后将得到的值相加，取总和最大的词组。比如：

* 设施/和服/务
	* 设施/和/服务

这两个词组中分别有“务”和“和”这两个单字词，假设“务”作为单字词时候的频率是5，“和”作为单字词时候的频率是10，对5和10取自然对数，然后取最大值者，所以取“和”字所在的词组，即“设施/和/服务”。

在实际中根据需求，选择或制定相应的规则来改善分词的质量。

### 算法流程

1. 比较正向最大匹配和逆向最大匹配结果
2. 如果分词数量结果不同，那么取分词数量较少的那个
3. 如果分词数量结果相同
	* 分词结果相同，可以返回任何一个
	* 分词结果不同，返回单字数比较少的那个

这种规则的出发点来自语言学上的启发：汉语中单字词的数量要远小于非单字词。因此，算法应当尽量减少结果中的单字，保留更多的完整词语。

##### 分词实例

正向匹配最终切分结果为：北京大学 / 生前 / 来 / 应聘，分词数量为 4，单字数为 1
逆向匹配最终切分结果为：”北京/ 大学生/ 前来 / 应聘，分词数量为 4，单字数为 0
逆向匹配单字数少，因此返回逆向匹配的结果。

数据准备：词库

```python
def fb_max_match(sentence,window_size,word_dict):
    """
    1. 比较正向最大匹配和逆向最大匹配结果
    2. 如果分词数量结果不同，那么取分词数量较少的那个
    3. 如果分词数量结果相同
       * 分词结果相同，可以返回任何一个
       * 分词结果不同，返回单字数比较少的那个
    :param sentence: 待分词的句子
    :param window_size: 词的最大长度
    :param word_dict: 词典
    :return:
    """
    forward_seg = forward_max_match(sentence,window_size,word_dict)
    backward_seg = backward_max_match(sentence,window_size,word_dict)

# 如果分词结果不同，返回词数较小的分词结果
    if len(forward_seg) != len(backward_seg):
        return forward_seg if len(forward_seg) < len(backward_seg) else backward_seg
    else:
        # 如果分词结果词数相同，优先考虑返回包含单个字符最少的分词结果
        forward_single_word_count = len([filter(lambda x:len(x) == 1,forward_seg)])
        backward_single_word_count = len([filter(lambda x:len(x) == 1,backward_seg)])
        if forward_single_word_count != backward_single_word_count:
            return forward_seg if forward_single_word_count < backward_single_word_count else backward_seg
        else:
            # 否则，返回任意结果
            return forward_seg
```

### 缺点：

对歧义问题的解决有点弱

## (N-)最短路径

### 基本思想

首先基于词典对文本进行全切分(改编版最大匹配)；然后基于词语的临接关系构建一个有向图；使用模型(比如一阶马尔科夫模型)对图里的边加权；最后使用最短路径算法求，从句首到句末质量最高(比如概率最大)的路径，就得到了分词结果。

### 举例

最短路径word_seg首先将一句话中的所有词匹配出来，构成词图（有向无环图DAG），之后寻找从起始点到终点的最短路径作为最佳组合方式，以“他说的确实在理”为例，给出对这句话的3-最短路：
![](https://markdown-images-1257755739.cos.ap-guangzhou.myqcloud.com/hexo/posts/word_seg/%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84%E5%88%86%E8%AF%8D%E7%AE%97%E6%B3%95.png)

1. 构建有向图：根据一个已有词典构造出的有向无环图（全切分，根据临接关系构建有向图）。它将字串分为单个的字，每个字用图中相邻的两个结点表示，故对于长度为n的字串，需要n+1个结点。两节点间若有边，则表示两节点间所包含的所有结点构成的词，如图中结点2、3、4构成词“的确”。

2. 计算权重：本例子中权重为1（为了简单），实际应用中，可以使用一阶马尔科夫模型进行权重计算。

* p(实，在)=p(实)*p(在|实)。概率取值越大，说明一个边出现的概率越大，这条边会提升所在分句结果的概率，由于最后要计算最短路径，需要构造一个连接权重与分局结果质量成反比的指标，因此对概率取了倒：weight=1/p(实,在)
   * 这个概率可能非常小，得到的权重取值非常大。而我们后面在计算路径的长度时，会将若干个边的权重加起来，这时候有上溢出的可能性。避免上溢出的常用策略是取对数。：weight=log(1/p(实，在))。

* 概率的估算：概率就用频率来估计，p(实) = （“实”字在语料中出现的次数）/（语料的总词数），

p(在|实) = p(实在)/p(实)=(“实在”在语料中出现的次数)/(“实”在语料中出现的次数)

数据准备：1、词库，2、词语之间的条件概率（用来计算路径权重）

```python
    # 使用维特比算法求词图的最短路径
    def viterbi(self, word_graph):
        path_length_map = {}  # 用于存储所有的路径，后面的邻接词语所在位置，以及对应的长度
        word_graph = [[["<start>", 1]]] + word_graph + [[["<end>", -1]]]
        # 这是一种比较简单的数据结构
        path_length_map[("<start>",)] = [1, 0]  # start处，后面的临接词语在列表的1处，路径长度是0,。

for i in range(1, len(word_graph)):
            distance_from_start2current = {}
            if len(word_graph[i]) == 0:
                continue
            for former_path in list(path_length_map.keys()):  # path_length_map内容一直在变，需要深拷贝key,也就是已经积累的所有路径
                # 取出已经积累的路径，后面的临接词语位置，以及路径的长度。
                [next_index_4_former_path, former_distance] = path_length_map[former_path]
                former_word = former_path[-1]
                later_path = list(former_path)
                if next_index_4_former_path == i:  # 如果这条路径的临接词语的位置就是当前索引
                    for current_word in word_graph[i]:  # 遍历词图数据中，这个位置上的所有换选词语，然后与former_path拼接新路径
                        current_word, next_index = current_word
                        new_path = tuple(later_path + [current_word])  # 只有int, string, tuple这种不可修改的数据类型可以hash，
                        # 也就是成为dict的key
                        # 计算新路径的长度
                        new_path_len = former_distance + self.word_distance.get((former_word, current_word), 100)

path_length_map[new_path] = [next_index, new_path_len]  # 存储新路径后面的临接词语，以及路径长度

# 维特比的部分。选择到达当前节点的路径中，最短的那一条
                        if current_word in distance_from_start2current:  # 如果已经有到达当前词语的路径，需要择优
                            if distance_from_start2current[current_word][1] > new_path_len:  # 如果当前新路径比已有的更短
                                distance_from_start2current[current_word] = [new_path, new_path_len]  # 用更短的路径数据覆盖原来的
                        else:
                            distance_from_start2current[current_word] = [new_path, new_path_len]  # 如果还没有这条路径，就记录它
        shortest_path = distance_from_start2current["<end>"][0]
        shortest_path = shortest_path[1:-1]
        return shortest_path
```

### 缺点

1. 对歧义和新词的处理不是很好，对词典中未出现的词没法进行处理。
2. 分词效果取决于词典的质量。

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可，转载请附上原文出处链接和本声明。
本文链接地址：https://flyai.com/article/923

讨论

500字

表情

发送

删除确认

是否删除该条评论？

取消删除