（计算机应用技术专业论文）中文搜索引擎中分词算法的研究和实现.pdf

南京邮电大学硕 ：研究生学位论文 摘要 摘要 中文自动分词是实现搜索引擎信息检索的基础，长期以来一直是人们研究的重点，它 广泛应用于中文信息处理的各个领域。传统的分词系统大都采用基于词典机制的分词算 法，它们必须在分词速度和精度之间做出选择，要提高速度，就要适当放弃精度的追求， 缩减词典，减少匹配次数，而要提高切分精度，就得舍弃速度，扩充词典，匹配次数也会 增加。 本文在介绍中文分词研究现状和基本概念的基础上，通过研究传统的词典机制，设计 和实现了一个高效的中文自动分词系统。在本文设计的分词系统中，词典中的每个词条加 载到设计好的双层哈希数据结构中去，且常驻内存，待分词的文本用标点符号和空格被分 割成一个个更小单位的的字符串，采用正向减字相对最大匹配法对字符串进行分词，对粗 分的分词结果运用回退一字和统计规则相结合的方法来识别和处理歧义字段和新词。其改 进特点主要体现在两个方面，一是采用“双层哈希+ 二分查找”的算法进行词典匹配，可 以在较短的时间内能达到匹配成功的目的，二是切分算法采用正向减字相对最大匹配法， 每次切分的是某字开始词语的最长长度，而不是词典中词语的最长长度，既防止了过长词 条的遗漏，又减少了不必要的匹配次数，提高了分词的速度。 最后，本文使用有针对性的文本用例对本文给出的分词系统进行了测试，将实验结果 和类似分词系统的运行结果进行比较和分析，结果表明本文设计分词系统在速度和精度上 均有较大的优势。 关键词：中文分词，词典机制，双层哈希，二分查找，歧义处理 南京邮电人学硕上研究生学位论文a b s t r a c t a b s t r a c t a u t o m a t i cc h i n e s ew o r ds e g m e n t a t i o ni st h eb a s i so fs e a r c h i n gi n f o r m a t i o ni nt h es e a r c h e n g i n e ，w h i c hi sa ni m p o r t a n tp o i n ti nt h i s f i e l d i ti sw i d e l yu s e di nm a n ya r e a so fc h i n s e s e i n f o r m a t i o np r o c e s s i n g t r a d i t i o n a ls e g m e n t a t i o ns y s t e m sm o s t l yu s ea l g o t h m e so fb a s i n go n d i c t i o n a r ym e c h a n i s m ，w h i c hm u s tm a k eab a l a n c eb e t w e e ns p e e da n dp r e c i s i o n i fi tw a n t st o i m p r o v es p e e d ，i th a st oq u i tt h ep u r s u i to fp r e c i s i o n ，r e d u c et h ed i c t i o n a r ya n dd e c r e a s e m a t c h i n gt i m e a n di fw a n t st oi m p r o v ep r e c i s i o n ，i th a st oq u i tt h ep u r s u i to fs p e e d ，e x t e n dt h e d i c t i o n a r ya n dt oi n c r e a s em a t c h i n gt i m e t h i st h e s i si n t r o d u c e st h ec u r r e n tr e s e a r c hs t a t eo fc h i n e s ew o r ds e g m e n t a t i o na n di t sb a s i c t h e o r y , t h e ni l l u m i n a t e st r a d i t i o n a ld i c t i o n a r ym e c h a n i s m s o nt h eb a s i so ft h ea b o v ek n o w l e d g e ， an o v e la u t o m a t i cc h i n e s ew o r ds e g m e n t a t i o ns y s t e mb a s eo nd i c t i o n a r ym e c h a n i s mi sd e s i g n e d a n di m p l e m e n t e d i nt h ed e s i g n e ds y s t e m ，i tf i r s t l yl o a d se v e r yw o r do ft h ed i c t i o n a r yi n t ot h e d a t as t r u c t u r eo fd o u b l el a y e rh a s hi n d e x i n ga n dl e t si ts t a yi nm e m o r yl a s t i n gb e f o r es e g m e n t i n g w o r d s ，a n du s i n gi n t e r p u n c t i o na n db l a n ks p l i t st h ec h i n e s et e x ti n t os m a l ls t r i n gu n i t s ， s u c c e s s i v e l ys e g m e n t st h es t r i n gu n i t sb y ”r i g h td i r e c t i o n - d e c r e a s ec h a r - c o m p a r a t i v e l ym a x i m u m m a t c h ”m e t h o d f i n a l l yi tu s e sr e t u r nb a c ko n ec h a r a c t e ra n dc o n b i n i n gl a n g u a g er u l e sa n d s t a t i s t i cr e s u l t sm e t h o dt oi d e n t i f ya n de l i m i n a t ea m b i g u o u s n e s s e sa n dn e ww o r d si nr o u g h r e s u l t so fs e g m e n t a t i o n t h ea l g o t h r i mh a st w ob e t t e r m a n t s o n ei su s i n g ”d o u b l el a y e rh a s h i n d e x i n g + b i n a r ys e a r c h ”a l g o r i t h md u r i n gt h ep r o c e s so fm a t c h i n gw o r d ，w h i c hi sc o m p l e t e di n l e s so ft i m e t h eo t h e ri st h a tt h es e g m e n t i n ga l g o r i t h mu s e st h e ”r i g h td i r e c t i o n d e c r e a s e c h a r - c o m p a r a t i v e l ym a x i m u mm a t c h ”m e t h o d ，i t sf e a t u r ei s ：t h es e g m e n t i n gl e n g t hi st h ef i r s t c h a r a c t e r sm a x i m u mw o r d ( b e g i n sf r o mt h ec h a r a c t e r ) l e n g t ho ft h es t r i n gu n i t ，b u tn o tt h e w o r d sm a x i m u ml e n g t hi nd i c t i o n a r y t h i si m p r o v e dm e t h o dn o to n l yp r e v e n t se x c e s s i v e l yl o n g w o r d sf r o mo m i t t i n g ，b u ta l s od e c r e a s e su n n e c e s s a r ym a t c h i n gt i m ea n di m p r o v e st h e a f t e rt e s t i n gs o m ec h i n e s et e x te x a m p l e sa n dc o m p a r i n gt h er u nr e s u l t s 、i t ht h es i m i l a r s y s t e m s ，t h ee x p e r i m e n t a lr e s u l t s h o w st h a tt h es y s t e mi sr e l a t i v e l yi d e a l ，a n di th a sm o r e a d v a n t a g ei ns p e e da n dp r e c i s i o n k e y w o r d s ：c h i n e s ew o r ds e g m e n t a t i o n ，d i c t i o n a r ym e c h a n i s m ，d o u b l el a y e rh a s hi n d e x i n g ， b i n a r ys e a r c h ，a m b i g u o u s n e s sh a n d l i n g i i 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研 究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得南京邮电大学或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在 论文中作了明确的说明并表示了谢意。 研究生签名：j 婢日期：j 掣 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保 留本人所送交学位论文的复印件和电子文档，可以采用影印、缩印 或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容 相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊 登) 授权南京邮电大学研究生部办理。 研究生签名：j 皿导师签名：址日期：掣) 南京邮电人学坝上研究生学位论文第一章绪论 1 1课题背景 第一章绪论 随着因特网的迅猛发展，各种信息呈现爆炸式的增长，用户要在信息海洋里查找信息， 如同在大海中捞针样，因此每个上网用户都面临信息过载的问题，无法准确找到所需要 信息。为了达到这个目的，众多商业公司开发出了许多检索引擎，有针对w e b 进行搜索 的g o o g l e 、百度等，也有针对各行业开发的专题检索系统。目前，国内的每个行业和领 域都在飞速发展，这中间产生了大量的中文信息资源，在这个信息社会里，谁能更快地获 取有效的信息，谁就在竞争中占据了先机，于是大型中文搜索引擎便成为人们查找信息的 首选工具。汉语分词技术、文本信息检索技术和排序技术都是影响中文搜索引擎性能的关 键技术，而这其中最重要就是中文分词技术。 中文搜索引擎与西文搜索引擎的实现机制和原理大致雷同，然而，在自然语言处理技 术中，中文自然语言的理解和处理比西文处理技术复杂得很多，主要体现在以下几个方面 【l 】：( 1 ) 分词的规范难以统一；( 2 ) 词的不同切分方法具有不同的含义，导致歧义性；( 3 ) 新 词不断的产生；( 4 ) 分词理解的先与后。因此，要理解中文文本的含义就必须对其进行分 词。汉语自动分词是中文信息处理的前提【2 1 ，它有着极其广泛的实际应用。从基本的输入 系统如智能语句输入法、语音输入、手写输入，到文字处理如文本校对、简体繁体转换、 拼音标注，以及语音合成、文本检索、文本分类、文本挖掘、人机交互、信息提取、自动 文摘、机器翻译1 3 】等等，无处不渗透着分词技术的应用。正如一位专家说的，“没有中文 分词，其他一切深入的中文信息处理都无从谈起”。 自从中文信息处理领域提出自动分词以来，巨大的商业前景和重要的学术价值，促使 业界和学术界不同领域的研究人员在这一领域开展研究，并且取得了令人可喜的进展，提 出了许多分词方法，有些比较成熟的技术已经应用到商业产品当中。但是这些分词方法本 身或多或少的都存在着种种不足之处，对于分词中所涉及的一些关键问题，我们仍然没有 很好的解决方案。而且随着近年来信息的多元化、复杂化，对信息处理技术的研究和发展 提出了新的挑战。要想在浩瀚纷繁的信息海洋中快速而准确的获得自己想要的信息，信息 处理技术必须具备比以往更高的效率。因此，中文信息处理技术的进步和中文信息处理系 统的广泛应用，有待于对分词中的关键问题进行进一步的深入研究和探索。 总之，国内外在中文搜索引擎中分词技术方面的理论研究和应用尚处于发展阶段，有 甬糸邮电大学硕l 研究生学位论文第章绪论 较大的发展空间。搜索引擎中的核心技术往往被一些公司所掌握，已经商业化的技术也很 难公开。因而，对这一课题进行理论研究和实践探索具有较大的挑战性，也具有重要的学 术和应用价值。 1 2分词在中文搜索引擎中的重要性 搜索引擎是一种在w e b 上应用的软件系统，它以一定的策略在w e b 上搜集和发现信 息，在对信息进行处理和组织后，能够响应用户提交的搜索请求，返回相应的查询结果信 息的技术和系统。从使用者的角度看，这种软件系统提供一个网页界面，让他通过浏览器 提交一个词语或者短语，然后很快返回一个可能和用户输入内容相关的信息列表。通过浏 览这些元素，用户对相应的网页是否真正包含他所需的信息进行判断【4 】。 一个典型的搜索引擎系统框架图如图1 1 所示。它一般包括4 个子系统，即搜索器、 分词器、索引器和检索器【5 1 。搜索引擎的实现原理也就是工作流程主要有四步组成，即从 互联网上抓取网页一建立索引数据库一在索引数据库中搜索一对搜索结果进行处理和排 序。 几翮而丽。 互联网卜叫网络蜘蛛卜一u r l 提取 文本索弓 索引数据库 两页数据库卜一链接信息提取 查询服务器 用户 链接数据库 网页评级 图1 - l 搜索引擎系统框架 由上图可以看出，搜索引擎的主要四步工作流程中，有两步都要用到分词算法。( 1 ) “网络蜘蛛”从互联网上抓取网页信息后，由于中文词汇之间没有天然的分割符，所以必 须先用分词技术对中文文本进行分词，从网页信息中提取关键字及其相关信息，并对各关 键字建立索引，形成“索引数据库，以备用户查询需要的信息。( 2 ) “用户提交查询请 求给“查询服务器 后，“查询服务器”用分词算法将查询请求分解为各关键字，然后由 2 甬京自电入学硕t 研究生学位论文第一蕈绪论 搜索系统程序从网页“索引数据库”中找到符合各关键词的所有相关网页。由此可见，分 词问题是实现对全部文本信息检索的首要任务。只有把“爬虫”抓取的网页信息以词分割， 建立关键字索引，才能实现需要检索内容与实际网页之间词与词的匹配，从而得到检索结 果。 自动分词技术同样也是信息检索的关键，对于用户输入的以自然语言形式存储的检索 要求，首先要迸行的也是自动分词，即将用户的自然语言请求分词，从中抽取出关键信息， 才能实现检索中的关键词匹配。 分i 五- j n 底对搜索引擎有多大影响? 有学者曾对雅虎中n ( h t t p ：c n y a h o o c o m ) 的查询 准确率( 检索出来的与查询真正相关的网页数检索出来的网页数) 做过局部调查，调查结 果表明，由于未做分词处理，平均检索精度仅为4 8 8 t 6 1 。另据i p r o s p e c t 在2 0 0 4 年4 月 间发布的搜索引擎用户使用习惯调查报告表明，8 1 7 的用户不会浏览三页之后搜索结 果，而5 2 2 的用户只会关注搜索引擎返回的第一页搜索结果。也就是说，通常用户只 关心搜索引擎返回的排在前列相关度较高的页面。因此对于搜索引擎来说，最重要的并不 是找到所有的结果，而是把最相关的结果排在最前面，这也称为相关度排序。中文分词的 准确与否，常常直接影响到对搜索结果的相关度排序。 为了充分证明分词对搜索引擎的影响，我们在百度上输入“和服”进行测试，发现总 共结果为2 8 7 ，0 0 0 条，前2 0 条结果中有6 条与“和服”一点关系都没有。在第一页有以 下错误： “通信信息报：瑞星以技术和服务开拓网络安全市场 “关于商品和服务实行明码标价的规定” “青岛东和服装设备” “产品和服务 这次搜索引擎结果中的错误，就是由于分词的不准确所造成的。由此可见，中文分词 的准确度，对搜索引擎结果相关性和准确性有相当大的关系。 分词准确性对搜索引擎来说十分重要，但如果分词速度太慢，即使准确性再高，对于 搜索引擎来说也是不可用的，因为搜索引擎需要处理数以亿计的网页，如果分词耗用的时 间过长，会严重影响搜索引擎内容更新的速度。因此，对于搜索引擎来说，分词的准确性 和速度，二者都需要达到很高的要求f 7 】。 3 南京邮电大学硕士研究生学位论文 第章绪论 1 3国内外研究状况及发展趋势 1 3 1 国内外研究现状 随着社会信息化的发展，计算机在各领域中得到越来越普遍的应用，为了更好的利用 计算机来处理大量主要是以自然语言为载体的信息，计算机自然语言理解就变得尤其重 要。而对于中文的自然语言理解来说，由于中文词与词之间没有明确的边界，因此，汉语 分词是机器翻译、文本分类、主题词提取以及信息检索的重要基础【引。 自从二十世纪八十年代初中文信息处理领域提出了自动分词以来，这一课题一直吸引 着计算机界和语言界无数的专家和学者，经过他们不懈的努力，涌现出了许多成功的汉语 自动分词系统。比较有代表性的成果有：北京航空航天大学计算机系1 9 8 3 年设计实现的 c d w s 分词系统，它是我国第一个实用的自动分词系统；山西大学计算机系研制的自动 分词系统a b w s ；清华大学先后研制开发的s e g 分词系统和s e g t a g 系统；国家语委文 字所应用句法分析技术的汉语自动分词；复旦大学研制的复旦分词系统；哈工大研制的统 计分词系统；杭州大学改进的m m 分词系统：北大计算语言所的分词系统等。现在应用 较广的是中国科学院的i c t c l a s 分词系统和北京海量公司分词系统。 为了克服汉语词计算机自动切分这一难题，近年来，汉语言学界、人工智能界和情报 检索晃的学者们也纷纷加入了这一领域的研究，在汉语自动分词的研究与实践上进行了大 量的探索，找到了许多解决中文分词的方法，并且取得了一些重要的进展和一些实用性的 成果。这些分词算法主要有三种类型： ( 1 ) 基于字典、词库匹配的分词算法，也叫机械分词方法。该方法按照一定策略将待 分析的汉字串与一个“充分大的”机器词典中的词条进行匹配，若在词典中找到某个字符 串，则匹配成功( 识别出一个词) 。在这方面的主要成果有：首字h a s h + 词次字的二分查找 + 词剩余字的紧邻匹配的分词算法，较单纯的首字h a s h 算法速度有了很大的提高；首字 h a s h + 全词二分查找的分词算法，进一步提高了分词速度；将词首字和次字组合成h a s h 索引表的组合h a s h 索引分词算法，使得一字词和二字词查询只须在组合h a s h 索引表中一 步完成，从而显著提高查询速度；基于n 最短路径方法的分词算法，该方法是最短路径 方法和全切分的有机结合，它运用图论知识快速的从n 种粗分结果中找出正确切分结果， 取得不错的分词效果。 f 2 ) 基于词频统计的算法。它通常和机械分词法一起使用，相当于机械分词的一种。 这种方法首先切分出与词表匹配的所有可能的词，运用统计语言模型和决策算法决定最优 4 南京邮电大学硕j ：研究生学位论文 第一章绪论 的切分结果。它的优点在于可以发现所有的切分歧义，但是统计语言模型的精度和决策算 法在很大程度上决定了解决歧义的方法【9 】，需要大量的标注语料，并且分词速度也因搜索 空间的增大而有所缓慢。目前，大部分的分词系统都采用互信息、n 元统计模型和t - 测试 这三种原理来统计分词【l o 】。互信息是统计相邻字出现的频率，它一般反映的是字与字间 的静态结合，体现了汉字之间结合关系的紧密程度，当紧密程度高于某一个阈值时，便可 认为此字组可能构成了一个词；n 元统计模型必须要知道一个单词前面所有词出现的概 率，体现了词与其上下文环境中出现的单词序列密切相关；t 测试通过公式计算比较这个 字与前面字的结合能力，以及与后一个字的结合能力，来判断它到底是与哪个字结合得更 紧密，更能组成一个词语，它反应字与字之间的动态结合。 ( 3 ) 理解分词法。理解分词法又称为人工智能法，该算法的分词过程是对人脑思维方 式的模拟，试图用数字模型来逼近人们对语言认识的过程。它是对信息进行智能化处理的 一种模式，主要有两种处理方式：一种是基于心理学的符号处理方法。模拟人脑的功能， 构造推理网络，经过符号转换，从而可以进行解释性处理；一种是基于生理学的模拟方法。 神经网络旨在模拟人脑的神经系统机构的运作机制来实现一定的功能。以上两种思路也是 近年来人工智能领域研究的热点问题，将它们应用到分词方法上，于是产生了专家系统分 词法和神经网络分词法。专家系统分词【l l 】算法从模拟人脑功能出发，构造推理网络，将 分词过程看作是知识推理过程。该方法将分词所需要的语法、语义以及句法知识从系统的 结构和功能上分离出来，将知识的表示、知识库的逻辑结构与维护作为首要考虑的问题。 知识库按常识性知识与启发性知识分别进行组织。神经网络分词法【1 2 1 是以模拟人脑运行， 分布处理和建立数值计算模型工作的。它将分词知识所分散隐式的方法存入神经网络内 部，通过自学习和训练修改内部权值，以达到正确得分词结果。 目前研究中文分词的大多是科研院校，清华、北大、中科院、东北大学、i b m 研究 院、微软中国研究院等都有自己的研究队伍，而真正专业研究中文分词的商业公司除海量 科技以外几乎没有了。科研院校研究的大部分技术不能很快产品化，而一个专业公司的力 量毕竟有限。因此，中文分词技术要想更好的服务于更多的产品，还有很长一段路要走。 综上所述，中文分词在短短的几十年中发展迅速，目前已有多种优秀的自动分词系统， 分词算法有了很大的进展。从目前已知的各类分词方法看来，各有优缺点：机械分词方法 速度快，效率高，算法简单，容易实现，但容易产生歧义；理解分词法准确度高，主要是 模拟人的思维方式，但实现起来相当麻烦，现在还属于实验阶段，整个系统还不是很成熟； 统计的分词方法不需要分词词典，但容易抽出一些不是词的词组，时空开销大。所有方法 都存在一个共同的不足，即它们在歧义区分和未登录词两方面都存在缺陷。如将机械匹配 5 南京邮电大学硕上研究生学位论文第一章绪论 式和其它切分方法相结合，来提高机械匹配分词对于切分歧义的处理能力，是目前中文自 动分词方法研究的一个比较成熟的发展方向【1 3 1 。因此，如果能够综合各类分词方法的优 点，并在一定程度上解决好歧义区分和未登录词问题，那么中文分词技术定能取得更大 的性能提升。 1 3 2 发展趋势 根据目前中文自动分词的研究现状以及相关学科的发展情况，中文自动分词有望在以 下几个方面取得进展【1 4 】： ( 1 ) 汉语词的规范研究 由于汉语词的规范是中文自动分词的基础，没有统一和明确的汉语词的定义，没有规 范的汉语分词词表，中文自动分词就无从谈起。在汉语语言学家和计算机中文信息处理研 究专家们的共同努力下，目前，我国汉语词的规范研究和汉语分词规范词表的制定已经有 了较大的突破。信息处理用现代汉语分词词表的制定及不断完善，说明我国在汉语自 动分词词表方面取得了重大研究成果，这为汉语自动分词的研究铺平了道路。 ( 2 ) 中文自动分析研究 机械分词难以解决复杂的汉语组词的关系，因此今后应注重对汉语句法和语义的自动 分析研究，并将其应用到中文文本自动分词与标引领域。应引入知识分词的技术和方法， 采用知识分词语义分析进行文本标引专家系统的研究。此外，应从自然语言理解角度出发， 采用不同层次的处理方法。具体地说，从语义、语法、知识库、语境相关分析等语言学角 度出发，进行知识分词的理论性研究，以推动整个自动标引技术研究的迅速发展。 ( 3 ) 汉语词自动切分歧义处理 对于歧义只能从歧义自身信息与上下文信息人手。倘若自身能完全解决的歧义就是所 谓的假歧义，而对于真歧义只能借助于上下文信息f 1 5 1 。随着分词研究的突破，分词歧义 处理研究也取得了重大进展。以前的消歧方法大体可分为两类：规则方法与统计方法，此 外，还可以人工干预分词，人工分词与计算机自动分词结合。在遇到计算机解决不了的歧 义时，借助于人工干预来完成。为了有效地消除歧义字段，还可以在上述方法的基础上建 立分词歧义知识库或规则库。随着计算机技术和汉语言研究的发展，汉语词自动切分歧义 处理将会有更大的突破。 ( 4 ) 汉语词自动切分应用研究 目前，中文自动分词主要在信息检索、自动标引、自动文摘、机器翻译、语言文字研 究、搜索引擎研究、自然语言理解和中文信息处理等方面的应用都取得了可喜的成绩。随 6 南京邮电大学硕j 二研究生学位论文第一章绪论 着汉语自动分词技术的进展，这一研究成果将会被应用到广泛的研究领域，如词频统计、 内容分析、概念分析、认知心理学和汉语语言学等方面的。 ( 5 ) 人工智能技术 人工智能技术目前的重点研究领域主要是专家系统、神经网络技术和生物芯片技术。 从人工智能的发展和汉语自动分词的要求出发，比较理想的自动分词系统应该综合词法、 句法和语义信息，而用计算机对语义、语法进行自动分析尚处在研究阶段。因而，已经推 出的汉语分词与标引系统只能采用以机械分词为主，辅之以能部分反映词法、句法和语义 规则的改进算法，但仍难以解决复杂的汉语组词关系。因此，今后应注重汉语句法和语义 的自动分析研究，并将其应用到汉语自动分词领域。应引入知识分词的技术与方法，采用 知识分词语义分析法进行自动分词系统的研究。 中文自动分词是一个综合性的难题，它的发展依赖于汉语的分词结构、句法结构、语 义等语言知识的深入系统地研究，依赖于对语言和思维的本质的揭示【1 6 1 ，同时，还在很 大程度上还依赖于神经网络、专家系统、知识工程等人工智能技术的研究进展。从目前看， 任何一种单一方法都无法完善解决汉语的分词问题。对于任何一个成熟的分词系统来说， 单独依靠某一种算法都不可能实现，需要综合不同的算法。 应该说，目前在分词领域的研究进展已经有了一定突破，但是这些分词方法在面对语 言现象不断变化时，显得适应性很差，所以还需要继续对分词方法作进一步的研究，以期 能形成更加完善的分词方法。基于人工智能技术的神经网络分词方法和专家系统分词方 法，是理论上最理想的分词方法，但是由于该类分词方法的研究还处于初级阶段，并且由 于汉语自然语言复杂灵活，知识表示困难，所以对于基于人工智能的中文自动分词技术还 需要进行更深入和全面的研究。虽然目前还处于起步阶段。但是该类分词方法是未来中文 自动分词方法的发展方向。 1 4本文主要研究内容和组织结构 自动分词技术在搜索引擎乃至整个中文信息处理领域中有着重要意义。但是，当前的 分词方法普遍存在切分效率不高的局限性，大部分分词方法基本上都是基于词典和规则的 分词方法，它们都必须在分词速度和精度之间做出选择【1 7 1 ，若要提高速度，则要适当放 弃精度的追求，缩减词典，减少匹配次数；若要提高切分精度，则要舍弃速度，无限扩充 词典，匹配次数也会无限增加。目前还没有找到有效的解决方法。 基于词典的分词算法作为当前分词技术的主流，由于分词系统所需要的各类信息都要 从词典中获取，所以其精确度依赖于词典的完全性和歧义的有效消除【1 3 1 ，速度则取决于 7 南京邮电人学硕仁研究生学位论文第一章绪论 所设计的加载词典的数据结构和相应的切分算法。因而，分词词典是基于词典机制的汉语 自动分词系统的重要组成部分，其性能的优劣直接影响到分词系统的速度和效率，建立高 效而快速的分词词典机制势在必行。 本论文的主要研究内容有：在研究传统的词典机制基础上，设计和实现了一个中文自 动分词系统。在设计的分词系统中，词典中的每个词条加载到设计好的双层哈希数据结构 中去，且常驻内存，待分词的文本用标点符号和空格被分割成一个个更小单位的的字符串， 采用正向减字相对最大匹配法对字符串进行分词，对粗分的分词结果运用回退一字和统计 规则相结合的方法来识别、处理歧义字段和新词。其改进特点主要体现在两个方面，一是 采用“双层哈希+ 二分查找”的算法进行词典匹配，可以在较短的时间内能达到匹配成功 的目的，二是切分算法采用正向减字相对最大匹配法，每次切分的是某字开始词语的最长 长度，而不是词典中词语的最长长度，既防止了过长词条的遗漏，又减少了不必要的匹配 次数，提高了分词的速度。 本文的组织结构如下： 第一章介绍了课题的研究背景，分词在中文搜索引擎中的重要性和中文分词国内外研 究的现状和发展趋势，以及本文的主要研究内容和组织结构。 第二章主要介绍了中文分词的基本知识，包括分词的理论基础，分词系统的目标和评 价标准，中文分词算法的分类，分析了现有分词所面临的困难。 第三章讨论了四种传统词典机制的的基本原理，在分析现有词典机制不足的基础上， 引入对词条除首次字外剩余词进行二分查找的改进，给出了本文改进的词典机制，然后重 点论述了词典机制中词典的收词标准、组织方式和结构设计。 第四章介绍了本文设计的分词系统( u d d c h i s ) 的框架结构和功能特点，给出了系统的 整体算法流程，说明了分词系统的五大主要模块的设计思想，实现了主要代码。着重论述 了改进的正向最大匹配分词法一正向减字相对最大匹配算法( r d c m m ) 。 第五章对改进的分词系统c u d d c h i s ) 和原系统( d c h i s ) 进行了对比测试，分析和说明 了试验结果。 第六章对本文工作进行了总结，对下一步工作做出展望。 8 南京邮电人学硕士研究生学位论文第二章中文分词概述 第二章中文分词概述 汉语自动分词多年来一直是计算机科学、汉语言学界、人工智能界和情报检索界研究 的重点课题，它被广泛应用于中文信息处理的很多领域。尽管已被研究了二十多年，但是 目前仍然是制约汉语信息处理发展的一个瓶颈f 1 9 】，歧义问题和未登录词问题一直没有完 全突破，这两个问题已经成为提高中文分词准确率和中文走向国际化的最大障碍。 2 1 中文分词理论基础 2 1 1 中文分词的概念 汉语是一种词根语，具有如下特点：( 1 ) 汉语缺乏形态变化，没有性、数、格的变化标 志，词本身不能显示与其他词的语法关系，它们的形式也不受其他词的约束；( 2 ) 词序严 格，词序不同，意义也随之不同( 如“上海”和“海上”意义截然不同) ；( 3 ) 虚词是主要的 语法手段( 如“老师和学生 和“老师的学生”意义截然不同) ；( 4 ) 汉语书写系统采用词标 的形式，词与词之间没有明显的形态界限。汉语的这些特征决定了针对其他语言处理的方 法并不能完全适用于汉语信息处理，因为在汉语信息处理中，凡是涉及句法、语法、语义 等都要以词为基本单位，所以必须引入中文分词这门技术。 中文自动分词，也称为切词，是汉语所特有的研究课题。简单地说，中文分词就是将 连续的字( 词) 序列按照一定的规范重新组合成词序列的过程，也就是从信息处理需要出 发，按照特定的规范，对汉语按分词单位进行划分的过程。在计算机科学中，中文分词则 是在计算机中通过人为的规则，编写计算机应用程序对中文文本进行处理，获得词的序列 的过程。 众所周知，英文是以词为单位的，词和词之间是靠空格隔开，计算机识别单词简单易 操作：而在中文书面语中，汉字是方块字，每一个方块汉字都自为一个独立的、完整的书 写单元，相互之间没有明显的界限，书写时字与字逐一连续等距离排列，词与词之间没有 空格隔开，没有任何区分标志，加上汉语词的定义含糊、一词多义、词频集中、构词灵活 等特点，使得汉语词语切分更加困难。因此如何自动识别词边界，将汉字串切分为正确词 串的汉语自动分词问题，无疑是实现中文信息处理中各项任务的首要问题。 虽然英文也同样存在短语的划分问题，但是在词这层上，中文比英文要复杂的多和 困难的多。如英文句子“s h eg o e st os c h o o l ，用中文表达则为：“她去学校，对于英文计 9 甬泉邮电大学硕l 研究生学位论文第二章中文分词概述 算机可以很简单通过空格知道s c h o o l 是一个单词，但中文不能很容易明白“学”、“校” 两个字合起来才表示一个词。另外，汉语的词序极为灵活，相对的语法限制也较少。在词 汇数量上，汉语的词汇量高达几百万甚至上千万。而且一个汉字序列可能有几种不同的切 分结果，因而易产生歧义现象。 自动分词系统只是中文信息处理系统的一部分，分词本身并不是目的，而只是后续处 理的必需过程。分词单位的选取，般情况下要以分词规范为准，当然还要考虑具体的应 用环境，灵活地加以控制。此外，还需兼顾大规模语料库处理的特殊要求。因此，自动分 词原则应包括以下四点： ( 1 ) 分词单位的选取：必须有利于标注、句法分析等后续过程的处理。这点具体体 现在某些词组的处理上，这些词组包括数字词组( 如七分之一) ，时间词组( 如十月一日) ， 人名( 如张三) 等。 ( 2 ) 分词准确率：它是分词系统最重要的性能指标。作为中文文本自动分类系统的子 系统，分词系统的准确率直接影响着后续过程的准确率。分词速度远远高于标注、分析等 过程，不构成系统的处理瓶颈，即使采用较为复杂的方案，所需的处理时间仍远少于后续 过程。因此主要的研究应在提高处理精度。 ( 3 ) 容错性能：为了处理大规模的文本，要求系统有较好的容错性能。 ( 4 ) 分词词典的可扩充性：要求可扩充性必须是良好的，具备从语料库中自动学习的 能力。 2 1 2 中文分词的重要性 中文分词是机器翻译、分类、主题词提取以及信息检索的重要基础，它的重要性主要 体现在以下四个方面： ( 1 ) 自动分词是现代汉语句法分析器的一项基础性工作。汉语语言理解有着及其广泛 的应用价值，在人机接口、问答系统、机器翻译等众多的应用领域中，对输入文本进行句 法分析是一项必不可少的处理任务。计算机从事句法分析所凭借的语法信息通常来自机器 词典和句法规则库。机器词典收录了每个词条的语法、句法和语义知识，而句法规则一般 是在词类等知识基础上构造的。因此，对汉语句子必须先进行词语切分处理，才有可能进 行句法分析。如果对输入的源文件中的句子未经处理，仍然是一些字串序列，就无法根据 句子中出现的每个具体词到机器词典中去查找相应的语言知识；而且如果不知道每个具体 词的词性等词汇知识，也就不可能直接调用相关的句法规则来判断句子的句法结构。 ( 2 ) 语词的计算分析已广泛应用于词频统计、新词辨识、计算机辅助编纂、词语搭配 1 0 南京邮电大学坝t 研箩e 生学位论文第二章中文分侧儆述 研究和文章或风格学研究等众多领域。例如，词典编纂中选入词典中的词条，每条词语的 用法( 或义项) 以及相应的例句，不应是由编辑者生造，而都应从大规模真实语料中获取。 这些语料库的每个文本或实体，都应是在对语料进行切分、词性标注等处理后才能提供使 用。 ( 3 ) 语言文献处理自动化只有以词的文本特征，词性、词义和句法结构等更深层次的 语言知识才有用武之地。 ( 4 ) “以词定字 、“以词定音方法是解决错别字辨识、多音字的字音辨识和简繁体转 换等的主要手段，“以词定字”是汉语文本自动晓对系统实现检错纠错功能的重要技术之 一。 自中文分词这一问题提出后，几十年来，许多专家学者对此课题进了深入研究与探讨。 目前，中文分词技术得到了很大的发展，它主要有以下应用领域： ( 1 ) 信息检索 信息检索技术是现代信息社会中关键的技术之一。信息检索是将信息按一定的方式组 织和存储起来，并根据用户的信息需求查找所需信息的过程和技术。所以信息检索的全称 又叫“信息存储与检索”，狭义的信息检索仅指从信息集合中找出所需信息的过程，也就 是利用信息系统检索工具或数据库查找所需信息的过程。如今人类社会进入个“信息爆 炸”的知识经济时代，面对这纷繁复杂、变幻莫测的信息新时空，如何更全面、准确地获 取最新、最有效的信息已经成为人们把握机遇，迎接挑战和获取成功的首要条件。对中文 文本信息检索来说，由于中文本身的特殊性，词与词之间没有明显的切分标记，如果不采 用分词技术，简单的以字为单位建立索引，那么，信息检索的结果就过于粗糙而导致检索 资源不正确或不可用。在信息检索中，最重要的并不是找到所有结果，而是要把最相关的 结果排在最前面。中文分词的准确与否，常常直接影响到对信息检索结果的相关度排序。 由于中文的词与词之间没有分隔符，因此若想建立基于词的索引，就需要专门的汉语词语 切分技术。因而，分词能有效地提高文本检索的效率。 ( 2 ) 语音识别系统 据统计，汉语单字同音现象非常严重，以6 7 6 3 个汉字为例，无同音字的汉字只有1 6 个，其中最多的有1 1 6 个同音字。相比而言，汉语词的同音现象则有很大改善，以5 2 5 0 5 的词表为例，其中3 5 9 4 2 个词语没有同音词，因此大多数同音字可以依靠词来确定。如“一 支漂亮的铅笔 “z h j 的同音字有“支、只、枝、直、之 等，但这里“支 与“笔 合 理搭配。由此看出，分词对同音词自动辨识所起的作用是不可忽视的。汉语中也存在着大 量的多音字，计算机对它们的辨识也需要分词的帮助。如“校、行、重、乐、率、分”等 l l 南京邮电大学硕士研究生学位论文第二章中文分词概述 多音字，无论是拼音自动标注还是语音合成都需要识别出正确拼音，而多音字的辨识可以 利用词以及句子中前后词语境，即上下文来判断出来。如以上几个字在以下几组词中得以 定音“学校校对，行列行进，重量重新，快乐音乐，率领效率，分别水分”。 ( 3 ) 简繁体自动转换 简体和繁体之间的转换，在单字一级，通常会有一个简体汉字对应多个繁体汉字的情 况，如：“发”对应繁体的“袋和“鬓”。如何判断简体繁体转换应该将“发”转为“赣 还是“鬟9 9 9 这就引入了简繁歧义的问题。同多音字的识别相同，但在词和词组的层面上， 它的转换通常是确定的。因而，分词对简体繁体自动转换有着至关重要的作用。此外， 简体中文和繁体在一些技术术语的运用上也不同，例如，简体中文计算机术语“物理地址” 和“逻辑地址”在繁体中文中写作“物理位址”和“逐辑位址”。简体繁体转换系统也需 要解决这种术语的不同用法问题。简体繁体转换系统运用分词模块切分词语，根据词语 以及上下文来决定最可能的转换结果，可以有效解决转换中的歧义问题。 ( 4 ) 机器翻译 机器翻译是允许计算机用户用某种语言输入文本然后由计算机将其翻译为( 从其自身 的字典资源) 另外一种语言。机器翻译所依赖的自动翻译技术包括语音翻译和文字翻译， 主要的关键技术有四个方面：单词分析、语法分析、意义分析和文理分析。它的工作过程 是，先把语句分成各个单词，通过存放于机器数据库内的电子字典查清词义，根据语法规 分析语句的意思，并把它变换成概念构造，然后借助语言模型生成目标语言。汉语分词是 机器翻译的开始和关键，分词效果的好坏直接影响到翻译的结果。机器翻译的目标不是像 人一样准确地翻译文本，而是向那些不懂英语的计算机用户提供一个解决办法，将那些没 有译文的软件翻译为他们熟悉的语言。随着信息的急剧增加，国际交流的日趋频繁，机器 翻译的潜在需求越来越大。 ( 5 ) 自然语言理解 俗称人机对话，人工智能的分支学科。研究用电子计算机模拟人的语言交际过程，使 计算机能理解和运用人类社会的自然语言如汉语、英语等，实现人机之间的自然语言通信， 以代替人的部分脑力劳动，包括查询资料、解答问题、摘录文献、汇编资料以及一切有关 自然语言信息的加工处理。自然语言理解是- - l - 新兴的边缘学科，内容涉及语言学、心理 学、逻辑学、声学、数学和计算机科学，而以语言学为基础。由于汉语用的是汉字，无论 是用汉字编码输入还是将来计算机能直接认识汉字，都要首先解决切分单词的问题，因为 输入就是一连串汉字，词和词之间没有空隔。因此，如果输入语句未经分词处理，就无从 根据句中出现的每个具体词到机器词典中去查找相应的语言知识：而如果不知道每个具体 1 2 堕京邮电大学硕上研究生学位论文第二章中文分词概述 词的词性等词汇知识也就不可能直接调用相关的句法规则来正确判断短语或句子的句法 结构。 ( 6 ) 文本分类 文本自动分类是信息处理的重要研究方向之一，指计算机在给定的分类体系下，将一 篇文章自动地分派到一个或多个预定义的类别中去，它属于信息检索和机器学习的交叉学 科。文本自动分类系统主要涉及主题词表和分类词表的建立、分词算法以及特征向量权重 算法。因此，汉语自动分词是文本分类首先要解决的问题，直接影响到文本分类的结果。 ( 7 ) 计算机和人工智能领域 主要利用自动分词成果从事自然语言理解和处理研究，如语义分析、自动便文摘、知 识工程、专家系统和智能计算机等。汉语自动分词是一个与汉语语言理解具有同等难度的 问题，它涉及了知识表示、知识获取、启发式推理、尝试性推理等一系列基本理论问题。 实际上，一个比较好的自动分词系统本身就是个知识系统。 ( 8 ) 情报信息领域 中文文献的内容分析、自动标引、自动编索引、自