（信号与信息处理专业论文）文本检索中若干问题研究.pdf

摘要 摘要 信息检索技术就是从信息的集合中识别和获取信息的技术，这种技术对人们 的日常学习和科研有着至关重要的意义，尤其在互联网广泛应用的今天，电子信 息日益丰富，如何有效的从大量的信息资源中提取用户所关心的内容，已经成为 信息检索技术中非常重要的一个方面。本文研究的主要内容涉及文本检索中的中 文分词、小波检索算法、查询优化等相关技术。 1 中文分词 由于英文的组成单位是单词，所以英文在检索层面具有天然的优势；而中文 的组成单位则是字，所以中文在检索时候则需要解决分词问题。本文对目前国内 外对中文分词的研究算法进行分析，提出了基于层次匹配的中文分词算法。 2 小波检索算法 空间向量模型仅仅考虑了词信号的频率，但是没有体现出词信号的位置信 息；而临近检索法则与之相反。本文结合二者的优点，提出了基于离散小波变换 的检索模型，它充分结合了二者的优点，既能体现出多个检索词之间的关系，又 能在词信号中显示出检索词的频率，避免交叉比较，提高了检索速度与精度。 3 查询优化 有时候，直接对查询词进行检索并不能取得很好的检索效果，因为检索词可 能查找不到，但是查询词可能具有同义词或者上义词，它们却满足用户的需求。 所以本文对基于语义的查询给出一种解决办法，从w o r d n e t 词典中求得查询词 的同义词及上义词，然后在文档中进行检索，返回更多与用户查询相关的结果。 关键词：文本检索，小波变换，词信号，查询优化 广东工业大学硕士学位论文 a bs t r a c t i n f o r m a t i o nr e t r i e v a lt e c h n o l o g ya i m sa tr e c o g n i z i n ga n da c q u i r i n gi n f o r m a t i o n f o r mt h es e to fi n f o r m a t i o na n dp l a y sa ni m p o r t a n tr o l ei no u rs t u d ya n ds c i e n t i f i c r e s e a r c h e s p e c i a l l yi nt o d a y , t h ei n t e m e ti sw i d e l ya p p l i e dm o r ea n dm o r ew i d e l ya n d e l e c t r o n i ci n f o r m a t i o n s oh o wt oc o l l e c tt h eu s e f u lc o n t e x to ft h eu s e r s w a n ti s b e c o m i n gam o r ea n dm o r ei m p o r t a n tp a r ti ni n f o r m a t i o nr e t r i e v a l t h er e s e a r c ho f t h et h e s i si n v o l v e si nr e l a t e dt e c h n o l o g i e so nc h i n e s ep a r t i c i p l e ，w a v e l e tr e t r i e v a l a l g o r i t h m , a n dq u e r yo p t i m i z a t i o na n d s oo n 1 c h i n e s ep a r t i c i p l e b e c a u s et h ef o u n d a t i o n a le l e m e n to f e n g l i s hi sw o r d ，s oi th a sm o r ea d v a n t a g ei n i n f o r m a t i o nr e t r i e v a lt h a nc h i n e s e a n dc h i n e s ei sc o n s i s t e do fc h i n e s ec h a r a c t e r , s o w es h o u l ds o l v et h ep a r t i c i p l ep r o b l e m t h i st h e s i sa n a l y s e ss o m em a i np a r t i c i p l e a l g o r i t h m sa l lo v e rt h ew o r l d ，a n dp u t sf o r w a r dt h ea l g o r i t h mo fa r r a n g e m e n tf i a m e m a t c h i n g 2 t h ew a v e l e tr e t r i e v a la l g o r i t h m i nt h i sp a p e r , w ep u tf o r w a r da na l g o r i t h mb a s e do nw a v e l e tt r a n s f o r mw h i c h i n t e g r a t e st h ea d v a n t a g e so fp r o x i m i t ym e t h o d sa n dv e c t o rs p a c er e t r i e v a lm e t h o d s n o to n l yc a ni ts h o wt h e 丘e q u e n c yo ft h et e r ms i g n a l ，b u ta l s os h o wt h er e l a t i o n s h i p o ft h er e t r i e v a lw o r d s p o s i t i o n , a n di m p r o v er e t r i e v a le f f i c i e n c y 3 q u e r yo p t i m i z a t i o n s o m e t i m e sw ec a n t g a i ne f f e c t i v er e t r i e v a lr e s u l tb yq u e r yw o r d sw i t h o u t t r a n s f o r m , f o rt h e m s e l v e sc a n tb es e a r c h e di nt h ed o c u m e n t s ，b u tt h e r ea r es o m e s y n o n y m o u sw o r d so rh y p e r - w o r d so ft h e mc a nm e e to u rd e m a n d s ow ep u tf o r w a r d am e t h o dw h i c hc a ng e ti n t e r r e l a t e d s y n o n y m o u sw o r d sa n dh y p e r - w o r d sf r o m w r o r d n e ta n dr e t u r nm o r ec o r r e l a t i v er e s u l t s k e yw o r d s ：t e x tr e t r i e v a l ，w a v e l e tt r a n s f o r m , t e r ms i g n a l ，q u e r yo p t i m i z a t i o n 独创性声明 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的是我个人在导师 的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注 和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不包含本 人或其他用途使用过的成果。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有。 5 2 篡鬟戮 论文作者签字f 赫妇， 忧瞻6 月厶自 第一章绪论 1 1 选题的意义 第一章绪论 文本检索( t e x tr e t r i e v a l ) 与图像检索、声音检索、图片检索等都是信息检 索的一部分，是指根据文本内容，如关键字、语意等对文本集合进行检索、分类、 过滤等。 最早最典型的文本检索是图书馆的图书索引，根据书名、作者、出版社、出 版时间、书号等信息对馆藏图书进行索引，读者只需根据索引即可很快的查到所 需要的书存放在图书馆的什么地方。 随着计算机的出现，人们借助计算机可以更加方便的管理更多的文档，计算 机硬盘甚至可以装下全世界所有图书馆藏书。为了快速查找计算机所管理的文 档，出现了第一代文本检索技术，即根据关键字匹配，将包含关键字的文档挑出 来作为检索结果呈现给用户。 随着文档数量的增加，运用第一代文本检索技术已经很难检索出精确的检索 结果，于是根据文本内容的第二代文本检索技术应运而生。即根据系统对文本和 检索语句的理解，计算文本和检索语句的相似度，根据相似度对检索结果排序， 将相似度最高的检索结果呈现给用户。 随着互联网的出现和发展，文本文献在互联网上的数量发展更加迅猛，文本 的数量级和文本的结构都发生了变化：文本数量大幅度增长、互联网上的文本成 为半结构化的。这给文本检索技术提出了更大的挑战和机遇。于是在基于相似度 的检索技术基础上，出现了结合文本结构信息( 如文本的网络地址、大小写、文 本在页面中所处的位置、所指向的其他文本、指向自己的其他文本等) 对检索结 果集进行再排序的第三代文本检索技术，g o o g l e 就是最经典的例子。 现代的文本检索技术逐渐向语意理解、特定领域等方向发展。全世界科学家 都在不遗余力的建设“本体库”，如w o r d n e t 、h o w n e t 等本体字典【l 】。通过本体 库将文本转化为语意集合，从提炼文本的语意，以提供语意层次的检索。此外， 对于生物、医学、法律、新闻、以及新出现的b l o g 等领域，都出现了转门针对 单个领域的检索技术，并且得到了迅猛发展。文本检索领域的著名国际学术会议 广东工业大学硕士学位论文 有s i g i r 、w w w 、t r e c 等。 由于庞大的知识结构，所以使用信息检索的意义日益重大： 一、避免重复研究或走弯路 我们知道，科学技术的发展具有连续性和继承性，闭门造车只会重复别人的 劳动或者走弯路。比如，我国某研究所用了约十年时间研制成功“以镁代银 新 工艺，满怀信心地去申请专利，可是美国某公司早在2 0 世纪2 0 年代末就已经获 得了这项工艺的专利，而该专利的说明书就收藏在当地的科技信息所口1 。科学研 究最忌讳重复，因为这是不必要的浪费。在研究工作中，任何一个课题从选题、 试验直到出成果，每一个环节都离不开信息。研究人员在选题开始就必须进行信 息检索，了解别人在该项目上已经做了哪些工作，哪些工作目前正在做，谁在做， 进展情况如何等。这样，用户就可以在他人研究的基础上进行再创造，从而避免 重复研究，少走或不走弯路。 二、节省研究人员的时间 科学技术的迅猛发展加速了信息的增长，加重了信息用户搜集信息的负担。 许多研究人员在承接某个课题之后，也意识到应该查找资料，但是他们以为整天 泡在图书馆“普查 一次信息就是信息检索，结果浪费了许多时间，而有价值的 信息没有查到几篇，查全率非常低。信息检索是研究工作的基础和必要环节，成 功的信息检索无疑会节省研究人员的大量时间，使其能用更多的时间和精力进行 科学研究。 三、是获取新知识的捷径 在改革开放的今天，传统教育培养的知识型人才已满足不了改革环境下市场 经济的需求，新形势要求培养的是能力型和创造型人才，具备这些能力的人才首 先需要具备自学能力和独立的研究能力。大学生在校期间，已经掌握了一定的基 础知识和专业知识。但是，“授之以鱼 只能让其享用一时。如果掌握了信息检 索的方法便可以无师自通，找到一条吸收和利用大量新知识的捷径，把大家引导 到更广阔的知识领域中去，对未知世界进行探索。是谓“授之以渔”，才能终身受 用无穷。 德国柏林图书馆门前有这样一段话：“这里是知识的宝库，你若掌握了它的 钥匙，这里的全部知识都是属于你的。 这里所说的“钥匙”即是指信息检索的 2 第一章绪论 方法。 1 2 信息检索研究现状 1 2 1 信息检索过程 为了使读者对信息检索研究的进展有更深的了解，这里我们简单介绍一下信 息检索技术的基本原理。信息检索系统流程大致图l l 所示： 图l 一1 信息检索系统流程图 f i g 1 1f l o wc h a r to fi n f o r m a t i o nr e t r i e v a ls y s t e m 总体上，信息检索系统流程大致可分为四个部分：( 1 ) 数据预处理， ( 2 ) 索引生成，( 3 ) 查询处理，( 4 ) 检索部分。下面我们分别对各个部分采用的技 术加以介绍【2 】。 ( 一) 、数据预处理 目前检索系统的主要数据来源是w e b ，格式包括网页、w o r d 文档、p d f 文档 等，这些格式的数据除了正文内容之外，还有大量的标记信息，因此从多种格式 的数据中提取正文和其他所需的信息就成为数据预处理的主要任务。此外，众所 周知，中文字符存在多种编码，i ：l 女hg b 2 3 1 2 、b i g 5 、u n i c o d e ( c j k 区) ，而原 始数据集往往包含多种编码，因此要正确地检索到结果必须进行统一编码转换。 研究者们对预处理部分要提取哪些信息并没有共识，这与后续处理所需的信息密 切相关，一般来说，正文、锚文本和链接地址都是要提取出来的。 ( 二) 、索引生成 对原始数据建索引是为了快速定位查询词的位置，为了达到这个目的，索引 的结构非常关键。目前主流的方法是以词为单位构造倒排文档表，其结构大致如 卜0 1 所示【3 ，4 】： 3 广东t , _ i k 大学硕十学位论文 表1 1 倒排文档表 t a b l e 1 1d o c u m e n tt a b l ea r r a n g e m e n tb yc o n v e r s e ：w o r d i di r i v e r t e d li s t p o s 2i ip o s t n l d o c i d lt f l p o s l ：w o r d i di n v e r t e d li s t d o c i d 2t f l p o s lp o s 2i 1 ip o s t 也l ：w o r d i di n v e r t e d l i s t 每个文档都由一串词组成，而用户输入的查询条件通常是若干关键词，因此 如果预先记录这些词出现的位置，那么只要在索引文件中找到这些词，也就找到 了包含它们的文档。为了进一步提高查询的速度，在组织索引时还可以采用一些 更复杂的方法，比如b 树、t r i e 树、哈希表等。这个阶段还需要对预处理之后 的文档进行词法分析，这是因为很多语言的文本都不宜直接把正文中的字符串用 于建立索引。例如，中文里的词与词之间不存在分隔符，因此必须先进行分词， 而英文中的词存在很多变形，比如“c o m p u t e ”就存在“c o m p u t e s 、“c o m p u t i n g ”、 “c o m p u t e d 等多种变形，应先进行词根还原。此外，有些词虽然出现频率很高， 但对于查询没有任何帮助，比如“的 、“了”等，就无需放入索引，为此需要 预备一个停用词表( s t o pw o r dl i s t ) 对这类词进行过滤。 ( 三) 、查询处理 用户输入的查询条件可以有多种形式，包括关键词、布尔表达式、自然语言 形式的描述语句甚至是文本，但如果把这些输入仅当作关键词去检索，显然不能 准确把握用户的真实信息需求。很多系统采用查询扩展来克服这一问题。各种语 言中都会存在很多同义词，比如查“计算机”的时候，包含“电脑”的结果也应 一并返回，这种情况通常会采用查词典的方法解决。但完全基于词典所能提供的 信息有限，而且很多时候并不适宜简单地以同义词替换方法进行扩展，因此很多 研究者还采用相关反馈、关联矩阵等方法对查询条件进行深入挖掘。中文检索相 对英文等其它语种来说，如何正确分词对于检索效果有所影响，尤其是命名实体、 缩略语以及新词等未登录词的正确识别对于某些查询来说影响较大。现在的大部 分检索系统在索引以及查询分析阶段采用了命名体识别，从结果来看，取得了比 较好的效果。 ( 四) 、检索 4 第章绪论 最简单的检索系统只需要按照查询词之间的逻辑关系返回相应的文档就可 以了，但这种做法显然不能表达结果与查询之间的深层关系。为了把最符合用户 需求的结果显示在前面，还需要利用各种信息对结果进行重排序。目前有两大主 流技术用于分析结果和查询的相关性：链接分析和基于内容的计算。许多研究者 发现，w w w 上超链结构是个非常丰富和重要的资源，如果能够充分利用的话， 可以极大的提高检索结果的质量。基于这种链接分析的思想，s e r g e yb r i n 和l a r r y p a g e 在1 9 9 8 年提出了p a g e r a n k 【5 】算法，同年j k l e i n b e r g 提出了h i t s 算法，其 它一些学者也相继提出了另外的链接分析算法，如s a l s a ，p h i t s ，b a y e s i a n 等算法。这些算法有的已经在实际的系统中实现和使用，并且取得了良好的效果。 而基于内容的计算则沿用传统的文本分类方法，多采用向量空间模型、概率模型 等方法来逐一计算用户查询和结果的相似度( 相关性) 。两者各有优缺点，而且 恰好互补。链接分析充分利用了w e b 上丰富的链接结构信息，但它很少考虑网 页本身的内容，而直观上看，基于内容的计算则较为深入地揭示了查询和结果之 间的语义关系，但忽略了不同网页之间的指向关系。因此现在很多系统尝试把两 者结合起来以达到更好的性能。 1 2 2 信息检索现状 作为实用化的系统，搜索引擎一般采用比较成熟的技术，并对稳定性、反映 速度、界面等工程化问题更为关注。因此，这些系统并不完全代表信息检索技术 的发展水平。但由于人们对于各种粒度的信息获取的需求不断增长，国外的学术 界和企业界对为此投入了相当大的力量进行前瞻性研究，这方面比较有代表性的 机构包括马萨诸塞大学、卡耐基梅隆大学、伦敦城市大学、i b m 、微软研究院、 滑铁卢大学等。 总的来看，早期以o k a p i 、s m a r t 、查询扩展、相关反馈为代表的内容分析技 术，后来以p a g e r a n k 、h i t s 为代表的链接分析技术，以及近年来的语言模型， 都曾在信息检索发展过程中掀起研究热潮，但近年来却少有激动人心的新技术出 现。2 0 0 5 年，t r e c 在其总结报告指出现在“信息检索性能已进入平台期”。这 表明，用户无关的传统信息检索技术已相对成熟。这些技术已经被商用搜索引擎 广泛应用，并在一定程度上解决了用户在粗粒度( 文档级) 上的信息获取需求。 广东t 业大学硕十学位论文 从t r e c 来看，现在的任务设置向高精度、细粒度和大规模三个方向倾斜， 比较有代表性的有高精度文档检索任务( h a r d ) 、新信息检测任务( n o v e l t y ) 、 问答任务( q a ) 、t b 级检索( t e r a b y t e ) 等。其中前三个任务要求返回的结果 不再是简单的一篇篇文档，而是信息片断，而t b 级检索则是把测试集的规模提 高到了t b 级，其他不变。从评测结果来看，这些任务已经取得了很大进展。但 相对于目前的技术而言，这些任务还是相当困难的，与实用还有一段距离。 当前的中文检索技术均基于国际主流的算法，在评测中成绩较好的单位在 t r e c 评测中也曾取得不错的成绩。可以看出，这些算法提供了基准级的性能， 系统级的创新或改进不多，不过现有系统都会针对中文的特点进行改进。总体上， 如果用户草拟的查询条件能够比较全面准确地表达用户需求的话，现有的中文检 索技术一般能够提供比较好的检索结果，但是对于以下方面还存在着一些问题： 1 查询条件与文档词汇内容失配； 2 部分命名体，新词以及缩略语识别还存在着一些问题； 3 在计算相似度时，查询词汇权重的设定j 下确与否也在一定程度上影响检 索效果。 这些问题的存在导致现有检索系统性能下降，针对这些问题，现有的检索技 术还有很大的改善空间来获得比较满意的检索结果。 1 3 本文的创新点 1 基于层次匹配的中文分词算法 由于中文的特殊性，需要对其中的词语进行划分。但是中文分词常用的最大 匹配法的效率低下，不能有效的划分词语。所以我们基于词库优化，歧义包容建 立了基于层次匹配的中文分词方案。 2 使用基于小波变换的文本相似性比较方法 本文结合向量空间法与临近检索法 6 1 ，避免关键词之间的交叉比较，有效提 高了检索速度与精度。 3 使用基于语义的查询扩展方法 搭建w o r d n e t 词典作为检索环境，使用查询词的同义词及上义词进行检索。 提高了检索效果，更好的满足用户的检索意愿。 6 第二章巾文分词 2 1 中文文本的特点 第二章中文分词 词是最小的、能独立活动的、有意义的语言成分，也是汉语的基本单位。因 此，通常的检索都是以每一个独立的词为单位建立索引，在查询时按照检索词出 现的位置和频率对文档进行输出，分词解决的就是如何将文本流转换成单词或词 序列的问题。中文文本的分词不同于英文文本的分词，因为英文文本是小字符集 上的已充分分隔开的词串，各个单词之间已经用空格自然格开，因此英文分词只 需要考虑一些特殊情况下的分词，例如数字、连字符、标点符号以及字母的大小 写；而中文文本是大字符集上的连续字串，它具有不同于其它语种的特点： 1 汉语没有性别、数量的变化，中文词语本身不能显示与其它词的语法关 系，他们的形式也不受其它词的约束； 2 在汉语中，词序严格，不同的词序会产生不同的含义，例如“中华”和 “华中”、“人工 和“工人 就表示截然不同的意义。 3 在检索中通常认为虚词无助于表达文本信息，应当作为停用词过滤掉， 但是在中文文本中，虚词的介入也会产生不同的表达含义。例如“老师 和学生与“老师的学生”、“停车场内的车与“停车场外的车 所表 述的意义完全不同。 4 中文文本中字与字之间以及词与词没有明显的分割标记来问隔开，因此 中文的分词首先要考虑的是如何判断哪些相邻的字可以构成一个有意 义的词，也就是存在一个对汉语中的词加以识别的问题。 由于汉语的这些特点，决定了中文信息检索不能完全采用针对其他语言的信 息检索方法，必须首先解决原文进行切分词的问题。研究表明，如果不切分词， 也就是以字为单位进行检索，可能检索的结果与用户的查询要求会大相径庭，例 如当检索“北京大学”时，就会把“北京邮电大学”、“北京交通大学 、“北京工 业大学等检索出来，而检索“华人”时会把“中华人民共和国 检索出来，从 而给出不满足用户查询需求的检索结果。由此可见，对中文文本的原文进行切分 词，可以大大提高检索的准确率。同时，中文自动分词也已经成为众多中文信息 7 广东工业大学硕士学位论文 处理任务的一项基础研究课题，例如机器翻译、信息提取、文本分类、自动文摘、 语音识别、自然语言理解等等【7 8 】。 中国的汉字是示意文字，总数有几万个，在由国家标准总局颁布的信息交 换用汉字编码字符集一基本集( u pg b 2 3 1 2 - - 8 0 ) 咩 共收录了一级和二级常用汉 字共6 7 6 3 个，而在u n i c o d e 编码中更是收录多达2 0 9 0 2 个汉字。据统计，在常 用汉语中，9 0 以上使用的是二字词和三字词，也有使用四字词和五字词。知道 这些汉字的特点，对于我们选择合理的切分算法是有益的。 2 2 一般的分词技术 首先解释几个概念： 1 ) 、歧义词 在对中文文本切分时，对同一字符串的不同的切分可能会产生两种语法上都 正确的切分结果。例如，“发展中国家兔养殖业 可以切分成“发展中国家兔 养殖业”，也可以切分成“发展中国家兔养殖业 。 2 ) 、未登录词 也称为新颖词，是指词典中没有收录的词汇，随着互联网的进一步发展，不 断地有许多包括网络词汇在内的新词涌现，例如“非典 、“伊妹儿 、“美眉 等。 3 ) 、专有名词 这类词汇包括专业术语，例如“甲醛”、“最大似然法则 等等，也包括人名、 地名、组织或活动名称等，例如“孔子 、“刀郎 、“北京 、“n b a 全明星赛”、 “国际电信同盟i t u 等等。由于书面汉语是字的序列，词与词之间没有间隔标 记，使得词的界定往往模糊不清。即使这样，在过去的时间里，人们在汉语的自 动分词技术的研究上还是做了很多工作，设计了许多实用、高效的算法。根据是 否利用机器可读词典和统计信息，通常可以将中文文本自动分词的方法分为三大 类【9 】，以下将逐个进行介绍。 2 2 1 基于词典、词库的分词方法 自动分词是基于字符串匹配的原理进行的。所谓自动分词方法，指的 是汉字字符串匹配的进行方式。 8 第二章巾文分词 1 最大匹配法亦称m m 法【7 1 ，其基本思想是这样的，假设自动分词 词典( 或词库) 中的最长词条是i 个字，则取被处理材料当前字符串序列中 的前i 个字作为匹配字段，查找词典，若词典中存在这样的一个i 字词，则 匹配成功，匹配字段被作为一个词切分出来；如果在词典中找不到这样一 个i 字词，则匹配失败，匹配字段去掉最后一个字，剩下的字段重新进行匹 配，如此进行下去，直到匹配成功，也就是完成一轮匹配，切分出一个词 为止。 这种分词方法，在由北京航空学院等十多个单位协同进行的我国第一 次大规模现代汉语词频统计工作中，实现了我国第一个自动分词系统 c d w s 。 2 逆向最大匹配法亦称o m m 法，或r m m ，i m m 法；其基本原理和 m m 法相同，不同的是分词切分方向；它从被处理材料的木端开始匹配， 每次取最末端的i 个字作为匹配字段，匹配失败则去掉最前面的一个字。 o m m 法要求配置逆序分词词典。 3 逐词遍历匹配法它把词典中的词按照由长到短递减的顺序逐个搜 索匹配整个待处理材料，直到把所有的词都切分出来为止。 4 设立切分标志法这种方法首先要收集那些标点符号( 称为自然切 分标志) 以外的众多非自然切分标志，例如，只充当词首字或词尾字的字， 对这些非自然切分标志进行搜索，根据这些标志，把句子切分为若干较短 的字段，然后再使用m m 或者o m m 等方法进行进一步的切分。准确的说， 这种方法并不是一种真正意义上的分词方法，只不过是自动分词的一种前 处理方式而已。而且，这种前处理并没有提高分词精确度，却要额外消耗 时间扫描切分标志，增加分词的时间复杂度。 5 正向最佳匹配法和逆向最佳匹配法最佳匹配法的出发点，是在词 典中按词频的大小排列词条，以求缩短对分词词典的搜索时间，达到最佳 效果，从而降低分词的时间复杂度，以加快分词速度。实际上，这是对分 词词典预先进行的一种加工，也不是纯粹意义上的一种分词方法。 基于词典的分词方法的优点是这类方法实用、具体，比较容易实现且对于歧 义词的处理在词典完备的情况下可以很准确的解决 1 1 , 1 2 】，但是这种方法也存在自 9 广东t 业大学硕十学位论文 身的缺陷，匹配速度慢，机器可读词典的组织结构、匹配的原则和扫描顺序都会 极大的影响分词速度，并且基于词典或词库的机械切词，其准确率主要受限于词 典的规模。由于国内中文信息检索的起步较晚，目前仍然没有统一、标准的词库， 各研究单位也都是自行收集中文词语，组建自己的中文词库；同时由于中文词汇 数量巨大，有许多词的含义己经悄然发生了变化，例如“恐龙 、“青蛙 、“下课 等等，因此词典还必须不停地更新和扩充，这显然需要投入巨大的人力和物力。 此外，对于相同或相近专业和领域建立起动态词库，将由统计得到的词不断加入 词库中，可以实现对词典的动态维护。 2 2 2 基于统计信息的分词方法 基于统计的分词方法所使用的主要统计量包括：词频、互信息、神经网络模 型、隐马尔可夫模型和指数模型( 最大熵模型) 等。 一、基于词频统计量的分词方法也就是n g r a m 模型，其基本思想是将待切 分字符串中每紧紧相邻的n 个字作为一个词切分出来，然后进行出现频率的统 计，出现的次数越高，成为一个词的可能性也就越大。在频率超过某个预先设定 的阂值汐时，就将其作为一个词进行索引，这里n 是一个正整数，统计结果表明 汉语中二字词和三字词占了最大的比重【1 3 】，因此n 通常取2 或3 个词。 例如，待切分字符串为“广东工业大学信息工程学院 ， 2 元文法切分的结果是：广东东i i 业业大大学学信信息息i i 程程 学学院； 3 元文法切分的结果则是：广东工东工大工大学大学信信息工息工程工 程学程学院。 假设待切分字符串长为l ，则n 元文法可以切分出l n + 1 个词。显然，该 方法切分出来的词数量巨大，而且其中包含许多虚假词，但是这种方法一般不依 赖于词典，而且能够有效地提取出未登录词。 二、互信息是用来度量不同字符串之间相关程度的统计量。其定义如下：对 于字符串x 和y ，它们之间的互信息由公式( 1 1 ) 计算： m i ( x , y ) = l 0 9 2 篇 ( 1 1 ) l o 第二章中文分词 这里，p ( x ，”为字符串x 和y 共同出现的概率，p ) 和p ) 分别是字符串x 和y 出现的概率。 当字符串x 和y 之间互信息的大小超过某个事先设定的阈值时，判定符x ，y 构成一个词。 虽通过将基于词典的处理方法和基于频率的统计方法结合起来，但是词语的 切分速度并不那么令人满意，而且会切分出一些错误的词语，可能这些词语根本 就不存在，因此对这种算法的直接应用效果不太好。 2 2 一基于理解的分词方法 这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效 果。其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和 语义信息来处理歧义现象。它通常包括三个部分：分词子系统、句法语义 子系统、总控部分。在总控部分的协调下，分词子系统可以获得有关词、 句子等的句法和语义信息来对分词歧义进行判断，即它模拟了人对句子的 理解过程。这种分词方法需要使用大量的语言知识和信息。由于汉语语言 知识的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形式， 因此目前基于理解的分词系统还处在试验阶段。 到底哪种分词算法的准确度更高，目前并无定论。对于任何一个成熟 的分词系统来说，不可能单独依靠某一种算法来实现，都需要综合不同的 算法。笔者了解，海量科技的分词算法就采用“复方分词法，所谓复方， 相当于用中药中的复方概念，即用不同的药材综合起来去医治疾病，同样， 对于中文词的识别，需要多种算法来处理不同的问题。 2 3 基于词库的层次匹配算法 2 3 1 层次匹配算法构思 对于有歧义的词语我们要求在检索时候都能分出来，也就是此算法的一个 目标：歧义包容。 几年来关系数据库给我们的思维是，我们查找的是数据库中的某条记录，通 广东 ：业大学硕十学位论文 过表格与代数，我们总能找到这个词。但是正是关系数据的这种思维束缚着我们， 关系数据库让我们的数据结构及关联表达得清楚、简单，并使某些查询的效率变 得较高。但是这不适用于中文分词，这时候层次数据库模型也许更合适。 首先我们将关系数据库中的词按字分开，并存放到层次数据库中，如图2 1 所示： 百崮卣一 图2 1 字的层次存取 f i g 2 1c h i n e s es i n g l ec h a r a c t e r sh d a m 实线框中的字表示树上面的字串可以单独构成一个词，例如“文本 ，“文本 检索 它们本身可以在词库中找到。实线框中的字表示匹配结束符。而虚线框表 示树上面的字串无法单独成词，例如“文本检就是不存在的词。 我们发现经过这样的设计之后，任何一个句子都会逐字去与树状结构中的单 字匹配，词的长度变成树的高度，每次匹配变成树的遍历，而且这种遍历是线性 的。 2 3 2 层次匹配算法设计 有了以上的中文词库之后，我们的算法设计也将水到渠成，下面来看下分词 的步骤： ( 1 ) 首先将要分的全文以标点符号为界分成一个一个的句子。作为预处理的 一个步骤，目的是让我们处理的句子短，效率更高，毕竟中间有标点符号的词是 1 2 第二章巾文分词 不存在的。 ( 2 ) 我们开始将要处理的句子在树状结构中遍历，如果找到匹配就继续，如 果遇到实线框就终止，此时得到的词已经是一个完整的词了，这样我们就可以把 这个词作为一个一个的分词了。 ( 3 ) 从分词后的下一字开始继续重复步骤2 ，如此循环即可完成分词。 可以看到，我们的字符匹配效率几乎是线性的，我们所要做的只是取出每一 个字去与树上的字进行相应的匹配，每次的匹配代价都是o ( 1 ) ( 如果词库用h a s h 表的话) ，这样匹配下来的时间复杂度就是字符串本身的长度。对于一个长度为 n 的字符串来说，它的分词复杂度是o ( n ) 。而最大匹配的平均复杂度是o ( n 2 ) 。 这里我们没有考虑歧义包容与分支处理的情况，但是即使加上这些复杂度仍然是 有限的。 2 3 3 层次匹配算法的实现细节 细节一、词库的保存格式。现在最常用的保存数据的方式当然是关系数据库， 其次是文件系统中的二进制文件。显然关系数据库对于我们并不适用，而自定义 的二进制文件则实现起来比较困难，而且读写效率也会出现问题。因为我们是用 j a 、，a 实现这个功能，而且其对文本文件的读取速度非常高，所以我们把整个内 存中的树状结构直接序列化成磁盘的文本文件是很方便的。 细节二、问题是树的父子节点为的导航。我们的树并不是颗二叉树，根结 点的子节点会有很多。尤其是第一层，我们会把词库中的所有的首字都取出来作 为根节点的子节点，这意味着如果首字有4 0 0 0 个的话，根节点就有4 0 0 0 个子树。 当然随着层数的增多，节点的子树个数也会减少，毕竟以“文本 开头的词在整 个词库中也就几十个，但是如果设计的不合理，我们要检索出文本检索可能要遍 历所有的子节点。最坏的查找算法是o ( n ) ( n 代表子节点个数) 。当然如果我们 建词库时将子节点有序排列，再按照二分法查找，则我们的复杂度会降到o ( 1 9 n ) ， 这样的复杂度已经可以接受了。但是使用h a s h m a p 将会比二分法查询简单的多， 因为在h a s h m a p 里查找东西时几乎是线性的。当然用h a s h m a p 要付出存储空间 变大的代价，而存储问题在今天已经不是个大问题。 细节三、问题是找到有终结符的字后，我们必须将它建成一个完整的词。这 广东丁业大学硕十学位论文 里我们要逐字往上回溯，直到要结点。因此我们在每个节点里都保存了父节点的 指针。 2 3 4 层次匹配算法实验 选择一篇2 0 0 0 字的文章，然后根据两种算法编写的分词器对它进行处理， 中文分词实验结果( 基于l u c e n e 里的s t a n d a r d a n a l y z e r 分词) 如表2 1 所示： 表2 1 实验结果比较 t a b 2 - 1t h ec o m p a r eo f e x p e r i m e n t a lr e s u l t s a n a l y z e r 分词算法耗时 s t a n d a r d a n a l y z e r将文章中的字分成一个 8 0 r n s 一个的单字 c h i n e s e a n a l y z e r层次匹配分词算法 6 3 m s 我没有找到最人匹配法分词可用的开源代码，因此只能用s t a n d a r d a n a l y z e r 与之比较。l u c e n e a n a l y z e r 算法事实上根本没有去查词库的，因此也不会按任何 语义去分词，只是简单地将文章的中文字分成一个一个的单字。实验结果确实让 人惊讶，当词库p r e l o a d 以后，我们的分词速度竟然远超不需要查任何词库的 s t a n d a r d a n a l y z e r 算法。 而后，我们对分割出的词建立索引，实验结果如表2 2 所示： 表2 2 索引生成 t a b 2 2i n d e xg e n e r a t i o n a n a l y z e r分词算法耗时 s t a n d a r d a n a l y z e r将文章中的字分成3 6 分钟 一个一个的单字 c h i n e s e a n a l y z e r层次匹配算法分出 3 0 分钟 的词 由于建索引时数据库的查询操作会耗费很多的时间，因此两者的差别不是太 明显，但结果至少说明了我们的分词效率确实是很高。 1 4 第二章巾文分词 2 4 分词中的难题 有了成熟的分词算法，是否就能容易的解决中文分词的问题呢? 事实远非如 此。中文是一种十分复杂的语言，让计算机理解中文语言更是困难。在中文分词 过程中，有两大难题一直没有完全突破。 1 、歧义识别 歧义是指同样的一句话，可能有两种或者更多的切分方法。例如：表面的， 因为“表面 和“面的”都是词，那么这个短语就可以分成“表面的”和“表面 的”。这种称为交叉歧义。像这种交叉歧义十分常见，前面举的“和服”的例子， 其实就是因为交叉歧义引起的错误。“化妆和服装可以分成“化妆和服装 或者“化妆和服装”。由于没有人的知识去理解，计算机很难知道到底哪个方 案正确。 交叉歧义相对组合歧义来说是还算比较容易处理，组合歧义就必需根据整个 句子来判断了。例如，在句子“这个门把手坏了 中，“把手是个词，但在句 子“请把手拿开 中，“把手”就不是一个词；在句子“将军任命了一名中将 中，“中将 是个词，但在句子“产量三年中将增长两倍 中，“中将 就不再 是词。这些词计算机又如何去识别? 如果交叉歧义和组合歧义计算机都能解决的话，在歧义中还有一个难题，是 真歧义。真歧义意思是给出一句话，由人去判断也不知道哪个应该是词，哪个应 该不是词。例如：“乒乓球拍卖完了，可以切分成“乒乓球拍卖完了”、 也可切分成“乒乓球拍卖完了 ，如果没有上下文其他的句子，恐怕谁也不知 道“拍卖”在这里算不算一个词。 2 、新词识别 新词，专业术语称为未登录词。也就是那些在字典中都没有收录过，但又确 实能称为词的那些词。最典型的是人名，人可以很容易理解句子“王军虎去广州 了”中，“王军虎 是个词，因为是一个人的名字，但要是让计算机去识别就困 难了。如果把“王军虎”做为一个词收录到字典中去，全世界有那么多名字，而且 每时每刻都有新增的人名，收录这些人名本身就是一项巨大的工程。即使这项工 作可以完成，还是会存在问题，例如：在句子“王军虎头虎脑的 中，“王军虎 还能不能算词? 广东工业大学硕士学位论文 新词中除了人名以外，还有机构名、地名、产品名、商标名、简称、省略语 等都是很难处理的问题，而且这些又正好是人们经常使用的词，因此对于搜索引 擎来说，分词系统中的新词识别十分重要。目前新词识别准确率已经成为评价一 个分词系统好坏的重要标志之一。 2 4 中文分词的应用 目前在自然语言处理技术中，中文处理技术比西文处理技术要落后很大一段 距离，许多西文的处理方法中文不能直接采用，就是因为中文必需有分词这道工 序。中文分词是其他中文信息处理的基础，搜索引擎只是中文分词的一个应用。 其他的比如机器翻译( m t ) 、语音合成、自动分类、自动摘要、自动校对等等， 都需要用到分词。因为中文需要分词，可能会影响一些研究，但同时也为一些企 业带来机会，因为国外的计算机处理技术要想进入中国市场，首先也是要解决中 文分词问题。在中文研究方面，相比外国人来说，中国人有十分明显的优势。 分词准确性对搜索引擎来说十分重要，但如果分词速度太慢，即使准确性再 高，对于搜索引擎来说也是不可用的，因为搜索引擎需要处理数以亿计的网页， 如果分词耗用的时间过长，会严重影响搜索引擎内容更新的速度。因此对于搜索 引擎来说，分词的准确性和速度，二者都需要达到很高的要求。目前研究中文分 词的大多是科研院校，清华、北大、哈工大、中科院、北京语言学院、东北大学、 i b m 研究院、微软中国研究院等都有自己的研究队伍，而真正专业研究中文分 词的商业公司除了海量科技以外，几乎没有了。科研院校研究的技术，大部分不 能很快产品化，而一个专业公司的力量毕竟有限，看来中文分词技术要想更好的 服务于更多的产品，还有很长一段路。 1 6 第二章常见的柃索模型 第三章常见的检索模型 文本信息检索是一个文本与用户提问比较的过程。目前，主要有三种模型用 来描述这一过程，即布尔检索模型、概率推理模型、空间向量模型。 3 1 检索模型的确立 文本信息检索中主要处理的问题有： 1 如何表示文本? 2 检索单元怎样确立和组织? 3 怎样将文本表示成文本描述符? 4 怎样表示用户需求? 5 如何通过用户需求获得文本? 6 如何比较各文本，并判断每个文本与用户需求之间的匹配程度? 7 如何评价整个匹配过程所得的结果? 由此可见，文本信息模型主要包括以下三个要素： 1 文本集 早期文本信息检索基本局限于目录或摘要等二次文献，它们的建立一般都采 用传统的人工赋词标引方法。这种标引方法需要由标引人员手工对各种信息进行 加工处理，给出检索标识。计算机根据这些标引词建立索引，用传统的数据库技 术实现管理和检索。因此，标引的工作量大，标引质量因人而异，带有很大的局 限性。随着大量且不断变化的各类信息的出现以及相关技术和硬件设备的发展， 人们对全文检索系统的需求越来越大，对检索的要求也越来越高。全文检索不同 于早期的检索系统，它是将全文本信息作为检索对象，建立文本集，利用计算机 抽取标识符，建立索引，再用全文检索技术实现检索。 2 用户提问 用户提交问题给检