面向信息检索的自适应中文分词系统
ＩＳＳＮ１０００—９８２５，ＣＯＤＥＮＲＵＸＵＥＷ
ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ，Ｖｏｌｌ７，Ｎｏ３，Ｍａｒｃｈ２００６。ＰＰ３５６—３６３
ＤＯＩ：１０１３６０ａｏｓｌ７０３５６
＠２００６ｂｙＪｏｕｒｎａｌｏｆＳｏｆｔ．＇ａｒｅＡｌｌｔｉｇｈｔｓｒｅｓｅｒｖｅｄ
面向信息检索的自适应中文分词系统＋曹勇刚＋，曹羽中，金茂忠，刘超
（北京航空航天大学计算机学院，北京１０００８３）
Ｅ－ｒａａｉｌ：ｊｏｓ＠ｉｓｃａｓａｃｅｎＴｅｌ／Ｆ磐：出怼０６”２５”６２５“６３ａｘ｝８６—１－
ＩｎｆｏｒｍａｔｉｏｎＲｅｔｒｉｅｖａｌＯｒｉｅｎｔｅｄＡｄａｐｔｉｖｅＣｈｉｎｅｓｅＷｏｒｄＳｅｇｍｅｎｔａｔｉｏｎＳｙｓｔｅｍ
ＣＡＯＹｏｎｇ—Ｇａｎｇ一，ＣＡＯＹｕ－Ｚｈｏｎｇ，ＪＩＮＭａｏ—Ｚｈｏｎｇ，ＬＩＵＣｈａｏ
（ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ，ＢｅｉＨａｎｇＵｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ１０００８３，Ｃｈｉｎａ）
＋Ｃｏｒｒｅｓｐｏｎｄｉｎｇａｕｔｈｏｒ：Ｐｈｎ：＋８６—１０－８２３２４４８８ｅｘｔ８８５。Ｅ—ｍａｉｌ：ｙｇｃａｏ＠ｃｓｅｂｕａａｅｄｕｅｎ，ｈａｐ：／／ｓｏｌｂｕａａｅｄｕｃａ
ＣａｏＹＧ，ＣａｏＹｚ，ＪｉｎＭＺ，ＬｌｕＣ．ＩｎｆｏｒｍａｔｉｏｎｒｅｔｒｉｅｖａｌｏｒｉｅｎｔｅｄａｄａｐｔｉｖｅＣｈｉｎｅｓｅｗｏｒｄｓｅｇｍｅｎｔａｔｉｏｎｓｙｓｔｅｍ．ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ，２００６，１７（３）：３５６－３６３．ｈｔｔｐ：／／ｗｗｗ．ｊｏｓｏｒｇｅｎ／１０００—９８２５／１７／３５６．ｈｔｍ
Ａｂｓｔｒａｃｔ：ＮｅｗｗｏｒｄｓｒｅｃｏｇｎｉｔｉｏｎａｎｄａｍｂｉｇｕｉｔｙｒｅｓｏｌｖｉｎｇｈａｖｅｖｉｍｌｅｆｆｅｃｔＯｌｌｉｎｆｏｒｍａｔｉｏｎｒｅｔｒｉｅｖａｌｐｒｅｃｉｓｉｏｎＴｈｉｓｐａｐｅｒｐｒｅｓｅｎｔｓａｓｔａｔｉｓｔｉｃａｌｍｏｄｅｌｂａｓｅｄａｌｇｏｒｉｔｈｍｆｏｒａｄａｐｔｉｖｅＣｈｉｎｅｓｅｗｏｒｄｓｅｇｍｅｎｔａｔｉｏｎ
Ｔｈｅｎ，ａｎｅｗｗｏｒｄｓｅｇｎｌｅｎｔａｔｉｏｎｓｙｓｔｅｍｃａｌｌｅｄＢＵＡＡＳＥＩＳＥＧｉｓｄｅｓｉｇｎｅｄａｎｄｉｍｐｌｅｍｅｎｔｅｄｕｓｉｎｇｔｈｉｓａｌｇｏｒｉｔｈｍＢＵＡＡＳＥＩＳＥＧｃａｎｒｅｃｏｇｎｉｚｅｎｅｗｗｏｒｄｓｉｎｖａｒｉｏｕｓｄｏｍａｉｎｓａｎｄｄｏｄｉｓａｍｂｉｇｕａｔｉｏｎａｎｄｓｅｇｍｅｎｔｗｏｒｄｓｗｉｔｈａｒｂｉｔｒａｒｙｌｅｎｇｔｈＩｔｕｓｅｓａｎｉｔｅｒａｔｉｖｅｂｉｇｒａｍｍｅｔｈｏｄｔｏｄｏｗｏｒｄｓｅｇｍｅｎｔａｔｉｏｎＴｈｒｏｕｇｈｏｎｌｉｎｅｓｔａｔｉｓｔｉｃａｌａｎａｌｙｓｉｓ０１１ｔａｒｇｅｔａｒｔｉｃｌｅａｎｄｕｓｉｎｇｔｈｅｏｆｆｌｉｎｅｗｏｒｄｓｆｒｅｑｕｅｎｃｉｅｓｄｉｃｔｉｏｎａｒｙｏｒｔｈｅｉｎｖｅｒｔｅｄｉｎｄｅｘｏｆｔｈｅｓｅａｒｃｈｅｎｇｉｎｅ，ｔｈｅｃａｎｄｉｄａｔｅｗｏｒｄｓｓｅｌｅｃｔｉｏｎａｎｄｄｉｓａｍｂｉｇｕａｔｉｏｎａｒｅｄｏｎｅＯｎｔｈｅｂａｓｉｓｏｆｔｈｅｓｔａｔｉｓｔｉｃａｌｍｅｔｈｏｄｓ，ｐｏｓｔ—ｐｒｏｃｅｓｓｕｓｉｎｇｓｔｏｐｗｏｒｄｓｌｉｓｔ，ｑｕａｎｔｉｔｙｓｕｌ币ｘｗｏｒｄｓｌｉｓｔａｎｄｓｕｍａｍｅｌｉｓｔａｒｅｕｓｅｄｆｏｒｆｕｒｔｈｅｒｐｒｅｃｉｓｉｏｎｉｍｐｒｏｖｅｍｅｎｔ．Ｔｈｅｃｏｍｐａｒａｔｉｖｅｅｖａｌｕａｔｉｏｎｗｉｔｈｔｈｅｆａｍｏｕｓ
ＣｈｉｎｅｓｅｗｏｒｄｓｅｇｍｅｎｔａｔｉｏｎｓｙｓｔｅｍＩＣＴＣＬＡＳ，ｕｓｉｎｇｎｅｗｓａｎｄ
ｐａｐｅｒｓａｓ
ｔｅｓｔｉｎｇｔｅｘｔ，ｓｈｏｗｓｔｈａｔＢＵＡＡＳＥＩＳＥＧｏｕｔｐｅｒｆｏｒｍｓＩＣＴＣＬＡＳｉｎｎｅｗｗｏｒｄｓｒｅｃｏｇｎｉｔｉｏｎａｎｄｄｉｓａｍｂｉｇｕａｔｉｏｎ
Ｋｅｙｗｏｒｄｓ：ｗｏｒｄｓｅｇｍｅｎｔａｔｉｏｎｓｙｓｔｅｍ；ｗｏｒｄｓｅｇｍｅｎｔａｔｉｏｎａｌｇｏｒｉｔｈｍ；ｉｎｆｏｒｍａｔｉｏｎｒｅｔｒｉｅｖａｌ；ｎｅｗｗｏｒｄｒｅｃｏｇｎｉｔｉｏｎ；ｄｉｓａｍｂｉｇｕａｔｉｏｎ
摘要：新词的识别和歧义的消解是影响信息检索系统准确度的重要因素．提出了一种基于统计模型的、面向信息检索的自适应中文分词算法基于此算法，设计和实现了一个全新的分词系统ＢＵＡＡＳＥＩＳＥＧ它能够识别任意领域的各类新词，也能进行歧义消解和切分任意合理长度的词．它采用迭代式二元切分方法，对目标文档进行在线词频统计，使用离线词频词典或搜索引擎的倒排索引，筛选候选词并进行歧义消解．在统计模型的基础上，采用姓氏列表、量词表以及停词列表进行后处理，进一步提高了准确度．通过与著名的ＩＣＴＣＬＡＳ分词系统针对新闻和论文进行对比评测，表明ＢＵＡＡＳＥＩＳＥＧ在新词识别和歧义消解方面有明显的优势
关键词：分词系统：分词算法；信息检索；新词识别；歧殳消解
中图法分类号：ＴＰ３９１文献标识码：Ａ
?ＳｕｐｐｏｒｔｅｄｂｙｔｈｅＮａｔｉｏｎａｌＨｉｇｈ?ＴｅｃｈＲｅｓｅａｒｃｈａｎｄＤｅｖｅｌｏｐｍｅｎｔＰｌａｎｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮｏ２００４ＡＡｌｌ２０３０（国家高技术研究发展计划（８６３））
Ｒｅｃｅｉｖｅｄ２００５－０８?０２；Ａｃｃｅｐｔｅｄ２００５—１０－１１
曹勇刚等：面向信息检索的自适应中文分词系统３５７
从句子中划分出的每个有独立意义的词被称作分词．由于中文词与词之『日Ｊ没有明确的边界，因此，中文分词是机器翻译、分类、主题词提取以及信息榆索的重要基础．与通用的分词系统不同．面向信息检索的中文分词有着强烈的目的性，对它的评价不应依据人的主观看法，而应该考察其是否有助于提高信息检索的准确度影响检索准确度的分词结果主要表现在两个方而¨Ｊ：对新同的识别ｆ包括人名、地名、组织名和荩他不在河典中的术语、俚语或网络用语的识别）；歧义的解决（包括交叉歧义和组合歧义的解决）
若对新词的识别能力不够，则会把一个新词拆分为与新词意义不符的词的组合，导致检索新词时，会得到大量无关的仅匹配新词的各个片段的结果．如对“前沿培训网报名须知”，ＩＣＴＣＬＡＳ分词系统【２】会把它切分为“前沿培训网报名须知”．这样分词在语法上并没有错误，但搜索引擎因此将会得到大量无关结果（以任意顺序包含这５个词的页面都会被找出来）．而从语义上来看，前述短语是两个词“前沿培训｜旬９”和“报名须知”的组合，用户查找的只是一个特定网站的报名须知．用前述短语对Ｇｏｏｇｌｅ和百度进行测试（２００５年７月１８日测试），结果均不令人满意Ｇｏｏｇｌｅ返回了４０６０个页面，其中只有两个符合要求而卣度只返回了１个整句匹配的页面（若手工对查询串分ｉ司，百度则返回了４３篇，同样包含大量不符合要求的页面）叫见，在新词识别不佳的情况下，搜索引擎只会走向两个极端：过多匹配或过少匹配．歧义问题可分为交叉歧义和组合歧义，一直是自然语言处理领域的难题歧义问题相对于新词来说．由于量少，因此对搜索结果影响相对较少，但仍然是一个明显可见的问题．不在词典中的同造成的组合歧义可以归并到新词识别中去．在交叉歧义方面，一些常被提及的词语歧义问题在经过多年的改进后，各主要搜索引擎已解决得几近完美但百度仍存在明显问题，如用“和服”搜索百度，仍在搜索结果首页出现了“青岛东和服装设备”为标题的页面．可见．包含新词的词语歧义仍然是个潜在的问题．综上所述，面向搜索引擎的分词系统对新词的识别能力以及歧义的解决都有很高的要求．而经过分析和实
验，我们发现目前已有的分词系统在这些方面还是有待改进的本文提出一个全新的分词系统ＢＵＡＡＳＥＩＳＥＧ，它的主要目标是尽可能地解决以上两个问题通过词典和统计的结合，ＢＵＡＡＳＥＩＳＥＧ能够在线进行上下文相关的新词识别和歧义消解只要具备定的上Ｆ文，它就具有识别各种类型的新词的能力（不局限于人名、地名、组织名１和消解各类歧义的能力ＢＵＡＡＳＥＩＳＥＧ虽然进行ｒ多遍扫描，但它不仅在准确度上得到大幅度提高，而且在速度上也仍然表现良好．
本文的贡献在于：提出了一种全新的基于语境的自适应分词算法，擅于识别长的未知词和消岐；实现了采用本算法的分词系统ＢＵＡＡＳＥＩＳＥＧ；结合程序和人工对比，评估了ＩＣＴＣＬＡＳ和ＢＵＡＡＳＥＩＳＥＧ的准确度．下面首先介绍统计模型，然后在系统实现部分介绍ＢＵＡＡＳＥＩＳＥＧ的自适应分词算法，包括分词流程、词频词典和停词、量词表的准备、词频和转移概率的统计和利用．其中给出新词识别和歧义消解的示例：最后给出与ＩＣＴＣＬＡＳ分词系统的对比评估以及总结和展单
１统计模型
对于一篇文章，忽略其他符号戒们可以把它看作有问隔的宇的序列的集合．这里的字，包括中文的字符、中文数字串以及英文的单词和数字串ＢＵＡＡＳＥＩＳＥＧ划分序列的标准是：中文序列被各类非巾文字或符号分割，英文序列被非单个卒格的其他符号分割按照以卜定义，我们不妨把这样划分出来的序列称为句子若不考虑句子之间的相关性，则文章４是由ｍ个序列置（０＜ｌ＜＝ｍ）构成的集合：Ａ－｛Ｓ．，＆，岛，．，岛｝．每个序列Ｓ由ｎ个字阡０（０＜ｊＳｎ）按序构成，即Ｓ＝（巩，，％２，，孵。）．对Ｓ，可Ｈ有多种切分为了简化表达并保持和其他文献的一致性，我们集中表示ｓ中的第Ｊ种切分，称为ｗ；产其巾，ｍ，为第，种切分中词的个数，第ｋ个词为ｗｊ，“ｏ＜艇ｍＪ．我们还将峨．至啊。表示为Ｃｌ到巴，即Ｃ．“
基于统计的分词算法就是要求下面概率公式的最优解Ｗ１３／：
矽＝ａｒｇｍａｘＰ（Ⅳ，＝ｗ；？’ｃ？）（１）
。。
Ｗ，
现在的问题就在于如何选取候选词来进行比较．最一般的做法是按序仟取ｎ元（ｎｇｒａｍ），然后做所有基于ｎｇｒａｍ的全切分比较由于直接按元划分，可划分出来的词的数目是旱几何级数增长的．如对＿个长为１１的串的
３５８ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ软件学报Ｖ０１．１７，Ｎｏ３，Ｍａｒｃｈ２００６
切分进行二元切分可切分出ｎ一１个二元组，因此目前最多能做到四元．此时若不考虑任何约束，四元切分的组合数为只“ｘ置川×蜀～×Ｂ州＝ｎ！（Ｈ一１）“Ｈ一２）１０—３）！，它是一个非常庞大的排列组合数，当然，由于字串的有序性以及ｎ元切分之间的包容和互斥性，实际有效组合数目要少得多但是，如何利用这些性质来减少排列组合数，以达到可以容忍的程度，并且让这种切分有意义，仍然是值得探索的问题（在系统实现部分，本文提出了全新的基于二元迭代的切分方法）
假设我们选定了切分方法，从而得到了一系列切分，问题就变为如何在这些切分中找到最佳的切分．若把ｃ？简称为墨则有
ｗ＝ａｒｇｍａｘＰ（霸ｌｓ）＝ａｒｇｍａｘＰ（％）Ｐ（ｓｌ∥，）（２）
一叶
由于有了词串，句子就唯一确定了，故Ｐ（司阡０＝１．实际上，我们需要求解式（３）的最优解：
Ｗ－＝ａｒｇｍａｘＰ（孵）（３）
町
如果假设词与词之间独立，可得式（４）：
矿＝ａｒｇⅡｍ．Ｐ（％）＝ａｒｇｍａｘⅡＨ叶，，）＝ａｒｇｍａｘ≯ｌｎＰ（ｗⅣ）（４）
”ｆ，＝１％Ｆ￡
ＩＣＴＣＬＡＳ的Ｈ最短路径粗分概率模型Ｈ是根据式（４）采用训练集中的全局词频进行求解的，如式（５）所示：
ｍ｛“，ｍｆ
矿２ａｒｇｎｌｌｌａｌ∑１“Ｐ（叶一）≈ａｒｇ肌ｍ１＝１ａｘ∑ｉ＝１ｌｎ（丘，。，７∑Ｉ＝１。啊）（５）
Ｈ，＂，
其中，五。表示词ｗ『，，在训练集中出现的次数但实际情况是，词是和语境相关的，ＩＣＴＣＬＡＳ只是做到了针ＸＣｉ口ｌｌ练
集的全局优化，而没有考虑上下文的影响因此，我们需要引入局部概率的思想，当使用局部概率时，令ｋ．．．为Ⅵ，在被处理文章Ａ中出现的次数．
由于在选择最佳切分时，统计值只是用于比较，且无论全局还是局部的统计值都只是似然估训值，故只具有相对意义，ＢＵＡＡＳＥＩＳＥＧ在保持用于比较的词的统计值计算方式一致的前提下，灵活采用局部概率和全局概率对不同的切分进行比较（优先比较局部概率，当它们相等时则比较全局概率）另外，为了衡量切分出来的各个词的独立性，我们引入转移数（ｔｎｎｓｉｔｉｏｎ）的计算，即一个词ｗｉ，：转移到它的后续词ｕ知的概率的总和，这里，Ｐ（Ⅵ．；叶Ｊ）是计算的局部概率，即在被处理文章Ａ中出现的频率．
丁（ｗＪ，，）＝∑Ｐ（叶．Ｗｊ，ｊ）（６）２系统实现
２．１分词流程
首先面临选词的问题，即选哪些词的序列进行切分评估．常用的ｎ元切分总是要假设一个小的、并不实际的词长度的上界，为识别尽可能多的新词，我们提出采取二元迭代法进行２”元词的选取即首先以二元切分作为候选，筛选后，合并选取的二元词，把它们作为字进入下一轮迭代．如此反复，直到规定的迭代次数或没有符合要求的二元词出现（迭代收敛）为ｉｔ．这种方法可以不设上界或设一个很大的上界．如：４次迭代就可以发现１６个字的词（一般汉字的词长在８个字以下），迭代收敛速度也很快（＋般３敬左右就收敛了）．
系统分词的基本流程如图Ｉ所示．首先，对文本流用有限自动机（ＦＳＡ）进行预处理，识别其中有明显特征的中英文数字（包括基数侧、序数词、分数、小数）、域名、日期等．然后，ＢｉｇｒａｍＦｉｌｔｅｒ对ＦＳＡ的输出进行过滤，并进行词频统计和候选词选择ＢｉｇｒａｍＦｉｌｔｅｒ的输出又被输入到另一个ＢｉｇｒａｍＦｉｌｔｅｒ中，如此反复不断地迭代，直到没有二元组可选为止．再次，基于前述分词结果进行一次最大匹配进行青漏补缺最后，对分词后的文本进行倒排表索引索引后的数据由于包含词和词在测试集中出现的频率，又可以作为新的词频词典来使用若需要更高的准确率，可以用这个由测试集产生的新词频词典对测试集进行新一轮的分词流程，从而形成逐级递进
曾勇刚等：面向信息检索的自适应中文分词系统３５９阳鸯口气（ｂｏｏｔｓ打印ｐｉｎ曲的增强学习由图１可以看到，除了数据输入，ＢＵＡＡＳＥＩＳＥＧ还需要一个词频词典或一个已分词的索引、中文姓氏列表、停词列表咀及量词列表．我们没有限定名字的列表，是因为当代人总是倾向于起不重名的名字，任何训练集都不能包含全部姓名组合
Ｆｉｇ１ＷｏｒｄｓｅｇｍｅｎｔａｔｉｏｎｆｌｏｗｏｆＢＵＡＡＳＥｌＳＥＧ
国１ＢＵＡＡＳＥＩＳＥＧ分词流程
２．２词频词典的准备Array词频词典的准备不像标注训练集的准备那样需要耗费大量的人力及刑间．我们用程序整台了ＣＤＷＳ【５ｊ统计的结果，包括拼音输入法中的词从《人民Ｕ报》１９９８年１月份标注语料中获得的词以及网上散布的一些其他小型词频表，词频表以词为索引，其出现的频率为值词频表中最小词频大于后面将提到的发现新词的词频闽值即收录到词频表中的词总是会作为候选词，这就要求词频表中没有错误的词另外，我们删除了词频表中的中文数字、日期、序数词等，这样可以缩小词频表，因为这些有明确特征的词很容易被ＦＳＡ找出．
２．３分词算法
前文已经提到，我们利用反复调用ＢｉｇｒａｍＦｉｌｔａｒ来选择最长为２”如为调用次数）元的词，这种按照长度硬性拆分的方法必然会包含大量无意义的组合我们的分词算法主要解决如何从中挑选小有意义的组合以及如何消歧的问题．ＢｉｇｒａｍＦｉｌｔｅｒ会对每次输入进行二元词频统计并计算转移（ｔｒａｎｓｉｔｉｏｎ）次数．首先，选取所有－ｔ＇ⅡＮ频词典匹配的词，然后，根据前文的模型推导（式（５）），根据动态规划的思想，利用统计值从前到后‘步步进行筛选即
』ｒｄ］
∑ｈＰ（ｗ：。）＝ＩｙｌｎＰ（ｗｊ，．）Ｉ＋ｌｎＪＤ（～。），Ｏ＜ｍ‘竹－
，＝ｆＬ捌Ｊ
对二元切分来说，句子肛曰在第１次迭代中的候选词ＣａｎｄｉａｔｅＢ喀ｒａｍ－｛ＣｌＣ２，Ｃ２Ｃ３，Ｃ３Ｃ４…．，Ｃｎ一１Ｃｎ｝，通过比较Ｐ（ＣＩＣ２）和只Ｃ２ＣＳ）以及比较按式（６）计算的玎ｃｌｃｚ）和疆ｃ２ｃ１３），可以决定是选ｃ１Ｃ２还是ｃ２ｃ３，依此类推但这样依旧带有盲Ｒ性，没有包含任何启发信息，从而造成迭代中过多的比较由于词频词典并不难构造，我们在词典的基础上进行统计分析，就能在很大程度上提高效率．在词典匹配的基础上，对于有歧义部分或非词典用词，我们定义了词频闽值和转移闽值定义词频闽值是为了加快速度，尽快去掉无关的结果；转移阐值则决定了此Ｂｉｇｒａｍ的相对独立性经过实验，我们把闽值都定义为２就能达到很好的效果．即此词至少出现两次，且有此词随后至少有两种转移
由于使用基于ｔ元（Ｂｉｇｒａ幽的迭代，前一次的Ｂｉｇｒａｍ被当作后～次的Ｇｒａｍ．这样，筛选的梯度也是呈指数缎增长的，解决了ｎ．ｇｒａｍ全切分所带来的组合爆炸问题．采用Ｂｉｇｒａｍ的迭代还避免了构造全切分网络，它每次只在两条路径中寻找更优的路径，直到走到终点，所走的路径就是局部最优的了，且迭代后可趋向于全局最优．在筛选的一系列候选Ｂｉｇｒａｍ中，相互可能存在交叉歧义我们通过比较前后两个词的词频和转移次数来决
定是拆还是合．语义往往具有局部特征，同一篇文章中的词会集中表达相同或相似的语义．某些在训练集中少见
ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ软件学报Ｖｏｌ１７，Ｎｏ．３，Ｍａｒｃｈ２００６
词的组合在特定语境下反复出现，反而更有代表性因此，我们决定优先采用局部概率，其次采用全局概率采用全局概率是不具备适应性的．例如：对ｊ二“曹勇刚才出来啊，曹勇刚太慢了！＂这句话，意义很明确但由于ＩＣＴＣＬＡＳ训练语料中没有出现过曹勇刚或频率过少，它会把这句话分为：“营勇刚才出来啊，茸勇刚太慢了”而ＢＵＡＡＳＥＩＳＥＧ优先采用局部的统计，按照前述的规则，在第一次迭代时，由于“曹勇”的转移次数＜“勇刚”的转移次数，故“曹勇刚”被拆分为“曹勇刚”，第２次迭代时，“曹勇刚”的出现次数和转移次数都是２，故“茸勇刚”被组旨当前后Ｂｉｇｒａｍ都存在时．会比较３个Ｂｉｇｒａｍ的局部概率和全局概率，以确定中间的Ｂｉｇｒａｍ是否拆分．如“郑重要求”会被拆分为“郑重要求”，而不是“郑重要求”而“研究生命苦”在“研究生命苦，研究生很累”中会被切分为“研究生命苦”：在无上Ｆ文或“生命”和“研究”出现多的上下文中会被拆分为“研究生命苦”．这样就使得ＢＵＡＡＳＥＩＳＥＧ具有了很强的适应性虽然对于仪在上Ｆ文中出现一次的新词或歧义，ＢＵＡＡＳＥＩＳＥＧ也不能全部正确识别但是，反映主题的新名词往往会在上下文中多次出现，因此，它的这个优势在实际使用时就十分明显了．
２．４后处理
上一节介绍的只是纯基于统计和词频词典的算法这样的结果对于识别新词已经非常有效了．但由于某些介词、代词、连词、助词等虚词常常和普通名词紧密结合，有较高新词识别率的基于统计的方法往往把它们切分到一起，我们的算法也不例外构造停词表是对这一问题的有效弥补但并不能发现停词就武断地切断Ｂｉｇｒａｍ’因为某些新词可能包台停词，所以仍需依据此停词和其他部分的结合情况进行判断．设在某轮送代中的二元模型由停词幅∽和另一部分（ａ）组成，Ｒ代表局部概率．我们提出３条经验规则：（１）优先切分——当且仅当Ｒ岱ＷＣｉ）＝ＰＬ（Ｃｉ）＝Ｐｚ（Ｓ砷时不予切分；（２）中度优先——当且仪当２ｘＰｚ岱ＷｃＯ＜Ｐ￡（ｃｉ）＋ＰＥ（ｓ叻时进行切分；（３）
优先组合一一当且仪当２×Ｐ＾（ｓｗｃ０玉Ｐ￡（ｃｆ）或２×岛岱ＷＣｉ）＜引ｏＬ姆聊或ｃＰｄｓｗＣｉ）＜ＰＬ嘏聊且ｎ（ｓｗｃ／）＜ＰＬ（ＣＯ）时进行切分．
这３条规则是经验规则，各有偏向如“比”是一个停词，但“比尔”就是一个词尉于规则１，只有没有“比”字单独出现的文中，“比尔”才能被识别．对于规则２，要求“比”和“尔”的次数总和超过了“比尔”的次数的两倍才进行拆分．对于规则３，只有在包含“比尔”的文章中，“比”或“尔”的次数超过或等于“比尔”的次数的两倍，或者“比”和“尔”的次数都超过了“比尔”的次数，“比尔”才会被拆开，在面向信息检索的应用上，我们尽可能保证检索的准确度。也就是宁缺勿滥．所以我们采用ｒ第３条规则处理停词，它适合停词表规模不大且包古的都是常用词的情况．规则２适合于设置了大量可能与新词冲突的停词时的情况而采用规则１ｎＪ以获得较高的召回率本文后面的评测是基于规则３的结果．在人力资源允许的情况下，采取人工标注的方法经过训练来获取常用词的切分边界会更加理想，ＩＣＴＣＬＡＳ就采用了这种方法
很多文章的人名仅出现一次洇此我们需要对人名进行特殊处理通过对ＧＡＴＥ（ｈｔｔｐ：／／ｇａｔｅａｃｕｋ）的姓氏表的增删，我们构造了姓氏表．姓氏足相对稳定的，但有些姓氏往往也是量词，如“年、元”等．所以在切分时，首先要识别量词，然后再识别姓氏．我们根据朱学锋等人总结的现代汉语量词陋】构造了量词表为了提高效率，仅在怀疑是人名时才去判断是否是量词．当确信是姓氏后，会在ＦＭＭＦｉｌｔｅｒ中再根据它随后的词的长度和词频，以及它的转移数和转移的词（如摄、校）进行进一步判断．由于很多文章的作者都被明确分割，故此法对文章标题下以及参考文献中的作者姓名几乎全部能够识别（没有纳入姓氏表的例外）．
３结果评测及相关工作比较
由于各种判定标准以及评测数据集的不一致，分词的评测很难保证完全公平．选用测试集本身就带有不公平性另一个问题是分词标准的不统一性，有砦标注语料自身的标准就不一致【”，造成自动比较的困难，因此大批量的比较不太现实，如：我们为了检索的灵活性，倾向于把数词和量词分开，而ＩＣＴＣＬＡＳ倾向于按照《人民日报》的标注方法把年月日和前面的数字放在一起ＩＣＴＣＬＡＳ把姓和名分开，而我们需要把姓名放在一起，因为搜索“张勇刚”和“曹勇刚”是两个不同的查询．由于ＩＣＴＣＬＡＳ是目前能够免费获取的最好的分词系统，区别于以最大匹配为基准进行比较的其他分词系统，我们以ＩＣＴＣＬＡＳ为基准进行对比评测．这样，可同时看出
曹勇刚等：面向信息检索的自适应中文分词系统３６１
ＢＵＡＡＳＥＩＳＥＧＲ的长处和不足
我们的目标是借助有效的分词系统让计算机更好地处理常用的信息因此在语料的选择上，我们选挥了主要的知识来源——新闻和科技文献．新闻类文章是按顺序取自２００５年７月１５日的５篇新浪网头条短篇新闻（编号为１～５）：科技文献是随机取的ＮＡＳＡＣ２００４的４篇投稿论文（编号为６～９）评测结果见表】，评测过程是：由程序自动剔除非文字符号以及两者分词一致的部分（假定它们都对），然后对照原文人工分析不一致的部分在比较差异时，取正确切分的词的数目作为计数如：“试开采权”被ＩＣＴＣＬＡＳ分为３个词，仍只认为它分错了一个词对于前述不一致的分词规范部分以及纯粹由词典造成的差异，认为两者都对．
ＴａｂｌｅＩＣｏｍｐａｒａｔｉｖｅｅｖａｌｕａｔｉｏｎｂｅｔｗｅｅｎＢＵＡＡＳＥＩＳＥＧａｎｄＩＣＴＣＬＡＳ
表１ＢＵＡＡＳＥＩＳＥＧ和ＩＣＴＣＬＡＳ的分词对比评测
从文章“９可以明显看到，对于上下文丰富、新词很多的几千字的论文，ＢＵＡＡＳＥＩＳＥＧ有着明显的优势；．从新闻１、新闻５我们可以看到，由于上下文的帮助，ＢＵＡＡＳＥＩＳＥＧ在识别新词的能力上，有着比较明显的优势；从对新闻２、新闻３的分词结果看，ＩＣＴＣＬＡＳ在侧法分析上的确具有不错的表现，它对介词短语和动词短语的分割相当出色。而ＢＵＡＡＳＥＩＳＥＧ由于新闻中大量重复出现类似于“通告称”，“向中国”这样的词语而造成较多切分失误（因为我们不把动词作为停词，“向”既是姓又是停词，且我们对停词采取优先组合的策略）．由于人们倾向于检索非平凡的知识．而平凡的知识由于过多，缺少～部分对检索的整体效果影响不大，故这些常用短语对主题检索的影响甚微．也需要指出，由于采取了二元迭代局部优化策略，在对于某些只出现一次的三元词组（ＬＬ如“发言人称”），ＢＵＡＡＳＥＩＳＥＧ会出现切分错误，因为“发言”和“人称”都是词，而文中“称”只出现在“人”后面因此，它会被拆分为“发言人称”．
另外。ＢＵＡＡＳＥＩＳＥＧ没有引入外文姓名的识别，ＩＣＴＣＬＡＳ对外文译名识别率较高，为它带来一定优势，但ＩＣＴＣＬＡＳ对中文分数没有识别能力，它将“十一分之二”分为“十一分之二”．在歧义消解方面，ＩＣＴＣＬＡＳ也存在明显的问题，如“预定义”和“存储量”分别被它分成了“预定义”和“存储量”．
综上所述，我们可以看出两个分同系统各有优势．ＢＵＡＡＳＥＩＳＥＧ倾向于长词切分，更适合于进行主题发现，可用于提高搜索引擎的准确度，使用以它进行索引的搜索引擎，用户不会被引言中所述的一些无关的结果所困扰：而ＩＣＴＣＬＡＳ则更适于词法分析，可进行细粒度切分，并能标注词性，特别是对于常用语的切分十分有效，但它对各领域的新词的识别能力以及词义消岐能力十分有限因此，从总体上看，ＢＵＡＡＳＥＩＳＥＧ倾向于基于语义的切分，比ＩＣＴＣＬＡＳ部分基于语法、部分基于语义的切分更加台理
微软亚洲研究院的ＳＣＭｔ即和ＩＣＴＣＬＡＳ的思路类似．都考虑到了对式（１）进行转换，构造相应的隐马尔科夫链，从而达到同时解决分词和词性／词类标注的效果．因此，两个系统异曲同工，均可以采用成熟的Ｖｉｔｅｒｂｉ算法对问题进行求解同样，ＳＣＭ和ＩＣＴＣＬＡＳ虽然实现细节各异（体现在角色或类的定义以及对新词的发现规则，模板的定义上），但是按照这种方式选取的词序列具有相同的局限性，即受限于被标注的语料的覆盖面训练语料的标注需要大量人力，很难做到全面覆盖虽然ＳＣＭ提出了逐级递进的方法来弥补训练语料的不足，但文中所提的逐级递进的方法需要人的持续参与，且主要是为了提高标注的准确率并进行歧义标识，而无助于发现训练集
ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ软件学报Ｖｏｌ１７，Ｎｏ．３，Ｍａｒｃｈ２００６
中未出现的末知词（如小波分析）．本文的分词算法不需要繁复的训练语料标注过程，是一种非监督方法，可进行跨领域的未知词识别．
某些基于统计的分词系统对新词识别率也较高，如基于互信息、熵的词语提取算法【９１以及基于上下文的二元词切分【１０１等旭它们在候选词的选取上要么依赖于词典，要么采用简单的二元切分，且对词频较小的词无能为力（因为闽值过大且没有对特殊词的处理），故也存在较大局限性ＢＵＡＡＳＥＩＳＥＧ在切分匕提出了迭代的思想，从而拥有了切分长词的能力．并且，它利用了词频词典并引入了对特殊词的处理，因此即便在没有上下文的情况下也能完成基本切分
为了增强分词系统的自适应性，高建峰等人提出了基于线形模型、根据不同拆分标准产生不同输出的方法，取得了良好的效果【【“．这种方法从语料准备到系统实现．在空间和时间上都显得过于复杂，虽然实验结果良好，但其实用性仍受到一定限制并且，这种分词系统对领域的适应性仍依赖于训练集的选取．由于领域的数量大且其划分也具有很多不确定性，很多文章可能是新兴领域或跨领域的，要对测试集自动区分领域并训练适当的分词器十分困难．相对来说，本文算法能在非监督的情况下进行优化选择，自身具有广泛的领域适应性，比较适合于领域混杂的网络文档，是一种简单而有效的方法．
最后，在效率和稳定性卜，我们也进行了对比．为了有较强的可移植性，ＢＵＡＡＳＥＩＳＥＧ全部使用解释型语言ＪＡＶＡ实现，它的切分速度约为使用ｃ＋卜语言实现的ＩＣＴＣＬＡＳ的一半（对于相同的程序，一般基于ＪＡＶＡ实现要比ｃ＋＋的慢１０倍左右喁】，由此可知，从算法的角度来说，ＢＵＡＡＳＥＩＳＥＧ算法的效率更高）在稳定性方面，ＩＣＴＣＬＡＳ开源版在处理包罗万象的网页文本过程中出现了严重的内存泄漏，在对约６００万个网页的数据集ＣＷＴｌ００Ｇ（ｈｔｔｐ：／／ｗｗｗｃｗｉｆｆ．ｏｒｅ４‘ＳｈａｒｅｄＲｅｓ／Ｔｏｏｌ／ＣＷＴｌ００９．ｈｔｍｌ）进行分词时，处理完３０多万个网页就能让拥有１Ｇ内存的机器内存溢｝｜＿ｊ而ＢＵＡＡＳＥＩＳＥＧ能够很顺利地处理完所有网页
４总结和展望
通过理论分析和实验，我制可以看到，ＢＵＡＡＳＥＩＳＥＧ是一个具备较强的跨领域新词识别能力的分词系统本文首次提出了基于二元迭代的切分方法（最长可以切分长度为２”的词，ｎ为迭代次数），并提出了将搜索引擎索引数据作为词频词典实现逐级递进的分词的方法（第１次采用通用词频词典分词并索引，以后再利用索引作为输入再分词，再索引，如此循环往复，直至结果不再变化）．ＢＵＡＡＳＥＩＳＥＧ有着灵活的系统结构，在针对有上下文的文章的分词评测中，有着优良的表现，它具有很高的稳定性和可扩展性，是非常适合搜索引擎使用的分词系统．值得强调的是，不同于以往的中文分词系统，本系统不仅针对中文，对于特定含义的英文词组或短语也同样具有识别能力．目前，ＢＵＡＡＳＥＩＳＥＧ对英文的识别主要是利用了前述分词算法中的统计模型，除ｒ停词表以外，并没有为它进行其他语言相关的特殊处理．因此，它能发现词频较高且相对独＿茏的英文词组，如“ｎｅｔｗｏｒｋｔｕｔｏｒｉｎｇ”（网络教学）．不仅如此，在ＢＵＡＡＳＥＩＳＥＧ的基础上进行中英文主题提取也是十分有效的（本文的关键词就主要来自于对本文的主题提取的结果），限于篇幅，有关内容将另文论述．以后的工作包括：引入对在上下文中出现频次少的外文译名的识别能力；对特殊中文语法现蒙的处理；对不合理切分的进一步排除以及对效率的进一步提升等．
致谢感谢沈旭昆教授提供ＣＤＷＳ的词频词典，感谢李诺、吴安怡同学参与繁复的分词结果人工评测
Ｒｅｆｅｒｅｎｃｅｓ：
［１】ＦｏｏＳ，ＬｉＨＣｈｉｎｅｓｅｗｏｒｄｓｅｇｍｅｎｔａｔｉｏｎａｃｃｕｒａｃｙａｎｄｉｔｓｅｆｆｅｃｔｓｏｉｌｉｎｆｏｒｍａｔｉｏｎｒｅｔｒｉｅｖａｌＩｎｆｏｒｍａｔｉｏｎＰｒｏｃｅｓｓｉｎｇａｎｄＭａｎａｇｅｍｅｎｔ２００４，４０（１）：１６Ｉ－１９０
【２］ＺｈａｎｇＨＰ，ＹｕＨｋＸｉｏｎｇＤＹ，ＬｉｕＱＨＨＭＭ—ＢａｓｅｄＣｈｉｎｅｓｅｌｏｘｉｅａｌａｎａｌｙｚｅｒＩＣＴＣＬＡＳＩｎ：Ｐｒｏｃｏｆｔｈｅ２ｎｄＳｉｇＨａｎＷｏｒｋｓｈｏｐ２００３１８４—１８７
［３］３ＳｕＫＹ，ＣｈａｉｎｇＴＨ，ＣｈａｎｇＪＳＡｎｏｖｅｒｖｉｅｗｏｆｃｏｒｐｕｓ－ｂａｓｅｄｓｔａｔｉｓｔｉｃｓ—ｏｒｉｅｎｔｅｄ（ＣＢＳＯ）ｋｃｈｎｌｑｕｅｓｆｏｒｎａｔｕａｌｌａｎｇｕａｇｅｐｒｏｃｅｓｓｉｎｇＣｏｍｐｕｔａｔｉｏｎａｌＬｉｎｇｕｉｓｔｉｃｓａｎｄＣｈｉｎｅｓｅＬａｎｇｕａｇｅＰｒｏｃｅｓｓｉｎｇ，１９９６，１（１）：１０Ｉ一１５７
曹勇刚等：面向信息检索的自适应中文分词系统
ＺｈａｎｇＨＰ，ＬｉｕＱＭｏｄｅｌｏｆＣｈｉｎｅｓｅｗｏｒｄｓｒｏｕｇｈｓｅｇｍｅｎｔａＯｏｎｂａｓｅｄｏｎＮ—ｓｈａｒｔｅｓｔ—ｐａｔｈｓｍｅｔｈｏｄＪｏｕｍａｉｏｆＣｈｉｎｅｓｅＩｎｆｏｒｍａｔｉｏｎ
Ｐｒｏｃｅｓｓｉｎｇ，２００２，１６（５）：ｌ－７（ｉｎＣｈｉｎｅｓｅｗｉｔｈＥｎｇｉｉｓｈａｂｓｔｒａｃｔ）
ＬｉａｎｇＮＹＣＤＷＳ：ＡｗｏｒｄｓｅｇｍｅｎｔａｔｉｏｎｓｙｓｔｅｍｆｏｒｗｒｉｔｔｅｎＣｈｉｎｅｓｅｔｅｘｔｓｌｏｕｒａａｌｏｆＣｈｉｎｅｓｅｌｎｆｏｒｍａｌｉｏｎＰｒｏｃｅｓｓｉｎｇ，Ｊ９８７，ｌ（２）：
１０１－１０６（ｉｎＣｈｉｎｅｓｅｗｉⅡＩＥｎｇｌｉｓｈａｂｓｔｒａｃｔ）
ＺｈａＸＦＷａｎｇＨＣｌａｓｓｉｆｉｃａｔｉｏｎｏｆｍｏｄｅｍＣｈｉｎｅｓｅｑｕａｎｔｉｔｙｓｕｆｆｉｘａｎｄｎｏｔｕｌ．ＴｅｃｈｎｉｃａｌＲｅｐｏｒｔ，１９９４（ｉｎＣｈｉｎｅｓｅｗｉｔｈＥｎｇｌｉｓｈ
ａｂｓｔｒａｃｔ）ｈｔｔｐ：／／ｗｗｗｉｃｌ．ｐｋｕｃｄｎｅｎ／ｉｃｌ＿ｔｒ／ｃ０１１＿ｅｃｔｅｄＡ】ａｐｅｒｓｉｃｂｉｎｅｓｅ，／ｃｏｌｉｅｅｔｉｏｎ—ｇ／ｙｙｙ２３．ｈｔｍ
ＧａｏＪＦ，ＬｉＭ，ＨｕａｎｇＣＮＩｍｐｒｏｖｅｄｓｏｎｉ＿ｃｅ－ｃｈａｎｎｅｌｍｏｄｅｌｓｆｏｒＣｈｉｎｅｓｅｗｏｒｄｓｅｇｍｅｎｔａｔｉｏｎＩｎ：Ｐｒｏｃｏｆｔｈｅ４１ｓｔＡｎｎｕａｌＭｅｅｔｉｎｇ
ｏｆｔｈｅＡｓｓｏｃｉａｔｉｏｎｆｏｒＣｏｍｐｕｔａｔｆｏｎａｉＬｉｎｇｕｉｓｆｉｃｓ２００３７—１２
ＧｉｌｅｓＪＴ，ＷｏＬＢｅｖｙＭｗＧＴＰ乜期啪ｌｔｅｘｔｐａｒｓｅｒ）ＳＤｆａｖａｒｅｆｏｒｔｅｘｔｍｉｎｉｎｇｉｖｓｔａｔｉｓｔｉｃａｌｄａｔａｍｉｎｉｎｇａｎｄｋｎｏｗｌｅｄｇｅｄｉｓｃｏｖｅｒｙ．
Ｉｎ：Ｂｃ口ｄｏｇａｎＨ，搴ｄ，ＢｏｃａＲａｔｏｎ：ＣＲＣＰｒｅｓｓ，２００３４５５－４７１．
ＣｈａｎｇＪＳ，ＬｉｎＹＣ，ＳｕＫＹＡｕｔｏｍａｔｉｃｃｏｎｓｔｒｕｃｔｉｏｎｏｆａＣｈｉｕｅｓｅｅｌｅｃｔｒｏｎｉｃｄｉｃｔｉｏｎａＷＩｎ：ＹａｒｏｗｓｋｙＤ，ＣｈｌｌｒｃｈＫ，ｅｄｓＰｒｏｃｏｆｔｈｅ
３ｒｄＷｏｒｋｓｈｏｐｏｌｌＶｅｒｙＬａｒｇｅＣｏｒｐｏｒａ、１９９５１０７一ｉ２０
ＤａｉＹＢ，ＫｈｏｏＳＧＴ。ＬｏｂＴＥＡｎｅｗｓｔａｔｉｓｔｉｃａｌｆｏｒｍｕｌａｆｏｒＣｈｉｎｅｓｅｗｏｒｄｓｅｇｍｅｎｔａｔｉｏｎｉｎｃｏｒｐｏｒａｔｉｎｇｃｏｎｔｅｘｔｕａｌｉｎｆｏｒｍａｔｉｏｎＩｎ：
Ｐｒｏｃ．ｏｆｔｈｅ２２ｎｄＡⅡⅡｕａｌＩｎｔ’１ＡＣＭＳＩＧｌＲＣｏｎｅＯｌｌＲｅｓｅａｒｃｈａｎｄＤｅｖｅｌｏｐｍｅｎｔＩｎＩｎｆｏｒｍａｔｉｏｎＲｅｔｒｉｅｖａｌ１９９９８２—８９ＧａｏＪＦ，ＷｕＡＤ，ＬｉＭ，ＨｕａｎｇＣＮ，ＬｉＨｏ，ＸｉａＸＳ，ＱｉｎＨＷ．ＡｄａｐｔｉｖｅＣｈｉｎｅｓｅｗｏｒｄｓｅｇｍｅｎｔａｔｉｏｎ．ｉｎ：Ｐｒｏｅｏｆｔｈｅ４１ｓｔＡＪｌｎｕａｌ
ＭｅｅｔｉｎｇｏｆｔｈｅＡｓｓｏｃｉａｔｉｏｎｆｏｒＣｏｍｐｕｔａｔｉｏｎａｉＬｉｎｇｕｉｓｔｉｃｓ２００４２１—２６
附中文参考文献：
【４１张华平，刘群基于Ｎ一最短路径方法的中文词语粗分模型中立信息学报，２００２。ｉ６（５）：ｉ一７．
【５】粱南元书面汉语自动分词系统——ｃＤｗｓ中文信息学报．１９８７，１（２）：１０１—１０６
［６Ｊ朱学锋，王惠．现代’援语量词与名词的子类划分技术报告，１９９４ｈｔｔｐ：／／ｗｗｗ．ｉｅｉｐｋｕｃｄｕｏｎ／ｉｃ｜ｔｒ／ｃｏｌｌｃｅｔｏｄ』ａｐｅｒｓ／ｃｈｉｎｅｓｅ／
ｅｏｉｌｅｃｔｉｏｎ－２／ｙｙｙ２３ｈｔｍ
窨荑刚（ｉ９７７—１，男，湖南长沙人，博上生．主要研究领域为知识，内客管理．文本挖掘．软件工程
曹羽ｑａ（ｉ９７８－－），男顺士生，主要研究领域为文本挖掘｛软件工程金茂忠（１９４１一），男，教授，博士生导师．主要研究领域为编译技术，软件工程刘超（１９５８一），男’教授，博士生导师，ＣＣＦ高级会员，主要研究领域为软件工程．
啪阿阿忉聊啪Ⅷ
Ⅲ