面向大规模信息检索的中文分词技术研究

面向大规模信息检索的中文分词技术研究王小飞指导教师：王斌前瞻研究中心2006-6-6提纲一、引言二、面向大规模中文信息检索的分词算法三、基于双数组Trie树优化算法的词典四、歧义消除五、未登录词识别六、查询扩展层面的覆盖歧义处理七、实验结果和分析八、总结一、引言研究意义信息检索简介中文分词简介常用评测指标研究意义分词技术的广泛应用：信息检索、人机交互、信息提取、文本挖掘等。目前对分词的研究，大都集中于通用的分词算法，以提高分词准确率为目的。目前的分词算法中，一些切分精度比较高的算法，切分的速度都比较慢；而一些切分速度快的算法，因为抛弃了一些繁琐的语言处理，所以切分精度都不高。–速度：每秒几十k~几M–切分正确率：80%～98%研究意义针对一项具体的上层应用来研究相关的分词技术，这样便于有一个比较确定的分词规范和目标，然后可以有针对性的在分词算法方面有所突破。信息检索：目前跟人们生活最接近，应用最频繁而且技术发展也最成熟的一项信息处理技术。信息检索简介信息检索(InformationRetrieval,IR)：对收集的信息进行标引(Index)，在接收到用户提交的查询请求以后在标引过的数据中进行查找，然后将查找到的相关结果信息返回给用户。用户接口文本操作查询操作标引检索排序数据库管理模块文本数据库索引检出文献查询用户回馈逻辑视图用户需求逻辑视图倒排文档文本文本图1检索过程示意图中文分词简介和困难中文分词(ChineseWordSegmentation)：将一个汉字序列切分成一个一个单独的词。比如将“组合成分子时”切分成“组合/成/分子/时”。困难–分词规范：词的概念和不同应用的切分要求–分词算法：歧义消除和未登录词识别分词规范方面的困难汉语中词的界定–“教育局长”：“教育/局长”？“教育局/长”？“教育/局/长”？–核心词表如何收词？–词的变形结构问题：“看/没/看见”，“相不相信”不同应用对词的切分规范要求不同–输入法：“这是”、“每一”、“并不”、“不多”、“不在”、“就是”–信息检索：“中国/科学院”、“计算/语言学”分词算法上的困难切分歧义的消除–交集型歧义（交叉歧义）：“组合成”我们/小组/合成/氢气了；组合/成/分子；–组合型歧义（覆盖歧义）：“马上”他/从/马/上/下/来；我/马上/就/来/了；–“学生会组织义演活动”:“学生/会/组织/义演/活动”or“学生会/组织/义演/活动”?分词算法上的困难未登录词识别–命名实体：数词、人名、地名、机构名、译名、时间、货币–缩略语和术语：“超女”、“非典”、“去离子水”–新词：“酱紫”、“星盘”先识别已知词还是先识别未登录词–先识别已知词：“内塔尼亚/胡说”–先识别未登录词：“胜利取决/于勇/气”常用评测指标召回率(Recall)–分词：–检索：准确率(Precision)–分词：–检索：正确切分的词语数切分准确率（Precision）=切分出的所有词语数检索出的相关文档数检索准确率（Precision）=检索出的所有文档数正确切分的词语数切分召回率（Recall）=答案中的所有词语数检索出的相关文档数检索召回率（Recall）=所有的相关文档数常用评测指标TREC(TextRetrievalConference)的评测指标–InterpolatedRecall-PrecisionAverages：用插值法计算在11个召回点(0.0~1.0)下相对的准确率。–Averageprecision(non-interpolated)：表示平均每篇相关文档被检索出来时的准确率。表示对于Queryj检索出的所有相关文档数，表示对于Queryj，在第i篇相关文档被检索出时总共检索出的结果文档数。1j#()Averageprecision()nijjiDociApjrjr#()jDoci常用评测指标TREC(TextRetrievalConference)的评测指标–Precision：在检索到x篇文档时的准确率。x为5、10、15、20到1000不等。例如Precision：At30docs(通常用P@30表示)的值为0.5784就是表示前30篇文档中检索的准确率是0.5784。–R-Precision：一个查询检索到R篇文档时的准确率。R为该查询真正相关的文档数。如果一个查询的相关文档数为30，在检索系统检索出的前30篇文档中相关文档数为18，则该查询的R-Precision为18/30＝0.6。二、面向大规模中文信息检索的分词算法分词方面的相关研究成果分词和大规模中文信息检索之间的关系探讨适用于大规模中文信息检索的分词算法分词方面的相关研究成果基于词典和规则的方法基于大规模语料库的统计方法规则和统计结合的方法基于字的切分法基于词典和规则的方法最大匹配–正向最大匹配、反向最大匹配和双向最大匹配–实现简单，而且切分速度快。但无法发现覆盖歧义，对于某些复杂的交叉歧义也会遗漏。全切分–利用词典匹配，获得一个句子所有可能的切分结果。–时空开销非常大。基于理解的分词算法–模拟人的理解过程，在分词过程中加入句法和语义分析来处理歧义问题。–难以将各种语言信息组织成机器可直接读取的形式，还处在试验阶段基于词典和规则的方法基于规则的消歧和未登录词识别–规则消歧CONDITIONFIND(R,NEXT,X){%X.ccat=~w}SELECT1CONDITIONFIND(L,NEAR,X){%X.yx=听|相信|同意}SELECT1CONDITIONFIND(L,NEAR,X){%X.yx=假如|如果|假设|要是|若}SELECT2OTHERWISESELECT1–用规则识别未登录词LocationNamePersonNameLocationNameKeyWordLocationNameLocationNameLocationNameKeyWordOrganizationNameOrganizationNameOrganizationNameKeyWordOrganizationNameCountryName{D|DD}OrganizationNameKeyWord基于大规模语料库的统计方法N元语法（N-gram）模型隐马尔可夫模型（HMM）对于一个随机事件，有一个状态序列{X1X2,…,Xn}，还有一个观察值序列{Y1Y2,…,Yn}。隐马模型可以形式化为一个五元组（S,O,A,B），其中：S={q1,q2,…,qn}：状态值的有限集合O={v1,v2,…vm}：观察值的有限集合A={aij}，aij=p(Xt+1=qj|Xt=qi)：转移概率B={bik}，bik=p(Ot=vk|Xt=qi)：输出概率={}，=p(X1=qi)：初始状态分布niiinnkwwwwPwwwwPwwwPwwPwPwwwPWP112112121312121)...|()...|()...|()|()()...()(ii基于大规模语料库的统计方法互信息(MI,MutualInformation)MI越大，表示两个字之间的结合越紧密。反之，断开的可能性越大。当x与y关系强时，MI(x,y)=0；x与y关系弱时，MI(x,y)≈0；而当MI(x,y)0时，x与y称为“互补分布”。最大熵模型(ME,MaxEntropy)在已知条件下选择一个合适的概率分布来预测事件。22(,)(|)(,)loglog()()()pxypyxMIxypxpypy2{|()(),1}()()log()*argmax()jjxPpEpfEpfjkHppxpxpHp规则和统计结合的方法通常利用词典进行初切分，然后用其它的概率统计方法和简单规则消歧和进行未登录词识别。比如：–利用词典匹配进行初切分得到一个切分词图，然后利用词频信息求词图N条最短路径的N-最短路径法。–最大匹配算法、state-of-the-art分类器和支持向量机的结合。–通过词典匹配找出所有交叉歧义，利用Bigram语言模型或其变形来消除歧义。基于字的切分方法N元切分法(N-gram)：对一个字符串序列以N为一个切分单位进行切分。–如二元切分法：“ABCDEFG”→“AB\CD\EF\G”–交叉二元切分法(OverlappingBigram)：“ABCDEFG”→“AB\BC\CD\DE\EF\FG”–简单快速，但会产生大量无意义的标引词，导致标引产生的索引文件的空间，以及检索和进行标引的时间都大大增加。同时，因为它的切分单位并非语言学意义上的词语，所以也会导致检索的查准率下降。分词和大规模中文信息检索之间的关系探讨在当前的信息检索技术中，中文切分是必要的。问题–是否需要按语言学意义上的词进行切分。–文档和查询二者的切分方法是否需要一致。–是否检索系统使用的分词算法切分精度越高其检索结果就越好。分词和大规模中文信息检索之间的关系探讨表1.TREC5和TREC6中文信息检索实验比较分词和大规模中文信息检索之间的关系探讨基于字的切分：单字切分，二元切分和交叉二元切分基于词的切分：基于词典的匹配和基于统计的方法7组关于切分方法的实验比较结论：–字比词好：3组；–词比字好：3组；–二者差不多：1组3组关于切分一致的实验比较结论：–切分方法一致更好：1组–切分方法不一致的更好：2组查询是基于字的切分时，文档是最大匹配切分的结果更好。查询是基于词的切分时，文档是基于字的切分的结果更好。分词和大规模中文信息检索之间的关系探讨两组实验：1．基于单字切分、交叉二元切分和利用ICTCLAS系统切分的检索性能比较。文档和查询采用同一种切分方法。2．基于单字切分、交叉二元切分和利用ICTCLAS系统切分的检索性能比较。查询采用人工切分的方法。实验环境：数据：北大提供的中文网页测试集CWT部分数据。检索系统：麻州大学和卡内基梅隆大学合作开发的检索工具包Lemur分词和大规模中文信息检索之间的关系探讨0.38720.38230.3565R-Precision0.41750.42110.3895At30docs0.43680.44210.4158At20docs0.51050.48950.4316At10docsPrecision0.35830.34270.3192Averageprecision(non-interpolated)forallreldocs0.00770.02520.02801.00.10700.11480.12930.90.19600.17770.18740.80.24350.23620.23260.70.29520.30470.27090.60.38930.34460.30150.50.46230.39300.35130.40.51500.48420.40680.30.53590.52220.47580.20.59230.61370.57450.10.75340.81000.74290.0InterpolatedRecall-PrecisionAveragesRecallICTCLAS二元交叉切分单字0.38720.38230.3565R-Precision0.41750.42110.3895At30docs0.43680.44210.4158At20docs0.51050.48950.4316At10docsPrecision0.35830.34270.3192Averageprecision(non-interpolated)forallreldocs0.00770.02520.02801.00.10700.11480.12930.90.19600.17770.18740.80.24350.23620.23260.70.29520.30470.27090.60.38930.34460.30150.50.46230.39300.35130.40.51500.48420.40680.30.53590.52220