分词的实现
分词（word segmentation）
根据输入的文本，如何进行分词呢？当然可以调用一些常用的分词工具包，例如：
Jieba分词 https://github.com/fxsjy/jieba
SnowNLP https://github.com/isnowfy/snownlp
LTP http://www.ltp-cloud.com/
HanNLP https://github.com/hankcs/HanLP/
比较常用的是jieba分词和LTP分词
那这些工具的内部实现方法有很多（如最大匹配法，HMM等）
下面介绍几个分词方法：
Segmentation Method 1
Max matching(最大匹配)
(1)前向最大匹配法（forward-max matching）
例⼦：我们经常有意⻅分歧
词典：[“我们”, “经常”, “有”, “有意⻅”，“意⻅”，“分歧”]
假设我们设置max_len参数为5（每次读取的长度）
①
我们经常有 false（这五个字没在字典中）
我们经常 false (这四个字没在字典中)
我们经 false
我们 True
②
经常有意⻅ false（这五个字没在字典中）
经常有意 false（这4个字没在字典中）
经常有 false（这3个字没在字典中）
经常 True
③
有意⻅分歧 false（这五个字没在字典中）
有意⻅分 false（这4个字没在字典中）
有意⻅ True
④“分歧” True
上边就是forward-max maching的流程
(1)后向最大匹配法（backward-max matching）
例⼦：我们经常有意⻅分歧
词典：[“我们”, “经常”, “有”, “有意⻅”，“意⻅”，“分歧”]
假设我们设置max_len参数为5（每次读取的长度）
①
有意⻅分歧 false（这五个字没在字典中）
意⻅分歧 false
⻅分歧 false
分歧 true
。。。。。。（下边同上 直到将文本遍历完）
以上两种匹配方法 9:1 (匹配结果相同：匹配结果不同)
缺点：
局部最优（这是一个贪心算法）
效率（与max_len有关）
语义（不能考虑语义）
上边这个例子的分词结果并不是理想的
max maching结果：我们 | 经常 | 有意⻅ | 分歧
理想结果：我们 | 经常 | 有 | 意⻅ | 分歧
所以接下来我们将语义考虑进来
Segmentation Method 2
Incorporate Semantic（考虑语义）
分词后的结果—>（工具）—>最有的结果
这个工具可以根据分词结果产生一个概率值来判断 符合语义的可能性
建立下边的流程图
举例说明：
例⼦：经常有意⻅分歧
词典：[ “经常”, “有”, “有意⻅”，“意⻅”，“见”,”意“,分歧”]
用算法生成所有的分词结果
经常 | 有 意⻅| 分歧 s1
经常 | 有 |意 | ⻅ | 分歧 s2
经常 | 有意⻅ |分歧 s3
经常 | 有意⻅|分歧 s4
…
接下来选择最好的结果（这个其实就是语言模型（Language Model））
语言模型 有多种 这里首先介绍（unigram Language Mode）
p(S)=p(w1,w2,w3,w4,w5,…,wn)
=p(w1)p(w2|w1)p(w3|w1,w2)...p(wn|w1,w2,...,wn-1)//链规则
p(S)被称为语言模型，即用来计算一个句子概率的模型。
这个链式法则 计算起来 参数过大，无法实用。
所以可以根据马尔可夫假设 （Markov Assumption）假设每个单词只和前边的几个词有关系
unigram Language Mode 就是假设每个单词是独立的
p(s1)=p(经常)*p( 有意⻅)*p( 分歧)
p(s2)=p(经常)(有) (意)(⻅ )(分歧)
…
因为概率相乘的话 得到的值非常小可能造成溢出问题
所以我们对等号的两边加上log不影响不同分词结果的概率大小关系
所以上边的式子可以表示为
log( p(s1) )=log( p(经常)
p( 有意⻅)
p( 分歧) )
log( p(s2) )=log( p(经常)(有) (意)(⻅ )(分歧) )
…
由log(a
b
)=loga+logb
所以：
log( p(s1) )=log( p(经常) ) +log（ p( 有意⻅) ）+log( p( 分歧) )
log( p(s2) )=log(p(经常))+log((有)) log ((意) ) log( (⻅ ) )+log ((分歧) )
…
转换成log形式 方便计算并不影响结果
上边这个方法可以明显看出复杂度比较高，（表示出所有的分词结果）。
那我们如何来提高效率呢？
我们采用维特比算法 。
维特比算法
维特比算法是一种动态规划算法用于寻找最有可能产生观测事件序列的-维特比路径-隐含状态序列。
维特比算法解决的是节点图的
最短路径问题
而这种
最短路径
恰好就是最符合语义的一组序列。
