jieba分词原理 ‖ 基于前缀词典及动态规划的分词实现

分词原理 ‖ 基于前缀词典及动态规划的分词实现"/>

jieba分词原理 ‖ 基于前缀词典及动态规划的分词实现

1. jieba分词原理 ‖ 基于前缀词典及动态规划的分词实现
2. jieba分词原理 ‖ 基于汉字成词能力的HMM模型识别未登录词实现
3. jieba分词原理 ‖ 词性标注
4. jieba分词原理 ‖ 关键词抽取

1 简介

jieba分词主要是基于统计词典，构造一个前缀词典；然后利用前缀词典对输入句子进行切分，得到所有的切分可能，根据切分位置，构造一个有向无环图；通过动态规划算法，计算得到最大概率路径，也就得到了最终的切分形式。

2 实例讲解

以“去北京大学玩”为例，作为待分词的输入文本。

离线统计的词典形式如下，每一行有三列，第一列是词，第二列是词频，第三列是词性。

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

2.1 前缀词典构建

首先是基于统计词典构造前缀词典，如统计词典中的词“北京大学”的前缀分别是“北”、“北京”、“北京大”；词“大学”的前缀是“大”。统计词典中所有的词形成的前缀词典如下所示，你也许会注意到“北京大”作为“北京大学”的前缀，但是它的词频却为0，这是为了便于后面有向无环图的构建。

...
北京大学 2053
北京大 0
大学 20025
去 123402
玩 4207
北京 34488
北 17860
京 6583
大 144099
学 17482
...

2.2 有向无环图构建

然后基于前缀词典，对输入文本进行切分，对于“去”，没有前缀，那么就只有一种划分方式；对于“北”，则有“北”、“北京”、“北京大学”三种划分方式；对于“京”，也只有一种划分方式；对于“大”，则有“大”、“大学”两种划分方式，依次类推，可以得到每个字开始的前缀词的划分方式。

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

0: [0]
1: [1,2,4]
2: [2]
3: [3,4]
4: [4]
5: [5]

对于0: [0]，表示位置0对应的词，就是0 ~ 0，就是“去”；对于1: [1,2,4]，表示位置1开始，在1，2，4位置都是词，就是1 ~ 1，1 ~ 2，1 ~ 4，即“北”，“北京”，“北京大学”这三个词。

对于每一种划分，都将相应