jieba分词原理

结巴分词基础：https://blog.csdn.net/Sakura55/article/details/84752000html

1、 jieba系统简介

"结巴"中文分词：作最好的Python中文分词组件。python

特色：
支持三种分词模式
支持繁体分词
支持自定义词典
MIT受权协议
涉及算法：
$~~~~~~~~$基于前缀词典实现词图扫描，生成句子中汉字全部可能成词状况所构成的有向无环图（DAG），采用动态规划查找最大几率路径，找出基于词频的最大切分组合；
$~~~~~~~~$对于未登陆词，采用了基于汉字成词能力的 HMM模型，采用Viterbi算法进行计算；
$~~~~~~~~$基于Viterbi算法的词性标注；
$~~~~~~~~$分别基于tfidf和textrank模型抽取关键词；web

2、 jieba系统框架

jieba分词系统，主要实现三个模块，算法

$~~~~~~~~$分词
$~~~~~~~~$词性标注
$~~~~~~~~$关键词抽取
其中，分词有三种模式，默认是精确模式，app

$~~~~~~~~$精确模式，试图将句子最精确地切开，适合文本分析；
$~~~~~~~~$全模式，把句子中全部的能够成词的词语都扫描出来, 速度很是快，可是不能解决歧义；
$~~~~~~~~$搜索引擎模式，在精确模式的基础上，对长词再次切分，提升召回率，适合用于搜索引擎分词；框架

3、jieba分词原理

1.基于前缀词典实现高效的词图扫描，生成句子中汉字全部可能成词状况所构成的有向无环图 (DAG)
$~~~~~~~~$ 1. 根据dict.txt生成trie树，字典在生成trie树的同时, 把每一个词的出现次数转换为频率（jieba自带一个dict.txt的词典, 里面有2万多条词, 包含了词条出现的次数和词性(做者基于人民日报语料等资源训练得出来)。trie树结构的词图扫描, 说的就是把这2万多条词语, 放到一个trie树中, trie树是有名的前缀树, 也就是说一个词语的前面几个字同样, 就表示他们具备相同的前缀, 就可使用trie树来存储, 具备查找速度快的优点）。svg

$~~~~~~~~$ 2.对待分词句子, 根据dict.txt生成的trie树, 生成DAG, 通俗的讲, 就是将句子根据给定的词典进行查词典操做, 生成全部可能的句子切分。jieba在DAG中记录的是句子中某个词的开始位置, 从0到n-1(n为句子的长度), 每一个开始位置做为字典的键, value是个list, 其中保存了可能的词语的结束位置(经过查字典获得词, 开始位置+词语的长度获得结束位置）搜索引擎

$~~~~~~~~$ 3. 有向无环图构建：而后基于前缀词典，对输入文本进行切分，对于“去”，没有前缀，那么就只有一种划分方式；对于“北”，则有“北”、“北京”、“北京大学”三种划分方式；对于“京”，也只有一种划分方式；对于“大”，则有“大”、“大学”两种划分方式，依次类推，能够获得每一个字开始的前缀词的划分方式。spa

在获得全部可能的切分方式构成的有向无环图后，咱们发现从起点到终点存在多条路径，多条路径也就意味着存在多种分词结果。所以，咱们须要计算最大几率路径，也即按照这种方式切分后的分词结果的几率最大。在采用动态规划计算最大几率路径时，每到达一个节点，它前面的节点到终点的最大路径几率已经计算出来。.net

2.动态规划查找最大几率路径, 找出基于词频的最大切分组合

$~~~~~~~~$ 1.查找待分词句子中已经切分好的词语（全模式下的分词list）, 得出查找该词语出现的频率(次数/总数), 若是没有该词(基于词典通常都是有的), 就把词典中出现频率最小的那个词语的频率做为该词的频率。

$~~~~~~~~$ 2.根据动态规划查找最大几率路径的方法, 对句子从右往左反向计算最大几率(这里反向是由于汉语句子的重心常常落在后面（右边）, 由于一般状况下形容词太多, 后面的才是主干。所以, 从右往左计算, 正确率要高于从左往右计算, 这里相似于逆向最大匹配), P(NodeN)=1.0, P(NodeN-1)=P(NodeN)*Max(P(倒数第一个词))…依次类推, 最后获得最大几率路径, 获得最大几率的切分组合。

3.对于未登陆词，采用了基于汉字成词能力的 HMM 模型，使用了 Viterbi 算法

$~~~~~~~~$ 1.利用HMM模型将中文词汇按照BEMS四个状态来标记, B是开始begin位置, E是end结束位置, M是middle中间位置, S是singgle单独成词的位置。jieba采用(B,E,M,S)这四种状态来标记中文词语, 好比北京能够标注为 BE, 即 北/B 京/E, 表示北是开始位置, 京是结束位置, 中华民族能够标注为BMME, 就是开始, 中间, 中间, 结束.

$~~~~~~~~$ 2.做者利用大量语料进行训练, 获得了三个几率表。分别是1)位置转换几率，即B（开头）,M（中间),E(结尾),S(独立成词）四种状态的转移几率，P(E|B) = 0.851, P(M|B) = 0.149，说明当咱们处于一个词的开头时，下一个字是结尾的几率要远高于下一个字是中间字的几率，符合咱们的直觉，由于二个字的词比多个字的词更常见。2）位置到单字的发射几率，好比P(“和”|M)表示一个词的中间出现”和”这个字的几率；3) 词语以某种状态开头的几率，其实只有两种，要么是B，要么是S。这个就是起始向量, 就是HMM系统的最初模型状态。实际上, BEMS之间的转换有点相似于2元模型, 就是2个词之间的转移。二元模型考虑一个单词后出现另一个单词的几率，是N元模型中的一种。
$~~~~~~~~$ 3. 给定一个待分词的句子, 就是观察序列, 对HMM(BEMS)四种状态的模型来讲, 就是为了找到一个最佳的BEMS序列, 这个就须要使用viterbi算法来获得这个最佳的隐藏状态序列。经过训练获得的几率表和viterbi算法, 就能够获得一个几率最大的BEMS序列, 按照B打头, E结尾的方式, 对待分词的句子从新组合, 就获得了分词结果. 好比 对待分词的句子 ‘全世界都在学中国话’ 获得一个BEMS序列 [S,B,E,S,S,S,B,E,S], 经过把连续的BE凑合到一块儿获得一个词, 单独的S放单, 就获得一个分词结果了。

利用HMM模型进行分词，主要是将分词问题视为一个序列标注（sequence labeling）问题，其中，句子为观测序列，分词结果为状态序列。首先经过语料训练出HMM相关的模型，而后利用Viterbi算法进行求解，最终获得最优的状态序列，而后再根据状态序列，输出分词结果。

HMM的两个基本假设：

1.齐次马尔科夫性假设，即假设隐藏的马尔科夫链在任意时刻t的状态只依赖于其前一时刻的状态，与其它时刻的状态及观测无关，也与时刻t无关；

2.观测独立性假设，即假设任意时刻的观测只依赖于该时刻的马尔科夫链的状态，与其它观测和状态无关。

3.Viterbi算法其实是用动态规划求解HMM模型预测问题，即用动态规划求几率路径最大（最优路径）。

4、jieba分词过程

1. 加载字典, 生成trie树。

2. 给定待分词的句子, 使用正则获取连续的 中文字符和英文字符, 切分红 短语列表, 对每一个短语使用DAG(查字典)和动态规划, 获得最大几率路径, 对DAG中那些没有在字典中查到的字, 组合成一个新的片断短语, 使用HMM模型进行分词, 也就是做者说的识别未登陆词。

3. 使用python的yield 语法生成一个词语生成器, 逐词语返回。