分词算法

因为汉语单字成词的特色,正向最小匹配和逆向最小匹配通常不多使用通常说来,逆向匹配的切分精度略高于正向匹配,遇到的歧义现象也较少算法

1、最大正向匹配算法数据库

一般简称为MM法。其基本思想为:假定分词词典中的最长词有i个汉字字符,则用被处理文档的当前字串中的前i个字做为匹配字段,查找字典。若字典中存在这样的一个i字词,则匹配成功,匹配字段被做为一个词切分出来。若是词典中找不到这样的一个i字词,则匹配失败,将匹配字段中的最后一个字去掉,对剩下的字串从新进行匹配处理……  如此进行下去,直到匹配成功,即切分出一个词或剩余字串的长度为零为止。这样就完成了一轮匹配,而后取下一个i字字串进行匹配处理,直到文档被扫描完为止。spa

例子:“今天来了许多新同事’”
假设:正向最大匹配方式,最大长度为5 (即词库词典中最长的词长度为5)
今天来了许 
今天来了 
今天来 
今天  >>>>>>> 获得一个词:今天 
来了许多新 
来了许多 
来了许 
来了 
来  >>>>>>>>> 获得一个词:来 
了许多新同 
了许多新 
了许多 
了许 
了 >>>>>>>>> 获得一个词: (在实际生产环境 “了”会被做为停用词过滤掉)
许多新同事 
许多新同 
许多新 
许多  >>>>>>>>> 获得一个词:许多 
新同事 
新同 
新  >>>>>>>>> 获得一个词:新 
同事  >>>>>>>>> 获得一个词:同事 

最后正向最大匹配的结果是: 
/今天/来/了/许多/新/同事/ 
orm

2、逆向最大匹配文档

一般简称为RMM法。RMM法的基本原理与MM法相同 ,不一样的是分词切分的方向与MM法相反,并且使用的分词辞典也不一样。逆向最大匹配法从被处理文档的末端开始匹配扫描,每次取最末端的i个字符(i字字串)做为匹配字段,若匹配失败,则去掉匹配字段最前面的一个字,继续匹配。相应地,它使用的分词词典是逆序词典,其中的每一个词条都将按逆序方式存放。在实际处理时,先将文档进行倒排处理,生成逆序文档。而后,根据逆序词典,对逆序文档用正向最大匹配法处理便可。it

例子:“今天来了许多新同事’”
假设:正向最大匹配方式,最大长度为5 (即词库词典中最长的词长度为5)效率

许多新同事 
多新同事 
新同事 
同事 ====》获得一个词:同事 
来了许多新 
了许多新 
许多新 
多新 
新 ====》获得一个词:新 
天来了许多 
来了许多 
了许多 
许多 ====》获得一个词:许多 
今天来了 
天来了 
来了 
了 ====》获得一个词:了 
今天来 
天来 
来 ====》获得一个词:来 
今天 ====》获得一个词:今天 

最后反向最大匹配的结果是: 
/今天/来/了/许多/新/同事/ 基础

正向最大匹配和反向最大匹配的结果并不必定都相同 
例子:’我一我的吃饭’ 
1.正向最大匹配方式,最大长度为5 
我一我的吃 
我一我的 
我一个 
我一 
我 ====》获得一个词: 我 
一我的吃饭 
一我的吃 
一我的 
一个 ====》获得一个词:一个 
人吃饭 
人吃 
人 ====》获得一个词:人 
吃饭 ====》获得一个词:吃饭 

最后正向最大匹配的结果是: 
/我/一个/人/吃饭/ 

2.反向最大匹配方式,最大长度为5 
一我的吃饭 
我的吃饭 
人吃饭 
吃饭 ====》获得一个词:吃饭 
我一我的 
一我的 
我的 ====》获得一个词:我的 
我一 
一 ====》获得一个词:一 
我 ====》获得一个词:我 

最后反向最大匹配的结果是: 
/我/一/我的/吃饭/ 
此次两种方式的结果就不一致了。 原理

3、双向匹配方法

将正向最大匹配法与逆向最大匹配法组合。先根据标点对文档进行粗切分,把文档分解成若干个句子,而后再对这些句子用正向最大匹配法和逆向最大匹配法进行扫描切分。若是两种分词方法获得的匹配结果相同,则认为分词正确,不然,按最小集处理

4、最少切分法

使每一句中切出的词数最少

5、全切分

全切分要求得到输入序列的全部可接受的切分形式,而部分切分只取得一种或几种可接受的切分形式,因为部分切分忽略了可能的其余切分形式,因此创建在部分切分基础上的分词方法无论采起何种歧义纠正策略,均可能会遗漏正确的切分,形成分词错误或失败。而创建在全切分基础上的分词方法,因为全切分取得了全部可能的切分形式,于是从根本上避免了可能切分形式的遗漏,克服了部分切分方法的缺陷。

全切分算法能取得全部可能的切分形式,它的句子覆盖率和分词覆盖率均为100%,但全切分分词并无在文本处理中普遍地采用,缘由有如下几点:

1)全切分算法只是能得到正确分词的前提,由于全切分不具备歧义检测功能,最终分词结果的正确性和彻底性依赖于独立的歧义处理方法,若是评测有误,也会形成错误的结果。

2)全切分的切分结果个数随句子长度的增加呈指数增加,一方面将致使庞大的无用数据充斥于存储数据库;另外一方面当句长达到必定长度后,因为切分形式过多,形成分词效率严重降低。