分词算法

先要简单介绍一下已知的常规算法:正向最大匹配法(FMM)、逆向最大匹配法(BMM)和双向最大匹配法(Bi-MM)。

然后再介绍的算法均基于相关系数\(\gamma\)。包括:双向最大匹配算法(\(\gamma\) Bi-MM),最小频次匹配算法(MF-MM),最大相关系数匹配算法(\(\gamma\) MM),最大相关系数循环匹配算法(\(\gamma^+\) MM)。这四种算法是作者自己研究出的算法,其中有些已经在前面的文章简单介绍过,有些则是首次介绍。还有些作者尝试过的算法,因为效果不理想,本文中只会简单提一下,并不作详细介绍。

分词算法的重点是什么?这个是一个十分重要的问题。这个是算法设计时的目标。只有确定好这个目标,才能想清楚什么是该做的事情。
语言是十分灵活的,这也导致了其形式变化多端,很难把握。但是语言学家还是能找到一些规律,否则就不会有汉语语法一说。对于编程人员来说,机器自然没有人类这样的理解能力。那么这些机器可以理解的规律到底是什么?

作者将分词算法的重点归结为:“锚”。
所谓锚,就是语句之中一成不变的部分。这些部分可以将语句切分成左右两个部分。而且一般情况下,左右两边的内容并不直接相关。这样的锚越多,语句就越容易切分。那么语句之中,哪些部分适合做“锚”呢?
名词、动词、形容词这些词汇数量大,变化多,而且很多具有兼类的性质,并不太适合。作者最初想到的就是虚词。虚词的种类相对有限,出现的频次高,而且变化相对较少。因此,最初以虚词为“锚”对语句进行切分,然后再使用双向最大匹配法。结果发现,以虚词做锚的效果并不理想。
在发现和研究了相关系数\(\gamma\)之后,作者才发现了一个新的“锚”。

最大匹配算法

常规的最大匹配算法包括:正向最大匹配法(FMM)、逆向最大匹配法(BMM)和双向最大匹配法(Bi-MM)。这些算法在互联网上可以找到介绍的资料。这里不再详细一一介绍。这里要说的是最大匹配算法与相关系数\(\gamma\)之间关系。

我们知道字符串\(\{s_1,s_2,…..,s_N\}\)的相关系数公式如下:

\[\gamma (s|s_1s_2…s_n) = \frac {f}{N} \sum \limits_{i=1}^N \frac {1}{f_i}\]

采用最大匹配法做分词算法时,对公式里面的两个参数有影响:

(1) \(N\)值降低。
字符串越长,所需要分成的份数就越少。因此\(N\)值降低。

(2)\(f_i\)值降低
由前面的性质可以知道:字符串越长,其对应的频次会降低。

两个因素叠加起来,会使得相关系数\(\gamma\)的数值提高。某种意义上:最大分词算法是一种相关系数\(\gamma\)速升的方法。这里的证明是不完备的,只能做出简单的定性分析结论。

不过根据“人择原理”:\(N\)值和\(f_i\) 能降低到何种程度,完全受制于语料库。如果语料库中不存在某个字符拼接组合,就需要回归到按单字进行分析和计算。这点上也与最大分词算法的具体步骤相吻合。

双向最大匹配算法(\(\gamma\) Bi-MM,简称:Mx算法)

基于相关系数\(\gamma\)的双向最大匹配算法,是在双向匹配算法的基础上利用相关系数\(\gamma\)做量化处理,并协助抉择的一种算法。

双向最大匹配算法可以简单描述为:将字符串\(s\)分为两段。左侧的一段实施逆向最大匹配算法,右侧的一段实施正向最大匹配算法。最后将两者的结果进行合并即可。从这个角度来说,正向最大匹配算法和逆向最大匹配算法只是双向最大匹配算法的两个特列而已。

为了找到所有路径,就要逐个访问字符串\(s\)的“分割点”。在路径去重后,就可以得到所有最有利于相关系数\(\gamma\)升值的路径。虽然不是所有路径,但是这些路径一定是最有利于提升相关系数\(\gamma\)数值的路径。所有路径的相关系数\(\gamma\)最大值以及“最优”路径必然在所提取到的其中一条路径上。
这里所说的“最优”,就是指使用者觉得满意的一种分词划分。双向最大匹配算法所得的各条路径中,必能找到一条令使用者满意的分词划分(前提:词典库的全部数据令使用者满意)。
这个“最优”路径和具有相关系数\(\gamma\)最大值的路径未必总是重叠的。很多情况下,“最优”路径会与正向最大匹配算法的路径相重合。这也是正向匹配算法大受欢迎的原因:简单而且有效。这个也主要符合汉语目前的阅读习惯:从左至右。

双向最大匹配算法的结果是一组路径。每条路径的因初始分割点不同,而结果有所不同。以字符串最左侧(索引为0)作为分割点的路径可以简称为M0算法,其等同于FMM算法。以字符串最右侧(索引为字符串长度)作为分割点的路径可以简称为Mx算法,其等同于BMM算法。以字符串中间某个位置为分割点的算法,可以称为M1,M2,M3……等等。应用时,某些路径会完全相互重合,此时只要选定其中一条即可。

最小频次匹配算法(MF-MM,简称:C算法)

最小频次匹配算法,算是基于相关系数\(\gamma\)的一种派生算法。此算法并未使用到相关系数\(\gamma\)的任何具体数值。

根据相关系数\(\gamma\)的公式,可以发现:字符串的相关系数\(\gamma\)主要取决于频次最低的那个字符串
很多时候,字符串的统计频次并不在一个数量级上。频次多的可达几百万,几十万,少的只有几百。因此对相关系数\(\gamma\)的数值贡献主要取决于频次最低的那个字符串。从阅读的角度来说:一个很少出现的词汇,应该总是能引起读者的注意。
因此,如果以这个频次最小的字符串做锚点,就可以将语句一分为二。然后再分别在左右两边寻找频次最低的字符串。如此递归,循环直至分到不能再分为止。切分完成之后,再利用深度优先遍历算法,将结果收集起来。最终,就可以得到一个完整的分割路径。绝大多数情况下,这条路径是双向最大匹配算法中的一条路径。

最大相关系数匹配算法( \(\gamma\) MM,简称:R算法)

最大相关系数匹配算法需要用到相关系数\(\gamma\)的计算和数据。这些数据应当在字典库中,提前准备好。
在这个准备过程中要注意一个问题:最大相关系数匹配算法需要用到相关系数。而长度超过两个字符以上的字符串有多个相关系数。在选择合适的分割方法以及相关系数时,又需要依赖本算法。这相互之间的依赖关系会导致“死循环”。
因此,计算时需要按照字符串的长度排序。优先计算字符串长度小的字符串,再计算字符串长度大的字符串。只有这样,这个死结才可以解开。否则,数据将是混乱不堪的,可能无法得到正确的结果。

根据相关系数\(\gamma\)的性质,可以知道:相关系数越大,则两者相关程度越高。最高可以达到1。
例如:如果语句中出现了“葡萄”,“垃圾”这类相关系数几乎为1的词汇,那么它们是最适合做“锚”点的。
因此,如果以相关系数最大的字符串做锚点,就可以将语句一分为二。然后再分别在左右两边寻找相关系数最大的字符串。如此递归,循环直至分到不能再分为止。切分完成之后,再利用深度优先遍历算法,将结果收集起来。最终,就可以得到一个完整的分割路径。绝大多数情况下,这条路径也是双向最大匹配算法中的一条路径。

最大相关系数匹配算法有两点需要注意的:
(1)某个字符串可能无法查到相关系数\(\gamma\)的具体数值,导致分割无法进行下去。
如果遇到这种情况,直接按单一字符拆分进行处理。即字符串有多长,就拆分多少个字符出来。或者在词典库中增加合适的数据,以保证拆分可以正确进行下去。
(2)该算法有一个明显偏向:不会选择字符较长的字符串。
这个是相关系数\(\gamma\)的特点所决定的。字符串越长,相关系数值一般会越低。因此,该算法偏向于选择较短的字符串。对于想尽量细致切分的用户来说,这个算法应是比较合适的。而对于另外一些喜欢短语的用户来说,可能达不到想要的效果。

最大相关系数循环匹配算法( \(\gamma^+\) MM,简称:R+算法)

最大相关系数循环匹配算法是在最大相关系数匹配算法的基础上做了一点改进。

前面谈到的最大相关系数算法有两个需要注意的问题。这两个问题都是由于相关系数\(\gamma\)的特点而产生的。为了使问题得到解决,再在最大相关系数匹配算法结果的基础上,增加依据最大相关系数\(\gamma\)的合并算法。

在最大相关系数匹配算法的基础上,字符串已经被分成了多段。其中不少字符串都是锚点。那么只需要以这些锚点为基础再逐一把能合并的进行合并,那么就可以得到比较理想的结果。合并的依据依然是最大相关系数\(\gamma\) 。

该算法会顺序扫描多段字符串,将字符串全部进行尽可能的合并。
(1)所有的合并必须依据词典库
合并后的字符串,如果在词典库中不存在。那么这个合并是无效的。
(2)依据被分割的多段,尽可能的进行多种合并。
即:要获得全部的可能合并项,并计算或者查找出其对应的相关系数\(\gamma\)。最后选择相关系数\(\gamma\)最大的那个字符串作为合并后的字符串。
(3)合并完成后,递归循环再次进行合并算法,直至无法合并为止。
终止条件:在词典库中查不到任何可以合并的项目。

最后这个得到的路径就是最终路径。这个路径,多数情况下也是双向最大匹配算法中的一条路径。其最终效果要胜于前几种的算法。由于该算法完成了一次自顶向下的分解,以及一次自底向上的合并,所以作者将其成为循环算法。

经过实测,R+算法相比于其他几种算法,能解决很多其他算法所遭遇的“歧义”问题。其分词结果也更符合阅读习惯。而且算法实现难度也不算太大。这也是目前作者推荐的分词算法。

实例

下面将给出一个分割的实例。

----------------------------------------
打印ShortContent.GetContent(38937459)内容!
----------------------------------------
我们已经离开了市区
----------------------------------------
打印CoreSegment.Split(38937459)内容!
----------------------------------------
11:59:40 >      Value = "我们已经离开了市区"
11:59:40 >      Count = 2
11:59:40 >      Method = M[1]|-|-|-
11:59:40 >      Gamma = 0.00003158
11:59:40 >      [0]("我" : 6316123 |代词) = 1.00000000
11:59:40 >      [1]("们" : 3267339 |助词.后缀) = 1.00000000
11:59:40 >      [2]("已经" : 936262 |副词) = 0.47659987
11:59:40 >      [3]("离开了" : 26114) = 0.08388353
11:59:40 >      [4]("市区" : 25552 |名词.地名) = 0.01776326
11:59:40 >      Method = M[3]|-|-|-
11:59:40 >      Gamma = 0.00003175
11:59:40 >      [0]("我们" : 1092735 |代词) = 0.25372456
11:59:40 >      [1]("已" : 1650773 |动词|副词) = 1.00000000
11:59:40 >      [2]("经" : 2425336 |动词|介词|名词|名词.姓氏) = 1.00000000
11:59:40 >      [3]("离开了" : 26114) = 0.08388353
11:59:40 >      [4]("市区" : 25552 |名词.地名) = 0.01776326
11:59:40 >      Method = M[2]|-|-|-
11:59:40 >      Gamma = 0.00003971
11:59:40 >      [0]("我们" : 1092735 |代词) = 0.25372456
11:59:40 >      [1]("已经" : 936262 |副词) = 0.47659987
11:59:40 >      [2]("离开了" : 26114) = 0.08388353
11:59:40 >      [3]("市区" : 25552 |名词.地名) = 0.01776326
11:59:40 >      Method = M[5]|-|-|-
11:59:40 >      Gamma = 0.00006191
11:59:40 >      [0]("我们已经" : 8823) = 0.00874894
11:59:40 >      [1]("离" : 559258 |动词|介词) = 1.00000000
11:59:40 >      [2]("开" : 2369942 |动词|量词|名词.姓氏) = 1.00000000
11:59:40 >      [3]("了" : 11661970 |动词|助词) = 1.00000000
11:59:40 >      [4]("市区" : 25552 |名词.地名) = 0.01776326
11:59:40 >      Method = M[8]|-|-|-
11:59:40 >      Gamma = 0.00007651
11:59:40 >      [0]("我们已经" : 8823) = 0.00874894
11:59:40 >      [1]("离开了" : 26114) = 0.08388353
11:59:40 >      [2]("市" : 2129304 |名词) = 1.00000000
11:59:40 >      [3]("区" : 1086101 |名词|名词.姓氏) = 1.00000000
11:59:40 >      Method = M[6]|-|-|-
11:59:40 >      Gamma = 0.00007945
11:59:40 >      [0]("我们已经" : 8823) = 0.00874894
11:59:40 >      [1]("离开" : 157762 |动词) = 0.17432975
11:59:40 >      [2]("了" : 11661970 |动词|助词) = 1.00000000
11:59:40 >      [3]("市区" : 25552 |名词.地名) = 0.01776326
11:59:40 >      Method = -[-]|C|R|-
11:59:40 >      Gamma = 0.00001902
11:59:40 >      [0]("我们" : 1092735 |代词) = 0.25372456
11:59:40 >      [1]("已经" : 936262 |副词) = 0.47659987
11:59:40 >      [2]("离开" : 157762 |动词) = 0.17432975
11:59:40 >      [3]("了" : 11661970 |动词|助词) = 1.00000000
11:59:40 >      [4]("市区" : 25552 |名词.地名) = 0.01776326
11:59:40 >      Method = M[0]|-|-|R+
11:59:40 >      Gamma = 0.00012718
11:59:40 >      [0]("我们已经" : 8823) = 0.00874894
11:59:40 >      [1]("离开了" : 26114) = 0.08388353
11:59:40 >      [2]("市区" : 25552 |名词.地名) = 0.01776326

其中Method参数指明了路径产生的方法。M表明是双向最大匹配算法;C表明是最小频次匹配算法;R表明是最大相关系数匹配算法;R+表明是最大相关系数循环匹配算法。
例如:“Method = M[0]|-|-|R+”
表明方法是最大正向匹配算法和最大相关系数循环算法,均产生了相同的该路径。中括号中的0,表明的是双向最大匹配算法的起始索引位置。0表明是从字符串最左侧开始,此时正好等效于最大正向匹配算法(FMM)。

可以看到该例中对“我们已经”这个字符串的处理有所不同。R算法倾向于切分成短小的字符串,因此结果上该字符串会被自动切分成“我们”和“已经”。R+算法则倾向于尽量长的字符串。
不过就作者看来:“我们已经”这个短语是不规范的短语,应该从词典库中删除掉。删除掉之后,其再次解析的结果如下:

----------------------------------------
打印ShortContent.GetContent(38937459)内容!
----------------------------------------
我们已经离开了市区
----------------------------------------
打印CoreSegment.Split(38937459)内容!
----------------------------------------
12:10:01 >      Value = "我们已经离开了市区"
12:10:01 >      Count = 2
12:10:01 >      Method = M[5]|-|-|-
12:10:01 >      Gamma = 0.00001447
12:10:01 >      [0]("我们" : 1092735 |代词) = 0.25372456
12:10:01 >      [1]("已经" : 936262 |副词) = 0.47659987
12:10:01 >      [2]("离" : 559258 |动词|介词) = 1.00000000
12:10:01 >      [3]("开" : 2369942 |动词|量词|名词.姓氏) = 1.00000000
12:10:01 >      [4]("了" : 11661970 |动词|助词) = 1.00000000
12:10:01 >      [5]("市区" : 25552 |名词.地名) = 0.01776326
12:10:01 >      Method = M[8]|-|-|-
12:10:01 >      Gamma = 0.00001667
12:10:01 >      [0]("我们" : 1092735 |代词) = 0.25372456
12:10:01 >      [1]("已经" : 936262 |副词) = 0.47659987
12:10:01 >      [2]("离开了" : 26114) = 0.08388353
12:10:01 >      [3]("市" : 2129304 |名词) = 1.00000000
12:10:01 >      [4]("区" : 1086101 |名词|名词.姓氏) = 1.00000000
12:10:01 >      Method = M[1]|-|-|-
12:10:01 >      Gamma = 0.00003158
12:10:01 >      [0]("我" : 6316123 |代词) = 1.00000000
12:10:01 >      [1]("们" : 3267339 |助词.后缀) = 1.00000000
12:10:01 >      [2]("已经" : 936262 |副词) = 0.47659987
12:10:01 >      [3]("离开了" : 26114) = 0.08388353
12:10:01 >      [4]("市区" : 25552 |名词.地名) = 0.01776326
12:10:01 >      Method = M[3]|-|-|-
12:10:01 >      Gamma = 0.00003175
12:10:01 >      [0]("我们" : 1092735 |代词) = 0.25372456
12:10:01 >      [1]("已" : 1650773 |动词|副词) = 1.00000000
12:10:01 >      [2]("经" : 2425336 |动词|介词|名词|名词.姓氏) = 1.00000000
12:10:01 >      [3]("离开了" : 26114) = 0.08388353
12:10:01 >      [4]("市区" : 25552 |名词.地名) = 0.01776326
12:10:01 >      Method = M[6]|C|R|-
12:10:01 >      Gamma = 0.00001902
12:10:01 >      [0]("我们" : 1092735 |代词) = 0.25372456
12:10:01 >      [1]("已经" : 936262 |副词) = 0.47659987
12:10:01 >      [2]("离开" : 157762 |动词) = 0.17432975
12:10:01 >      [3]("了" : 11661970 |动词|助词) = 1.00000000
12:10:01 >      [4]("市区" : 25552 |名词.地名) = 0.01776326
12:10:01 >      Method = M[0]|-|-|R+
12:10:01 >      Gamma = 0.00003971
12:10:01 >      [0]("我们" : 1092735 |代词) = 0.25372456
12:10:01 >      [1]("已经" : 936262 |副词) = 0.47659987
12:10:01 >      [2]("离开了" : 26114) = 0.08388353
12:10:01 >      [3]("市区" : 25552 |名词.地名) = 0.01776326

这回的关注重点变成了字符串:“离开了”。这个分或者不分,完全取决于用户的看法。如果从词典库中删除“离开了”,那么上述几种分词算法(FMM算法、C算法,R算法和R+算法)的结果将完全重合。如果不删除,那么可以将“离开了”作为一个整体来看待。这也是符合习惯的。

这个例子比较凑巧的是:整个字符串的最大相关系数\(\gamma\)恰好与M0(即FMM)算法结果以及R+算法结果相重合。一般情况下,整个字符串的最大相关系数\(\gamma\)与FMM算法重合的次数较多,与R+算法重合的次数较少。

从上面的分析可以看出:其实分词算法早就已经成熟,只是不知如何选择结果。如果有一个很好的量化方案,必然能得到一个理想的结果。

总结

经过实际检测,分词的最佳结果情况是:Mx算法、C算法、R算法和R+算法的路径结果完全一致
此时四个算法得到完全一致的结果:完全相同的整体相关系数和局部相关系数(如果Mx算法为M0算法则更佳)。而且此时,整体相关系数恰好是这些已知路径中的最大值。

其实Mx算法和C算法偏向于整体相关系数,而R算法和R+算法偏向于局部相关系数。由于取向不一致,很多时候,会产生分割不一致的情况。这些局部不一致,可以用人工干预或者其他辅助方法消除。

哪些情况下四种算法会出现不一致的现象,其表现如何?
(1)绝多数情况下,Mx算法的结果会覆盖C算法、R算法和R+算法的路径。
(2)多数情况下C算法、R算法和R+算法的结果不相同。其中R算法有时候与C算法一致,有时候与R+算法一致。可以说是在C算法和R+算法结果之间“摇摆”。
(3)算法结果之间的差异其实并不会很大,主要涉及3~4个字符长度的字符串分割问题。
(4)C算法与R+算法出现不一致的时候,可以表现为:字符串存在两种分割路径,两种分割均可;字符串存在两种分割路径,只有其中一个更符合阅读习惯。
(5)C算法与R+算法出现不一致的时候,还有一种情况是因为词典库中“混进”了不合理的词汇,导致两者分割出现不一致。

另外算法是无法改变的,可以改变的就只能是词典库。词典库不合理,即使四种算法结果完全一致,那么其结果也是无意义的。

对词典库的操作无非如下几种:
(1)删除不合理的词汇(特别是违反阅读习惯的词汇)。
(2)尽量使用2~3个字符长度的词汇,最多不要超过4个字符。再长的字符串,最好是特定名词字符串。
(3)增加和保留一些词汇,使得分词结构更加顺应阅读习惯。
经过这样调整后,分词结果将会越来越“合理”,而且更有利于后面的词性标注。

AlgMain : 相关系数
知乎:我的NLP(自然语言处理)历程(10)——相关系数
知乎:我的NLP(自然语言处理)历程(12)——分词算法
知乎:我的NLP(自然语言处理)历程(14)——基于相关系数的分词算法
知乎:我的NLP(自然语言处理)历程(17)——信息熵与分词
知乎:我的NLP(自然语言处理)历程(18)——分词最后环节