一种简单高效的中文分词方法

郑州轻工业学院学报(自然科学版)

JOURNALOFZHENGZHOUUNIVERSITYOFLIGHTINDUSTRY(NaturalScience)

Vol.21󰀁No.3Aug.2006

󰀁󰀁文章编号:1004-1478(2006)03-0088-03

一种简单高效的中文分词方法

程传鹏

(中原工学院计算机科学系,河南郑州450007)

摘要:根据Hash函数固有的特点,利用数组和链表这两种常见的数据结构,提出一种较为先进的词典存储结构.在提高了词典访问速度的同时,也兼顾了提高主存储器的空间利用率,而且本算法实现起来也比较容易.

关键词:中文分词;Hash函数;二分查找;最大匹配中图分类号:TP391.07󰀁󰀁󰀁󰀁文献标识码:A

OnasimpleandhighefficientChinesesegmentationapproach

CHENGChuan-peng

(Dept.ofSci.andTech.,ZhongyuanInst.ofTech.,Zhengzhou450007,China)

Abstract:AkindofarithmeticabouthighlyefficientdatastructureforChineseelectronictreasureissuggested,accordingtothefeatureofHashfunctionandusualarrayandlinktable.Itimprovesthespeedofsegmentationandutilizationratioofmainmemory.Furthermore,itsimplementisveryeasy.Keywords:Chinesesegmentation;Hashfunction;binarysearch;maximummatching

0󰀁引言

󰀁󰀁中文电子词表的研究是中文信息处理中基础性的工作,它在中文文本的自动分词、文本检索等诸多领域都有重要的应用价值.现有词典的汉语分词

算法中,词典的构造主要有两种方式:一种是利用关系数据库技术构建[2],另外一种是采用纯文本的方式构建[3].利用关系数据库技术是因为早期计算机的主存容量不足并且操作系统存储管理有缺陷,但随着主存储器容量的不断提升,采用关系数据库的优势已基本丧失.采用纯文本方式构建词表,由于数据没有经过有效组织,内部查找时的计算复杂度为O(N)(N为词表中的词条数),耗时较多,影响了中文信息处理的实时性.为此,本文根据汉字的内码,

󰀁󰀁收稿日期:2005-12-01

[1]

建立Hash函数,把Hash函数的值依照升序存入到数组中去,并采用二分法进行分词词典的查找.提出了一种简单高效的分词方法SHSEG(SimpleandHighEfficientSegmentation).在有效减少I/O次数,提高词典访问速度的同时,也兼顾了提高主存储器的空间利用率.

1󰀁汉字编码问题

国标(GB)码是指我国公布的国家标准󰀁信息交换用汉字编码字符集-基本集󰀁,其中包含了6763个汉字,并分作两级,一级为常用字,有3755个,二级为3008个.一级按照拼音排序,二级则按照部首排序.一个汉字的国标码由两个部分组成,分别是该汉字的区号和位号[2].GB码规定共有94个区,每个

󰀁󰀁作者简介:程传鹏(1976󰀁),男,河南省信阳市人,中原工学院助教,硕士,主要研究方向:信息检索、计算机网络.

第3期程传鹏:一种简单高效的中文分词方法

󰀁󰀁

区中有94个位.前15区用来编排西文字母、数字、日文片假名、图形符号等,16区󰀁87区是汉字,88区󰀁94区是用户自定义区.汉字GB码要和ASCII码一同使用会有冲突问题,解决的办法是高位置1.已知一个字的区位码,将区码和位码分别加A0(A0=101000002=16010)就得到汉字机内编码,一般称为内码.

字内码的低字节-0xa0:计算位号(转化为十进制,即为二维数组的列下标).CHi为中文汉字.Wi,j为所有以CHi为首字的词,不包括CHi.i,j为按词条机内码排序所得到的序号.

用二维数组的下标来表示Hash函数的地址,由于每个汉字的内码不同,所以,SHSEG词典不存在地址冲突问题.

2󰀁SHSEG词典的方案

散列(Hash)是一种重要的存储方法,也是一种常见的查找方法[3].它的基本思想是:以结点的关键字为自变量,通过一个确定的函数关系f,计算出对应的函数值f(K),把这个值解释为结点的存贮地址,将结点存入f(K)所指的存储位置上.查找时再根据要查找的关键字用同样的函数计算地址,然后到相应的单元里去取要找的结点.

SHSEG分词词典方案如下:1)首先把以文本形式存贮的字典读入到关系数据库中.2)在关系数据库中以词条的机内码进行索引排序.3)按顺序读数据库中的记录,遇到单个汉字时建立新的链表,根据该汉字的机内码计算出其在二维数组的下标;把随后的记录添加到该链表一直到下一个单字.

借鉴文献[4]的词表数据结构,最终在计算机的内存中所建立的词典数据结构如图1所示.

3󰀁SHSEG词表的查找

词的查找首先计算待查字串的首字机内码(即为相应的Hash地址),设首字为Ci,其内码为ICi,则

Q(RCi)=HighByte(ICi)-0xa0󰀁

W(RCi)=LowByte(ICi)-0xa0利用Hash方法求其在内存中的地址Ai:Ai=f(Q(RCi),W(RCi))在SHSEG的词表管理系统中,利用Q(RCi)和W(RCi)计算二维数组的下标.然后找出所有以该字为链表头的链表,在链表里进行二分查找.

这种Hash方法实质上是一种一一映射,首字不同,地址亦不同,有效地避免了Hash地址冲突问题.利用Ci可经过式󰀁、式󰀁的运算而直接得到首字索引项,这一过程不进行任何匹配找到索引项后,如待查项为单字,还要看Ci是否能够成词;否则根据待查项的余下字串在以该首字为表头的链表中进行二分查找,最后返回查找结果0或1(0为未找到,1为找到).

󰀁

4󰀁SHSEG分词过程描述

最大匹配法的基本思想是:假设自动分词词典中的最长的词条所含的汉字个数为L,则取被处理材料当前字符串序数中的L个字作为匹配字段,查找分词词典.若词典中有这样的一个字词,则匹配成功,匹配字段作为一个词被切分出来;如果词典中找不到这样的一个字词,则匹配失败.去掉匹配字段的最后一个字,重新进行上述的操作,直到切分出所有词为止.

首先对一篇文档按标点符号做一次粗切分,假设得到的结果为:C1C2󰀁Ci󰀁N1N2󰀁NiNj󰀁Ci+1Ci+2󰀁E1E2󰀁EiEj󰀁Ci+3Ci+4󰀁;其中C为汉字,N为数

图1󰀁词典结构图

󰀁󰀁图1中:ki=汉字内码的高字节-0xa0:计算区号(转化为十进制,即为二维数组的行下标).liI=汉字,E为英文字符.把N1N2󰀁和E1E2󰀁作为分隔符,再做一次切分.

假设按照上面的方法处理后得到的一个待切分的字符串为HZString=CiCi+1󰀁,然后对该句子进行分词处理,假设词典中最长词长为n,Len(x)为判断[5]

󰀁90󰀁

郑州轻工业学院学报(自然科学版)2006年

汉字串x长度的函数.

依照以上的分析和最大匹配法的基本思想,最终形成的算法描述如下:

输入:预处理后的文档

输出:文档中所有的词条

1)假如Len2)存在,则CiCi+1󰀁Ci+

n-1为切分结果,

1

2)查找时间复杂度分析.若记󰀁n为所有汉字作首字时的平均词数,且每个词被查询的机会均等,则󰀁=N/6763.根据词表查找算法可知,平均查找次数n

n)

主要来自二分查找过程,故计算复杂度为O(log2󰀁.假设N=100000,则平均查找次数为3次左右.

实验中采用的词典有40000多条的词条,收录了信息检索中常见的词条.把词条分别转换成文本的方式和关系数据库的方式存储.采用正向最大匹配的分词方法对200篇文本文件(865K)进行了比较,比较的指标是分词所用的时间和词典所占用的空间利用率,如表1所示.

表1󰀁分词效率和空间利用率比较

词典文本的方式关系数据库的方式

本文的方式

分词时间/s

108󰀁75󰀁3

空间利用率/%

10010084

󰀁

一次分

词结束,继续处理文档中剩余的汉字串.

3)不存在,从HZString的最右边去掉一个汉字,得到汉字串CiCi+1󰀁Ci+n-3.

4)重复3)直到能在字典中查找出Ci󰀁Cj字串(也可能为单字).

5)从HZStirng中去掉切分出来的汉字串,把余下的汉字串作为待切分的汉字串,返回到1).

6)如果待切分汉字串的长度为0,则一次分词结束.继续处理文档中剩余的汉字串.

5󰀁算法的空间利用率和查找时间复杂

度分析

󰀁󰀁空间利用率和查找时间复杂度,通常是衡量分词方法优劣的非常重要的标准.在其他条件相同的情况下,如果空间利用率和查找时间复杂度越低,则说明这种分词方法的性能越好,分词速度越快.计算分词方法的复杂度时,一般选择匹配比较次数作为基本衡量单位.分词方法的时间复杂度,具体的是指这种分词方法进行的平均每切分出一个词所需要的匹配比较次数.

1)空间利用率.设原词表有N个词,平均词长为L,每个指针变量所占字节数为p,则按照本文方法所构建的电子词表在主存中的存储利用率um为:

N(2L+p)󰀁100%

6763󰀁p+N󰀁[2(L-1)+p]

其中,6763为GB2312中单个汉字的个数.um=

由于在存储中,对有相同首字的词条,只在第一次出现该字时候存储该汉字,所以减少了词条的存储利用率.而文本和关系数据的存储方式,对词条全部存储,所以存储利用率为100%.

6󰀁结语

本文提出的分词方法由于采用了数组和链表等常用的数据结构存储方式,在算法实现上比较简单,提高了分词速度.分词的结果也基本上满足了中文信息处理中对分词的要求,故本方法存在一定的合理性和应用价值.参考文献:

[1]󰀁陈桂林,王永成,韩客松,等.一种高效的中文电子词表

数据结构[J].计算机研究与发展,2001,(1):109󰀁116󰀁[2]󰀁俞士汶,朱学锋.现代汉语语法信息词典详解[M].北

京:清华大学出版社,1998󰀁

[3]󰀁郭祥昊,钟义信.基于两字词簇的汉语快速自动分词算

法[J].情报学报,1998,17(5):352󰀁357󰀁

[4]󰀁揭春雨.汉语自动分词实用系统CASS的设计和实现

[J].中文信息学报,1990,(4):27󰀁34󰀁

[5]󰀁赵拍璋,徐力.计算机中文信息处理[M].北京:宇航出

版社,19.

[6]󰀁严蔚敏,陈文博.数据结构及应用算法教程[M].北京:

清华大学出版社,2001.󰀁