正向最大匹配，逆向最大匹配

汉语正向、逆向最大分词算法

汉语分词最大匹配法(Maximum Matching)：

1. 正向最大匹配算法(Forward MM)
2. 逆向最大匹配算法(Backward MM)

算法

假设句子：$S = c_1c_2···c_n$，某一词：$w_i = c_1c_2···c_m$，$m$为词典中最长词的字数。 FMM 算法描述

1. 令$i=0$，当前指针$p_i$指向输入字串的初始位置，执行下面的操作：
2. 计算当前指针$p_i$到字串末端的字数（即未被切分字串的长度）$n$，如果$n=1$，转(4)，结束算法。否则，令$m=$词典中最长单词的字数，如果$n<m$，令$m=n$。
3. 从当前$p_i$起取$m$个汉字作为词$w_i$，判断： 3.1. 如果$w_i$确实是词典中的词，则在$w_i$后添加一个切分标志，转(3.3); 3.2. 如果$w_i$不是词典中的词且$w_i$的长度大于1，将$w_i$从右端去掉一个字，转(3.1)步；否则（$w_i$的长度等于1），则在$w_i$后添加一个切分标志，将$w_i$作为单字词添加到词典中，执行(3.3)步； 3.3. 根据$w_i$的长度修改指针$p_i$的位置，如果$p_i$指向字串末端，转(4)，否则，$i=i+1$，返回(2)；
4. 输出切分结果，结束分词程序。

逆向最大匹配算法同理。

数据

人民日报语料，总共100344条样本。 样例：’/w ９９/m 昆明/ns 世博会/n 组委会/j 秘书长/n 、/w 云南省/ns 副/b 省长/n 刘/nr 京/nr 介绍/v 说/v ，/w ’/w ９９/m 世博会/j

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# -*- coding:utf-8 -*-
from collections import defaultdict
import numpy as np
import matplotlib.pyplot as plt
import seaborn
plt.style.use('fivethirtyeight')

def readFile(filename):
    '''
    read file return a generator, each element is one line
    
    Parameters