词典与后缀数组相结合的中文分词方法 |
| 2013-01-25 12:22 作者：曹月雷 纪文彦 贾斌 来源：硅谷网-《硅谷》杂志 HV： 编辑： 【搜索试试】
|
|
据《硅谷》杂志2012年第21期刊文称，目前中文分词成熟的方法主要有基于字符串匹配和基于统计的分词方法，这两种方法各有优缺点，为达到更好的分词效果，提出一种词典与后缀数组相结合的中文分词算法。其基本思想是首先利用后缀数组快速准确地抽取文档中的中、高频词，同时利用词典进行其他词汇的切分。另外，我们对词典的存储结构进行改进，提高匹配速度。实验证明本算法能够有效的提高分全率和准确率。
关键词：中文分词；基于词典的分词；后缀数组；散列表
随着中国计算机技术的发展，诸多领域对计算机的中文信息处理能力提出了更高的要求，中文分词则是中文信息处理的基石。由于汉语的复杂性和多变性，中文分词已成为中文信息处理的瓶颈[1]。如何进一步提高分词的准确率是众多学者研究的课题。
中文分词中遇到的主要问题是歧义问题和未登录词问题[2]，在Bakeoff数据上的评估结果表明，未登录词造成的分词精度失落至少比分词歧义大5倍以上[3]，故解决未登录词问题是提高分词准确率的关键。本文引入的后缀数组能够通过上下文自动识别中高频和未登录词汇，使歧义问题不易出现，但是分全率和准确率较低，无法识别文档中只出现一次的词汇，而中文分词中最基本的基于词典的方法分全率和准确率高[7]，但是不能识别未登录词，因此本文提出了词典与后缀数组相结合的方法，使其兼具基于串匹配和基于统计分词算法的优点，取长补短，以期达到更好的分词效果。
1词典与后缀数组相结合的中文分词
本文提出的词典与后缀数组相结合的中文分词算法可分为两步。第一步是基于后缀数组的无词典的处理：读入待分词的文档，将整篇文档存入一个字符串str中，根据此字符串生成一个后缀数组及最长公共前缀信息数组，由此得到汉字的结合模式并存入散列表结构HashMap中，再对HashMap中的汉字结合模式（即候选词）进行处理和筛选，得到的结果就是抽到的词；第二步是基于词典的字符串匹配处理：将上一步基于后缀数组抽取到的词语和一个已有的常用词典结合到一起，共同作为分词所用的词典，采用正向最大匹配算法对待分词文档进行处理，处理单元为句子，对每一个句子分别进行正向最大匹配，得到分词结果。下面分别对这两个步骤所涉及到的问题和算法进行详述。
2基于后缀数组的分词处理
基于后缀数组的处理部分主要完成文档中未登录词和中高频词汇的识别，是本算法的先进之处。此部分工作还能使得整个分词算法不易产生歧义。
2.1后缀数组
后缀数组是当今算法研究的热门之一，它在Web搜索、文本处理、基因匹配等方面都有着极大的应用潜力。后缀数组是作为一种文本索引结构提出的，它记录某个文本的所有半无限串（起点在文本任意位置，终点在文本尾的字符串）的字典排序。
先来介绍几个必要的概念：
后缀：后缀是指从某个位置开始到整个串末尾结束的一个特殊子串。字符串的从开头的后缀表示为即，约定字符集Σ和字符串S，设，S中的字符都属于Σ，且，也就是说以一个特殊字符结尾，并且小于∑中的任何一个字符。字符串，从位置开头的后缀直接写成，省去参数。
后缀数组：后缀数组是一个一维数组，它保存的某个排列，并且保证。也就是将的个后缀从小到大进行排序之后把排好序的后缀的开头位置顺次放入中。
名次数组：名次数组，也就是说若，则，不难看出保存的是在所有后缀中从小到大排列的“名次”。
最长公共前缀：对两个字符串定义函数，也就是从头开始顺次比较和的对应字符，对应字符持续相等的最大位置，称为这两个字符串的最长公共前缀。
2.2后缀数组的构造
Manber和Myers[5]提出的算法，可以利用O（N)的额外空间，在O（NlgN)时间内同时构造出后缀数组及最长公共前缀信息数组的算法[5，6]。下面介绍一下倍增算法，它充分利用了后缀之间的联系，高效的构造出后缀数组：
我们定义运算符“”、“”、“”表示两个串的前个字符按照字典序比较，于是我们可以得到以下重要的性质：
性质1：对等价于
性质2：等价于性质3：等价于或（
且)。
k-后缀数组：保存的某个排列，，…使得。
也就是说对所有的后缀在-前缀比较关系下从小到大排序，并且把排序后的后缀的开头位置顺次放入数组中。
k-名次数组：，代表在-前缀关系下从小到大的“名次”，也就是1加上满足的的个数。通过很容易在O（n)的时间内求出。
根据上述性质和定义，若我们已经求出了和，那么我们可以很方便地求出和，而数组实际上给出了在常数时间内进行和比较的方法，即：
当且仅当当且仅当
使用倍增算法构造后缀数组的算法如下：
输入：要进行处理的字符串str
输出：由str构造出的后缀数组SA
算法开始
将要str存入数组s中，下标从1开始。数组s的元素由两部分组成，p1部分存储字符，p2部分存储此元素的数组下标。
根据s.p1对数组s排序，这时s.p2的值即是SA1的值，由SA1可很容易得到Rank1的值。SAj和Rankj的长度都是str.length，下标均从1开始。
j=2，m=//取天棚
Whilej≤m+1do//开始倍增
k=
SAj=SAj-1
i=1
Whilei>str.lengthdo
/*利用SAj-1构造SAj*/
b1=Rankj-1[SAj[i]]-Rankj-1[SAj[i+1]]
b2=Rankj-1[SAj[i]+k/2]-Rankj-1[SAj[I+1]+k/2]
Whileb1=0/*根据比较结果，决定SAj中元素的位置*/
If(b2<0)Then
q=q+1
Endif
If(b2>0)Then
swap(SAj[i],SAj[q])//交换
q=q+1
ElseIf(b2=0)Then
q=q+1
Endif
Endif
b1=Rankj-1[SAj[i]]-Rankj-1[SAj[q]]
b2=Rankj-1[SAj[i]+k/2]-Rankj-1[SAj[q]+k/2]
Repeat//Whileb1=0
Repeat//Whilei>str.length
利用SAj计算出Rankj/*j从2到m+1,共m项*/
Repeat//Whilej≤m+1
SA=SAm+1
算法结束
算法1：后缀数组的构造
算法中k的值从1开始，每次增加2倍（k=k*2)，直到k≥n，即经过logn趟比较，后缀数组就生成了。
2.3最长公共前缀数组
现在计算出了了一个字符串S的后缀数组SA，但是要想用后缀数组来识别未登录词和中高频词，我们必须要计算出后缀数组中相邻两后缀的最大公共前缀。
关于LCP有两个显而易见的性质：
性质1：
性质2：
这样我们在计算时只需要考虑的情况。
定义一维数组
令，，并设。此一维数组即我们所必须要求的数组----按字典序相邻后缀的最大公共前缀数组。
对于一个固定的字符串S，其数组显然是固定的，只如何尽量高效地算出数组使我们做要做的。
另设，即：。数组满足一个性质：
性质3[5]：对于且，一定有
由上述性质可得到后缀数组中相邻后缀的最大公共前缀数组构造如下：
由2.1节的方法求得的后缀数组SA，算出名次数组Rank
i=1
Whilei≤str.lengthdo
If(rank[i]=1)Then
h[i]=0
ElseIf(i=1或h[i-1]≤1)
从第一个字符开始依次比较Suffix(i)和Suffix(Rank[i]-1)直到有字符不相同，记录下相同字符的个数即h[i]。
Endif
Else
/*这时有i>1，Rank[i]>1，h[i-1]>1，由性质3h[i]≥h[i-1]-1*/
从h[i-1]开始从第一个字符开始依次比较Suffix(i)和Suffix(Rank[i]-1)直到有字符不相同，记录下相同字符的个数h[i]
Endif
Repeat
height[i]=h[result[i]]，i从1开始
算法结束
算法2：最大公共前缀数组的构造算法getLcp
height数组即为所求，算法的复杂度为O（n）[6]。求出了h数组，根据关系式height[i]=h[SA[i]]可以在O（n）时间内求出height数组，于是可以在O（n）时间内求出height数组。
2.4基于后缀数组的无词典分词算法
有了前面后缀数组、最长公共前缀数组的基础知识和构造方法，接下来我们就可以用这两个数组来识别待分词文档中的未登录词和中高频词汇。
第一步，使用后缀数组、最长公共前缀数组抽取汉字的结合模式
我们使用HASHMAP存放提取出来的汉字结合模式。HASHMAP具有速度快，使用方便的优点。HASHMAP由两个元素组成（KEY，VALUE），存放汉字串和汉字串在文章中出现的次数，这里我们用HASHMAP的KEY存放汉字字串，VALUE存放汉字串在文章中出现的次数，VALUE的值至少是2。
取词算法GetWords如下算法3：
输出：文档的候选词条集合word（HashMap散列表类型）
初始化word为空表；
利用上两节的两个算法将待分词文档读入到str字符串中，并求出此字符串对应的后缀数组SA[]和最长公共前缀信息数组LCP[]。两个数组的长度均为n=str.length()+1；i=1
Whilei≥nDo
str1=str<SA[i],LCP[i]>/*str1为取str中第SA[i]字符开始，长度为LCP[i]的字符串*/
/*对str1进行处理*/If(str不以汉字开始)Then
不做任何处理；
Else//str1以汉字开始
str=str<0,k>/*即取str1中以第0个字符开始,长度为k的字符串,且这个字符串全为汉字组成str1=str1<0,k>*/
j=2；
Whilej≤kDo
str1<0,j>放到word中//word由(key,value)构成
j=j+1；
Repeat
Endif//若str1不以汉字开始
i=i+1；
Repeat
算法结束
算法3：取词算法
第二步，对HashMap中的汉字串（候选词）进行处理和筛选，最终得到的结果就是抽到的词语。把第一步中放到HashMap中的汉字串称为候选词集。
介绍下筛选算法的依据和思想：
在候选词集中，假设有两个汉字串W1和W2。其中W1是W2的子串，在这种情况下，可能W1与W2都是词，也可能只有W1是词而W2不是词，还有可能W2是词而W1不是词。我们使用置信度来进行筛选。
汉字串W2相对与W1的置信度为
其中TF（W1）和TF（W2）分别是W1和W2的词频。设置置信度的上限是0.90，下限为0.30。若confidence高于上限，则W1可以去除，若是低于下限，则W2可以去除。通过这些规则对候选词集进行处理后，HashMap中的汉字串（KEY值）就是所抽到的词。
另外，值得一提的是第二步取词算法中关于一个字符是否是汉字的判断。
在Java中我们可以利用String类中的getBytes（"GB2312"）函数将字符串所表示的字符按照GB2312编码，并以字节方式表示。例如要求一个汉字“霸”的GB2312编码，只需通过函数“霸”.getBytes（"GB2312"）即可获得。
经过提取与筛选之后，散列表word中的key值，即是我们从待分词文档中使用无词典的方法识别出来的词汇。这些词汇都是多次在文档中的出现的中高频词汇，包括常用词典中没有记录的未登录词。
3基于词典的分词处理
3.1基于词典方法的必要性和实现方法
上述基于后缀数组的无词典中文分词算法虽然已经识别出来一些中高频词汇，但是对于在待分词文档中只出现一次的词语却无法识别，而且这种基于统计的方法常常会抽取一些出现频率高但是并不是词的常用字串。
为了克服上述不足，我们使用一部基本的分词词典（常用词词典）进行串匹配分词，配合基于后缀数组的无词典算法，即将两种方法结合起来，以期达到理想的分词效果。
根据用词典对句子进行字符串匹配的方向和匹配长度，可以有三种匹配方法[4]：
1）正向最大匹配法（MM）
通常简称为MM法。其基本思想为：设D为词典，MAX表示D中的最大词长，str为待切分的字串。MM法是每次从str中取长度为MAX的子串与D中的词进行匹配。若成功，则该子串为词，指针后移MAX个汉字后继续匹配，否则子串逐次减一进行匹配。
2）逆向最大匹配法（RMM）
通常简称为RMM法。RMM法的基本原理与MM法相同，不同的是分词的扫描方向，它是从右至左取子串进行匹配。统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245，显然RMM法在切分的准确率上比MM法有很大提高。
3）最少切分（使每一句中切出的词数最小）
本算法中我们采用正向最大匹配法（MM）。考虑到标点符号等绝对切分标记和条件切分标记[9，10]切分出来的断句一般长度较短，我们算法中没有设定最大词长。
3.2词典的存储结构
基于词典的分词方法，在分词过程中，需要频繁的在词典中进行查找以获取词语信息，而为了满足后面信息检索的需要，我们的分词算法又要尽可能的快。因此，一个高效的词典组织和查找机制对于提高分词系统的速度来说至关重要。
典型的汉语分词词典机制有五种[8]：基于整词二分的分词词典机制、基于TRIE索引树的分词词典机制、基于逐字二分的分词词典机制、首字Hash索引分词词典机制，双字哈希索引分词词典机制。其中双字哈希索引分词词典机制是最新的词典机制，匹配速度也是最快的，该机制的改进处是词的第一个字和第二个字都采用Hash表进行存储，因此词的匹配速度大大提高。
在本算法中我们采用首字Hash索引结构来实现词典的存储。此存储结构的实现还要借助于散列表结构HashMap。
算法将词典读入内存，并将按照词典的首字进行分类，以词的首字作为HashMap中的key值，而value值则是以该字为首的所有词构成的ArrayList类型的一维线性表。基于这种结构，在进行字符串匹配时先将其首个字符作为key，若HashMap中不包含这个key则返回false，否则取出改线性表即value后使用折半查找的方法查询。
HashMap存储结构如下图所示（以霸字为首的词汇为例）
key value
"霸" ArrayList链表
霸王 霸权 …… 霸道
其它首字相同的各组词汇也同样存储。
这种结构使得每次匹配的时候可以利用HashMap的性质，根据首字符快速找到该首字符对应的所有词汇线性表，于是算法每次匹配需要检索的范围变得很小，匹配字典的时间会大幅度地降低。首字的查找可直接用HashMap中的get函数，即简便又快速。对同首字的一维线性表采用对分查找，实现可用Collections类中的binarySearch因此在同一个首字所对应的词组中的匹配速度也很高。总而言之，我们设计的字典存储结构既简单又高效。下面给出首字Hash词典的实现算法，其中包括向词典中插入新词汇，在词典中查找某个词汇（即匹配字符串）。
向词典中插入新词汇insertWord（String）的算法如下：
输入：要插入的词汇letters
算法开始
Ifletters=nullThen
return；
Endif
fch=letters.substring(0,1)//取首字
Ifdic.containsKey(fch)Then/*词典中已存在此首字*/
val=dic.get(fch)/*val为ArrayList类型的线性表*/
Else
新建一个空的val；
Endif
Ifval中没有词语lettersThen
val.add(letters)
Collections.sort(val)//排序
dic.put(fch,val)//放入词典中
Endif
算法结束
算法4：向词典中插入词汇
在词典中查找某个词汇的算法很简单省略。
我们的算法在将词典读入内存时，除了txt词典文档中的词语要读入内存词典，还有2.3节中基于后缀词典的无词典算法中提取出来的词语也要读入，这样就实现了基于后缀数组的无词典中文分词算法与基于词典的中文分词算法的结合。
这样我们所要用的分词结构就构造好了，接下来只需要对待分词文档与词典进行经典的正向最大匹配即可，在此不再赘述。
4实验结果及分析
我们采用java语言实现本文的分词系统，测试实验结果如下：
4.1实验结果
我们使用一篇新闻稿作为测试例子，切分结果如下：
中共中央总书记/国家/主席/中央军委/主席/胡锦涛/16/日/中午/抵达/绵阳/南郊/机场/后/立即/在/机场/主持/召开/会议/同/先期/抵达/灾区/的/中共中央/政治局/常委/国务院/总理/抗震救灾/总指挥部/总指挥/温家宝/共同/研究/部署/抗震救灾工作/
会上/温家宝/报告/了/四川/特大/地震/的/特点/灾情/前一/阶段/抗震救灾工作/进展/的/情况/当前/存在/的/困难/和/下一阶段/工作/的/重点/胡锦涛/就/继续/做好/抗震救灾工作/作出/重要/指示/
会议强调/在/党中央/国务院/和/中央军委/坚强/领导/下/在/抗震救灾/总指挥部/直接/指挥/下/抗震救灾工作/全面/展开/正/有力/有序/有效/进行/为/下一步/工作/打下/了/比较/好/的/基础/现在/时间/十分/紧迫/要继续/发扬/不怕/疲劳/连续作战/的/作风/顽强拼搏/迎/难/而上/努力/把/地震/灾害/造成/的/损失/减到/最低/程度/真正/打好/抗震救灾/这场/硬仗/
会议强调/抗震救灾工作/要/坚持/以/人为/本/把/抢救/人民群众/生命/作为/重/中/之/重/要继续/尽/最大/可能/救人/只要/有/一线希望/就要/作出/百倍/努力/
会议/要求/增派/的/3/万名/部队/官兵/要/尽快/到位/立即/投入/抗震救灾/一线/要/采取措施/保证/救援队伍/在/进入所有/乡镇/的/基础/上/尽快/进入所有/村庄/救援队伍/要与/基层/干部/结合/起来/深入/到群众中去/广泛开展/救援工作/要/为/救援/人员/配备/必要/的/设备/进行/必要/的/培训/真正/实行/科学/救援/对/已经/救出/的/群众/要/及时/转移/对/其中/的/孤儿/孤老/要/妥善安置/要/严密/关注/震/情/加强/余震/防范/防止/发生/新/的/伤亡/要/认真/开展/卫生防疫/工作/防止/灾/后/疾病/流行
其中基于后缀数组的无词典算法从文档中提取的词汇共34个：
抗震救灾工作救援队伍进入所有中央军会议强调抗震救灾中共中央胡锦涛要继续必要的国务院一阶段总指挥温家宝努力地震立即作出开展下一指挥进行中央防止真正会议一线工作群众继续主席抵达救人救援
4.2分析结果
我们通过中文分词系统的两个主要性能参数准确率和分全率来进行分析。
准确率：是指算法所分得的正确的词的个数与分得的所有的词的个数之比；
分全率：是指算法所分得的正确的词的个数和原文应有的词的个数之比；
我们对单纯使用词典的方法和使用基于后缀数组和基于词典结合方法分别计算其准备率与分全率，以达到比较优劣的作用。对4.1中使用的待分词文档，
单纯使用词典的方法：
其准确率=232/274=84.67%
其分全率=232/257=90.27%
使用基于后缀数组和基于词典结合方法：
其准确率=241/253=95.25%
其分全率=241/244=98.77%
由计算结果可知，不论是准确率还是分全率，使用基于后缀数组和基于词典结合方法都远远优于单纯使用词典的方法。
另外，我们对本文算法实现的分词系统与DSfenci分词系统[11]的进行了比较。DSfenci分词系统[11]是使用字典与统计的方法实现的。我们使用复旦大学李荣陆等整理的中文文本语料库（http://www.nlp.org.Cn/docs/doclist.php?cat-id=16&type=15）中的五个领域的文档进行了测试，结果如下表1：
表1词典与后缀数组相结合的算法
领域 大小（kb） 准确率（%） 分全率（%）
经济 32.46 98.38 99.64
计算机 31.12 98.44 99.72
体育 29.19 98.36 98.67
环境 29.52 98.27 99.73
医药 25.87 98.52 99.55
DSfenci分词系统[11]的测试结果如下表2：
表2字典与后缀数组相结合的算法
领域 大小（kb） 准确率（%） 分全率（%）
经济 32 98.58 99.57
计算机 45 98.52 99.52
体育 34 98.4 99.59
环境 32 98.60 99.64
医药 30 98.51 99.50
比较两个表的统计数据可知，本文算法的分全率要高于字典与统计相结合的分词算法，但由于本文没有进行切分歧义的处理，准确率上稍有不足。实验过程中，本文分词系统的切分速度要比DSfenci分词系统[11]的切分速度快。这些数据说明用后缀数组提取词汇的方法要优于传统的基于统计的方法。
5结束语
通过实际的实验测试、数据统计和计算，我们可以看出基于后缀数组和基于词典结合的方法能显著的提高分全率和准确率，获得一个较好的分词精度。最重要的是，随着社会的不断进步，科技的不断发展，新词识别准确率已经成为评价一个分词系统好坏的重要标志之一。将基于后缀数组的分词方法结合到基于词典的方法中，能够迅速准确的识别新词，优化分词效果，是很有必要的。
作者简介：
曹月雷（1987-），男，山东莒县人，本科，中国人民解放军63958部队；纪文彦（1986-），女，山东莒县人，硕士研究生，中国农业银行总行软件开发中心；贾斌（1990-），男，吉林省吉林市人，本科，吉林大学计算机科学与技术学院。
|
|
|
|
【对“词典与后缀数组相结合的中文分词方法”发布评论】 |
版权及免责声明：
① 本网站部分投稿来源于“网友”，涉及投资、理财、消费等内容，请亲们反复甄别，切勿轻信。本网站部分由赞助商提供的内容属于【广告】性质，仅供阅读，不构成具体实施建议，请谨慎对待。据此操作，风险自担。
② 内容来源注明“硅谷网”及其相关称谓的文字、图片和音视频，版权均属本网站所有，任何媒体、网站或个人需经本网站许可方可复制或转载，并在使用时必须注明来源【硅谷网】或对应来源，违者本网站将依法追究责任。
③ 注明来源为各大报纸、杂志、网站及其他媒体的文章，文章原作者享有著作权，本网站转载其他媒体稿件是为传播更多的信息，并不代表赞同其观点和对其真实性负责，本网站不承担此类稿件侵权行为的连带责任。
④ 本网站不对非自身发布内容的真实性、合法性、准确性作担保。若硅谷网因为自身和转载内容，涉及到侵权、违法等问题，请有关单位或个人速与本网站取得联系（联系电话：01057255600），我们将第一时间核实处理。
|
|
|
|
