2009-12-06 Programming >> 1 comment
概述

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

//===================================
// Name        : wordSegment.cpp
// Author      : Arthur1989
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//===================================
#include
#include
#include
#include
#include
#include
#include 
using   namespace   std;
#define MAX 120000
/*尝试使用set优化.不到3秒.时间主要耗在读取字典上面.*/

int   main()
{
	// timer is start
	clock_t start, finish;
	double duration;
	start = clock();
	set   vec;
	ifstream dic("dictiory.txt");
	ifstream text("sou.txt");
	string   s;
	while(dic>>s)
	{
		vec.insert(s);
	}
	cout<<"dic read.."<>s)
	{
		len =8;
		for(size_t   i   =   0;i

//====================================
// Name        : wordSegment.cpp
// Author      : Arthur1989
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//====================================
#include
#include
#include
#include
#include
#include
#include 
using   namespace   std;

#define MAX 120000

/* 最最朴素的版本,需要63秒 */

int   main()
{
     // timer is start
      clock_t start, finish;
      double duration;
       start = clock();
	vector   vec;
	ifstream dic("dictiory.txt");
	ifstream text("sou.txt");

	string   s;

	while(dic>>s)
	{
		vec.push_back(s);
	}
	cout<<"dic read.."<::iterator   it   =   vec.begin();
	while(text>>s)
	{
		len =8;
		for(size_t   i   =   0;i

初步改进的的中文分词


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


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


#include 
#include 
using namespace std;
/*sorry,我没找到字典中最后一个字，于是用"座"替上了.*/
int main()
{
	char c[5];
	strcpy(c,"啊");
	cout<

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


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


参考:

[0]搜索引擎--原理,技术与系统 李晓明等

[1]一种改进整词二分法的中文分词词典设计 谭骏珊等

[2]全二分最大匹配快速分词算法 李振星等


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


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