1.前向最大匹配算法

例子：我们经常有意见分歧
词典：['我们', '经常', '有', '有意见', '意见', '分歧']

对于上面的例子我们应用前向最大匹配算法怎么分词呢，步骤如下：

确定最大长度max_len, 也就是说我们是在max_len这个长度内寻找匹配的字符串，这里我们不妨令max_len=5。
将例子分割为[我们经常有] 意见分歧,看前面5个词'我们经常有'是否在词典库中，我们查看发现不在。
接着分割为[我们经常] 有意见分歧,看这4个词'我们经常'是否在词典库中，查看发现依然不在。
继续分割为[我们经] 常有意见分歧,看这3个词'我们经'是否在词典库中，查看发现不在。
继续分割为[我们] 经常有意见分歧,看这2个词'我们'是否在词典库中，查看发现在词典库，那么'我们'就被分割出来,原例子变成我们 | 经常有意见分歧。
然后从'经'字开始往后数max_len个单词重复前面步骤。
最后分割完的句子为我们 | 经常 | 有意见 | 分歧。

python实现如下：

s = '我们经常有意见分歧'
dic = ['我们', '经常', '有', '有意见', '意见', '分歧']

def forward_max_seg(s, dic, max_len):
    p1, p2 = 0, min(max_len-1, len(s)-1)
    res = []
    while p1 <= p2:
        if s[p1:p2+1] in dic:
            res.append(s[p1:p2+1])
            p1 = p2 + 1
            p2 = min(p1 + max_len-1, len(s)-1)
        else:
            p2 -= 1
    return res

res = forward_max_seg(s, dic, 5)
print('|'.join(res))

输出为：

我们|经常|有意见|分歧

2.后向最大匹配算法

例子：我们经常有意见分歧
词典：['我们', '经常', '有', '有意见', '意见', '分歧']

后向匹配跟前向匹配方向相反，过程如下：

同样需要确定最大长度max_len, 这里我们也令max_len=5。
从后往前看将例子分割为我们经常 [有意见分歧],看后面5个词'有意见分歧'是否在词典库中，我们查看发现不在。
接着分割为我们经常有 [意见分歧],看这4个词'意见分歧'是否在词典库中，查看发现依然不在。
继续分割为我们经常有意 [见分歧],看这3个词'见分歧'是否在词典库中，查看发现不在。
继续分割为我们经常有意见 [分歧],看这2个词'分歧'是否在词典库中，查看发现在词典库，那么'分歧'就被分割出来,原例子变成我们经常有意见 | 分歧。
然后从'见'字开始往前数max_len个单词重复前面步骤。
最后分割完的句子为我们 | 经常 | 有意见 | 分歧。
python实现如下：

def backward_max_seg(s, dic, max_len):
    p1, p2 = max(len(s)-max_len, 0), len(s)-1
    res = []
    while p1 <= p2:
        if s[p1:p2+1] in dic:
            res.insert(0, s[p1:p2+1])
            p2 = p1-1
            p1 = max(p2-max_len+1, 0)
        else:
            p1 += 1
    return res
res = backward_max_seg(s, dic, 5)
print('|'.join(res))

输出：

我们|经常|有意见|分歧

3.双向最大匹配法

算法流程：
比较正向最大匹配和反向最大匹配结果：

如果分词数量结果不同，那么取分词数量较少的那个
如果分词数量结果相同：
- 分词结果相同，可以返回任何一个
- 分词结果不同，返回单字数比较少的那个

上面的例子两种分法一致，所以选任何一个都可以，下面看另一个例子：

例子：北京大学生前来应聘
词典：['北京大学', '北京', '大学生','生前', '来', '应聘']

正向匹配最终切分结果为：北京大学 | 生前 | 来 | 应聘，分词数量为 4，单字数为 1
反向匹配最终切分结果为：”北京 | 大学生 | 前来 | 应聘，分词数量为 4，单字数为 0

因此选择反向匹配的结果作为最终结果

最大匹配算法缺点：

找到的是局部最优解
严重依赖于max_len的大小，当max_len特别大时，效率会很低
无法考虑语义信息

3. 考虑语义的分割-维特比(viterbi)算法

例子：经常有意见分歧
词典：['有', '有意见', '意见', '分歧', '见', '意']

前面讲到最大匹配算法是无法考虑语义信息的，那么如果要考虑语义信息应该怎么做呢？
最直接的想法是分成两步，step1:将句子的所有可能分割方式分割出来，step2:选出这些分法中哪个最好最合乎常理的，过程表示如下：

语义分割过程示意图

比如step1得到了所有可能的分割：
s1 = 经常 | 有 | 意见 | 分歧
s2 = 经常 | 有| 意 | 见 | 分歧
s3 = 经常 | 有意见 | 分歧
......
那么step2如何选出最好的呢，,最简单的一种方式是 unigram，拿s1和s2的比较举例：
p(s1) = p(经常, 有, 意见,分歧) = p(经常)p(有)p(意见)p(分歧)
p(s2) = p(经常, 有, 意, 见,分歧) = p(经常)p(有)p(意)p(见)p(分歧)
就是比较p(s1)和p(s2)哪个大，选择大的那个。
即使我们使用最简单的unigram，我们也会发现这种做法进行了大量的重复性工作，效率很低。那么怎么解决效率问题呢，一种途径就是将两步合并，用DP(动态规划)进行优化，提升效率，也就是接下来要讲的维特比算法。

例子：经常有意见分歧
词典: ['经常', '经', '有', '有意见', '意见', '分歧', '见', '意', '见分歧', '分']
概率：[0.1, 0.05, 0.1, 0.1, 0.2, 0.2, 0.05, 0.05, 0.05, 0.1]
-log(概率):[2.3, 3, 2.3, 2.3, 1.6,1.6, 3, 3, 3, 2.3]

维特比算法示意图

算法流程：
用图来表示，边权重表示这个这个字的-log概率，遍历词典，将各概率标注如下图，将未出现的词用较大的数表示，这里用20表示。因为使用-log，这里权重和最小也就是原概率乘积最大问题。原问题为：找到一种划分使得这种划分的概率乘积最大，那么现在原问题就转化成找到一条路径从节点1到节点8，使权重和最小，就能用DP解决。

DP算法流程：
做如下定义：
f(8):从节点1到节点8的最短路径
f(7):从节点1到节点7的最短路径
......
那么
f(8) = min(f(7)+20, f(6)+1.6, f(5)+3)
f(7) = f(6)+2.3
f(6) = min(f(5)+3, f(4)+1.6, f(3)+2.3)
......