中文分词
中文分词算法及实现
主流方法
中文分类方法大致可以分为以下三类:
- 基于词表的分词方法
- 正向最大匹配法FMM
- 逆向最大匹配法BMM
- N-最短路径方法
- 基于统计模型的分词方法
- 基于n-gram语言模型的分词方法
- 基于序列标注的分词方法
- 基于HMM的分词方法
- 基于CRF的分词方法
- 基于词感知机的分词方法
- 基于深度学习的端到端的分词方法
评价指标
准确率(Precision)
召回率(Recall)
F-测度
未登录词的召回率(ROOV)
- 词典词的召回率(RIV)
基于词表的最大匹配方法
正向最大匹配和反向最大匹配算法实际上都是通过贪心的方法依据词典切分出当前位置上长度最大的词,只是两种方法对于句子的处理方向不同而已。FMM实质上是很简单粗暴的匹配方法,对于一些歧义词的处理能力很一般。一般来说,BMM方法要优于FMM方法,但现在是几乎不会使用这种基于匹配的方法了。
BMM算法:
逆向匹配法思想与正向一样,只是从右向左切分,这里举一个例子:
输入例句:S1=”计算语言学课程有意思” ;
定义:最大词长MaxLen = 5;S2= “ “;分隔符 = “/”;
假设存在词表:…,计算语言学,课程,意思,…;
最大逆向匹配分词算法过程如下:
(1)S2=””;S1不为空,从S1右边取出候选子串W=”课程有意思”;
(2)查词表,W不在词表中,将W最左边一个字去掉,得到W=”程有意思”;
(3)查词表,W不在词表中,将W最左边一个字去掉,得到W=”有意思”;
(4)查词表,W不在词表中,将W最左边一个字去掉,得到W=”意思”
(5)查词表,“意思”在词表中,将W加入到S2中,S2=” 意思/“,并将W从S1中去掉,此时S1=”计算语言学课程有”;
(6)S1不为空,于是从S1左边取出候选子串W=”言学课程有”;
(7)查词表,W不在词表中,将W最左边一个字去掉,得到W=”学课程有”;
(8)查词表,W不在词表中,将W最左边一个字去掉,得到W=”课程有”;
(9)查词表,W不在词表中,将W最左边一个字去掉,得到W=”程有”;
(10)查词表,W不在词表中,将W最左边一个字去掉,得到W=”有”,这W是单字,将W加入到S2中,S2=“ /有 /意思”,并将W从S1中去掉,此时S1=”计算语言学课程”;
(11)S1不为空,于是从S1左边取出候选子串W=”语言学课程”;
(12)查词表,W不在词表中,将W最左边一个字去掉,得到W=”言学课程”;
(13)查词表,W不在词表中,将W最左边一个字去掉,得到W=”学课程”;
(14)查词表,W不在词表中,将W最左边一个字去掉,得到W=”课程”;
(15)查词表,“意思”在词表中,将W加入到S2中,S2=“ 课程/ 有/ 意思/”,并将W从S1中去掉,此时S1=”计算语言学”;
(16)S1不为空,于是从S1左边取出候选子串W=”计算语言学”;
(17)查词表,“计算语言学”在词表中,将W加入到S2中,S2=“计算语言学/ 课程/ 有/ 意思/”,并将W从S1中去掉,此时S1=””;
(18)S1为空,输出S2作为分词结果,分词过程结束。
class BMM(object):
def __init__(self,
dict_path='./dict.txt',
max_word_length=5,
split_mark='/'):
self.dict = self.load_dict(_get_abs_path(dict_path))
self.max_word_length = max_word_length
self.split_mark = split_mark
def load_dict(self, path):
word_dict = []
with open(path, 'r', encoding='utf-8') as fr:
for line in fr:
word = line.strip().split(' ')[0]
word_dict.append(word)
return word_dict
def seg(self, line):
"""
seg the line into word list
"""
word_list = []
s1 = line[-self.max_word_length:]
while len(s1):
if s1 in self.dict or len(s1) == 1:
word_list.append(s1)
s1 = line[:len(line)-len(''.join(word_list))]
else:
s1 = s1[1:]
return self.split_mark.join(word_list[::-1])
基于n-gram语言模型的分词方法
假设$S$表示一个有意义的句子,由一连串特定顺序排列的词$w_{1}, w_{2},…., w_{n}$组成,则此句子成立的概率为
$P(S)$称为语言模型,就是建立了一个基于统计的模型去计算一个序列$S$的可能性。
N-gram就是语言模型。对于前面提到的语言模型从计算上来看,序列的前两个词的条件概率 不难计算,但是,越到后面的单词可能性越多,无法估算。因此,引入马尔可夫假设:任意一个词出现的概率只和它前面的几个词有关,于是
,这就是N-gram模型中的二元模型(bigram)。同理,可得到一元模型(unigram)、三元模型(trigram)的定义。
求解概率:
$P\left(w_{i} | w_{i-1}\right)=\frac{P\left(w_{i-1}, w_{i}\right)}{P\left(w_{i-1}\right)}$
当训练集语料库足够大,通过其相应的词和词对的频数,相对频度就约等于概率。所以BI-gram分词时,有以下步骤:
- 首先要准备一个足够大语料库作为训练集,对此语料库构造出词频统计字典和每个词之后的词频度字典
- 要分词的语句首先找出所有可能的备选分词结果,根据词频统计字典中出现的键递归寻找。
- 对每个分词结果,计算其相应的概率$P$,输出最大的就为分词结果。而怎么计算$P$可见下面的代码
def _get_prob(self, result):
"""
计算每种情况的概率分数
"""
p = 1.0
for index in range(len(result)):
if index == 0:
if result[index] in self.word_count:
# 第一项a在词频表中,p = (count(a) + 1) / count(all)
p *= ((self.word_count[result[index]] + 1) / self.length)
else:
# 若不在则 p = 1 / count(all)
p *= (1 / self.length)
else:
if result[index - 1] in self.word2_dict and \
result[index] in self.word2_dict[result[index - 1]]:
# 若前一项a存在于gram表,且下一项b存在于它对应的value中
# p = (count(b|a) + 1) / count(|a)
p *= ((self.word2_dict[result[index - 1]][result[index]] + 1) /
self.word_next_count[result[index - 1]])
elif result[index - 1] in self.word2_dict:
# 若前一项a存在于gram表,但下一项b不存在于它对应的value中
# p = 1 / count(|a)
p *= (1 / self.word_next_count[result[index - 1]])
else:
p = p * pow(0.1, 10)
return p
参考
- 比赛SIGHAN官网
- 中文分词入门之最大匹配法