面向大规模信息检索的中文分词技术研究.ppt
面向大规模信息检索的中文分词技术研究,王小飞指导教师：王斌前瞻研究中心2006-6-6,提纲,一、引言二、面向大规模中文信息检索的分词算法 三、基于双数组Trie树优化算法的词典 四、歧义消除五、未登录词识别六、查询扩展层面的覆盖歧义处理 七、实验结果和分析 八、总结,一、引言,研究意义信息检索简介中文分词简介常用评测指标,研究意义,分词技术的广泛应用：信息检索、人机交互、信息提取、文本挖掘等。目前对分词的研究，大都集中于通用的分词算法，以提高分词准确率为目的。目前的分词算法中，一些切分精度比较高的算法，切分的速度都比较慢；而一些切分速度快的算法，因为抛弃了一些繁琐的语言处理，所以切分精度都不高。速度：每秒几十k几M切分正确率：80%98%,研究意义,针对一项具体的上层应用来研究相关的分词技术，这样便于有一个比较确定的分词规范和目标，然后可以有针对性的在分词算法方面有所突破。信息检索：目前跟人们生活最接近，应用最频繁而且技术发展也最成熟的一项信息处理技术。,信息检索简介,信息检索(Information Retrieval,IR)：对收集的信息进行标引(Index)，在接收到用户提交的查询请求以后在标引过的数据中进行查找，然后将查找到的相关结果信息返回给用户。,图1 检索过程示意图,中文分词简介和困难,中文分词(Chinese Word Segmentation)：将一个汉字序列切分成一个一个单独的词。比如将“组合成分子时”切分成“组合/成/分子/时”。困难分词规范：词的概念和不同应用的切分要求分词算法：歧义消除和未登录词识别,分词规范方面的困难,汉语中词的界定“教育局长”：“教育/局长”？“教育局/长”？“教育/局/长”？核心词表如何收词？词的变形结构问题：“看/没/看见”，“相不相信”不同应用对词的切分规范要求不同 输入法：“这是”、“每一”、“并不”、“不多”、“不在”、“就是”信息检索：“中国/科学院”、“计算/语言学”,分词算法上的困难,切分歧义的消除交集型歧义（交叉歧义）：“组合成”我们/小组/合成/氢气了；组合/成/分子；组合型歧义（覆盖歧义）：“马上”他/从/马/上/下/来；我/马上/就/来/了；“学生会组织义演活动”:“学生/会/组织/义演/活动”or“学生会/组织/义演/活动”?,分词算法上的困难,未登录词识别命名实体：数词、人名、地名、机构名、译名、时间、货币 缩略语和术语：“超女”、“非典”、“去离子水”新词：“酱紫”、“星盘”先识别已知词还是先识别未登录词先识别已知词：“内塔尼亚/胡说”先识别未登录词：“胜利取决/于勇/气”,常用评测指标,召回率(Recall)分词：检索：准确率(Precision)分词：检索：,常用评测指标,TREC(Text Retrieval Conference)的评测指标Interpolated Recall-Precision Averages：用插值法计算在11个召回点(0.01.0)下相对的准确率。Average precision(non-interpolated)：表示平均每篇相关文档被检索出来时的准确率。表示对于Query j检索出的所有相关文档数，表示对于Query j，在第i篇相关文档被检索出时总共检索出的结果文档数。,常用评测指标,TREC(Text Retrieval Conference)的评测指标Precision：在检索到x篇文档时的准确率。x为5、10、15、20到1000不等。例如Precision：At 30 docs(通常用P30表示)的值为0.5784就是表示前30篇文档中检索的准确率是0.5784。R-Precision：一个查询检索到R篇文档时的准确率。R为该查询真正相关的文档数。如果一个查询的相关文档数为30，在检索系统检索出的前30篇文档中相关文档数为18，则该查询的R-Precision为18/300.6。,二、面向大规模中文信息检索的分词算法,分词方面的相关研究成果分词和大规模中文信息检索之间的关系探讨适用于大规模中文信息检索的分词算法,分词方面的相关研究成果,基于词典和规则的方法 基于大规模语料库的统计方法规则和统计结合的方法基于字的切分法,基于词典和规则的方法,最大匹配正向最大匹配、反向最大匹配和双向最大匹配实现简单，而且切分速度快。但无法发现覆盖歧义，对于某些复杂的交叉歧义也会遗漏。全切分利用词典匹配，获得一个句子所有可能的切分结果。时空开销非常大。基于理解的分词算法模拟人的理解过程，在分词过程中加入句法和语义分析来处理歧义问题。难以将各种语言信息组织成机器可直接读取的形式，还处在试验阶段,基于词典和规则的方法,基于规则的消歧和未登录词识别规则消歧CONDITION FIND(R,NEXT,X)%X.ccat=wSELECT 1CONDITION FIND(L,NEAR,X)%X.yx=听|相信|同意SELECT 1CONDITION FIND(L,NEAR,X)%X.yx=假如|如果|假设|要是|若SELECT 2OTHERWISE SELECT 1 用规则识别未登录词 LocationName Person Name LocationNameKeyWordLocationName Location Name LocationNameKeyWordOrganizationName Organization Name OrganizationNameKeyWordOrganizationName Country Name 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)：初始状态分布,基于大规模语料库的统计方法,互信息(MI,Mutual Information)MI越大，表示两个字之间的结合越紧密。反之，断开的可能性越大。当x 与y 关系强时，MI(x,y)=0；x与y关系弱时，MI(x,y)0；而当MI(x,y)0时，x与y称为“互补分布”。最大熵模型(ME,Max Entropy)在已知条件下选择一个合适的概率分布来预测事件。,规则和统计结合的方法,通常利用词典进行初切分，然后用其它的概率统计方法和简单规则消歧和进行未登录词识别。比如：利用词典匹配进行初切分得到一个切分词图，然后利用词频信息求词图N条最短路径的N-最短路径法。最大匹配算法、state-of-the-art分类器和支持向量机的结合。通过词典匹配找出所有交叉歧义，利用Bigram语言模型或其变形来消除歧义。,基于字的切分方法,N元切分法(N-gram)：对一个字符串序列以N为一个切分单位进行切分。如二元切分法：“ABCDEFG”“ABCDEFG”交叉二元切分法(Overlapping Bigram)：“ABCDEFG”“ABBCCDDEEFFG”简单快速，但会产生大量无意义的标引词，导致标引产生的索引文件的空间，以及检索和进行标引的时间都大大增加。同时，因为它的切分单位并非语言学意义上的词语，所以也会导致检索的查准率下降。,分词和大规模中文信息检索之间的关系探讨,在当前的信息检索技术中，中文切分是必要的。问题是否需要按语言学意义上的词进行切分。文档和查询二者的切分方法是否需要一致。是否检索系统使用的分词算法切分精度越高其检索结果就越好。,分词和大规模中文信息检索之间的关系探讨,表1.TREC5和TREC6中文信息检索实验比较,分词和大规模中文信息检索之间的关系探讨,基于字的切分：单字切分，二元切分和交叉二元切分 基于词的切分：基于词典的匹配和基于统计的方法 7组关于切分方法的实验比较结论：字比词好：3组；词比字好：3组；二者差不多：1组3组关于切分一致的实验比较结论：切分方法一致更好：1组切分方法不一致的更好：2组查询是基于字的切分时，文档是最大匹配切分的结果更好。查询是基于词的切分时，文档是基于字的切分的结果更好。,分词和大规模中文信息检索之间的关系探讨,两组实验：1基于单字切分、交叉二元切分和利用ICTCLAS系统切分的检索性能比较。文档和查询采用同一种切分方法。2基于单字切分、交叉二元切分和利用ICTCLAS系统切分的检索性能比较。查询采用人工切分的方法。实验环境：数据：北大提供的中文网页测试集CWT 部分数据。检索系统：麻州大学和卡内基梅隆大学合作开发的检索工具包Lemur,分词和大规模中文信息检索之间的关系探讨,表2 实验1的结果,分词和大规模中文信息检索之间的关系探讨,表3 实验2的结果,分词和大规模中文信息检索之间的关系探讨,分词精度与检索性能的实验比较(Fuchun Peng等,2002)测试数据：TREC-5和TREC-6的中文测试集 检索系统:OKAPI系统 三种分词算法：基于词典的前向最大匹配71%和85%基于文本压缩的PPM算法90%和95%基于EM的自监督算法44%,49%,53%,56%,59%,70%,75%,77%,分词和大规模中文信息检索之间的关系探讨,图2 Kd=10时的12组检索结果比较,分词和大规模中文信息检索之间的关系探讨,原因：查询切分和文档切分采用相同的分词算法，有一些文件切分错误的词，在查询时也遇到相同的切分错误，所以即使切分阶段错误，但最后相同错误匹配，使得仍然可以正确检索到；有些词被错误的切分成几个部分，尽管这样会导致分词正确率下降，但对于检索来说，最后可以通过结果合并得到正确的结果，分词的错误并不影响检索的性能；分词测得的准确率高低并不是绝对的，有时跟用标准答案有关。这涉及到对词的定义问题，有些标准答案认为是该切分的词，实际上不切分用于检索更加准确一些。如：“国内”vs”国内“、“民进党团”vs”民进党团“vs”民进党团“,适用于大规模中文信息检索的分词算法,分词算法的时间性能要比较高。尤其是现在的web搜索，实时性要求很高。所以作为中文信息处理基础的分词首先必须占用尽可能少的时间。分词正确率的提高并不一定带来检索性能的提高。分词到达一定精度之后，对中文信息检索的影响不再会很明显，虽然仍然还是有一些影响，但是这已经不是CIR的性能瓶颈。所以片面的一味追求高准确率的分词算法并不是很适合大规模中文信息检索。在时间和精度之间存在矛盾无法兼顾的情况下，我们需要在二者之间找到一个合适的平衡点。切分的颗粒度仍然可以依照长词优先准则，但是需要在查询扩展层面进行相关后续处理。在信息检索中，分词算法只需要集中精力考虑如何消除交叉歧义。对于覆盖歧义，我们可以利用词典的二次索引和查询扩展来解决。未登录词识别的准确率要比召回率更加重要。要尽量保证未登录词识别时不进行错误结合，避免因此切分出错误的未登录词。如果将单字错误的结合成未登录词了，则有可能导致无法正确检索到相应的文档。,适用于大规模中文信息检索的分词算法,待切分文本,初切分结果,核心词典,消除交叉歧义,未登录词识别,新词词典,切分结果,交叉歧义检测,图3 面向大规模中文信息检索的分词算法流程图,三、基于双数组Trie树优化算法的词典,图4.传统的Trie树结构转换成两个线性数组,三、基于双数组Trie树优化算法的词典,s,t,c,base,check,s,t,c,图4.双数组Trie树的状态转移示意图,三、基于双数组Trie树优化算法的词典,数组构造的基本思想：对6763个常用汉字根据其内码相应的赋予从16763的序列码，放入base1-base6763。若首字序列码是i的词语有n个，设所有第二个字的序列码依次为a1,a2,a3,an,则这n个第二字在base数组中的位置依次为 basei+a1,basei+a2,basei+an。依次类推第三字、第四字第k字的位置。如果basei和checki同为0，表示位置i为空；如果basei为负值，表示该状态为一个词语。,三、基于双数组Trie树优化算法的词典,以前的处理顺序：S-A-B-C-D-E-F-G-H-I-J-K-L加入优化策略之后的处理顺序：S-A-C-B-F-D-E-G-H-I-J-K-L,三、基于双数组Trie树优化算法的词典,实验环境：CPU 1.5G，内存512M，操作系统为Windows XP 词典词条总数：75784所有算法均用c+实现。,实验一 分别用未加入优化策略的双数组Trie树（Double-Array Trie）算法与优化后的双数组Trie树（Double-Array Trie）算法生成词典的双数组文件，比较空间利用率。结果：未加入优化策略生成的数组长度为140438，加入优化策略后生成的数组长度为114624，数组长度减少了2万5千多。数组的空间利用率由85.44%提高到91.27%。,三、基于双数组Trie树优化算法的词典,实验二 比较双字Hash索引机制算法和优化的双数组Trie树（Double-Array Trie）算法查找词语的速度。,三、基于双数组Trie树优化算法的词典,实验三 比较普通Trie树算法和双数组Trie树优化算法用于正向最大匹配自动分词的速度。语料库文本均为未切分的人民日报98年语料。文本1：98年1月语料大小为4,092,478字节文本2：98年2月语料大小为4,153,811字节文本3：98年4月语料大小为4,666,292字节,四、歧义消除,交叉歧义检测基于双字耦合度和t-测试差消歧实验结果,四、歧义消除,图5.交叉歧义图,四、歧义消除,双字耦合度：求两个字的结合强度 和互信息比较：字间位置切分正确率PSeg正确切分的位置数/切分文本字间位置总数训练集：98年1至6月的人民日报语料库测试集：SIGHAN03香港城市大学测试语料,四、歧义消除,图6 双字耦合度和互信息的字间位置切分正确率比较,四、歧义消除,双字耦合度的缺点：只是独立的计算两个连续汉字的结合强度，并没有考虑到上下文的信息。比如：Couple（对，比）0.75，Couple（比，方）1.0，Couple（方，法）0.97,四、歧义消除,t-测试(t-test)：t-测试差总体来说，0时，yz的字间位置倾向于判断为连接；反之判断为断开。,四、歧义消除,双字耦合度和t-测试差结合消歧,四、歧义消除,利用词典扫描，找出句子中所有的交叉歧义，标记相关的歧义位置。计算歧义位置的双字耦合度和t-测试差的线性叠加值CDT。按值的大小顺序依次判断歧义位置的切分与否。其中并不需要每个位置都进行判断，因为有一个歧义位置确定之后，该歧义位置相关的其它歧义位置就不需要再判断，可以直接选择是切分还是连接了。,消歧过程：,四、歧义消除,实验训练语料库：已经切分过的人民日报98年16月语料 封闭测试：人民日报98年1月语料开放测试：SIGHAN 05年北京大学和微软研究院语料四组实验结果比较：1.单独用双字耦合度判断歧义位置；2.用t-测试差判断歧义位置；3.互信息和t-测试差结合判断歧义位置；4.双字耦合度和t-测试差结合判断歧义位置；,四、歧义消除,实验结果,表4 三种歧义判断算法的准确率比较,五、未登录词识别,采用各种命名实体和新词一体化识别策略正确的合并被错误切分成单字的汉字。单字的成词位置概率对于连续的单字串/c1/c2/c3/cn/，其中汉字ci的各位置概率分别为：P(ci,B)ci出现在词首的概率P(ci,I)ci出现在词中的概率P(ci,E)ci出现在词尾的概率P(ci,S)ci单独成词的概率,五、未登录词识别,表5 基于位置成词概率的单字合并规则,五、未登录词识别,局部二元串频统计：预先统计待切分文档中二元字对的共现次数 如果字串(cici+1)在被切分文档中重复出现次数超过某个数时，(P(ci,S)+P(ci+1,S)/2的阈值可以增大为s。,五、未登录词识别,实验实验环境：同上一章歧义消除的环境。一共2组实验：根据字的位置成词概率识别未登录词。用字的位置成词概率结合局部二元串频统计识别未登录词。,五、未登录词识别,表6 未登录词识别实验结果,六、查询扩展层面的覆盖歧义处理,目的：解决切分粒度过大问题，提高召回率。方法：基于词典的二次索引进行查询扩展。在查询扩展时将相应的覆盖词加入到查询表达式中去。这里覆盖词是指词典中包含了查询词的其他词。,六、查询扩展层面的覆盖歧义处理,图7 词典的二次索引示意图,六、查询扩展层面的覆盖歧义处理,实质：简单的词语切分过程。将分词中的覆盖歧义处理部分放到词典预处理阶段。优点：节省切分的时间，减少了索引数据的冗余度,图8 分词中覆盖歧义省略示意图,六、查询扩展层面的覆盖歧义处理,缺点：有可能将一些语义上无关联的词加入到查询扩展中去，导致检索准确率降低。为了避免检索时将过多的不相关文档排到结果集的前面，我们根据切分位置互信息的大小赋予两个词不同的权重。权重计算方法：如果W是由一次索引得到的词，则W的权重为1；如果W是由词W的二次索引得到的词2.1 若W在W中未引起交叉歧义，则W的权重；2.2 若W在W中是交叉歧义的一种结果，则W的权重，其中W是W中和W引起交叉歧义的另一个词。,七、实验结果和分析,分词测试：硬件环境：CPU3.2G，内存512M三种算法：IRSEG、ICTCLAS、前向最大匹配。词典：75784个词条 测试集：SIGHAN 05年北大和微软研究院提供的语料库,七、实验结果和分析,分词测试：评测指标：,未登录词识别准确率,未登录词识别召回率,登录词识别召回率,七、实验结果和分析,分词测试结果,表7 分词算法切分速度比较,七、实验结果和分析,分词测试结果,表8 pku语料库测试结果,七、实验结果和分析,分词测试结果,表9 msr语料库测试结果,七、实验结果和分析,分词测试结果,图9三种算法平均的切分准确率和召回率,七、实验结果和分析,分词测试结果相关说明测试集切分标准不同。比如人名、时间、数量词等未登录词的切分标准。语料库本身就存在一些切分不太合理或者可以说错误的地方。“相当大军区级单位的正职首长”语料库切分结果：相当大军区级单位的正职首长IRSeg切分结果：相当大军区级单位的正职首长有些地方虽然与语料库切分结果不同而被认为是切分错误，但实际上在语言学上来说，并没有严格的对错之分。甚至，有些我们认为要比语料库中的切分更合适一些。比如：“系主任”、“并不可怕”等,七、实验结果和分析,检索测试：实验环境：1.检索系统：采用CMU和UMass合作开发的Lemur工具包2切分算法：IRSEG、ICTCLAS、前向最大匹配（Forward Maximum Match,FMM）和交叉二元切分法（Overlapping Bigram，OVB）。检索采用查询切分和文档切分一致。3测试数据：北大天网提供的中文Web测试集CWT100g的部分数据。查询集是选用SEWM2005中文Web检索主题查询集。评测指标：采用trec评测指标。,七、实验结果和分析,表10 没有进行查询扩展的检索结果比较,七、实验结果和分析,图10 Precision at 10docs,20docs,30docs,七、实验结果和分析,表11 IRSEG加入查询扩展前后的检索结果比较,八、总结,主要工作：1.分析总结了适合于大规模信息检索的分词算法特点；在分词的时间性能、准确率、切分颗粒度和未登录词识别四个方面给出了我们自己的看法。2.设计和实现了一个面向大规模中文信息检索的分词系统。在词典算法上，提出了基于双数组Trie树优化算法的词典机制，大大提高了分词速度；在歧义消除方面，提出了双字耦合度和t-测试差结合的方法来消除交叉歧义；在未登录词识别方面，用字的位置成词概率和局部二元串频统计来提高统一识别各种命名实体和新词；另外，对于切分中的覆盖歧义，提出了在查询扩展层面利用词典二次索引的解决方法；,八、总结,下一步研究方向和需要改进的地方：1.利用机器学习的方法进行一些参数选择的实验，争取得到更加合理的参数值。2.未登录词识别方面，本文提出的算法还有很多可以改进的地方。比如引入一些姓氏、机构名和地名特征用字，相信还会使准确率和召回率有进一步的提高。,谢谢,THIS IS THE END!,
