概述
中文分词是自然语言处理中的一个不小的话题,当然,这是指以前了.计算机是很愚蠢的,而在以英文为代表的拉丁文中,词与词之间是有空格隔开的,所以计算机可以很容易地对英文分词,但是,中文只有可怜的(,.)断句,因此在计算机看来,它唯一能够做的就是分句了.说到这,也许你已经开始有点明白,为什么我们需要劳神对中文做分词了.可以这么说,只要涉及到中文的处理,就不能不使用中文分词,比如说检索,没有分词,计算机连关键词(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算法的流程吧:
(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版本的代码..
