（计算机应用技术专业论文）基于统计分词改进算法的网络信息检索系统研究.pdf

摘要 随着i n t e r n e t 的发展，网络信息以前所未有的速度膨胀着，整个社会都进 入到一个信息极其丰富的时代。如何更好的利用网络信息资源，如何通过 i n t e r n e t 快速查找自己所需要的资料，如何替代传统的信息检索手段，发展新 的检索系统，以满足人们增长的需求和适应快速更新的网络信息资讯，已成为人 们日益关注的问题。 本文在对检索系统关键技术进行研究的基础上，主要实现了一个以统计分词 改进算法为基础的网络信息检索系统。该系统通过网页内容提取技术对网页进行 处理，形成纯文本形式，并通过中文自动分词技术对其进行分词处理，提取出特 征索引词，提供给检索模块，实现对信息的检索。 本文对几种分词算法进行了详细介绍与研究，并在比较分析的基础上，提出 了一种统计分词的改进算法，这种算法不仅可以提高未登录词的识别能力，同时 引入了串匹配分词算法，降低了高频冗余词对文本特征索引词提取的干扰，为信 息检索提供了良好的处理依据，增强了检索性能，改进分词算法本身也具有良好 的扩展性和应用性。 本文介绍和比较了几种常见的检索模型，并在对它们进行研究分析的基础 上，采用了较为成熟的布尔检索模型实现检索系统，并通过建立索引文件，加速 了对表征文本内容的词组匹配，实现对信息进行检索的目的。 最后的试验结果表明，改进的分词算法，在准确率和召回率上，基本可以满 足信息处理分词要求，而检索系统本身，也己达到一般信息检索的要求，并具有 可扩展性和广泛应用性等特性。 关键词信息检索；中文自动分词；布尔检索模型；b i g r a m a b s t r a c t w i t ht h ed e v e l o p i n go fb t c m e lm t e m c ti n f o r m a t i o nd e v e l o p f a s t , an e w i n f o r m a t i o ne r ah a sc o m et 0l i v e so fm e m b e r so f e i e t y h o wt 0i l l s et h e i n f o i m a f i o nr e s o u r c e s ，h o wt 0s e a r c hi n f o r m a t i o no nm c 锄c t ，h o wt ot a k ep l a c eo l d i n f o 删o nr e t r i e v a lm e 吐i o d ，d e v e l 叩n e wi n f o r m a t i o nr e i d c v a ls y s t e m , h o wt om e e t p e o p l e r e q u i r e sa n ds a t i s 母t h ei n c r e d i b l es p e e do fm t e m c ti n f o r m a d o nu p d a t m 舀a l l o f m e s cp r o b l e m sn o wb e c o m ep o p u l 骶o b a s e do nt h er e s e a r c ho fk e yt e c b d o l o g ya _ b o mi n f o r m a t i o nr e t r i e v a l ，姐m t e m d i n f o r m a d o nr e t r i e v a ls y s l e mb a s e do ni m p r o v e d 一枷s t i c s s e g m e m 撕o n w a s i n l p l 锄e l l t c d t h r o u g ht h ec o n t e n t se x t r a c d o n 丘d mh t m l , t h i ss y s t e mc o 试dg e t c h 舭a c t e r i s t i c sb yu s i n gc l l i n e w o r d g m e m a t i 蚰t e c h n o l o g y a n dt h e nr e e d c b a r a c t c r i s t i c st 0a c c o m p l i s ht h ei n f o m a t i o nr e 缸e v a l s o m ec o m m o nc h i n e s ew o r ds e g m e n tm e t h o d sw e r ed e s e f i b e da n dc 伽叩a r c di n t h i sp a p e r , b a s e do nt h e s e ，a ni 苴巾r o v e ds 扭t i s 蛀c ss e g m e n tm e t l l o dw a sp r o p o s e d t h i s m e t h o dn o to n l ym c r e 刹t h er e c o g n i t i o n a b i l i t y , b u ta l s oc o u l dd e g r a d et h e d i s n 州血培o f n e ww o r d sb ym m g t h ee h a r 蜘o f s t r i n g - m a t c h 掣n tm e t h o d t h i s i m p r o v c dm e t h o d c o l l l d p r o v i d cg o o d c h a r a c t e r i z e s 州c hw o u l d i m p r o v e i n f o r m a t i o nf 鲥e v a la b i l i 够 t h r o u g ht h ec o m p 础s o na n dd e r i 埘o no f m cc o m m o nr e t r i e v a lm o d e l s ，t h e s y s t e mu s e db o o l - i 嘶e v a lm o d e lt oa e e o m p f i s ht h ei n f o r m a t i o nr e t r i e v a lm o d i l l e t h r o u g hc r e a t i n gi n d 懿丘l e ，t h es y s t e mi n c r e 蠲e dt h es p e e do fw o r d sm a t c h i n ga n d 删e v e dt h ea i mo f i n f o r m a t i o nr e t r i e v a la tl a s t t h ea n a l y s i so ft h er e s l l l t s p r o v c dt h a tt h ei m p r o w 沮粤咧tm e t h o dc o m d s a t i s 匆t h er e q u i r eo fi n f o r m a d o np r o e e s s i n g i nt h ec o r r e c tr a t e ，t h ei n f o r m a t i o n r e m e 、枷s y s t e ma l c o l l l ds u p p o nt h eg e n e r a l c do fi n f o r m a t i o nr e t r i e v a l 、) l ，i l h e x p 姐s i b i l 时a n dh 碘l l s a b i l i 劬 k e y w o r d s m f o m l a n o n 彤啊e v a lc h i n e 辩w o r ds e 笋e n t , b o o l - r e l f i e v a lm o d e l ，b i g r a m i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 签名：蜷差 日期： 关于论文使用授权的说明 砂7 _ 1 1 2 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名： 篇应 导师签名： 第1 章绪论 第1 章绪论 1 1 信息检索系统的产生与意义 网络技术的迅猛发展，带来了因特网信息时代的高速发展，因特网的出现改 变了人类的工作和生活方式，同时也极大地改变了人们获取、传播、利用信息的 方式。随着w w w 上信息量的不断积累，如今因特网己经成为当今最大的信息库， 并且成为全球范围内传播信息的最主要渠道之一，成为人们学习、工作中最重要 的知识和信息来源。 随着时间的推移，网络信息急剧增加，人们对网络的信息需求也在不断增加， 这都对传统的信息服务模式提出了挑战，单纯地靠手工查找或组织所有的信息已 经不能够满足要求，人们迫切需要能够快速、准确、经济地查找某个主题全部信 息的信息检索系统，于是越来越多的人开始对信息检索进行大量的探索和研究， 以求更加有效地利用信息资源为经济和社会发展服务“1 。 随着网络技术的飞跃，越来越多的专业信息数据库通过提供检索服务，充分 发挥网络的作用，能够在上百万个网站中快速有效地查找到所需信息，从而使检 索方法更简单，更趋于平民化，而信息检索的对象从相对封闭、稳定一致、由独 立数据库集中管理的信息内容，扩展到开放、动态、更新快、分布广泛、管理松 散的w e b 内容“。信息检索的用户也由原来的信息专业人员扩展到包括商务人员、 管理人员、教师学生、各专业人士等在内的普通大众，不同的职业，不同的需求， 不同的检索方式，这些对信息检索从结果到方式都提出了更高、更多样化的要求。 当今社会中，信息已成为全社会的重要资源，对信息的占有量及信息处理手 段的先进程度已成为衡量一个国家或地区现代化程度的重要标志。信息检索技术 的研究和高效的信息检索系统的开发在现代具有非常重要的意义，认清网络信息 检索的发展趋势，掌握先进的网络信息检索技术，利用网络快速、有效地检索到 所需的信息资源，已成为当前重要而迫切的研究课题。 1 2 信息检索的发展现状 信息检索( i n f o r m a t i o nr e t r i e v a l ) 是一门关于信息资源存储、排序和查找 理论、方法的学问，通俗地说，信息检索就是信息用户为处理解决各种问题而查 找、识别、获取相关的事实、数据、知识的活动及过程，将信息按一定的方式组 织和存储起来，并根据用户的需要找出有关信息资源的过程和技术嘲。 随着网络技术的不断提高以及信息量的爆炸式增长，越来越多的信息存储于 北京工业大学工学硕士学位论文 计算机硬盘或光盘上，并建立了相应的信息检索系统，从而使信息的存储量更大、 检索更方便，基于这种趋势，越来越多的人开始对信息检索进行大量的探索和研 究，以便更加有效地利用信息资源为经济和社会发展服务。网络信息检索系统也 根据人们的需要和相关技术要求，发展了好几种形式，一般的信息检索主要有网 页搜索引擎和网络分类目录两种。 网页搜索引擎是通过“网络蜘蛛”等网页自动搜寻软件搜索到网页，然后自 动给网页上的某些或全部字符做上索引，形成目标摘要格式文件以及网络可访问 的数据库，供人们检索网络信息的检索工具，网络耳录则是和搜索引擎完全不同， 它不会将整个网络中每个网站的所有页面都放进去，而是由专业人员谨慎地选择 网站的首页，将其放入相应的类目中。网络目录的信息量要比搜索引擎少得多， 再加上不同的网络目录分类标准有些混乱，不便人们使用，因此目前网络信息检 索技术最主要的应用就是搜索引擎，按照信息搜集方法和服务提供方式的不同， 搜索引擎系统可以分为三大类：分别是全文搜索引擎( f u l t e x ts e a r c h e n g i n e ) 、目录索引类搜索引擎( s e a r c hi n d e x d i r e c t o r y ) 和元搜索引擎 ( m e t ss e a r c he n g i n e ) 嘲埘。 ( 1 ) 全文搜索引擎全文搜索引擎是名副其实的搜索引擎，国外具代表性 的有g o o g l e 忉、f a s t i a l l t h e w e bm 、a 1 t a y s t a 嘲、i n k t o m i 嘲、t e o m a 、w i s e n u t 等，国内著名的有百度( b a i d u ) 。它们都是通过从互联网上提取的各个网站的信 息( 以网页文字为主) 而建立的数据库中，检索与用户查询条件匹配的相关记录， 然后按一定的排列顺序将结果返回给用户，因此他们是真正的搜索引擎“1 。 ( 2 ) 目录索引目录索引虽然有搜索功能，但在严格意义上算不上是真正 的搜索引擎，仅仅是按目录分类的网站链接列表而己，用户完全可以不用进行关 键词( k e y w o r d s ) 查询，仅靠分类目录也可找到需要的信息。目录索引中最具代 表性的莫过于大名鼎鼎的y a h o o 雅虎，其他著名的还有o p e nd i r e c t o r yp f o j e c t ( d m o z ) 叫、l o o k s m a r t “”、a b o u t “”等，国内的搜狐、新浪、网易搜索也都属 于这一类。 目录搜索引擎主要包括如下的几部分：网页采集、网页分类、网页索引、搜 索器等。网页采集以人工方式或半自动的方式进行的，分类目录一般都有专门的 编辑人员，负责收集网站的信息，随着收录站点的增多，现在一般都是由站点管 理者递交自己的网站信息给分类目录，然后由分类目录的编辑人员审核递交的网 站，以决定是否收录该站点，如果该站点审核通过，分类目录的编辑人员还需要 分析该站点的内容，并将该站点放在相应的类别和目录中。所有这些收录的站点 同样被存放在一个“索引数据库”中，用户在查询信息时，可以选择按照关键词 搜索，也可按分类目录逐层查找，如以关键词搜索，返回的结果跟全文搜索引擎 一样，也是根据信息关联程度排列网站，需要注意的是，分类目录的关键词查询 第1 章绪论 只能在网站的名称、网址、简介等内容中迸行，它的查询结果也只是被收录网站 首页的u r l 地址，而不是具体的页面。分类目录就像一个电话号码薄一样，按照 各个网站的性质，把其网址分门别类排在一起，大类下面套着小类，一直到各个 网站的详细地址，一般还会提供各个网站的内容简介，用户不使用关键词也可进 行查询，只要找到相关目录，就完全可以找到相关的网站( 注意：是相关的网站， 而不是这个网站上某个网页的内容，某一目录中网站的排名一般是按照标题字母 的先后顺序或者收录的时间顺序决定的) 。 ( 3 ) 元搜索引擎元搜索引擎在接受用户查询请求时，同时在其他多个引 擎上进行搜索，这类搜索引擎没有自己独立的数据库和索引机制，而是将用户的 查询请求同时向多个搜索引擎递交，将返回的结果进行重复排除、重新排序等处 理后，作为自己的结果返回给用户，服务方式为面向网页的全文检索。这类搜索 引擎的代表是w e b c r a w e r “、i n f o m a r k c t “等，在搜索结果排列方面，有的直接 按来源引擎排列搜索结果，如d o g p i l e “”，有的则是按照自定的规则将结果重新 进行排列组合，如v i s i m o “”。 但无论何种搜索形式，作为网络信息处理的一种，如何对网页进行自然语言 处理，如何对文本内容进行自动分词处理，以减小检索难度和空间复杂度，达到 提高检索质量的目的，已成为当今所有检索系统中不可逾越的重要处理过程。 1 3 分词技术在信息检索中的应用 分词技术作为网络信息处理的重要组成部分，一直有着举足轻重的地位，而 在信息检索领域中，分词处理的好坏，更是会对检索结果产生直接影响，因此在 检索系统中，人们也常常将分词处理的准确率和识别能力作为评价系统好坏的标 准之一。 与其他信息处理的应用相比，信息检索会遇到更多的未登录词问题，同时对 系统处理歧义问题的要求也比较高，这就要求自动分词系统具备很强的对未登录 词的识别能力，同时能够通过分词技术，综合词语多方面的特性，提高对未登录 词识别的准确率和召回率，同时提高歧义切分的精确度。 信息检索对自动分词处理的要求很高，但同时，它又是检索中不可跨越的重 要组成部分，因此人们对分词系统傲了大量研究。目前，已经有一些搜索引擎使 用了自动分词技术( 如百度、北大天网“”等) ，虽然只是简单地应用，且存在种种 不尽人意之处，但却仍显示了自动分词在信息检索中应用的广阔前景。 1 4 中文分词技术研究的技术动态 目前在信息检索领域，英文信息检索发展得较为迅速和完善，如信息的表示 北京工业大学工学硕士学位论文 采用矢量空间方法，基于内容相关性的查询反馈等，而中文的网络信息检索的发 展则相对较慢，这主要是由中文语言自身的特点决定的。 众所周知，对于英文由于词与词之间是用空格隔开，切分起来很方便，而相 对来讲，中文的情形就复杂得多，比如中文词语在索引前如何合理切分，汉语语 义理解和句法分析十分困难等，这些都是由于中文的词与词之间，没有类似英文 空格之类的显式标示词的边界标志。因此若想对中文文本建立基于词表的索引， 就需要专门的技术，这种技术被称之为汉语词语切分技术，即中文自动分词技术 【n 】 o 中文自动分词技术是中文信息处理的基础技术，也是中文信息检索向智能化 检索、自然语言检索、多语种检索等方向进一步发展的关键问题。目前，信息检 索领域的研究已经开始注重对自然语言的处理技术，并对中文自动分词技术做了 大量的研究，并取得了一些重大的成就，虽然还存在一些问题，但有的中文自动 分词系统已经在实际系统中有所应用。 1 4 1 中文分词技术研究现状 近几年，人们不断对中文自动分词进行研究，提出了很多算法，取得了很大 成就。 清华大学研究实现的s e g 分词系统，提供了带回溯的正向、反向、双向最大 匹配法和全切分评价切分算法，由用户来选择合适的切分算法，这个系统最大 的特点就是带修剪的全切分一评价算法。系统考虑到了切分盲点的问题( 某些字 串永远不会被某种分词方法匹配出来) ，由此提出了全切分的概念，即找出输入 字串的所有可能的子串，然后利用某种评价方法从所有这些可能的子串中选出最 佳子串序列作为分词结果“”。 北京大学计算语言学研究所研制开发的分词系统，属于分词和词类标注相结 合的分词系统。此系统的一大特色是将最稳定、最常用的4 万6 千余条现代汉语 基本词汇( 即将扩充到7 万多条) 及其有关属性组织成为基本词典，在此词典的基 础上充分利用汉语构词法的研究成果，可以识别出大部分的常用词。允许用户加 入3 部到3 0 部以上的自定义词典，这样就可以用较小规模的多个特殊词典更有 针对性地解决具体领域的文本处理“叮。 微软研究院的自然语言研究所的多国语言处理平台n l p w i n “”，它对中文的 处理，以北大计算语言所的现代汉语语法信息词典为基础，将词的切分同句 法分析器融合起来，在其匹配切词阶段保留所有可能的切分结果( 包括歧义切 分) ，然后在句法分析阶段使用汉语的句法规则判断切分的合理性，对于有上下 文的歧义切分字段，系统将生成两棵以上的分析树( 可以使用某种标准进行排序) 第l 章绪论 来进行处理，以达到更高的准确率。 但是以上介绍的这些技术和成果都是基于词典分词，这种方法有一个缺陷就 是对词典的依赖性太大，虽然上述系统对此都作了很多改进，但仍在应用范围和 字典维护上受到了一定的限制，因此人们提出了一种无词典基于统计的汉语自动 分词，这种方法根据字与字出现在一起的频率来进行词组的划分，独立于词典， 具有非常强的通用性。针对无词典分词这种技术，复旦大学的韩客松等曾经从基 于字词统计的角度，对汉语语言的无词典分词模型系统作了相应的研究“”，并提 出了一些相关的思想和概念。 但是由于汉语本身的复杂性与对于语义要求的严格性，这些年虽提出了很多 不同的算法，却仍然存在着这样或那样的缺陷，对于中文词语识别的精确度不高。 如今中文自动分词技术已成为制约信息检索发展的一个难点，如果能突破这个难 点，那么检索中的中文信息自动处理就会迎刃而解，可见中文自动分词技术的研 究具有非常强的现实意义。 1 4 2 中文分词技术存在问题 要将汉语文本的字序列切分成词的序列，即使确定了一个合适的分词标准， 要实现这个标准也还存在算法方面的困难，下面主要介绍中文自动分词在信息检 索领域面临的主要问题： ( 1 ) 切分歧义汉语文本中含有许多歧义切分字段，典型的歧义有交集型 歧义( 约占全部歧义的8 5 以上) 和组合型歧义，只有向分词系统提供进一步的 语法、语义知识才有可能做出正确的决策，但在实际中却难以做到，因此一般排 除歧义常常用词频、词长、词闯关系等信息“”，比如“其实会”中，“其”作为 单字词的频率大大低于“会”作为单字词的频率，即“会”常常单独使用而“其” 作为单字词使用的可能性较小，所以应切成“其实会”。有时切分歧义发生在 小段文字中。但为了排除歧义，需要看较长的一段文字，如“工会组织”既可能 是一个名词，指一种工会的组织，也可能是“工会组织”，即分别表示一个名 词和一个动词的组合，但在“工会组织演出活动”中歧义仍然排除不了，这常常 成为影响分词准确率和召回率的重要原因。 ( 2 ) 未登录词识别未登录词即未包括在分词词表中，但必须切分出来的 词，包括各类专名( 人名、地名、企业字号、商标号等) 和某些术语、缩略词、新 词等等，还包括外族、外国名的汉译名“”，未登录词的识别对于各种汉语处理系 统不仅有直接的实用意义，而且起到基础性的作用，如果自动分词中对未登录词 识别不对，后面的信息处理就会有很大误差。 ( 3 ) 词典的编制与运作网上信息的膨胀，加大了信息加工标引的难度， 北京工业大学工学硕士学位论文 各种新概念、新说法层出不穷，大大超出了规范词表的收录范围，如何为这些信 息赋予合理的标引词，并力求标引的一致性，是词表编制及运作机制方面面临的 一大挑战“”。 在信息检索中运用中文自动分词技术存在不少困难，因此想要在中文网络信 息检索上取得重大进展，就必须突破中文分词这一制约信息检索发展的瓶颈。 1 5 课题来源 本课题来源于北京市科委资助项目基于校园网的可信运行保障系统研 究，此项目被北京市科委成功验收。在项目中，本课题在校园网络文本内容的中 文自动分词和检索方面做了一定的研究和实现。 1 6 本文主要研究工作 本文主要是针对检索系统所涉及的各项主要技术进行全面的论述，并对其中 所涉及的网页获取、网页内容提取、中文自动分词和检索技术等关键技术分别予 以设计实现，同时对检索系统中的分词算法进行了深入的研究，提出了一种改进 的统计分词算法，提高分词的准确率和召回率。 本文从信息检索系统及自动分词技术着手，进行了以下几方面的研究； ( 1 ) 本文对检索系统中自动分词技术发展及其所面临的困难等进行阐述， 并在参阅国内外大量文献的基础上，对几种分词算法进行比较分析分析，提出了 一种改进分词算法，解决了目前分词算法所面临的一些问题。 ( 2 ) 设计并实现了中文检索系统的总体结构及相应的关键技术，并对几种 常用的检索模型进行比较分析，选择合适的检索模型实现检索。 ( 3 ) 结合信息检索模型和改进的分词算法，实现了基于改进分词算法的网 络信息检索系统。 1 7 文章章节组织 第一章绪论 第二章介绍常见的信息检索模型，并对这几种检索模型进行比较分析，除 此之外，还详细介绍了几种常见的分词算法，并对这几种分词算法进行比较分析。 第三章详细介绍了统计分词改进算法的原理和过程 第四章详细介绍了中文检索系统中各个模块的设计和实现 第五章基于统计分词改进算法的检索系统的实验结果及分析 最后是全文工作的总结和展望 第2 章自动分词算法与检索模型研究比较 第2 章自动分词算法与检索模型研究比较 2 1 中文自动分词算法 几乎任何一个基于中文处理的系统，都必须经过分词这一步，自动分词系统 是中文信息处理中的一个主要组成部分，因此同样在文本信息检索中，也需要应 用中文自动分词。在信息检索中，检索系统一般采用词表索引，这是因为，首先 以词为单位比较符合人的表达习惯，其次以词表为索引项就可以借用英文全文检 索系统中已有的理论和方法。 词法分析主要指从接受输入串开始到对输入串进行句法层面的分析之前，对 输入串所进行的词一级的处理。相对英文信息处理，中文信息处理中的分词技术 却成为制约其发展的难点之一，这主要是由于中文和英文差异性造成的。英文有 类似空格之类的显式边界标志，可以明确定义词与词的界限，而中文无论是词语 联系，语法还是语义，都更加复杂多变。汉语词法的主要任务不是分析单词的形 态变化，而是进行单词的自动切分，必须采用专门的算法，来对词语进行切分处 理，这就是中文自动分词技术，也因此，中文自动分词就成为包括信息检索等自 然语言处理的不可逾越的阶段。 现有的分词算法主要可以分为三大类：基于字符串匹配的分词算法、基于统 计的分词算法和基于理解的分词算法。而其中，又以前两种算法应用更为广泛， 本文首先对这些算法做一个简单介绍。 2 1 1 基于字符串匹配的分词算法 字符串匹配算法，一般称为串匹配算法，又叫做作机械分词算法。它是按照 一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行匹配， 若在词典中找到某个字符串，则匹配成功( 识别出一个词) ，这种分词方法最大的 优点就是快速高效。按照扫描方向的不同，字符串匹配分词方法可以分为正向匹 配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大( 最长) 匹配和最小 ( 最短) 匹配：按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词 与标注相结合的一体化，常用的几种机械分词方法有逐层遍历法、正向最大匹配、 逆向最大匹配、伽法、二次扫描法。 ( 1 ) 逐次遍历法该方法是将词典中的所有词按由长到短的顺序在文章中 逐个搜索，匹配整个待处理材料，直到把所有的词都切分出来为止“”，也就是说， 不管文章有多短，词典有多大，都要将词典遍历一遍。故这种方法的时间复杂度 比较高，是一种不常使用的分词方法。 ( 2 ) 正向( 删) 与逆向( r m m ) 最大匹配算法正向最大匹配法的基本思想 是先取一句话的前几个字查字典，若不是一个词，则删除几个字的最后一个字再 查，这样一直下去，直到找到一个词为止，对句子剩余部分重复此操作，直到把 所有的词都分出来为止，逆向最大匹配法和正向匹配法一样，不同之处在于它是 从句子的最后几个字开始的，每次匹配不成功时去掉汉字串中最前面的一个字 嘲 0 ( 3 ) o m 方法o m ( t h eo p t i m u mm a t c h i n gm e t h o d ) 方法称为最佳匹配法， 伽方法分为正向最佳匹配法和逆向最佳匹配法。最佳匹配法的出发点，是在词 典中按词频的大小顺序排列词条，以求缩短分词词典的检索时间，达到最佳效果， 从而降低分词的时间复杂度，加快分词速度。 实质上，这种分词方法是预先对分词词典进行处理，而不是一种纯粹意义的 分词方法。o m 方法中分词词典每条词前面必须有指明长度的数据项，所以o m 方 法的空间复杂度稍有增加，例方法虽然降低了分词的时间复杂度，但是并没有 提高分词精度m ，。 ( 4 ) 二次扫描法二次扫描法的基本思想是取出待处理材料中两个切分标 志之间的部分作为样本串，首先从该样本串中取两个汉字作为匹配串，检查分词 词典中是否有一个词，它的前两个汉字和该样本串相同，若有的话，则取出样本 串的前三个汉字作为匹配串，重新在分词词典中找可以匹配串的词，若有则重复 下去，直到进行i 个汉字为止( 设i 为词典中最长词所含汉字的个数) ，则切分 出一个i 字词，若没有则完成了一次扫描，把匹配中的最后一个汉字去掉，作为 新的匹配串，进行第二次扫描，第二次扫描是用删方法或r m m 方法进行。“。 2 1 2 基于理解的分词算法 基于理解的分词算法基本思想就是在分词的同时进行句法、语义分析，利用 句法信息和语义信息来处理歧义现象。它通常包括三个部分：分词子系统、句法 语义子系统、总控部分，在总控部分的协调下，分词子系统可以获得有关词、句 子等的句法和语义信息，来对分词歧义进行判断，即它模拟了人对句子的理解过 程，基于理解的分词方法主要有以下几种： ( 1 ) 专家系统方法专家系统方法从专家系统角度把分词的知识( 包括常 识性分词知识与消除歧义切分的启发性知识即歧义切分规则) 从实现分词过程的 推理机中独立出来，使知识库的维护与推理机的实现互不干扰，从而使知识库易 于维护和管理，它还具有发现交集型歧义字段、多义组合歧义字段的能力和一定 的自学习功能m ，。 ( 2 ) 规则描述语言切词法规则描述语言是用以描述汉语分词，分析和生 善 第2 章自动分词算法与检索模型研究比较 成规则的一种工具。整个规则语言由多个规则块构成，每个规则块包括多条规则， 规则块的结构采用多层次的树型结构，该方法对正确描述汉语是一种有意义的尝 试。“。 ( 3 ) 扩充转移网络分词法扩充转移网络分词法是以有限状态机概念为基 础，有限状态机只能识别正则语言，对有限状态机作的第一次扩充使其具有递归 能力，形成递归转移网络( r t n ) 嘲。在r t n 中，弧线上的标志不仅可以是终极 符( 语言中的单词) 或非终极符( 词类，如名词n ，动词v 等) ，还可以调用另 外的子网络的非终极符或字串的成词条件，这样计算机在运行某个子网络时，就 可以调用另外的子网络，还可以递归调用。目前大多数的语言理解系统都把词典 组织成一个表，表是静态的，用扩充转移网络来组织词典就可以构成一个动态的 词典，词法扩充转移网络的使用，使分词处理和语言理解的句法处理阶段的交互 成为可能，并且有效地解决了汉语分词的歧义。 虽然人们针对这一类的分词方法，提出了很多的解决方案，但是这种分词方 法需要使用大量的语言知识和信息，由子汉语语言知识的笼统、复杂性，难以将 语言信息组织成机器可直接读取的形式，因此目前基于理解的分词系统多数还处 在试验阶段。 2 1 3 基于统计的分词算法 统计分词算法的基本思想主要是：从形式上看，词是稳定的字的组合，因此 在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词，因此字与 字相邻共现的频率或概率能够较好地反映成词的可信度脚。可以对语料中相邻共 现的各个字的组合的频度进行统计，计算它们的互现信息，两个字的互现信息的 定义可用公式( 2 - 1 ) 为： m ( x ，y ) = l o g p ( x ，y ) ( p ( x ) x p ( y ) ) ( 2 - 1 ) 其中p ( x ，y ) 是汉字x 、y 的相邻共现概率，p ( x ) 、e ( y ) 分别是x 、y 在语料 中出现的概率。 互现信息体现了汉字之间结合关系的紧密程度，当紧密程度高于某一个闺值 时，便可认为此字组可能构成一个词。这种方法只需对语料中字的频度进行统计， 不需要切分词典，因而又叫做无词典分词法或统计分词方法，基于统计的分词方 法主要有以下几种： ( 1 ) 高频优先法高频优先法是基于词颇的统计，在对字与字之间的构成 结合律和歧义切分等现象进行分析的基础上提出来的，根据现代汉语颇率词 典，对于报刊和政论性文章，不同音节词的词频为：双音节词乃8 9 ，三音 节词3 7 ，单音节词4 2 ，五以上字节词4 。汉语是一字一音节，可以看出 北京工业大学工学硕士学位论文 两字组词的概率比其它所有方式的概率加起来还多，分词时首先考虑两字词，然 后考虑单字词。这种方法提高了分词效率，但对歧义问题也无能为力，出错率并 不减低1 。 ( 2 ) n - g r a m 算法n g r a m 汹1 算法的基本思想是将文本中的字认为是一连串 有意义的字符流，在不考虑意义的情况下，按照连续n 个字符将文本分割成所有 可能出现的长度为n 的字符串，经常出现的n 个连续字符有可以表示文本特征的 可能，这样就可以避免对词典和复杂词语切分程序的依赖。 2 2 各种分词算法的比较 由于分词是一个智能决策过程，串匹配分词方法无法解决分词阶段的三大基 本问题： ( 1 ) 搜索时存在的交集型和组合型歧义切分问题； ( 2 ) 未登录词识别问题； ( 3 ) 词典的完备性不能得到保证的问题。 众所周知，词表中不能包含所有领域的全部词汇，一方面是因为语言是在不 断的发展和变化的，新词会不断的出现，另一方面是因为词的衍生现象非常普遍， 没有必要把所有的衍生词都收入辞典中。比如用一个含有5 0 0 0 0 个词的词典去切 分含有1 0 0 0 0 个词的语料库，却仍有可能有3 0 以上的词条没有被分出来，也就 是说有3 0 0 0 个词没有在词典中登录，而且对于词典的维护，也需要很大的工作 量。 除此之外，缺乏自学习的智能性是机械分词法的一大弱点，目前使用的词典 要么是人工编制，要么是从语料库中自动生成的，但不管是哪种词典，一旦建立 好了，都是固定的、静态的，而w e b 上的词是动态的，各种领域各样词汇都有， 用一个静态的词典去匹配一个动态的w e b 文档，自然是不可能得到良好的效果 的。机械分词只局限于分出统计词典中的词，不能分出那些在文档中出现而又不 在词典中出现的关键词( 即未登录词) ，所以机械分词缺乏必要的灵活性和扩展 性。 但是这种方式回避了许多难度较大的语言自身信息的处理问题，实现简单， 而且这种分词方法最大的优点就是快速高效，所以串匹配分词算法至今仍然得到 广泛的应用。实际使用的分词系统仍有很多将机械分词作为一种切分手段，它与 信息检索挂接性强，因为目前大多数检索系统是基于主题词表、分类表及分类主 题一体化词表建立的，两者都是建立在大量的词表之上，所以也是最容易结合的 形式。 基于理解的分词算法需要大量的语言知识和信息，只能是一种理想的方法， 第2 章自动分词算法与检索模型研究比较 在语法分析、语义分析乃至篇章理解还没有得到解决之前，这类算法模型的复杂 与不确定性，注定了将他们转换成可用的成熟模型时会遇到很大的挑战，所以目 前这类算法并没有很大的实际应用。 基于统计的分词算法是通过词频来对中文进行切分，他消除了对词典的依 赖，并具有结合上下文识别生词、自动消除歧义的优点，对于未登录词有很好的 识别效果，可以适应w e b 文档上语言的不断更新与发展要求。 而统计分词算法也有一定的局限性，由于它将频度作为分词的标准之一，因 此使用这种方法，很容易抽出一些出现频度高，但实际并不具备有效语义的字组， 如“之一”、“有的”、“许多”等) ，导致语言处理的识别精度差，时空开销 大。 表2 - 1 分词算法比较 t a b l e2 - ic o m p a r i s o no fw o r d ss e g m e n t a t i o n s 分词算法 优点缺点 基于串匹配分词算法1 ) 快速高效1 ) 缺乏自学习的智能性 2 ) 实现简单 2 ) 不能保证辞典完备性 3 ) 缺乏必要的灵活性 基于理解的分词算法1 ) 利用语法分类1 ) 占用资源较大 2 ) 准确率高2 ) 算法复杂 3 ) 多数算法仍在实验阶 段 基于统计分词算法1 ) 消除了对词典的依1 ) 会提取出高频无用词， 赖 影响识别精度 2 ) 可以根据上下文分 词，消除歧义 3 ) 解决未登录词问题 2 3 信息检索模型 信息检索系统要为用户提供快速方便的信息服务，就得要实现网页的本地索 引和检索，这就涉及到检索模型问题。信息检索模型是基于内容的检索的核心， 决定了信息组织的模式及信息查找的方式，根据搜索索引的方式不同，可将信息 检索模型分为：模糊逻辑模型、概率检索模型、向量空间检索模型、布尔逻辑检 索模型等。 2 3 1 模糊逻辑模型 模糊逻辑模型是以模糊数学作为理论基础，模糊逻辑善于表达界限不清晰的 北京工业大学工学硕士学位论文 定性知识与经验，它借助于隶属度函数概念，区分模糊集合，处理模糊关系。模 糊规则建立在用户对对象的认知基础之上，能够反映用户主观感知，由于具有相 似特征变化范围的不同对象可以适用于相同的规则咖。 设置单个的检索词w 在文档d 中的隶属度u ，u 在0 与l 之间，u 越大代表 w 和文档d 的相关性越高。用户给出查询要求，查询模块根据模糊逻辑运算给出 查询的结果，并能够按照相关度排序。 2 3 2 概率检索模型 在信息检索中存在不确定性问题，对查询本身来说，它不能唯一地表示信息 需求，对于结果来说，不能判定查询结果的正确与否，信息检索的主要任务就是 计算文档与查询之间的相关性。概率模型则考虑到了词条、文档间的内在联系， 利用词条闯和词条与文档问的概率相依性进行信息检索。1 。 概率检索模型是为了解决检索模型中的词的不确定性问题而发展的模型，具 有比较严格的数学理论基础，它是基于这样一种概率排队理论：如果文档按照与 查询的概率相关性的大小进行排序，那么排在前面的文档是最有可能被检索的文 档。 概率检索模型有多种形式，常见的为第二概率检索模型，首先设定标引词的 概率值，一般是对检索作业重复若干次，每一次检索用户对检出文档进行相关性 判断，再利用这种反馈信息，根据每个词在相关文档集合和无关文档集合的分布 情况来计算它们的相关概率，将词的权值m 设计为： m = l o g 而p ( i - p ) ( 2 2 ) 其中p 、p 分别表示某词在相关文档集和无关文档集中出现的概率，某一 文档的权值则是它所含的标引词权值之和，于是文档d 与用户查询q 相关概率可 定义为： 泓q ) = l o g ，p 州w ( 1 1 - ，i - p w w ) i ( 2 - 3 ) 其中p - 和p 分别为w 在相关文档和无关文档中的概率，式( 2 3 ) 中右边 和式是对所有出现在文档d 和查询q 中的词w 求和。 2 3 3 向量空间检索模型 向量空间模型( v s m ) 。”是由s a l t o n 等人在2 0 世纪6 0 年代提出的，是当前 第2 章自动分词算法与检索模型研究比较 使用较为广泛的一种检索模型。 ( 1 ) 文档表示向量空间检索模型将文档d i 和查询q j 都映射为n 维空间 ( t 1 ，t 2 ，t n ) 中的一个向量，假设d 是一个文档集合，文档d j 是文档集合 d 中的一个文档嘲。每个文档都被表示成： w i = ( w i l ，w i 2 ，w i n ) 以及 q j = ( q j l ，q j 2 ，q j n ) 其中w i k 和q j k 分别表示特征向量t k 在文档d j 和查询请求q j 中的权值( 或 称权重) ，它表示该特征词在该文档中或查询请求中的重要性。 对于文档的权值计算，最常用的是t f xi d f 表示法，t f xi d f 表示法嘲是 s a l t o n 和m c g i l l 针对向量空间信息检索范例提出来的，其中t f ( t e r m f r e q u e n c y ) 表示特征项在文档中出现的次数，称为词频( 或频度) ；i d f ( 1 n v e r s d o c u m e n tf r e q u e n c s ) 叫做倒排频度，是反映该特征项出现在不同文档中的频繁 程度的数值洲。根据t f xi d f 公式，文档集中包含某一词条的文档越多，说明它 区分文档类别属性的能力越低，其权值越小；另一方面，某一文档中某一词条出 现的频率越高，说明它区分文档内容属性的能力越强，其权值越大。 ( 2 ) 相似度计算在向量空间检索模型中，向量每一维的值就是该特征项 在文档中的权值，所有的文档和查询则分别映射成为n 维向量空间中的一个点， 相关度的计算也就演变成了两个向量之间的距离或向量的夹角计算，大大降低了 闯题的复杂性。通常两文档之间的相似度可以用其对应的向量之间的夹角余弦来 表示，即文档d 和文档d 。的相似度可以表示为： l 吃) 。q ( 谚) s i m ( 旃，d j ) = e o s o = 1 当一 ( 2 4 ) h 、7 ( 群( d ：f ) ) ( 研( 们) y k s lk - i 其中。表示文档的权值，它是由文档d 中某词t 。出现的频率t ( t 。，d ) 和这 个词在其他文档中的出现频率f ( t ，) 的乘积来表示，即： ft ( t i ，d ) f “1 ) ( 2 5 ) 公式( 2 - 5 ) 即词t 。在文档d 中的权值计算公式跚。 2 3 4 布尔逻辑检索模型 布尔逻辑检索模型是简单而常用的严格匹配检索模型，它是一个二元逻辑模 型，逻辑值为( o ，1 ) ，当某特征在文档中出现时，该特征所对应的变量的值就 为1 ( t r u e ) ，否则就是0 ( f a l s e ) 。模型中的文档要么与查询相关，要么与查询 北京工业大学工学硕士学位论文 无关，当布尔值为真时，文档就可以被检索出来，因此布尔检索模型的结果具有 二值性。 布尔逻辑检索是当令检索技术中最成熟的技术之一，也是构造检索表达式最 基本、简单的匹配模式，布尔逻辑检索是通过布尔逻辑算符来实现，这些算符能 把一些具有简单概念的关键词组配成为一个具有复杂概念的检索式，以达到扩大 检索范围或缩小检索范围及精确检索的目的踟。 在信息检索系统中，布尔逻辑模型是使用得最频繁的模型。在布尔逻辑模型 中，一个文档通过一个关键词条的集合来表示，这些词条都来自一个词表，在查 询与文档匹配过程中，主要看该文档中的词条是否满足查询的条件。 2 4 各种检索模型的比较 前面一节对目前常见的检索模型进行了介绍，这些检索模型根据不同的问题 而提出，现对这些检索模型的优缺点进行比较： 模糊逻辑模型虽然能够实现检索结果排列，克服检索结果的无序性，但是它 在对查询词增加权重方面的设置比较困难，检索结果也不尽如人意，这给查询词 设置准确隶属度带来一定困难。 概率逻辑模型具有严格的数学理论基础，可以克服中文信息处理中的不确定 性，可以运用理论模型和相关反馈原理