一：分词
常用的分词工具有jieba分词，snowNLP，LTP，HanNLP
1.前向最大匹配算法
现在假设我们有一个词典库{‘这些’，“这些年”，‘年’，‘的’， ‘情’，‘与’，‘爱’，‘终究’，‘是’， ‘错’，‘错付’，‘了’， ‘甄嬛’，。。。}
我们对“这些年的情与爱终究是错付了”利用前向最大匹配法进行分词。
1.首先需要设置max-len，这个参数表示每次分词时候的窗口大小。例如我这里设置为5
2.首先开始划分，将原句划分为"[这些年的情]与爱终究是错付了"，但是“这些年的情”并没有在词典库中，所以需要对这5个字逐渐缩小范围
3.缩小一个字，将2中的句子进一步划分为“[这些年的]情与爱终究是错付了”，发现“这些年的”也不在词典库中，所以要再次缩小范围
4.继续缩小范围，将3中的句子划分为“[这些年]的情与爱终究是错付了”，“这些年”在词典库中，所以可以划分出来。我们得到了第一个划分的词汇：这些年
5.接下来继续使用max_len指示的长度划分出5个字符，即“这些年[的情与爱终]究是错付了”，词典库找不到，继续缩小范围
6.缩小成“这些年[的情与爱]终究是错付了”，词典库找不到，继续缩小范围
7.缩小成“这些年[的情与]爱终究是错付了”，词典库找不到，继续缩小范围
8.缩小成“这些年[的情]与爱终究是错付了”，词典库找不到，继续缩小范围
9.缩小成“这些年[的]情与爱终究是错付了”，词典库找到了，所以得到第二个划分的词汇：的
10.接下来继续使用max_len指示的长度划分出5个字符，即“这些年的[情与爱终究]是错付了”，词典库找不到，继续缩小范围
11.缩小成“这些年的[情与爱终]究是错付了”，词典库找不到，继续缩小范围
12.缩小成“这些年的[情与爱]终究是错付了”，词典库找不到，继续缩小范围
13.缩小成“这些年的[情与]爱终究是错付了”，词典库找不到，继续缩小范围
14.缩小成“这些年的[情]与爱终究是错付了”，词典库找到，所以得到第三个划分的词汇：情
依次划分下去便可以得到“这些年 的 情 与 爱 终究 是 错付 了”
前向最大匹配算法是基于贪心算法的。
二：后向匹配算法
就是前向匹配算法倒着来啦。举个例子，划分“我们经常有意见分歧”，词典库中有{‘我们’，‘经常’，‘有’，‘有意见’，‘分歧’}，maxlen = 5
1. 划分成“我们经常[有意见分歧]”, 词典库中找不到
2.划分成“我们经常有[意见分歧]”，词典库中找不到
3.划分成“我们经常有意[见分歧]”，词典库中找不到
4.划分成“我们经常有意见[分歧]”, 词典库中找到了，所以分出来
5.继续划分“我们[经常有意见]分歧”,词典库中找不到
6.划分成“我们经[常有意见]分歧”，词典库中找不到
7.划分成“我们经常[有意见]分歧”,词典库中找到了，所以分出来
依次划分下去，将原句划分为“我们 经常 有意见 分歧”
三：维特比算法
前面介绍的最大匹配算法，除了时间复杂度很大之外，一个很大的缺陷就是，由于它是基于单词的方法，所以效果不一定会很好。例如，如果对“南京市长江大桥”进行前向最大匹配，很可能划分为“南京市长 江 大桥”。nlp的算法有针对单词的，针对语法的，针对语义的，由于前向最大匹配无法理解句子的语义，所以没办法合理划分。下面是一个基于概率统计的划分方法。
对于unigram模型，可以认为每个词汇的出现是独立的，例如P("南京 长江 大桥") = P("南京")P("长江")P("大桥")，而P("南京")，P("长江")，P("大桥")可以通过统计他们在文中出现的频率来获得。
下面举一个例子，对于如下图所示的问题
根据词典中的词汇，可以将句子划分为如下若干种：
S1：经常 有 意见 分歧
S2：经常 有意见 分歧
S3：经常 有 意 见 分歧
S4：经常 有 意 见分歧
……
然后求P(S1)，P(S2)，P(S3) ，P(S4)，……中的最大值，对应的最大值的划分就是我们需要的划分。但是由于每个单词出现的频率都是一个非常小的小数，所以P(S1)，P(S2)，P(S3) ，P(S4)，......非常小，甚至可能超过了计算机能够表达的下界，所以，我们可以把原来的问题转化为求-logP(S1)，-logP(S2)，-logP(S3) ，-logP(S4)，......的最小值即可
但是聪明的小朋友会发现，这个方法理论上可行，但是实际执行时间复杂度会非常大，例如，对于“我爱你”，可以有“我 爱 你”，“我爱 你”， “我 爱你”， “我爱你”，四种划分，对于一个长度为n的句子，最差的情况下可能有2^(n-1)种划分。
所以我们使用维特比算法，其实质就是动态规划。还是对与上面图中的这个例子
首先画出如下的图
设f(8)表示从1到8的最短路径的值，f(7)表示从1到7的最短路径的值……f(1)表示从1到1的最短路径的值。于是我们现在就是要求f(8)对应的路径。
而f(8) 是f(7) + distance(7,8), f(6)+distance(6,8), ……, f(1) + distance(1,8)的最小值，所以我们接下来求子问题f(7), f(6), ……,f(1)。使用递归的方式的话，时间复杂度还是指数级，所以使用动态规划解决。
先求f(1) = 0
而f(1) +distance(1,2)是3，所以f(2)是3
而f(1)+distance(1,3)是2.3，f(2) + distance(2,3)是23,所以f(3)是2.3
……
后面就不算了，反正写成代码就是两层嵌套循环而已，时间复杂度是O(n^2)。
这就是维特比算法了