概述

中文分词是自然语言处理中的一个不小的话题,当然,这是指以前了.计算机是很愚蠢的,而在以英文为代表的拉丁文中,词与词之间是有空格隔开的,所以计算机可以很容易地对英文分词,但是,中文只有可怜的(,.)断句,因此在计算机看来,它唯一能够做的就是分句了.说到这,也许你已经开始有点明白,为什么我们需要劳神对中文做分词了.可以这么说,只要涉及到中文的处理,就不能不使用中文分词,比如说检索,没有分词,计算机连关键词(key)都不知道;举个近一点的例子,当你在中国这片神圣的局域网上大肆抨击party时,有关部门的满身G点的GFW会很霸道地封掉你的服务器,为什么GFW这么无敌呢?就是因为它能无耻地过滤我们请求的网页啊.所以,如果没有中文分词的话,GFW就不过是中国男足般的软脚蟹罢了.

话题扯得有点远了,回到中文分词,可以说,如今的分词算法可以说是相当的成熟了,它主要有基于字符串匹配的分词方法和基于统计的分词方法.基于字符串匹配的方法又称为机械分词的方法,它以一定的策略在一个充分大的词典中尝试匹配待分析的汉字串.比如说,假设GFW的词典中有“六四事件”这个词组(该假设永远成立),当你请求的网页中包含这个词时,你就很不幸的被墙了;基于统计的方法,它考虑了词组中单字的相关性,因为词是稳定的字的组合,因此,在上下文中,相邻的字同时出现的次数越多,它们就越有可能构成一个词.因此,字与字相邻出现的概率能够比较好的反应成词的可信度.如果你学过贝叶斯公式的话,相信你已经大概明白应该怎么实现了.

机械分词

接下来,本文集中于机械分词的方法,如果你感兴趣的是基于统计的分词,现在你可以按下Alt+F4离开本页面了.

机械分词按照扫描方向的不同,可以分为正向匹配和逆向匹配;按照不同长度优先匹配的情况,它又可以分为最大匹配和最小匹配;按照匹配失败后增加/减少字串长度,它还可以分为增字匹配和减字匹配.这样说起来有点绕,我们不妨建一个模型,因为分词的英文是Word Segment,我们将模型记为WS(d,a,m);其中,

  • d:匹配方向,+表示正向,-表示逆向
  • a:增字减字,+表示增字,-表示减字
  • m:最大匹配/最小匹配,+表示最大匹配,-表示最小匹配

举个例子,WS(+,+,+)表示正向增字最大匹配法,WS(-,-,-)表示逆向减字最小匹配法,由于中文单词成词的特点,我们很少使用 WS(+,*,-)和WS(-,*,-)模型(*表示+或者-).对于现代汉语来说,只有m=+,也就是最大匹配才是实用的方法.这样说点有点让人沮丧,因为能用的模型突然之间从8种剧减为4种了.但是,如果你足够牛叉的话,你可以考虑将WS(+,*,+)和WS(-,*,+)结合起来,实现一个神奇的双向的匹配.

正向减字最大匹配法

下面要介绍的是正向减字最大匹配法(maximum match based approach,MM),也就是传说中的MMSeg算法了.也许前面我写得有点模糊,还是给个MM算法的流程吧:

MM(via: 搜索引擎–原理,技术与系统 李晓明等,猛击这里可以免费下载到电子版本,赞一下大牛.)

下面是一个MM算法的实例:

[例]我想找个女朋友.(假设词典中词组的最大长度为4,黑色表示已找到的词,红色表示正在处理的汉字串,灰色表示未处理的汉字串)

0.我想找个女朋友。
1.我想找个 女朋友。(从字符串起始点分出4个字)
2.我想找 个女朋友。
3.我想 找个女朋友。(在词典中找到一个词,我想)
4.我想 找个女朋 友。
5.我想 找个女 朋友。
6.我想 找个 女朋友。
7.我想 个女朋友。(单字也是词,找)
8.我想 个女朋友
9.我想 个女朋 友。
11.我想 个女 朋友。
12.我想 女朋友。(个)
14.我想 女朋友 (女朋友)
15.我想 找 个 女朋友 (标点也是词,但是如果你把结构写得好一点的话,标点是应该被预过滤掉的)

看完例子,你应该明白为什么它叫做MM算法了吧!很容易地可以写出伪代码(抄自<搜索引擎–原理,技术与系统>):

string CutWord ( s1 )

Preprocess ( s1 )                // 跳过非汉字部分字符串
While (s1 != “”)                 // 如果输入不为空

W = s1.substr ( 0, MaxLen ) // 取等于最大词长的候选词
While( length(W)> 1 )

If( FindInRBTree (W)= false) //如果不是词并且不是单字
then W = W – 1         // 将 W 中最右边一个字去掉
s2 = W + “/”                      // 将找到的词用分隔符隔开
s1= s1 – W                        // 去掉找到的词,继续分析

return s2

下面是我写的两个最最朴素的版本,没有考虑如今流行的中文说着说着嘣个英文的情况,而且简单地认为词典中包含了各种标点符号.两个版本中,一个以 vector存储词典,一个以set存储,在词典为十万行的情况下(词典在这里),vector版耗时60多秒对<卜算子·黄州定慧院寓居作>分词,set 版耗时仅为3秒.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//===================================
// Name        : wordSegment.cpp
// Author      : Arthur1989
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//===================================
#include<string>
#include<fstream>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include <time.h>
using   namespace   std;
#define MAX 120000
/*尝试使用set优化.不到3秒.时间主要耗在读取字典上面.*/
 
int   main()
{
	// timer is start
	clock_t start, finish;
	double duration;
	start = clock();
	set<string>   vec;
	ifstream dic("dictiory.txt");
	ifstream text("sou.txt");
	string   s;
	while(dic>>s)
	{
		vec.insert(s);
	}
	cout<<"dic read.."<<endl;
	string temp;
	int len=8;
	while(text>>s)
	{
		len =8;
		for(size_t   i   =   0;i<s.length();)
		{
			len =8;
			bool continue_for=true;
			while(continue_for)
			{
				temp=s.substr(i,len);
 
				if(vec.find(temp)!=vec.end())
				{
					cout<<temp<<endl;
					continue_for=false;
					i=i+len;
					break;
				}
 
				if(continue_for==false)
					break;
				len=len-2;
			}
		}
	}
	// timer is finish
	finish = clock();
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	cout << "have cost " << duration << " seconds\n";
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//====================================
// Name        : wordSegment.cpp
// Author      : Arthur1989
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//====================================
#include<string>
#include<fstream>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include <time.h>
using   namespace   std;
 
#define MAX 120000
 
/* 最最朴素的版本,需要63秒 */
 
int   main()
{
     // timer is start
      clock_t start, finish;
      double duration;
       start = clock();
	vector<string>   vec;
	ifstream dic("dictiory.txt");
	ifstream text("sou.txt");
 
	string   s;
 
	while(dic>>s)
	{
		vec.push_back(s);
	}
	cout<<"dic read.."<<endl;
	string temp;
	int len=8;
	vector<string>::iterator   it   =   vec.begin();
	while(text>>s)
	{
		len =8;
		for(size_t   i   =   0;i<s.length();)
		{
			len =8;
			bool continue_for=true;
			while(continue_for)
			{
				temp=s.substr(i,len);
				it   =   vec.begin();
				for(;it<vec.end()&&continue_for==true;it++)
			        {
 				       if(*it==temp)
					{
						cout<<temp<<endl;
						continue_for=false;
						i=i+len;
						break;
					}
				}
				if(continue_for==false)
					break;
				len=len-2;
			}
		}
	}
    //   timer is finish
    finish = clock();
    duration = (double)(finish - start) / CLOCKS_PER_SEC;
    cout << "have cost " << duration << " seconds\n";
    return 0;
}
初步改进的的中文分词

下文借鉴自参考[1]:一种改进整词二分法的中文分词词典设计 谭骏珊等,其实这篇论文是参考 全二分最大匹配快速分词算法 李振星等 来的,但是后文写的有点难懂,因此在这里,我写写我所明白的改进分词.

汉语词典中词组不下十万行,就算是我们日常用到的词组,也不下2万行,如果你使用的输入法支持词典导出功能的话(大部分输入法是支持的),你可以亲自试试.在最最朴素的MM算法中,比如说前面运行了60多秒的vector版本,拖累算法效率的主要是词的存储.选择一个合适的数据结构是很重要的,事实上,你可以使用Trie树(这里,还有这里)来存储汉字词组,速度绝对飞快,可惜这样有点麻烦,这是由于汉字特殊的编码问题.与英文字符不同的是,汉字通用的编码是gb2312编码,每个汉字占两个字节,起始编码为OxB0A1,终止编码为OxF7FE(见下面的小程序).也许你会说,我们可以考虑使用哈希,但是这样的话也许会很耗内存,这我没有测试过,因为在用map测试之前,我发现set版本速度对我来说已经够用了,占用的内存也不多,600K左右.如果你有时间的话,强烈建议你试试哈希.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <string>
using namespace std;
/*sorry,我没找到字典中最后一个字,于是用"座"替上了.*/
int main()
{
	char c[5];
	strcpy(c,"啊");
	cout<<c[0]<<c[1]<<endl; /*输入汉字 啊,gb2312中编码最小*/
	printf("%XH %XH\n",(unsigned char)c[0],(unsigned char)c[1]); /*输出 啊 的gb2321编码,十六进制*/
	strcpy(c,"座");
	cout<<c[0]<<c[1]<<endl; /*输入汉字 座*/
	printf("%XH %XH\n",(unsigned char)c[0],(unsigned char)c[1]); /*输出 啊 的gb2321编码,十六进制*/
 
}

下面讲讲参考[1]中是如何实现所谓改进的:我们知道,词典中有很多词是另外一些词的前缀,比如说,”我” 就是 “我们” 的前缀,“中华” 是 “中华人民共和国” 的前缀,拥有相同前缀的词中,长度也有很多是相同的.为简单起见,我们这里把前缀定义为单字,那么,“女” 既是 “女流之辈” 的前缀,又是 “女中豪杰” 的前缀,我们可以将拥有相同前缀的词根据它们的长度划分为不同的组,这样查询某汉字串的时候,可以根据汉字串首字哈希找到该字对应的结点,然后根据汉字串的长度找到该结点下对应的分组,这样就大大地缩小了查询范围.如果递归地这么构造树下去,我们得到的就是Trie树了,但是,其实这没有多少必要, 因为复杂度已经被降低了不止一个数量级了.至于参考[1]中是如何实现二分的呢,其实我没看懂,因为写得也是很烂.而且,在写完了set版本的分词之后,我才看到这篇论文,set的内部实现是红黑树,与二分已经没有什么差异了.

如果你有什么好的算法愿意分享,可以给我发封邮件. — arthur19891106#gmail.com

参考:
[0]搜索引擎–原理,技术与系统 李晓明等
[1]一种改进整词二分法的中文分词词典设计 谭骏珊等
[2]全二分最大匹配快速分词算法 李振星等

ps: 代码高亮的插件被我搞坏了,贴代码的地方貌似有点不正常,你可以将就着下载下来看. I am so sorry.  — From Arthur1989

[Update 2009-12-12] 上次写的代码纯粹是测试用的,这里是写得规范一点的set版本的代码..