（计算机应用技术专业论文）中文索引策略的研究.pdf

啥尔滨工程大学硕士学位论文 摘要 随着i n t e r a c t 的迅猛发展。互联网上的信息呈爆炸性增长。研究并掌握 信息检索的核心技术具有十分重要的理论意义和广泛的应用价值。由于中文 文档没有用于切分单词的空格，使得对索引策略的研究成为中文信息检索的 特有问题。 对文档进行分词处理是研究索引策略必须要实现的问题，因此，本文对 分词进行了研究。首先分析了分词歧义，然后剖析了当前各种处理歧义问题 的解决方案以及数据平滑闯题，最后针对在分词中非常重要的未登录词处理 问题提出了一种解决方案。 为研究中文索引策略，本文实现了一个信息检索系统。首先研究了实现 信息检索系统中索引的组织、存储、查找以及压缩等问题，然后研究了检索 模型，最后选择了恰当的索引的数据结构，确认目前被公认为较好的2 - 泊松 概率模型的b m 2 5 公式为本文所使用的检索模型。 本文对索引策略进行了深入研究。首先对基于词的索引策略、一元文法 索引策略和二元文法索引策略的性能进行了比较，然后探讨了索引策略的融 合问题，最后提出了改进的二元文法索引策略。本文应用2 泊松模型的b m 2 5 公式在啦c 公开数据集上测试了上述几种索引策略的性能。实验表明，改 进的二元文法索引策略在主要性能评测参数平均精确率、m 精确率参数上相 对较优，在召回率与精确率对应表、文件数与精确率对应表中性能较优或与 最优可比。 关键词：中文信息检索；索引策略；检索模型；分词 哈尔滨工程大学硕士学位论文 a b s t r a c t w i mt h e i n c r e a s i n g i n f o r m a t i o na v a i l a b l ei nt h ei n f o r m a t i o ne r a , t h e i n f o r m a t i o nr e t r i e v a l ( i r ) s y s t e mb e c o m e sm o r ea n dm o r ei m p o r t a n ta sa n i n d i s p e n s a b l ew a yo fa c c e s s i n gt h ei n f o r m a t i o n b e c a u s et h e r ei sn ob l a n kt o s e g m e n tc h i n e s et e x t s ，r e s e a r c ho ni n d e x i n gs t r a t e g i e si sap e c u l i a rp r o b l e mi n c h i n e s ei i l s e g m e n t a t i o ni sa l li n d i s p e n s a b l es t e pi nc h i n e s ei r s o ，t h i st h e s i ss t u d i e s s e g m e n t a t i o n n 圮t h e s i sa n a l y z e ss e g m e n t a t i o na m b i g u i t y , a n a l y s e st h ec u r r e n t s o l u t i o n sf o rs e g m e n t a t i o na m b i g u i t ya n dd a t as m o o t h i n gt e c h n o l o g i e s , a n dp u t s f o r w a r das o l u t i o nf o ro u t - o f - v o c a b u l a r yp r o b l e m , w h i c hi sak e yp r o b l e mi n c h i n e s ei r 1 1 1 i st h e s i si m p l e m e n t sa ni rs y s t e mf o rt h er e s e a r c ho i lc h i n e s ei n d e x i n g s t r a t e g y f o rt h ef i r s t , o r g a n i z a t i o n , s t o r e ，s e a r c ha n dc o m p r e s s i o no fi n d e x i n gi n t h ei rs y s t e mi ss t u d i e d f o rt h es e c o n d ，i rm o d e l sa r ee x p l o r e d a tl a s t ，t h e p r o p e ri n d e x i n gd a t as t r u c t u r ei ss e l e c t e d ，a n dt h ef o r m u l ab m 2 5o f2 - p o s s i o n m o d e l ，w h i c ha c h i e v e sg o o dr e s u l t si np r e v i o u se x p e r i m e n t s ，i su s e di nt h i st h e s i s 1 1 1 i st h e s i sd e e p l ys t u d i e si n d e x i n gs t r a t e g y f o rt h ef i r s t t h ep e r f o r m a n c eo f t h ei n d e x i n gs t r a t e g yb a s e do i lc h i n e s ew o r d ，b a s e do nu n i g r a ma n db i g r a ma r e c o m p a r e d f o rt h es e c o n d , t h ec o m b i n a t i o no ft h ed i f f e r e n ti n d e x i n gs t r a t e g i e si s d i s c u s s e & a tl a s t , t h ei m p r o v e db i g r a mi n d e x i n gs t r a t e g yi sp u tf o r w a r d 1 1 1 i s e f f e c t i v e n e s so ft h en e wa p p r o a c hi se v a l u a t e do nt r e cm a n d a r i nc o r p u sb y a p p l y i n gb m 2 5o f 2 - p o s s i o nm o d e l e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ei m p r o v e d b i g r a mi n d e x i n gs t r a t e g yi sn o to n l yr e l a t i v e l ye f f e c t i v ew i t hm e a na v e r a g e p r e c i s i o na n dr - p r e c i s i o nb u ta l s ob e t t e ro rc o m p a r a b l ew i t ht h eb e s tr e s u l ti n r e c a l ll e v e lp r e c i s i o n a v e r a g e sa n dd o c u m e n tl e v e la v e r a g e s k e y w o r d s ：c h i n e s ei n f o r m a t i o nr e t r i e v a l ；i n d e x i n gs t r a t e g y ；i n f o r m a t i o n r e t r i e v a lm o d e l ；s e g m e n t a t i o n 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：垒：! 主， 日期：伽7 年月7 日 哈尔滨工程大学硕士学位论文 第1 章绪论 1 1 课题研究的背景和意义 随着i n t e r n e t 的迅猛发展，各种信息资源越来越丰富。互联网上的信息 呈爆炸性增长，表1 1 列出了不同时期的搜索引擎索引的文档情况。 表1 1 不同时期搜索引擎索引的文档数量 时间搜索引擎索引的文档数据来源 1 9 9 4 m c b r y a n 1o 0 0 0 m c b r y a n9 4 1 9 9 7 1 1w e b c r a w l e r2 百万一1 亿 s e r g e yb r i n9 8 h t t p y w w w g o o g l e e o r n p r e s s p r e s s r e l 3 b i l l i o 2 0 0 1 1 2 g o o g l e 3 0 亿 n h t m l h t l p ：n e w s ，x i n h u a n e t c o n y i t 2 0 0 5 - 0 8 1 0 e o n t 2 0 0 5 9 y a h o o 1 9 2 亿 e n l3 3 3 3 5 8 2 ，h m t 当信息的来源己不再是主要问题时，如何快捷准确地获取感兴趣的信 息，就成为人们关注的主要问题。但互联网信息天生的异构、分散以及海量 等特性对检索技术提出了更高的要求，各种信息检索、过滤、提取技术逐渐 成为研究的重点。现在，以w e b 搜索引擎为代表的信息检索技术已经取得 了很大成功，g o o g l e 、百度、y a h o o ! 等搜索引擎已深入到大家的日常工作和 生活之中，成为获取信息不可或缺的工具，也因此带来了数千亿美元的商业 价值。 信息检索的任务是根据用户提交的关键词在文档集中为用户检出最相 关的子文档集，或者按检出的文档与关键词的相关程度进行排序，作为对检 索用户所提出查询的回应。目前的信息检索系统已经能够为用户提供大量的 检索结果，初步解决了“查到”的问题。例如用g o o g l e 检索“哈尔滨工程大 学”可检索到2 ，1 8 0 ，0 0 0 个网页，即使要求搜索到的页面中必须是完整的”哈 1 哈尔滨1 ：程大学硕士学位论文 尔滨工程大学”这个字符串，可检索到的页面仍然高达6 9 2 ，0 0 0 项。但是用户 不可能对检索到的网页全部进行测览，这就需要对检索到的结果文档集进行 排序。如何对结果文档集进行排序是当前信息检索技术中研究的主题之一。 信息检索的引擎的优劣将直接影响到提供给用户什么样的信息，随着人 们对网络信息的依存度的提高，优良的搜索引擎将对我们的生产生活产生重 要的影响，同时信息检索也是情报获取的一个重要手段，目前最具影响力的 t r e c 评测会议由美国国防部高等技术研究局资助，目的是促进信息检索技 术的发展，并为美国军方的情报检索提供有效的技术支持。因此，研究并掌 握信息检索的核心技术，无疑具有十分重要的经济意义、社会意义和军事意 义。 一个信息检索系统组成较为复杂，影响信息检索系统的性能因素较多， 其中，索引策略作为一个重要组成部分，有必要对其进行深入的研究。本文 将研究中文索引策略问题，其研究成果将为中文信息检索系统的构建提供一 定的参考意义，具有重要的理论价值和广泛的应用价值。 1 2 信息检索技术综述 1 2 1 信息检索系统主要工作流程 一个信息检索系统主要的流程如图1 1 所示： 1 ) 信息收集与预处理：由爬行器将互联网上的网页读取过来，经过处理 之后保存为文档。本文主要研究的是索引策略，所使用的实验数据是已经处 理过的数据，因此不对此步骤进行探讨。 2 1 索引策略：是研究以什么作为索引单元。根据不同的索引策略，对文 档使用不同的分词处理方法，根据处理后的结果建立索引，索引一般为倒排 格式，记录索引单元在哪些文档中出现，出现频率等相关信息。此步骤是检 索技术中十分重要的一个环节，不同的索引策略直接影响着检索能力的优劣。 目前的索引策略主要有基于词的索引策略和n 元文法索引策略。 基于词的索引策略以词作为索引单元，一篇文档通过分词处理变成某种 本文认为的词的序列，依据这个序列，建立索引。词是语言中最小的可以独 2 哈尔滨工程大学硕士学位论文 立运用的有意义单位，使用词作为索引单元符合人们的思维习惯，也更符合 语言学知识，并为绝大多数检索系统采用，取得了较好的检索效果。 n 元文法索引策略以1 1 个字作为索引单元，一篇文档通过分词处理变成 相邻n 个字组成的。1 1 元文法的索引策略优势在于它不需要语义的相关知识， 这也是中文以及亚种语言中使用n 元文法的一个主要的原因；与其相应的分 词处理方法简单，易于实现，运算量较小。字的n 元文法的劣势在于耗费的 空间比较大。 3 ) 检索模型：用户的查询提交到检索系统中，通过对查询和索引的相似 度进行计算，完成结果文档集的查询和排序，将最终结果反馈给用户。 图1 1信息检索系统流程 1 2 2 实现信息检索系统的关键技术 在实现中文信息检索系统过程中，由于本文所使用的数据为以经过预处 理的数据，因此这里不讨论信息收集与预处理问题。本文在实现信息检索系 统时主要处理以下几项关键技术： 3 哈尔溟工程大学硕十学位论文 1 ) 分词问题 基于不同索引策略的中文信息检索系统所采用的分词方法不同。分词就 是把文档和查询分割成若干个较短的信息单元。索引策略主要分为基于词的 索引策略和n 元文法的索引策略，对应的分词方法差异较大。 常用的是n 元文法的索引策略是一元文法和二元文法，基于一元文法的 索引策略也被称为基于字的索引策略。对于基于n 元文法的索引策略的中文 信息检索系统采用的分词方法处理较为简单，就是将相邻n 个字组合成一个 单元，作为索引单元。 对于基于词的索引策略的中文信息检索系统采用的分词方法较为复杂。 中文信息有别于英语等其他语言，由于中文信息没有将单词用空格加以切分， 因此如何将文档进行恰当的切分，形成包含较少歧义的索引单元甚为重要。 目前的主要的切分排歧方法有最大匹配法，基于规则的方法，基于记忆的交 叉歧义排除法，n 元文法( 此处的n 元文法指分词的二元文法) 等，切分的 方法不同，产生的索引单元也不同。词作为最小的能自由运用的语言单位， 将有助于检索性能的提高，但由于自动分词会存在错误，尤其是当前未登录词 的识别性能并不令人满意，这会对检索的性能产生负面影响。利用大规模的 语料库和成熟的n 元文法统计模型，可以很容易将切分正确率提高到很高。 高山的实验表明使用n 元文法，在不考虑未登录词的情况下，就可以将切分 的正确率提高到9 3 以上i l j 。 2 1 索引的数据结构 对文档进行分词处理后，为该文档建立索引。索引文件通常采用倒排的 方式组织，采用h a s h 表管理索引的存储和查找，使用压缩算法进行文档和 索引的压缩。 3 ) 信息检索模型 信息检索模型根据查询，通过相应的公式，计算查询和文档之间的相似 程度，每个文档得到一个分值，依据这个分值就可以把文档进行排序，反馈 出该模型认为最好的前n 篇文档。 4 哈尔滨t 稗大学硕十学位论文 1 3 信息检索的评测会议 除了理论和技术外，评估也是系统发展过程重要的一环。信息检索有三 个主要的评测会议；t r e c ( t e x tr e t r i e v a lc o n f e r e n c e ) 、c l e f ( c r o s s - l a n g u a g e e v a l u a t i o nf o r m ) 和n t c i r ( n i it e s tc o l l e e t i o nf o ri n f o r m a t i o nr e t r i e v a l s y s ：t e m s ) 。其中影响最大的是t r e c 会议，该会议吸引了国际上高水平的研 究团队参与，有信息检索的奥林匹克之称。t 1 m c 以英文为主，并搭配一些 战略语言，“9 1 l ”之后，t r e c1 1 进行了英文阿拉伯文跨语言信息检索；伴 随中国的崛起，t r e c5 、n 逻c6 以及1 1 也c9 进行了中文信息检索和中文 英文跨语言信息检索；t r e c7 、t r e c8 进行了法文、德文、意大利文检索。 c l e f 得到欧盟的数字图书馆计划支持，以欧洲语言为主，但因应欧洲语言 的多样化，主题和文件集所涵盖的语言数相对多起来，挑战性也强很多。2 0 0 0 年的主题包括荷兰文、英文、法文、德文、意大利文、西班牙文、瑞典文、 芬兰文等。文件集包括英文、德文、法文、意大利文。2 0 0 1 年主题增加俄文、 日文、中文和泰文，文件集增加西班牙文。n t c i r 则以东亚语言为主，初期 是英文和日文的跨语言信息检索，2 0 0 0 2 0 0 1 加入中文信息检索和英中跨语 言信息检索。2 0 0 1 年以后，规模扩大至中、日、韩、英四国语言的信息检索 及跨语言信息检索。 中文信息处理研究起步较晚，上世纪八十年代，还面临着汉字编码、分 词等基本问题尚未解决的局面。九十年代，随着这些问题取得突破，中文信 息处理技术取得了长足进展。此后，随着中文信息处理数据规模的膨胀以及 国内外学术交流的增加，国内研究者逐渐认识到评测对于研究的促进作用。 2 0 0 2 年，国内的相关研究机构开始尝试参加t r e c 等国际评测，并且相继 取得了不错的成绩。但专门针对中文的测试项目的缺位使中文信息处理技术 还不能得到有效检验。这种状况得到了国内的研究机构和科研管理部门的重 视。经过大量的准备，国内相继召开了多个面向中文信息处理技术的评测会 议，其中比较有影响的是8 6 3 评测、全国搜索引擎和网上信息挖掘会议 ( s e w m ) 等。 这里仅对具有中文信息检索评测的最重要的两个评测会议1 1 也c 和 n t c i r 进行介绍。 5 哈尔滨t 程大学硕士学位论文 1 3 1t r e c 二十世纪九十年代，基于军事和反恐情报处理的需要，美国国防部高级 研究计划署( d a 船a ) 提出了t i p s t e r 文本处理计划，文本检索会议( t e x t r e t r i e v a lc o n f e r e n c e ，简称n 也c ) 就是该计划的重要组成部分。1 9 9 2 年， 在美国国防部高级研究与开发机构和d a r p a 的资助下，n i s t 召开了第一 届t r e c 会议，以后每年举办一次，到2 0 0 5 年已举办了1 4 届。t r e c 的 组织者认为，对不同系统的比较，其意义并不在于要证明某个系统优于其他 系统，而是要把更多不同的技术放在一起公开讨论，这对技术的发展有很大 好处。于是，t r e c 自开办之初，就明确提出了四个目标： 1 1 以大规模测试集为基础，推动信息检索的研究； 2 ) 通过建立一个开放式的论坛，使与会者交流研究成果与心得，以增 进学术界，产业界与政府的交流互通； 3 ) 通过对真实检索环境的模拟与重要改进，加速将实验室研究技术转 化为商业产品： 4 1 开发适当且具有实用性的评价技术，供各界遵循采用。 t r e c 发展到现在，已经成为备受瞩目的标尺性测试，对信息检索研究 领域产生了巨大而深远的影响。今天，在t r e c 评测中名列前茅的算法往往 成为大家研究的重点，很多商用搜索引擎所采用的核心技术就是那些被 t r e c 证明成功的算法发展而来的。t r e c 论坛成为研究人员互相交流学习 的重要途径，很多新的思想和方法正是从这里碰撞产生。t r e c 为新的热点 研究提供了急需的数据和评价体系，促进了这些技术的快速发展。鉴于t r e c 的巨大成功，现在的众多评测，甚至其他研究领域的评测，如跨语言检索评 测会议n t c i r 、c l e f ，机器翻译评测t c s t a r 等，都或多或少受到它的 影响。 在t r e c 中，用户查询就是所谓的“主题”( t o p i c ) ，这些主题是预先 确定的问题，用来向检索系统提问。主题由标题( t i t l e ) 、描述c d e s c r i p t i o n ) 和详细描述( n a r r a t i v e ) 构成。标题部分由几个单词构成，非常简短。描述 部分是一句话，比标题详细。详细描述部分更详细地描述了哪些文档是相关 的。 6 哈尔谈 _ 程大学硕士学位论文 在进彳亍相关评估时，对于每一个主题，t r e c 将从参加者取得的结果中 取出前若干文档，构成一个文档池，使用人工方式对这些文档进行相关性判 断。没有进行判断的文档被认为是不相关的，即没有进入文档池的所有文档 都被认为是不相关的。 t r e ce v a l 软件包( t r e c 的免费评测软件) 对所有参加者的运行结果进 行评估，给出大量参数化的评测结果( 主要是精确率p r e c i s i o n 和召回率 r e c a l l ) 。根据这些评测数据来评价参加评测的检索系统的性能。 由于t r e c 评测具有很高的权威性，本文采用t r e c _ e v a l 对检索系统的性 能进行评估。 1 3 2n t c i r n t c i r ( n a c s i st e s tc o l l e c t i o n sf o ri r ) 是由日本国家科学信息系统中心 ( n a t i o n a lc e n t e rf o rs c i e n c ei n f o r m a t i o ns y s t e m s ，简称n a c s i s ) 策划主办的。 其目的是希望能建立一个日文标竿测试集，作为资讯检索与自然语言处理研 究的基础资料，后来逐渐发展以东亚语言为主的评测。 第一届n t c i rw o r k s h o p 开始于1 9 9 5 年1 1 月，并于1 9 9 9 年8 月3 0 日 至9 月1 日在日本东京举行了会议。来自6 个国家的2 8 个组织参加了研究任 务并提交了结果。 第二届开始于2 0 0 0 年的6 月，并于2 0 0 1 年3 月7 - 9 目在日本东京举行 会议。来自包括美国、b 本、中国等8 个国家的4 6 个组织参加了研究任务。 第二届的研究任务包括以下三个方面：中文信息检索：中文单语言信息检索、 英中跨语言信息检索；日文与英文信息检索：日文与英文的单语言信息检索、 日英或英日跨语言信息检索；文本摘要：对日文文本自动摘要。 n t c i r 文件集的来源主要为n a c s i s 学术会议论文资料库中的摘要与关 键词等资料，最初为英日对照。每篇文件均具有s g m l 标识，此外也有部分 文件加上了词类标记( p a r t - o f - s p e e c ht a g s ) 。2 0 0 0 - 2 0 0 1 加入中文信息检索和英 中跨语言信息检索。2 0 0 1 年以后，规模扩大至中、日、韩、英四国语言的信 息检索及跨语言信息检索。n t c i r 为信息检索提供了基础数据。 n t c i r 文件集的来源主要为n a c s i s 学术会议论文资料库中的摘要与关 7 哈尔滨工程大学硕七学位论文 键词等资料，目前已有超过3 0 0 , o o o 笔，且为英日对照。每篇文件均具有s g m l 标注，此外也有部分文件加上了词类标记( p a r t - o f - s p e e c ht a g s ) 。 n r c i r 目前已有1 0 0 个查询主题，分别属于数个不同的学科领域。查询 主题的建构是依据真实使用者需求，再加以修正改写而成，其组成结构包括 标题( t i t l e ) 、简短的资讯需求( d e s c r i p t i o n ) 、详细的资讯需求( n a r r a t i v e ) 、以及 相关概念( c o n e e p t s ) 等数个部分其中详细的资讯需求亦对相关词汇定义、背 景知识、检索目的、预期的相关文件数量及文件形式、相关判断的标准等部 分加以描述。 1 4 本文的主要内容及其组织 本文对中文信息检索中的索弓l 策略进行了研究。 由于中文文档没有用于切分单词的空格，这使得对索引策略的研究成为 中文信息检索的特有问题。对文档进行分词处理是研究索引策略必须要实现 的问题，因此，本文首先对分词进行了研究，并提出一种解决方案处理分词 过程中的未登录词问题。 为研究中文索引策略，本文实现了个信息检索系统。除了对分词方法 进行了研究以外，本文还研究了实现信息检索系统中索引的数据结构以及检 索模型。检索模型中2 泊松概率模型的b m 2 5 公式是目前公认较好的检索模 型，所以本文将在此模型上对索引策略进行研究。 本文对索引策略进行了深入研究，首先比较基于词的索引策略、一元文 法索引策略和二元文法索引策略的性能，然后探讨索引策略的融合问题，最 后提出了改进的二元文法索引策略，并用实验检验改进的二元文法索引策略 的性能，为中文信息检索系统的构建提供依据。 本文随后章节组织如下； 第2 章对中文信息检索系统的分词问题进行了研究。应用n 元文法索引 策略分词处理较为简单，所以本文不傲深入讨论。本章重点分析了基于词的 索引策略相关的分词处理方法。首先分析了中文分词的歧义现象，然后介绍 了处理歧义问题的相关模型以及平滑算法。分词过程中的未登录词是一个难 点问题，本文提出级联隐马尔科夫模型来处理未登陆词问题，并用实验验证 8 哈尔滨。t = 程大学硕士学位论文 i t i i | i i 写皇鼍；| i i i i i i j i i ；i i i | i ；i j j i i ；i z z ；自i i ；自；自目i e ；j 自i e _ 了此方法的性能。后续实验将采用分词方法中的n 元文法结合k n e s e r - n e y 平 滑算法进行初步分词。采用本文提出的解决方案进行未登录词的处理。 第3 章讨论在实现中文信息检索系统时的相关技术问题，具体包括索引 的组织、存储、查找和压缩以及信息检索模型。根据实验数据的特点，选择 相应的数据结构以及检索模型。 第4 章是本文的核心。本章分析了基于词的索引策略、基于字的一元文 法、二元文法索引策略的优缺点，对比了这三种索引策略的性能，在此基础 上将基于词的索引策略与二元文法索引策略进行了融合研究，最后在二元文 法索引策略之中加入部分语义信息，提出了性能较好的改进的二元文法索引 策略。 第5 章通过应用2 一泊松模型的b m 2 5 公式在t r e c 公开数据( t r e c m a n d a r i n ) 上对基于词的索引策略、元文法、二元文法索引策略、索引策 略的融合以及改进的二元文法索引策略的性能进行了比较。实验表明相对而 言，改进的二元文法索引策略性能在平均精确率和r - 精确率相对较优，在召 回率与精确率对应表和文件数与精确率对应表中相对较优或可比。 9 哈尔滨- 【程大学硕士学位论文 第2 章中文分词问题的研究 对索引策略的研究，需要搭建一个中文信息检索系统。在实现中文信息 检索系统时首先要对文档进行分词处理。采用不同索引策略的中文信息检索 系统所使用的分词处理方法不同。因为采用1 1 元文法的索引策略的信息检索 系统分词处理较为简单，只需要将相邻r 1 个字组成一个基本单位就可以实现， 所以本章重点分析采用基于词的索引策略的信息检索系统的分词问题。在不 引起歧义的情况下，本文分词特指采用基于词的索引策略的中文信息检索系 统在实现时所使用的分词方法。首先分析了中文分词的歧义现象，然后介绍 了用予处理自然语言歧义问题的相关模型，最后介绍了平滑算法。最后针对 未登录词提出一种解决方案，并通过实验验证该解决方案的性能。 2 1 中文分词歧义问题 中国的汉字是示意文字，总数有几万个，在由国家标准总局颁布的信 息交换用汉字编码字符集一基本集( 郎g b 2 3 1 2 - 8 0 ) 中共收录了一级和二级 常用汉字共6 7 6 3 个，而在u n i e o d e 编码中更是收录多达2 0 9 0 2 个汉字。 词是最小的、能独立活动的、有意义的语言成分。因此，通常的检索引 擎都是以每一个独立的词为单位建立索引，在查询时按照检索词出现的位置 和频率对文档进行输出。英语文本是小字符集上的已充分分隔开的词串，而汉 语文本是大字符集上的连续字串，并且在词与词之间并没有明显的分割标记。 故而存在一个对汉语中的词加以识别的问题，即中文检索引擎首先必须对原 文进行切分词。如果不切词( 按字检索) ，可能检索的结果与用户的查询要求 会大相径庭，例如当检索德国货币单位”马克”时，就会把”马克思”检索出来， 而检索”华人”时会把”中华人民共和国”检索出来。因而进行切词，可以大大提 高检索的准确率。 在自动分词的过程中，消除边界歧义是一个重要的步骤。所谓词语边界 歧义指的是对于给定的句汉语句子或一个汉字串，可以划分出多种词语边 界形式。汉语词语边界歧义包括组合歧义和交集型歧义。 1 0 哈尔滨下程大学硕十学位论文 2 1 1 交集型歧义 设a 、b 、c 为汉字符串，交集型歧义是指在汉字串a b c 既可切分成 a b c 形式，又可切分成a b c 形式，即a b 是词，b c 也是词。在下面的表 2 1 中的例子中，计算机也会面临词串l 和词串2 之间的选择问题。其中字串 “中游鱼”可能是“中游”跟“鱼”这两个词，也可能是“中”跟“游鱼” 这两个词。人们一般把这个问题称为自动分词中的交集歧义( 交叉歧义) 问 题。再例如：句子“从d , 学到中学”和“从小，学，计算机”中，字串“从 小学”则存在交集歧义。 表2 1 交叉歧义示例 字串小河中游鱼多 词串i小河中游鱼多 词串2小河中游鱼多 但会有更复杂的交集型歧义字段，比如字段：“爱人民主要”，“爱人”、 “人民”、“民主”、“主要”都是词，“爱人民主要”包括了四个歧义字段。 根据在大规模语料中的分析结果，交叉歧义还可细分为真歧义和伪歧义 【2 】。真歧义指存在两种或两种以上的可实现的切分形式，如句子“鱼在河中 游”和“鱼在河，中游”中的字段“河中游”是一种真歧义；而伪歧义一般 只有一种可实现的切分形式，如“建设有”、“中国人民”、“各地方”、“本 地区”等。 在这些歧义中，伪歧义字段的切分结果是上下文无关的，一般仅依据字 段内部的信息如词频或字问互信息就可正确切分伪歧义字段，而真歧义字段 或组合歧义字段的切分结果依赖于它所处的上下文环境，因而正确处理真歧 义字段，常常需要更多的信息，特别是上下文信息。 2 1 2 组合型歧义 设a 、b 为汉字符串，组合型歧义是指组合歧义即汉字串a b 是词而a 、 b 也是词的情况。如果只按照“长词优先”的原则。显然不会有组合型歧义 哈尔滨_ 丁程大学硕+ 学位论文 现象。但在具体的语境中，必须针对不同的情况做出不同的切分。这类歧义 现象出现的比例不高，所占比例约为1 5 ，但不对它们进行处理也会影响分 词的准确度。组合型歧义字段都是不确定的歧义字段。 例如人们能很容易地将表2 2 中的字串变换为词串1 形式，但计算机却 会面临在词串1 和词串2 之间进行选择的问题。其中字串。上学”可能是两 个词，也可能是一个词。人们一般把这个问题称为计算机分词中的组合歧义 问题。再例如：句子“以我，个人的名义”和“他一个a 在家”的“个 人”是一个组合歧义字段 表2 2 组合歧义示例 字串 我们在广场上学打羽毛球 词串1我们在广场上学打羽毛球 词串2我们在广场上学打羽毛球 组合型歧义字段具有偶发性。如“美德”，大部分情况下是一个名词， 但在一定语境条件下可以成为歧义字段：“中俄美德四强争雄”，分为“美 德”。又如“等同”一般情况下是一个动词，但在句子“我驻德外交机构与 华人华侨留学生等同庆新春”，则分为“等同”。由此可见，很多词形在一 些特定语境下会成为歧义字段，而且还不为人所能料想到的。这增加了识别 组合型歧义字段的难度。 2 2 切分歧义问题的解决方案 由于书面汉语是字的序列。词与词之间没有闯隔标记，使得词的界定往 往模糊不清。即使这样，在过去的时间里，人们在汉语的自动分词技术的研 究上还是做了很多工作，设计了许多实用、高效的算法。通常的方法主要分 为两类：第一类主要基于字典、词库的匹配和词的频度统计，这类方法实用、 具体，比较容易实现；第二类方法主要基于句法、语法分析，并结合语义分 析，通过对上下文内容所提供信息的分析对词进行定界，这类方法试图让机 器具有人类的理解能力，其原理较为晦涩，一般不易实现。 下面介绍几种最主要的切分排歧算法： 1 2 哈尔溟工程大学硕士学位论文 1 ) 最大匹配法 3 1 1 4 j ；这是最早出现也是基本的一种方法，是一种机械分 词方法。该方法根据一个分词词表和一个基本的切分评估原则“长词优 先原则”来进行分词，即从左到右或从右到左，每次取最长词，得到切分结 果。 a ) 最大正向匹配法( m a x i m u mm a t c h i n gm e t h o d ) 通常简称为m m 法。其基本思想为：设d 为词典，m a x 表示d 中的最 大词长，s t r 为待切分的字串。m m 法是每次从s 订中取长度为m a x 的子串 与d 中的词进行匹配。若成功，则该子串为词，指针后移m a x 个汉字后继 续匹配，否则子串逐次减一进行匹配。 b ) 逆向最大匹配法( r e v e r s em a x i m u mm a t c h i n gm e t h o d ) 通常简称为蝴法。r m m 法的基本原理与m m 法相同，不同的是分 词的扫描方向，它是从右至左取子串进行匹配。 2 ) 基于记忆的交叉歧义排除法：孙茂松考察了一亿字的语料，发现交集 型歧义字段的分布非常集中1 5 j 。仅仅通过基于记忆的方法，保存一种伪歧义 切分字段表，就可以使交集型歧义切分的正确率达到5 3 3 5 ，再加上那些有 严重偏向性的真歧义字段，交集型歧义切分的正确率可以达到5 8 5 8 。 3 ) 基于规则的方法：使用规则排除切分标注中的歧义也是一种很常用的 方法。规则的形式定义可以非常灵活。通过规则可以在整个句子的范围内查 找对于排歧有用的信息，非常灵活。规则方法的主要问题在于知识获取。如 果单纯依靠人来写规则，无疑工作量太大，而且也很难总结得比较全面。 4 ) n 元文法：这是一种基于统计的方法( 此处讨论的n 元文法不同于索 引策略中的i i 元文法，本章后续小节n 元文法如果不做特殊说明特指分词方 法中的n 元文法，本文其他章节n 元文法特指索引策略中的n 元文法) 。统计 方法也可以依赖于词典，将原文切分后中任意前后紧邻的两个单元进行出现 频率的统计，选择最优的路径。 2 3n 元文法 n 元文法可以预测一个单词序列出现的概率。n 元文法假设一个单词出 现的概率分布只与这个单词前面的n - 1 个单词有关，与更早出现的单词无关。 ” 哈尔滨t 程大学硕士学位论文 即： ，( w 1 心m 嵋) = p ( w o p ( w 21w 1 ) p ( 1w l w 2 嵋d ) ( 2 。1 ) 这样，为了描述这个概率分布，需要使用一个n 维数组，这个数组中每 一维长度为单词的个数m ，这个数组中元素的个数为m n 。 所谓切分排歧过程，可以看作从词图中选择一条最优路径的过程。词图 上的一条路径就表示一种切分方法，分词就是找出词图中最合适的一条路径。 例图2 ，1 是句子“我们在广场上学打羽毛球。”对应的词图示例。 4 上l _ 学 圆固囹葡面匦 图2 i 词图示例 以往有大量实验表明，在n 元文法中，三元文法的性能最优。对于三元 语法，可根据公式( 2 2 ) 对其中的任意一条路径进行概率评分。 上 p ( w , w 2 “，) = p ( w 1 ) p ( w 2iw 1 ) il p ( 1w _ h 0 2 ) ( 2 2 ) t - 3 采用n 元文法，可以从一个词图中选取一条最优路径，作为最好的分词 结果。其中，i i 元文法的参数可以事先从语料库中训练得到。在未定义词识 别以后，词图中加入了新识别出来的未定义词。不过，由于未定义词可能是 语科库没有出现的，无法事先得到未定义词的n 元文法参数。 由于三元文法分词方法的系统开销较大，但是性能提升有限，因此本文 只考虑一元文法分词方法和二元文法分词方法。 考虑到未登录词情况的n 元文法，把每一种类型的未定义词( 如中国人 名、中国地名等) 作为同一个词进行n 元语法的参数估计。在实际计算词图 中的一条路径的概率评分时，除了要利用n 元语法的概率评分之外，还臻乘 上句子中每一个未定义词在该类未定义词中出现的概率。也就是评分函数修 改如下： lr r ( w 。w 2 。朋) = p ( m 一) 兀p ( 嵋iw t - i , w l 。) 兀兀p ( 屹it y p e c t ) )( 2 3 ) 1 4 哈尔滨丁程大学硕十学位论文 其中，t y p e ( t ) t = l t ，表示t 种类型的未定义词，峨1 为句子中识 别出来的类型为t y p e ( t ) 的i t 个未定义词。其中p ( i t y p e ( t ) ) 可以由前面的未 定义词识别算法得到。 2 4 数据稀疏问题及解决方案 2 4 1 数据稀疏问题 在应用公式2 1 进行词法分析的时候，假设单词表中有m 个单词，如果 使用一元文法，假设每个单词出现的频率与其他单词无关，那么所使用的参 数实际上就是每个单词出现的词频，参数个数等于m 。如果使用二元文法， 就是说，假设每个单词出现的频率只与上一个单词相关，那么所使用的参数 就是一个单词后面出现另外一个单词的转移概率，参数个数为m x m 。如果 采用三元文法，参数的个数将是m x m x m 。实际上，由于很多的单词序列 在实际的语料库中并不会出现。所以实际上有效的参数数量会少得多。不过， 如果这些在训练语料中没有出现的单词序列出现在测试文本中，会导致该文 本的预测概率为o 。为了避免这种情况，就要采用某种策略将这些概率为0 的 单词序列赋予一个很小的猜测值，这种策略叫做数据平滑。数据平滑使低概 率( 包括零概率) 被调高，高概率被调低，模型参数概率分布趋向均匀。数 据平滑除了通常用来避免零概率之外，还被试图用来提高模型的整体精度。 由于数据稀疏问题的大量存在，数据平滑在语言模型中都是必须采用的，数 据平滑技术是语言模型中重要的技术埘。 2 4 2 平滑算法 本文使用的符号如下：以。是指w i - n + l ，w i - n + 2 ，w i ，即n 个连续的词串。 c ( 。) 为以。出现的次数。( 令) 为口的极大似然估计值 需要指出的是，所有参数平滑算法都是基于实际统计的数据之上，是对 实际统计数据的平滑。大多数情况下采用极大似然估计来统计实际数据，对 数据的平滑自然是在此数据基础上进行的。参数平滑算法主要有：加法平滑 1 5 哈尔滨t 程大学硕十学位论文 吼引( a d d i t i v es m o o t h i n g ) 、线性插值平滑( l i n e a ri n t e r p o l a t i o ns m o o t h i n g ) 、 g o o d - t u r i n g 估计1 9 l 、折扣参数x t z 滑( d i s c o u n t i n gs m o o t h i n g ) 1 1 0 1 、k a t z s 式平 滑【i l l 和k n e s e r - n e y 平滑【1 2 】f 1 3 】等。 加法平滑( a d d i t i v es m o o t h i n g ) ，是一种简单易行的数据平滑方法。该方 法的基本思想是：为了避免零概率问题，为每个实际统计的数据加一个常量。 该常量是个经验值，经常取1 和0 5 。这种平滑技术的性能一般来说较差。线 性插值平滑( l i n e a ri n t e r p o l a t i o ns m o o t h i n g ) 的基本思想是：利用低元参数的线 性组合来估计高元参数，应用范围广泛。g o o d t u r i n g 估计的基本思想是：将 事件的出现次数r 调整为r ，一般而言，调整后的r 一般满足心 什l 。折 扣参数平滑( d i s c o u n t i n gs m o o t h i n g ) ，主要包括绝对折扣参数平滑( a b s o l u t e d i s c o u n t i n gs m o o t h i n g ) 和线性折扣参数平滑( l i n e a rd i s c o u n t i n gs m o o t h i n g ) ， 基本思想是：按照某种比例从观察到的参数数据中折扣出一部分平分给未观 察到的参数。如果折扣参数选取的好，绝对折扣参数平滑能取得比较好的效 果。k a t z s 式平滑主要思想是：当对n 元对的概率估计不准时，回退到n - 1 元，该算法是一种回退式数据平滑( b a c k i n g - o f f s m o o t h i n g ) 算法。当一个n 元对吐。，的出现次数“m _ j ，+ ，) 足够大时，极大似然估计a 吐( m 皑+ ) 是昧。 可靠的概率估计。而当“以。1 ) 不是足够大时，采用g o o d t u r i n g 估计对其平 滑，将其部分概率折扣给未出现