1.3 中文分词

发表于 2022-06-01 分类于 FunRec ， 01-自然语言文本处理基础阅读次数：本文字数： 5.2k 阅读时长 ≈ 24 分钟

0x00 Abstract

中文分词的目的：对中文句子中的词与词之间加上边界标记，本质就是对中文句子做划分词的边界。

为什么要做中文分词？
- 因为英文单词之间是天然分开的，但中文没有
怎么做中文分词？
- 基于统计学习的方法
- 基于机器学习的方法等

0x01 中文分词的难点

中文分词面临以下难点： - 标准（颗粒度选择，场景多样） - 搜索领域、推荐领域以及其他垂直领域的需求不同 - 歧义（一词多义） - 苹果 => 手机还是水果？ - 炒鱿鱼？ - 新词（未登录词）

后面两点很容易理解，第一点需要详细阐述一下。在不同的场景中，对于分词颗粒度的选择是不同的。下面举两个例子。 - 切词颗粒度： - 粗颗粒度：适合推荐场景 - 例子：分成 => /环球影城/ - 推荐环球影城有关的 - 而不是跟环球有关，或者其他跟影城有关的 - 细颗粒度：适合搜索场景 - 例子：需要分成 => /环球/影城/ - 保证召回质量，出现的词都涉及到 - 而不是只召回了有关环球影城的，其余的召回就全是无关的。

也就是说对于推荐场景来说，哪怕漏掉一些也没关系，但一定要准；但对于搜索来说，要保证召回的全面。

0x02 中文分词的方法

基于规则字典：
- 最大长度匹配（正、逆、双序）中文分词算法之--最大匹配法 - 知乎
- 加入前缀树改进最大长度匹配
基于机器学习：
- HMM——双序列标注
- CRF——标注训练

0x03 案例1：基于字典匹配的方法

在字典树里寻找逐字寻找匹配的词，如果已经匹配切分好的词，那么结束这个词，下一个字符从新的字符开始。

那么如何实现？首先基于前缀树的数据结构构成字典树，然后通过概率语言模型预测分词结果。

1. 一种重要的数据结构（前缀树）

Trie 树，即字典树，又称单词查找树或者键树，是一种树形结构，是一种哈希树的变种，常被搜索引擎系统用于文本词频统计。

优点：最大限度地减少无谓的字符串比较，查询效率高于哈希表。

有了字典树，就可以实现基于最大长度分词，如下。

正向和逆向最大长度匹配（对输入字符串开始匹配方向不同）：

正向最大长度匹配对字符串从前向后匹配，逆向最大长度匹配从后向前匹配。

但是，仅仅基于最大长度匹配的分词方法靠谱吗？

正向与反向最大长度匹配都可能出现特例，比如：

在这个例子中，正向不如反向的效果。一般来讲，因为中文比较复杂以及中文的特殊性，逆向最大匹配大多时候往往会比正向要准确。

由此也可以发现只通过最大长度匹配来分词是不够的。

所以，需要借助概率语言模型来完善分词的效果。

2. 概率语言模型

基础原理

输入=> 对于输入的字符串，以字为单位，根据字典，将所有可能的词都连起来，构成一个有向无环图（DAG）。如何输出？=> 将所有可能的词的组合概率都计算出来，然后取概率最高的组合。

==输入==：字串 C = c1, c2, ..., cn（以字为单位） ==输出==：词串 S = w1, w2, ..., wn （以词为单位）

从输入到输出，由条件概率 P(S|C) 来衡量——P(S|C)：字串 C 产生切分 S 的概率。

说明：上面式子的变形基于贝叶斯公式。 P(A|B) = P(A,B) / P(B) = P(B|A) * P(A) / P(B) P(A, B) = P(B|A) * P(A) = P(A|B) * P(B)

=> 上面的式子可以继续化简。 因为 P(C) = 1 并且 P(C|S) = 1，上式只剩下 P(S)。P(C) = 1 很容易理解，那么为什么 P(C|S) = 1？结合下面的例子理解。

==举个栗子：==

以 P(C|S1) 为例，S1: 南京市/长江/大桥，C：南京市长江大桥，所以 S1 去掉那两个分词斜杠就得到了 C，可得根据 S1 必然能得到 C。因此 P(C|S1) = 1 对于其他的词串字串也一样。

对于字串 C 的分词结果 => seg(C) = argmax P(S) ：令 P(S) 取到最大的 S。

那么在本例就只需要计算 P(S1) 与 P(S2)。

如何计算 P(S1)？ P(S1) = P(南京市)*P(长江)*P(大桥) 以 P(南京市) 为例。假设有十篇文章，词语总量为 100，南京市总共出现了 2 次。那么 P(南京) = 2 / 100 = 0.02 以此类推，算出所有概率。

==优化：== 概率连乘，而且这些概率一般都是小数点后几位，比如 0.00002,那么概率连乘后，最后得到的概率会在小数点后很多位，因此会导致计算机的精度不够。如何解决？

=> 取 log。 - 取 log 的作用 - 防止向下溢出 - 加法比乘法快

N 元语言模型（N-Gram）

N-Gram
- Unigram model：不考虑前面出现的词
- Bigram model：考虑前面的一个词
- Trigram model：考虑前面的两个词

如何计算 N-Gram 的概率？

以“广州/本田/雅阁/汽车”为例。

一元：P（广州，本田，雅阁，汽车）= P(广州) * P(本田) * P(雅阁) * P(汽车)
二元：P（广州，本田，雅阁，汽车）= P(广州) * P(本田|广州) * P(雅阁|本田) * P(汽车|雅阁)
三元：P（广州，本田，雅阁，汽车）= P(广州) * P(本田|广州) * P(雅阁|本田，广州) * P(汽车|雅阁，本田)

以 P(本田|广州) 为例，怎么计算？

P(本田|广州) = $本田，广州广州$

即计算本田和广州同时出现的次数（一定要广州在前，本田在后），以及广州出现的次数。

3. 实践

方法一：最大长度匹配（反向）

import sys

WordDic = {}
MaxWordLen = 1

# 写入字典
# 并且找到词语最大长度
def LoadLexicon(lexiconFile):
    global MaxWordLen
    infile = open(lexiconFile, 'r', encoding='gb2312')
    s = infile.readline().strip()  # 每次读一行
    while len(s) > 0:  # 通过判断每行的长度，放在 while 循环里读完整个文件
        #s = s.decode("gb2312")
        WordDic[s] = 1  # 读到的每行的词，放入字典
        if len(s) > MaxWordLen:
            MaxWordLen = len(s)  # 记录词语最大长度
        s = infile.readline().strip()
    infile.close()

def BMM(s):
    global MaxWordLen
    wordlist = []
    i = len(s)  # 句子长度为 i，代表有 i 个字
    while i > 0:
        start = i - MaxWordLen  # 从后向前，以最大长度匹配
        if start < 0:
            start = 0
        while start < i:
            tmpWord = s[start:i]  # 框起来 start 到 i 的字
            if tmpWord in WordDic:
                wordlist.insert(0, tmpWord)  # 在字典中找到匹配的词，那么放入 wordlist
                break
            else:
                start += 1
        # 如果 start 一直向后移动，直到 i（句尾）还没有匹配的词
        # 那么将最后的一个字作为一个分词结果
        if start >= i:
            wordlist.insert(0, s[i-1:i])
            start = i - 1
        i = start
        # 因为 start~i的字已经构成了分词结果
        # 所以下一次循环中，句尾坐标 i 重新赋值，左闭右开，所以不包括 start
    return wordlist

def PrintSegResult(wordlist):
    print("After word-seg:")
    for i in range(len(wordlist)-1):
        print(wordlist[i])
    print(wordlist[len(wordlist)-1])

LoadLexicon("./lexicon.txt")

inputStr = u"南京市长江大桥"

wordlist = BMM(inputStr)
PrintSegResult(wordlist)
# 输出：
# After word-seg:
# 南京
# 市
# 长江
# 大
# 桥

方法二：最大概率(Bigram)

Step 1.
# convert token to id
python CreateLexicon.py

Step 2.
# gen lang model
python BiLMTrain.py

Step 3.
# viterbi
python ViterbiCWS.py

4. 小结

中文分词
- 容易区分的——登陆词（词表中已有的）=> 字典树（Trie）
- 不容易区分的——未登录词（新词）=> 单字

通过上面的学习，我们知道中文分词是这样处理的：对于登录词，使用字典树，对于未登录词，分为单字。

那么如何才能更合理的处理未登录词呢？比如 广州/本田/雅/阁/汽车，如何将雅阁分为一个词呢？

=> 隐马尔可夫模型

隐马模型可以像胶水一样，将他认为合适的词粘到一起，合并为一个词。

最后重新总结一下中文分词的技术点，并且引出后面要学习的内容——动态规划。

中文分词的技术
- 字典树：处理登录词
- 隐马模型：处理未登录词
- 动态规划（Viterbi 算法）：支撑以上两个技术

0x04 动态规划——Viterbi 算法

多步骤，每步多选择模型的最优选择问题。

每一步的所有选择都保存了前序步骤到当前步骤的最优选择。

依次计算完所有步骤后，通过回溯的方法找到最优选择路径。

这里不是很容易理解，需要好好思考一下。如何通俗地讲解 viterbi 算法？ - 知乎

Viterbi 与枚举的区别到底在哪？以上图为例，枚举的话需要 3×3×3 次计算，Viterbi 需要 3×3×2 次计算。假设每一步有 N 种选择，一共有 L 步。那么枚举的时间复杂度为 O(N^L)，Viterbi 的时间复杂度为 O(N^2*L)，也就是说当这个序列越长（步数 L 越大）时，两种方法的复杂度差距会越大。这时，Viterbi 的优势就体现出来了。

实现参考上一节的实践方法二中 ViterbiCWS.py。

0x05 案例2：复用轮子——jieba

1. 安装

方式1：

pip install jieba

方式2：

先下载 http://pypi.python.org/pypi/jieba/

然后解压，运行 python setup.py install

// 具体信息可参考github文档：[https://github.com/fxsjy/jieba](https://link.zhihu.com/?target=https://github.com/fxsjy/jieba)

2. 整体逻辑

梳理一下 jieba 分词的逻辑，也是重新复习一遍中文分词的相关技术。

整体逻辑如上，对于登录词通过前两步处理，对于未登录词，使用 HMM。

进一步拆分：

对于剩下的未登录词，不知道这些字应不应该粘到一起，使用 HMM 判断。

3. 举例子

这里用一个例子带入上面的分词整体逻辑，理解分词的细节。

句子：广州本田雅阁汽车

构成 ==DAG 表示==：

如图可见，每个字用一个 id 表示。0:[0,1,3] 代表通过查字典，0 到 0：广，可以作为一个词；0 到 1：广州，可以作为一个词；0 到 3：广州本田，可以作为一个词。以此类推。

每种分词结果，比如 广州、广州本田、汽车 都有自己的概率。下一步就是找出概率最大的路径组合。

以上的概率是怎么算的？是根据词表（字典）算的。

以 汽车 为例。比如汽车在词表中的词频为 10，然后词表中所有词的词频相加为 1000，那么 p(汽车)= log(10/1000)，为了防止下溢，取个 log。

0x06 案例3：基于统计机器学习的方法

1. 马尔科夫模型

简介

每个状态只依赖之前有限个状态。 - N 阶马尔科夫：依赖之前 n 个状态 - 1 阶马尔科夫：仅仅依赖前一个状态

所以二元语言模型相当于 1 阶马尔科夫。

参数：
- 状态（S1, S2, ...）——其实在这里就相当于词语
- 初始概率
  - 比如共 1000 篇文章，其中 100 篇文章以 今天 作为开头
  - 那么 今天 的初始概率就为 100/1000
- 状态转移概率
  - 其实就是 N-Gram 中，在前 n 个词出现的条件下，当前词出现的概率

==最重要的两类概率：==

例子

p(w1=今天，w2=我，w3=写，w4=了，w5=一个，w6=程序) = p(w1=今天)p(w2=我|w1=今天)p(w3=写|w2=我)……p(w6=程序|w5=一个)

局限

马尔科夫是单序列模型，可以解决的业务问题有限。比如机器翻译、语音识别这种工作，马尔科夫是做不了的。 - 机器翻译：源语言序列 <--> 目标语言序列 - 语音识别：语音信号序列 <--> 文字序列

2. 隐马尔科夫模型 (HMM)

简介

马尔科夫是单序列建模，隐马是双序列建模。

参数：
- 状态序列（未知）
- 初始概率
- 状态转移概率
- 观察序列（已知）
- 发射概率

以机器翻译为例，解释一下上面的五个参数。比如翻译 我爱你 —> I love you。

我爱你，是已知的观察序列；I love you 是未知的状态序列（想要得到的）。
初始概率和状态转移概率同之前的马尔科夫模型一样，即代表 I 作为开头的概率，以及在前面一个词为 I 的条件下，下一个状态（词）为 love 的概率，等等。
发射概率：从状态序列到观察序列的概率。也就是说，I 翻译为 我 的概率，love 翻译为 爱 的概率，以此类推。

梳理一下整个模型的过程：首先完成第一状态，然后依次由当前状态生成下一状态，最后每个状态发射出一个观测值。

因此，最后就是寻找一个最大的联合概率。

应用

那么在 jieba 分词 中，是如何运用隐马模型将那些未登录词的单个字符粘到一起的呢？

以 广州塔 为例，假设这个词是一个未登录词。那么输入模型就是以单字输入。

如上图，以单字输入模型。

那么每个字的状态有以下几种： 1. B —— 词语开头 2. M —— 词语中间 3. E —— 词语结尾 4. S —— 单字

举例：汽车——BE 面包车——BME 天天向上——BMME 哦——S

因此通过这四种状态，预测出一个状态序列，就可以得到分词结果。

那么对应着 HMM 的五个参数，依次分析如何实现分词的隐马模型。

观察序列（已知）：广州塔
状态序列（未知）：需要预测的，预测每个位置到底是哪种状态（BMES其中之一）
初始概率（状态序列）
- 四种概率：P(B), P(M), P(E), P(S)
- 比如，有 1000 篇文章，那么去统计这些文章的第一个字的状态。比如有 800 篇，第一个字的状态为 B；有 200 篇，第一个字的状态为 S。=> 那么，P(B)=0.8，P(S)=0.2（不可能会有 E 或者 S 这两个状态，但是这两个状态概率要给一个很小的值，防止乘 0）。

在 jieba 分词的代码中印证一下。

git clone https://github.com/fxsjy/jieba.git

cd jieba/jieba/finalseg

cat prob_start.py

# 输出：
# P={'B': -0.26268660809250016,
# 'E': -3.14e+100,
# 'M': -3.14e+100,
# 'S': -1.4652633398537678}

可以看到初始概率文件中一共有四种概率，其中 E 和 M 都是给了一个接近 0 的概率值。

转移概率
- 如 P(M|B), P(E|B) 等。
- 以 P(M|B) 为例，怎么计算？
  - =>
  - 统计一共有多少 B 状态，统计出现 B 状态后出现 M 状态的次数。然后相除。

在 jieba 分词的代码中印证一下。

cd jieba/jieba/finalseg

cat prob_start.py

# 输出：
# P={'B': {'E': -0.510825623765990, 'M': -0.916290731874155},
# 'E': {'B': -0.5897149736854513, 'S': -0.8085250474669937},
# 'M': {'E': -0.33344856811948514, 'M': -1.2603623820268226},
# 'S': {'B': -0.7211965654669841, 'S': -0.6658631448798212}}

发射概率
- 如 P(广|B), P(州|M) 等。
- 以 P(广|B) 为例，怎么计算？
  - => $广$
  - 统计一共有多少 B 状态，然后统计有多少状态是B，同时这个字是“广”的次数。然后相除。

在 jieba 分词的代码中印证一下。

cd jieba/jieba/finalseg

vim prob_emit.py

输出：

以上这些概率，都是通过人工标注，然后统计得来。

总结一下，从具体落地实现的角度，分别需要三张词表。

上面的概率包含了词性。在 jieba 的这个目录可以看到：./jieba/jieba/posseg]。

其中
- BEMS 表示位置信息：B（开头）、M（中间）、E（结尾）、S（独立成词）
- 词性：n（名词）、nr（人名）、ns（地名）、v（动词）
  - 参考：中文分词词性对照表_kevin_darkelf的专栏-CSDN博客_ucn是什么词性的缩写

回顾之前的例子：广州塔

对于 HMM 的应用，最典型的就是给定 O（观察序列），找最优的 S（状态序列）。

0x07 实践

以分词为例，在实际业务落地过程中，需要批量处理与流式处理协同完成。比如当天24点之前的，昨天的数据使用批量处理；而今天过了24点，实时产生的数据使用流式处理。

使用 Hadoop 批量处理的数据可以追求模型效果，使用复杂的模型；而使用 Flink 等做流式处理的数据，需要考虑延时，追求高效性（避免阻塞），一般使用简单一些的模型，不要要求很完善的效果。

1. 批量分词

待更新

2. 增量分词（流式处理）

cd ./nlp/1.nlp-foundation/1.2.chinese-segmentation/pyweb_pg_test

pip install web.py

python main.py 8888

# 在浏览器中输入：
# http://127.0.0.1:8888/?content=南京市长江大桥

# 或者
curl http://0.0.0.0:8888/\?content\=%E5%8D%97%E4%BA%AC%E5%B8%82%E9%95%BF%E6%B1%9F%E5%A4%A7%E6%A1%A5

0x08 作业

作业： 1. 用自己的话，把“广州塔”的 HMM 逻辑大概介绍一下。 2. 用自己的话，把 Viterbi 的逻辑大概介绍一下。

面试题： > 一道面试题： > 有一个非常非常长的字符串，标记为L，这个字符串里面的每个字符不限于字母和数字，由于字符串太大了，导致内存无法存储 > 另，有M个小的字符串，最大长度为N > 问题：统计出，这些M个小字符串，一共被包含多少次？ > > 答：同使用最大长度匹配做中文分词一样，小字符串构建前缀树，长字符串每次取 N 个字符去匹配小字符串，每次匹配的起点一位一位向后移动。

Conclusion

这篇笔记比较完备地记录了中文分词从理论到实践的全过程。

中文分词的难点： - 中文不像英文天然分词，因此产生了中文分词的需求 - 以及中文分词在不同场景下的需求。 - 比如搜索场景需要分的全，检索结果完善； - 而推荐场景下，需要召回结果准确，不能分的太细，保留原始的完整语义。

中文分词的方法： - 基于字典匹配 - 基于最大长度匹配的方法 - 还有进一步改进，通过概率语言模型（N-Gram）优化的方法。 - 当然，无论是基于字典匹配或者后面的机器学习，词典都可以用前缀树来构建，提高运算的效率。 - 基于机器学习方法 - HMM - CRF

接着也了解了动态规划——Viterbi 算法。HMM 以及 N-Gram 的实现都需要借助维特比算法，找到最大概率的分词组合。或者说，如下图，类似寻找最优路径的问题，从起点到终点，有 N 个步骤，每个步骤有 M 种选择。这样的问题都可以使用 Viterbi 算法，因为当 N 较大时，相比枚举，可节省大量时间空间。

最后学习了从单序列建模的马尔科夫模型到双序列建模的隐马模型。

马尔科夫模型 - 每个状态只依赖之前有限个状态 - 1 阶马尔科夫（只依赖之前一个状态） == 二元语言模型 - 参数 - 状态序列 - 初始概率 - 转移概率

隐马尔科夫模型（HMM）： - 单序列建模的马尔科夫模型可以解决的问题有限，因此需要双序列的 HMM - 处理如机器翻译，语音识别，词性标注，拼音纠错等业务 - 机器翻译：源语言序列 <--> 目标语言序列 - 语音识别：源语音信号序列 <--> 文字序列 - 词性标注：源文字序列 <--> 词性序列 - 写/一个/程序 - Verb/Num/Noun - 参数 - 状态序列（未知） - 观察序列（已知） - 初始概率 - 转移概率 - 发射概率（从状态到观察）

并且也对以上的方法都进行了实践。不过批量分词里配置这个 Hadoop 集群环境真的，搞得太开心了 --!