基于Lucene的中文自然语言搜索引擎


上海交通大学 硕士学位论文 基于Lucene的中文自然语言搜索引擎 姓名:胡长春 申请学位级别:硕士 专业:通信与信息系统 指导教师:刘功申 20090101 上海交通大学硕士学位论文 摘要 I 基于 Lucene 的中文自然语言搜索引擎 摘 要 Internet 技术的飞速发展,信息的发布与共享超越了时空的限制,人 类进入一个前所未有的“信息爆炸”时代。互联网信息的极速膨胀提供 给用户海量的信息资源的同时,也带来了寻找信息的困难。如果没有一 个强有力的工具来帮助人们寻找、发掘有用的信息,人们就会被湮没在 信息的海洋中,迷失方向。搜索引擎正是为了解决网络“信息迷航”问 题而诞生的技术。它以一定的策略在因特网中搜集、发现信息,对信息 进行理解、提取、组织和处理,并为用户提供检索服务。它成为连接用 户和互联网的最佳纽带,起到网络信息导航的作用。然而由于搜索引擎 技术涉及数据库管理、信息检索、人工智能、自然语言处理、机器学习 等诸多学科,各商业公司都不愿意将自己的搜索技术公布于众,这使得 搜索引擎的应用,受到了某种程度的限制。然而,开源工具 Lucene 的出 现,使得搜索引擎开发者可以简单、快捷、并且有针对性地实现相当强 大的搜索功能。 首先,本文针对 Lucene 中的中文分析器不符合汉语的习惯,造成检 索查全率、查准率以及检索性能不够理想,实现基于标准中文词库和前 向最大匹配算法的中文分析器。实验证明:该分析器的分词结果更符合 汉语的习惯,并且在检索速度方面性能提升了 2-4 倍,在检索召回率方 面性能提升了 59%。 其次,本文对用户查询接口进行改进,实现基于自然语言理解的查 询接口。对用户提交的以自然语言表述的问题进行分词处理,去除相关 辅助词,最后提取出核心词进行查询。为更准确对用户提交的自然语言 进行分词,本文采用两种相结合的双向扫描的方法,再利用利用词句切 上海交通大学硕士学位论文 摘要 II 分概率对歧义字段进行处理。 另外,本文通过对网页相关度、PageRank 算法[1]Lucene 评分系统进 行研究,提出将 PageRank 算法引入 Lucene 评分系统,让系统能够将更 重要的网页更好的返回给用户。同时利用 simhash 算法[2]来计算返回页面 之间的相似度,检测过滤相似网页。并且通过对排序算法的研究,改进 原有快速排序。 最后,完成自然语言搜索引擎原型系统的设计和实现。原型系统对 上海交通大学网络资源进行整合。试验证明,改原型系统具有较好的性 能和实用性,为后续相关的研究工作提供了良好的平台。 关键词: Lucene,搜索引擎,索引,检索,分词 上海交通大学硕士学位论文 ABSTRACT III CHINESE NATURAL LANGUAGE SEARCH ENGINE BASED ON LUCENE ABSTRACT With rapid development of Internet technology, information sharing and releasing, humanity has entered an unprecedented "information explosion" of the times. The expansion Internet information, provided us mass of information resources, but also brought us difficulties to find information. If we do not have a powerful tool to help us find and discover useful information, we will be lost in the ocean of information. Search engine is a technology to address such problem. It's a technology in the collection and found information, understanding of the information, extraction, processing and organizations, and to provide users with search services. It the best tool to bring Internet to us, and play a role as navigation. However, the search engine technology related to database management, information retrieval, artificial intelligence, natural language processing, machine learning and many other disciplines, commercial companies are not willing to share their own search technology with the public, which block the development of search engine applications. However, with open source tool Lucene, search engine developers can make a very powerful search engine simply, fast, and in a targeted manner. First of all, the word segmentation algorithm of most Chinese analyzers for the Lucene search engine does not meet the Chinese habit. In order to overcome such deficiency, this paper has proposed a new Chinese analyzer based on the maximal match algorithm and a standard dictionary. From the experimental results, the proposed word segmentation algorithm of our 上海交通大学硕士学位论文 ABSTRACT IV Chinese analyzer meets the Chinese habit. And its indexing performance is very close to that of the analyzers based on mechanical segmentation. In addition, the retrieval efficiency is greatly improved by 2-4 times and the rate of retrieval response is improved by 59%. Secondly, this paper has proposed a natural language query interface to meet user’s requirement. When user submits the query sentence, system will process word segmentation, remove the relevant auxiliary word, finally extracted the core words of query and then search the words. To improve the accuracy of word segmentation, this paper combines two word segmentation algorithm and using probability to deal with ambiguities. In addition, this article research into page relevance, PageRank algorithm, Lucene scoring system and conducting the PageRank algorithm into Lucene scoring system, so that the system be able to return more important pages to the user. And this paper proposes simhash algorithm to filter the similar pages. Besides this paper improve the quick sort algorithm to make it stable and faster. Finally, this paper implements a prototype system of Chinese natural language search engine. Prototype system integrates the network resource of Shanghai Jiaotong University. Experiment proved that the prototype system is with good performance and practicality, and providing a good platform for farther research. Key words: Lucene, search engine index, retrieval, word segmentation 上海交通大学 学位论文原创性声明 本人郑重声明:所呈交的学位论文,是本人在导师的指导下,独立 进行研究工作所取得的成果。除文中已经注明引用的内容外,本论文不 包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究 做出重要贡献的个人和集体,均已在文中以明确方式标明。本人完全意 识到本声明的法律结果由本人承担。 学位论文作者签名:胡长春 日期: 2009 年 2月 2日 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定,同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版,允许 论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的全部或 部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制 手段保存和汇编本学位论文。 保密□,在 年解密后适用本授权书。 本学位论文属于 不保密√。 (请在以上方框内打“√”) 学位论文作者签名:胡长春 指导教师签名:刘功申 日期: 2009 年 2月 2日 日期: 2009 年 2月 2日 上海交通大学硕士学位论文 引言 1 第一章 引言 1.1 研究背景 Internet 技术的飞速发展,信息的发布与共享超越了时空的限制,人类进入一个 前所未有的“信息爆炸”时代。“2007 年中国互联网络信息资源数量调查报告”表明: 自从 20 世纪 90 年代中期开始,互联网在我国迅猛发展,网上中文信息资源快速增 长,截止 2007 年 12 月 31 日,全国在线数据库达到 82929 个,共 15709 万个网页, 2744G 数据量。互联网信息的极速膨胀提供给用户海量的信息资源的同时,也带来 了寻找信息的困难。浩瀚纷繁的信息海洋中,一方面由于面对过多的信息无从选择 和消化;另一方面是信息迷失,难于找到真正所需的信息,人们陷入了进退两难的 尴尬境地。“我们淹没在信息中,但是却渴求着知识”。 网络信息多元性、复杂性、冗余性、以及快速的更新速度,对信息检索技术的 研究和发展提出新的挑战。面对这如海潮般涌来的五光十色、瞬息万变的信息,人 们正以从来没有过的迫切心情,要求能借助于某些工具,自动筛选这些信息,并自 动剥除附加在这些信息上的泡沫、硬壳、无用的包装等,直接获取到情报和知识。 如果没有一个强有力的工具来帮助人们寻找、发掘有用的信息,人们就会被湮没在 信息的海洋中,迷失方向。 搜索引擎正是为了解决网络“信息迷航”问题而诞生的技术。它以一定的策略 在因特网中搜集、发现信息,对信息进行理解、提取、组织和处理,并为用户提供 检索服务。 它成为连接用户和互联网的最佳纽带,起到网络信息导航的作用。 因为搜索引擎技术涉及数据库管理、信息检索、人工智能、自然语言处理、机 器学习等诸多学科,各商业公司都不愿意将自己的搜索技术公布于众,这使得搜索 引擎的应用,受到了某种程度的限制。而 Lucene 的出现,使得搜索引擎开发者可以 简单、快捷、并且有针对性地实现相当强大的搜索功能,因此,受到了越来越多的 关注,得到了越来越广泛的使用。 1.2 搜索引擎技术的现状 总的来看,早期以 Okapi、Smart、查询扩展、相关反馈为代表的内容分析技术, 后来以 PageRank 、HITS 为代表的链接分析技术,以及近年来的语言模型,都曾在 信息检索发展过程中掀起研究热潮,但近年来却少有激动人心的新技术出现。2005 上海交通大学硕士学位论文 引言 2 年,文本检索会议在其总结报告指出现在“信息检索性能已进入平台期”。这表明, 用户无关的传统信息检索技术已相对成熟。这些技术已经被商用搜索引擎广泛应用, 并在一定程度上解决了用户在粗粒度(文档级)上的信息获取需求[3]。根据采用的信 息搜集方法和服务提供方式的不同,当前主流的搜索引擎可分为如下四种类型: ¾ 全文搜索引擎 全文搜索引擎利用网页自动搜集器(Robot 或 Spider)周期性搜索互联网,收集 尽可能多的 Web 网页,提交给自动索引系统。索引系统处理网页文档,建立基于相 应检索元的索引库。系统提供的访问接口接受用户检索。检索系统根据用户的检索 提问搜索索引库,寻找用户需要的网页。评价系统计算用户提问和网页之间的相关 性。结果页面生成系统将检索结果按相关度顺序组装成 HTML 页面,提交给用户。 这该类搜索引擎自动化程度高,维护费用少,信息量大、更新及时。但由于系统仅 对搜集到的信息做基于统计和语法层面的处理,缺乏语义层次的理解,致使检索结 果中无关信息过多[4]。这类搜索引擎的代表是:Google、AllTheWeb、AltaVista、Excite、 Lycos;国内代表为:百度、中搜等。 ¾ 目录式搜索引擎 目录式搜索引擎以人工或半自动方式搜集信息,建立网站目录数据库。编辑人 员通过访问网站,根据站点的内容和性质将网站归为预先设定的类别中。一些目录 式搜索引擎也接受用户提交的网站和描述,当目录的编辑人员认可该网站及描述后, 就会将之添加到合适的类别中。 该类搜索引擎信息较为准确,导航质量高,但需要大量的人工介入、维护量大、 信息量少、信息更新不及时。主要代表有:Yahoo、AOL、Open Directory 等。 ¾ 元搜索引擎 元搜索引擎也称为搜索引擎之上的搜索引擎。用户递交检索请求,元搜索引擎 负责转换处理后提交给多个预先选定的独立搜索引擎,并将所有查询结果集中起来 以整体统一的格式提供给用户[5]。 这类搜索引擎充分发挥各个独立搜索引擎不同的功能与优势,弥补独立搜索引 擎信息覆盖面上的局限性,一定程度上保证了搜索结果的权威性和可靠性。缺点是 不能够充分使用原搜索引擎的功能,用户需要做更多的筛选。主要代表包括: All4One、Monster Crawler 、ez2Find、等。 ¾ 点对点搜索引擎 点对点式搜索引擎构架在对等搜索(P2P)理念。P2P 计算模式引导网络计算模式 从集中式向分布式偏移,也就是说网络应用的核心从中央服务器向网络边缘的终端 上海交通大学硕士学位论文 引言 3 设备扩散,充分发掘网络中空闲的资源,包括磁盘空间、内存和网络带宽。搜索引 擎不通过中央服务器,不受信息文档格式和宿主设备的限制,对互联网络进行全方 位的搜索,其搜索深度和广度是传统搜索引擎所难以比拟的,理论上最终将网络中 所有开放的信息资源采集到,有更强的实时性和有效性。 这类搜索引擎将用户的搜索请求同时发给网络上另外的 PC,如果搜索请求未得 到满足,这些 PC 中的每一台都会把该搜索请求再转发给另外的 PC。这样,搜索范 围将在几秒钟内以几何级数增长,几分钟内就可搜遍几百万台 PC 上的信息资源。因 此可以利用这个速度以及搜索的深度来达到搜索的目的,找到需要的信息。 1.3 新一代搜索引擎技术的研发方向 随着互联网技术的进一步的发展,用户对搜索引擎性能的要求越来越高。世界 各国计算机工业界和学术界都对搜索引擎技术的研究投入的高度重视。许多科研人 员致力于新一代搜索引擎关键技术的研究。目前研究十分活跃,出现了很多值得注 意的动向。 ¾ 本地化搜索 当前大型搜索引擎都以英语为基础,完全按英语的思维方式和观点搜集和处理 信息资料。由于,各国的文化传统、思维方式和生活习惯不同,在对网站内容的搜 索要求上也就存在差异。新一代搜索引擎采用的技术愈来愈要求本土化,采用适合 于本土语言特点的搜索技术。 ¾ 个性化 个性化搜索机制能够有效地提高搜索引擎的检索质量。搜索引擎配备有效的学 习机制,分析用户的搜索行为,获取用户真正的需求,使得搜索结果更符合每个用 户的需求。 ¾ 智能化 搜索引擎实现基于语义层次的理解网络信息和用户的请求提问。系统能够对知 识理解和处理能力,并广泛运用分词技术、同义词技术、概念搜索、短语识别、机 器翻译和自然语言理解技术。 ¾ 更加关注检索准确度 网络信息是海量的,传统的搜索引擎总是返回成千上万的检索结果。用户在信 息查询时,不再关注返回结果的多少,而更加关注搜索引擎返回结果序列的合理性。 提高搜索结果的准确度,也就是说如何准确地计算网页与用户信息需求之间的相关 度,成为搜索引擎技术的研究热点。 上海交通大学硕士学位论文 引言 4 ¾ 定题式搜索引擎 定题式搜索引擎提供某一领域、某一大类主题的搜索功能,因此信息少(相对 于整个 Internet)而精(相对于某一特定主题)。采用定题搜索算法的 Robot 程序仅对 给定主题相关的网页文档进行搜集,搜索算法对页面的主题有一定的识别,尤其是 访问页面之前就能识别出这些页面是否和主题相关,决定是否采集他们或者制定页 面采集的优先顺序,节约了网络带宽,提高信息搜索的效率。 ¾ 分布式体系结构设计 搜索引擎可以采用集中式和分布式二种体系结构。这二种体系结构存在不同的 性能特点。当系统规模达到一定程度时,分布式体系结构的性能优势将特别明显。 搜索引擎的各个关键部分都可以实现分布式。搜索器可以在多台机器上相互合作、 相互分工进行信息发现,以提高信息发现和更新速度。索引器可以将索引分布在不 同的机器上,以减小索引对机器的要求。检索器可以在不同的机器上进行文档的并 行检索,以提高检索的速度和性能。 ¾ 交叉语言检索的研究 交叉式语言信息检索是指用户使用母语提交查询,搜索引擎在多种语言的信息 索引库中进行信息检索,返回能够回答用户问题的所有语言的文档。返回检索结果 借助机器翻译用母语形式显示。 ¾ 信息检索和其它信息技术的结合 搜索引擎是一个综合性很强的领域,必然要使用信息技术其它领域的理论和技 术。例如分类(Categorization)、聚类(Clustering)、抽取(Extraction)、摘要 (Abstraction)、事件检测(Event Detection)等。相关技术的相互借鉴有助于提高搜 索引擎的使用性能。 1.4 本文研究的意义 第一,尽管国外主流的 Web 检索技术已比较成熟,无论从结果、性能还是稳定 性来看,都能提供令人满意的结果,并且已经在人们的日常信息获取中发挥作用, 但是国内的搜索引擎技术与国外还是存在相当大的距离。并且在国外 Web 检索技术 主要针对西方语言,由于中文的特点,使得这些 Web 检索技术在理解中文准确性方 面还是存在一些问题。对于中文搜索引擎的研究还存在巨大的空间。 第二,虽然现在的搜索引擎越来越能帮助用户找到需要的东西,而人们逐渐习 惯输入关键字来搜索内容,但是人们逐渐适应关键字搜索并不能说明基于关键字的 搜索是人们最终的搜索方式。显然,能够理解用户语言的搜索方式才能更满足用户 上海交通大学硕士学位论文 引言 5 的需要。与传统的目录查询、关键词查询相比,自然语言查询方式更加贴近人类的 生活习惯,使检索系统与用户的交流更加人性化。普通用户难以准确地使用复杂的 布尔逻辑表达式来表述自己的需求,而是更倾向于以日常生活中的自然语言进行检 索。目前国外基于自然语言的搜索引擎有 Ask Jeeves,Powerset。但是由于中文语义 的多样性和复杂性,目前还没有很好的支持中文的自然语言搜索引擎。 第三,由于搜索技术本地化、定制化以及个性化等的研究,都要建立在以后搜 索引擎平台和技术上。但是因为搜索引擎技术涉及数据库管理、信息检索、人工智 能、自然语言处理、机器学习等诸多学科,各商业公司都不愿意将自己的搜索技术 公布于众,这使得搜索引擎技术发展,受到了某种程度的限制。 因此研究基于开源项目的搜索引擎技术,并且在这些技术的基础上对搜索引擎 技术进一步的改进和研究都是现在研究的重要内容。 1.5 论文的研究内容以及论文安排 自然语言搜索引擎是新一代搜索引擎技术的重要研发方向。当前,许多研究人 员正着手进行相关的研究,但由于尚处于初步阶段,技术还远不够成熟。中文自然 语言搜索引擎所涉及的关键技术包括:中文分析器、自然语言理解、网页相关度定 序算法、网页重要性、相似网页检测等。我们围绕着这些关键技术进行深入研究。 本论文紧紧围绕着中文自然语言搜索引擎关键技术的研究展开。 论文的组织安排如下: 第一章介绍了本文的研究背景、搜索引擎的现状以及目前新一代搜索引擎的研 究方向。综述了中文自然语言搜索引擎研究的意义,最后阐述了本论文的主要研究 内容和章节安排。 第二章介绍了 Lucene 搜索引擎。 第三章分析了目前支持中文的 Lucene 分析器,并根据正向最大匹配切分算法实 现了自己的分析器。通过实验证明该分析器的分词结果更符合汉语的习惯,并且提 升了 Lucene 检索性能。 第四章介绍了自然语言的理论知识并提出使用基于规则的分析方法为基础,综 合基于语料库统计分析的方法来分析用户输入搜索语句。 第五章介绍了分析了文档相关度、PageRank 算法、相似网页检测、网页排序算 法。提出将 PageRank 算法应用于 Lucene 评分机制,应用相似网页检测技术过滤检 索结果。并对网页排序算法进行优化改进。 上海交通大学硕士学位论文 引言 6 第六章介绍中文自然搜索引擎原型系统的整体框架及实现。 第七章总结本文工作的内容和成绩,展望了本课题未来需要深入研究的内容。 上海交通大学硕士学位论文 全文检索引擎 Lucene 的分析研究 7 第二章 全文检索引擎 Lucene 的分析研究 Lucene 是 Apache 软件基金会 Jakarta 项目组的一个子项目,是一个开放源代码 的全文检索引擎工具包,它不是一个完整的全文检索引擎,而是一个全文检索引擎 的架构,提供了完整的查询引擎和索引引擎,部分文本分析引擎。Lucene 的目的是 为软件开发人员提供一个简单易用的工具包,以方便的在目标系统中实现全文检索 的功能,或者是以此为基础建立起完整的全文检索引擎。 作为一个开放源代码项目,Lucene 从问世之后,引发了开放源代码社区的巨大 反响,程序员们不仅使用它构建具体的全文检索应用,而且将之集成到各种系统软 件中去,以及构建 Web 应用,甚至某些商业软件也采用了 Lucene 作为其内部全文检 索子系统的核心。Apache 软件基金会的网站使用了 Lucene 作为全文检索的引擎,IBM 的开源软件 eclipse 的 2.1 版本中也采用了 Lucene 作为帮助子系统的全文索引引擎, 相应的 IBM 的商业软件 WebSphere 中也采用了 Lucene。Lucene 以其开放源代码的特 性、优异的索引结构、良好的系统架构获得了越来越多的应用[6]。 2.1 全文检索系统 全文检索是指计算机索引程序通过扫描文章中的每一个词,为每一个词建一个 索引,指明该词在文章中出现的次数和位置,当用户查询时,检索程序就根据事先 建立的索引进行查找,并将查找的结果反馈给用户的检索方式。这个过程类似于通 过字典中的检索字表查字的过程。 全文检索的方法主要分为按字检索和按词检索两种。按字检索是指对于文章中 的每一个字都建立索引,检索时将词分解为字的组合。对于各种不同的语言而言, 字有不同的含义,比如英文中字与词实际上是合一的,而中文中字与词有很大分别。 按词检索指对文章中的词,即语义单位建立索引,检索时按词检索,并且可以处理 同义项等。英文等西方文字由于按照空白切分词,因此实现上与按字处理类似,添 加同义处理也很容易。中文等亚洲文字则需要切分字词,以达到按词索引的目的[7]。 全文检索系统是按照全文检索理论建立起来的用于提供全文检索服务的软件系 统。一般来说,全文检索需要具备建立索引和提供查询的基本功能,此外现代的全 文检索系统还需要具有方便的用户接口、面向 Web 的开发接口、二次应用开发接口 等[8]。功能上,全文检索系统核心具有建立索引、处理查询返回结果集、增加索引、 上海交通大学硕士学位论文 全文检索引擎 Lucene 的分析研究 8 优化索引结构等功能,外围则由各种不同应用的功能组成。结构上,全文检索系统 核心具有索引引擎、查询引擎、文本分析引擎、对外接口等等,加上各种外围应用 系统等等共同构成了全文检索系统。图 2-1 展示了上述全文检索系统的结构与功能。 图 2-1 全文检索系统结构 Figure 2-1 Full-Text retrieve system structure 由图 2-1,我们得出结论:全文检索系统中最为关键的部分是全文检索引擎,各 种应用程序都需要建立在这个引擎之上。一个全文检索应用的优异程度,根本上由 全文检索引擎来决定。因此提升全文检索引擎的效率即是我们提升全文检索应用的 根本。 2.2 Lucene 系统结构分析 Lucene 作为一个优秀的全文检索引擎,其系统结构具有强烈的面向对象特征。 首先是定义了一个与平台无关的索引文件格式,其次将系统的核心组成部分设计为 抽象类,具体的平台实现部分设计为抽象类的实现,此外与具体平台相关的部分比 如文件存储也封装为类,经过层层的面向对象式的处理,最终达成了一个低耦合高 效率,容易二次开发的检索引擎系统。 以下将讨论 Lucene 系统的结构组织,并给出系统结构与源码组织图[9]: 上海交通大学硕士学位论文 全文检索引擎 Lucene 的分析研究 9 图 2-2 系统结构与源码组织结构图 Figure 2-2 Figure of system and source code structure 从图中我们清楚的看到,Lucene 的系统由基础结构封装、索引核心、对外接口 三大部分组成。其中直接操作索引文件的索引核心又是系统的重点。Lucene 的将所 有源码分为了 7 个模块,各个模块所属的系统部分也如图 2-2 所示。需要说明的是 org.apache.lucene.queryPaser 是作为 org.apache.lucene.search 的语言分析器而存在,不 被系统之外实际调用,因此这里没有当作对外接口看待,而是将之独立出来。 从面向对象的观点来考察,Lucene 应用了最基本的一条程序设计准则:引入额 外的抽象层以降低耦合性。首先,引入对索引文件的操作 org.apache.lucene.store 的 封装,然后将索引部分的实现建立在 org.apache.lucene.index 其之上,完成对索引核 心的抽象。在索引核心的基础上开始设计对外的接口 org.apache.lucene.search 与 org.apache.lucene.analysis。在每一个局部细节上,比如某些常用的数据结构与算法上, Lucene 也充分的应用了这一条准则。在高度的面向对象理论的支撑下,使得 Lucene 的实现容易理解,易于扩展。 Lucene 在系统结构上的另一个特点表现为其引入了传统的客户端服务器结构以 外的应用结构。Lucene 可以作为一个运行库被包含进入应用本身中去,而不是作为 一个单独的索引服务器存在。这自然和 Lucene 开放源代码的特征分不开,但是也体 现了 Lucene 在编写上的本来意图:提供一个全文索引引擎的架构,而不是实现。 上海交通大学硕士学位论文 全文检索引擎 Lucene 的分析研究 10 2.3 Lucene 数据流分析 理解 Lucene 系统结构的另一个方式是去探讨其数据流的走向,并以此认识清楚 Lucene 系统内部的调用时序。在此基础上,我们能够更加深入的理解 Lucene 的系统 结构组织,以方便以后在 Lucene 系统上的开发工作。这部分的分析,是深入 Lucene 系统的钥匙,也是进行重写的基础。 我们来看看在 Lucene 系统中的主要的数据流以及它们之间的关系图: 图 2-3 数据流图 Figure 2-3 Data flow diagram 图 2-3 很好说明了 Lucene 在内部的数据流组织情况,并且沿着数据流的方向我 们也可以对与 Lucene 内部的执行时序有一个清楚的了解。现在将图中的涉及到的流 的类型与各个逻辑对应系统的相关部分的关系说明一下。图中共存在 4 种数据流, 分别是文本流、Token 流、字节流和查询语句对象流。文本流表示了对于索引目标和 交互控制的抽象,即用文本流表示了将要索引的文件,用文本流向用户输出信息。 在实际的实现中,Lucene 中对文本流采用 UTF-8 作为编码,以达到适应多种语言文 字的处理的目的[10]。Token 流是 Lucene 内部所使用的概念,是对传统文字中的词的 上海交通大学硕士学位论文 全文检索引擎 Lucene 的分析研究 11 概念的抽象,也是 Lucene 在建立索引时直接处理的最小单位。简单的讲 Token 就是 一个词和所在域值的组合,后面在叙述文件格式时也将继续涉及到 Token,这里不详 细展开。字节流则是对文件抽象的直接操作的体现,通过固定长度的字节流的处理, 将文件操作解脱出来,也做到了与平台文件系统的无关性。查询语句对象流则是仅 仅在查询语句解析时用到的概念,它对查询语句抽象,通过类的继承结构反映查询 语句的结构,将之传送到查询逻辑来进行查询的操作。 2.4 Lucene 索引机制 为了实现快速检索,Lucene 采用的是反向索引(inverted index)机制[11],反向索 引是相对前向索引(forward index)而言的。在前向索引中,每个文档对应着一个该文 档所包含的词或者短语的列表;在反向索引中,文档中的每个词或者短语对应着一 个文档列表,该列表中的文档是所有包含这个词或者短语的文档。该列表还会包含 一些辅助信息,比如该词或者短语在文档中出现的次数以及出现的位置等,这些信 息会被用来对搜索结果进行排序。这种结构对于“哪些文档中包含单词 X”这样的 问题能够快速得到搜索结果。 2.4.1 Lucene 索引建立 Lucene 为文档建立索引的过程,对文档格式没有要求,只要能从这些文件中提 取出文本信息即可。以 HTML 文件为例,其索引建立过程是:(1)通过一个 HTML Parser 对 HTML 文档进行解析,过滤掉其中的 HTML Tag,提取出重要信息,比如 Title 等;(2)将这些信息传送给 Lucene Analyzer,Lucene Analyzer 把这些内容转换成 单独的索引项并提取出相关信息,存储到索引文件中。该过程如图 2-4 所示,不同的 富文本文件通过相应的解析器解析出文本信息通过 Lucene 分析器分析得到索引文 件。 上海交通大学硕士学位论文 全文检索引擎 Lucene 的分析研究 12 图 2-4 Lucene 的索引过程 Figure 2-4 Lucene indexing process 下面介绍索引过程中数据流逻辑。如图 2-5 所示的数据流图十分清楚的勾画出了 整个索引构建逻辑这部分的设计:通过层层嵌套的类结构,在构建时候即分步骤有 计划的生成了索引结构,将之存储到内存中的文件系统中,然后通过对内存中的文 件系统优化合并输出到实际的文件系统中。 图 2-5 索引构建部分的数据流逻辑 Figure 2-5 Data flow logic of constructing index HTML 文件 XML 文件 MS Word 文件 PDF 文件 TXT 文件 HTML 解析器 XML 解析器 MS Word 解析器 PDF 解析器 Lucene 分析器 Index 文件 上海交通大学硕士学位论文 全文检索引擎 Lucene 的分析研究 13 2.4.2 Lucene 索引文件结构 为了实现高效的索引和检索,就必须具有良好的索引文件结构。Lucene 的索引 文件包括概念结构和物理结构。 Lucene 的每个索引文件都由一个或者多个片段(segment)组成。每个片段都是一 个可以被独立检索的模块,包含一定数量的文档(document)。这里文档可以是一个 HTML 页面,一个 XML 文档,或一个 Word 文档等等。Lucene 的索引文件的概念结 构如图 2-5。每一个文档由若干的域(field)组成,每一个域由若干的项(term)组 成。项是最小的索引概念单位,它直接代表了一个字符串以及其在文件中的位置、 出现次数等信息[12]。域是一个关联的元组,由一个域名和一个域值组成,域名是一 个字符串,域值是一系列项,比如一个域名为“content”,对应的域值为页面正文的 所有索引项。文档是提取了某文件中的所有信息之后的结果,这些组成了段,或者 称为子索引。子索引可以组合为索引,也可以合并为一个新的包含了所有文档的子 索引[13]。 图 2-6 Lucene 索引文件概念结构 Figure 2-6 Lucene index file conceptual structure 从概念上映射到结构中,索引被处理为一个目录(文件夹),其中含有的所有文 件即为其内容,这些文件按照所属的段(segment)不同分组存放,同组的文件拥有相 同的文件名,不同的扩展名。此外还有三个文件,分别用来保存所有的段的记录、 保存已删除文件的记录和控制读写的同步,它们分别是 segments,deletable 和 lock 文件,都没有扩展名。每个段包含一组文件,它们的文件扩展名不同,但是文件名 均为记录在文件 segments 中段的名字。 上海交通大学硕士学位论文 全文检索引擎 Lucene 的分析研究 14 图 2-7Lucene 索引文件结构组成 Figure 2-7 Lucene index file structure 每个段的文件中,主要记录了两大类的信息:域集合与项集合。这两个集合中 所含有的文件在图 2-7 中均有表明。由于索引信息是静态存储的,域集合与项集合中 的文件组采用了类似的存储办法:一个小型的索引文件,运行时载入内存;一个对 应于索引文件的实际信息文件,可以按照索引中指示的偏移量随机访问。索引文件 与信息文件在记录的排列顺序上存在隐式的对应关系,即索引文件中按照“索引项 1、 索引项 2…”排列,则信息文件则也按照“信息项 1、信息项 2…”排列。比如在图 2-7 所示,segment1.fdx 与 segment1.fdt 之间,segment1.tii 与 segment1.tis、segment1.prx、 segment1.frq 之间,都存在这样的组织关系。域集合与项集合之间则通过域的在域记 录文件(比如 segment1.fnm)中所记录的域记录号保持对应关系,在图 2-7 中 segment1.fdx 与 segment1.tii 中就是通过这种方式保持联系。这样,域集合和项集合 不仅仅联系起来,而且其中的文件之间也相互联系起来。此外,标准化因子文件和 被删除文档文件则提供了一些程序内部的辅助设施(标准化因子用在评分排序机制 中,被删除文档是一种伪删除手段)。这样,整个段的索引信息就通过这些文档有机 的组成[14]。 以上所阐述的,就是 Lucene 所采用的索引文件结构。基本上而言,它是一个倒 排索引,但是 Lucene 在文件的安排上做了一些努力,比如使用索引/信息文件的方式, 从文件安排的形式上提高查找的效率。 2.5 小结 本文介绍了 Lucene 的系统结构特点、源代码结构,分析了 Lucene 数据流以及 上海交通大学硕士学位论文 全文检索引擎 Lucene 的分析研究 15 索引机制。Lucene 是一种可应用全文检索系统的工具包,而不是完整的搜索引擎系 统。但是 Lucene 提供了简易的借口,用户可以通过调用这些结构实现定制化的搜索 引擎系统。通过对 Lucene 数据流河索引机制的分析,可以看出 Lucene 采用了倒排 索引文件结构。倒排索引文件结构更利于搜索关键字。 上海交通大学硕士学位论文 Lucene中文分析器改进 16 第三章 Lucene 中文分析器改进 使用 Lucene 时,选择一个合适的分析器是非常关键的。对分析器的选择没有惟 一的标准。待分析语种是影响分析器选择的重要因素之一,因为每种语言都有其自 身的特点。影响分析器选择的另一个因素是被分析的文本所属的领域,不同的行业 有不同的术语、缩写词和缩略语,分析过程中这一点是非常重要的。 针对目前应用于搜索引擎 Lucene 的中文分析器的分词不符合汉语习惯的现状, 本文根据正向最大匹配切分算法和采用包括基本标准中文词语的词库,实现了自己 的分析器。该分析器的分词结果更符合汉语的习惯,并且在分词,建立索引等方面 的性能非常接近基于机械分词的分析器,另外在检索速度方面性能提升了 2-4 倍,在 检索召回率方面性能提升了 59%。 3.1 Lucene 分析器 分析器的作用是:通过执行若干操作,将文本语汇单元化。这些操作包括提取 单词、去除标点符号、去掉语汇单元上的音调符号、将字母转换为小写(也称为规 格化)、移除常用词、将单词转换为词干形式(词干还原),或者将单词转换为基本 形等。这个过程也称为语汇单元化过程,而从文本流中得到的文本块称为语汇单元。 各语汇单元与关联的域名相结合就形成了各个项[15]。 3.1.1 分析器剖析 为了完全认识和理解 Lucene 分析文本的工作原理,我们需要进行一些深入的剖 析,以认识它真实的面目。因为需要创建自己的分析器,所以对 Lucene 所提供架构 和构件模块的理解就显得非常重要。下面主要研究语汇单元的组成。 语汇单元流是经过分析所产生的基本单元。在索引时,Lucene 使用特定的分析 器来处理需要被语汇单元化的指定域,并且将每个语汇单元以索引项的形式写入索 引中。语汇单元和项之间的区别似乎并不明显。我们先来看看语汇单元的组成部分, 再在稍后的部分回到从语汇单元到索引项的转换过程上来。 我们以对文本“the quick brown fox”的分析来为例。该文本中每个语汇单元都表 示一个独立的单词。一个语汇单元携带了一个文本值(这个单词本身)和其它一些 元数据:原文本从起点到终点的偏移量、语汇单元的类型和位置增量[16]。图 3-1 向 上海交通大学硕士学位论文 Lucene中文分析器改进 17 我们展示了使用 SimpleAnalyzer 分析这个短语生成语汇单元流的一些细节。 图 3-1 带有位置和偏移信息的语汇单元流 Figure 3-1 Token flow with ocation and migration information 起点的偏移量是指语汇单元文本的起始字符在原文本中的位置,而终点的偏移 量则表示语汇单元文本终止字符的下一个位置。语汇单元的类型以一个字符串对象 表示,其值默认为“word”,如果需要的话,读者可以在语汇单元的过滤过程中控制 和利用到其类型属性。文本被语汇单元化之后,相对于前一个语汇单元的位置信息 被保存为位置增量值。所有的内置语汇单元化器将位置增量的默认值设置为 1,表 示 所有语汇单元都是连续的,位置上是一个紧接一个的。 语汇单元转换为项的过程:当文本在索引过程中经过分析后,每个语汇单元都 作为一个项被传递给索引。位置增量是语汇单元携带到索引中的惟一的附加元数据 [17]。起点和终点偏移量和语汇单元类型都被抛弃了——这些元数据仅在分析过程中 使用。 语汇单元的位置增量值使得当前语汇单元和前一个语汇单元联系起来。一般来 说,位置增量为 1,表示每个单词存在于域中唯一且连续的位置上。位置增量因子会 直接影响短语查询和跨度查询的执行情况,因为这些查询需要知道域中各个项之间 的距离。如果位置增量大于 1,则允许单词之间有空隙,它用来表示那个空缺的位置 上有一些单词已经被删除了。位置增量值为 0 的语汇单元,会将该语汇单元放置在 前一个语汇单元的位置上。用于加入单词别名的分析器可以通过零位置增量来放置 某个单词的同义词。这样做使得 Lucene 在进行短语查询时,输入任意一个同义词都 能匹配到相应的结果。 3.1.2 Lucene 内置分析器 Lucene 中包含了一些内置的分析器如表 3-1 所示。表中列出了其中几个主要的 分析器。这些分析器几乎可以用于分析所有的西方(主要指欧洲)语言。由于 StopAnalyzer 和 StandardAnalyzer 这两个分析器都具有比较特殊而又突出的处理效 果,下面进行详细的介绍。 上海交通大学硕士学位论文 Lucene中文分析器改进 18 表 3-1 Lucene 内置分析器 分析器 内部操作步骤 WhitespaceAnalyzer 在空格处进行语汇单元的切分 SimpleAnalyzer 在非字母字符处切分文本,并将其转换为小写形式 StopAnalyzer 在非字母字符处切分文本,然后小写化,再移除停用词 StandardAnalyzer 基于复杂的语法来实现语汇单元化;这种语法规则可以识别 e-mail 地 址、首字母缩写词、汉语-日语-汉语字符、字母数字等;小写化;并移 除停用词 StopAnalyzer 不只是完成最基本的拆分和小写转化的工作,而且还负责对停用词 进行移除。在 StopAnalyzer 中有一个表示常用的英语停用词列表的数据成员,在默 认的情况下,StopAnalyzer 就使用以下这个列表: 表 3-2 StopAnalyzer 停用词列表 “a”, “an”, “and”, “are”, “as”, “at”, “be”, “but”, “by”, “for”, “if”, “in”, “into”, “is”, “it”, “no”, “not”, “of”, “on”, “or”, “s”, “such”, “t”, “that”, “the”, “there”, “these”, “they”, “this”, “to”, “was”, “will”, “with” 要注意的是默认列表中的“s”和“t”。这是因为在英语中,缩略词是很常见的,比 如 don’t、can’t 和 it’s。在移除停用词之前,StopAnalyzer 会事先将连续字符组合在 一起,并且在非字母字符(包括撇号)处进行拆分,将 s 和 t 作为独立的语汇单元。 因为这些字符本身没有任何实际的意义,所以将它们移除也是有道理的。停用词的 移除为我们引入了一个有趣的内容:应该如何处理单词移除后留下的空位?假设你 要对“one is not enough”进行索引。经过 StopAnalyzer 分析后得到的语汇单元将是 one 和 enough,而 is 和 not 则都会被移除。此时,StopAnalyzer 不会对被移除的单词做任 何的说明,这样,索引“one is not enough”的结果就和索引“one enough”是一样的。这 时如果你在某个 QueryParser 对象中使用 StopAnalyzer 分析器,由“one is not enough” 这个句子就会匹配到以下的一些结果,例如“one enough”、“one is enough”、“one but not enough”,当然也包括查询“one is not enough”。这是因为 QueryParser 也会对这些 短语进行分析,并将它们削减为“one enough”,从而匹配到索引后的项。 StandardAnalyzer 是公认的最有用的内置分析器。该分析器是基于 JavaCC 进行 操作的,它能够将下列类型的词汇准确地转化为语汇单元:字母数字混合编列的词 汇、由各单词首字母组成的缩写词、公司名称、e-mail 地址、电脑主机名、数字、带 撇号的单词、序列号、IP 地址以及 CJK(汉语、日语、韩语)字符。StandardAnalyzer 上海交通大学硕士学位论文 Lucene中文分析器改进 19 还可以通过与 StopAnalyzer 相同的机制来移除停用词。 StandardAnalyzer 的使用方法和其它分析器的使用方法并没有多大区别。尽管如 此,在处理文本的方式上,它与众不同的效果是显而易见的。例如,我们来比较一 下表 3.1 中各个分析器对词组“XY&Z Corporation - xyz@example.com”的处理效果。 StandardAnalyzer 是唯一能够将 XY&Z 以及 e-mail 地址 xyz@example.com 保留在一 起的分析器,而这两段文本都是需要十分复杂的分析过程才能正确处理的。 3.1.3 支持中文的分析器 众所周知,西方语言是使用空格和标点来分隔单词。但是在汉语、日语、韩语 等亚洲语种中,一般使用表意文字,而不是使用由字母组成的单词。这些字符不是 通过空格来分隔的,所以我们需要使用一种分析方法来识别和分隔语汇单元,这种 分法成为分词。由于中文语义的复杂性好多样性使得中文分词一直以来都是一件相 当困难的事情。 目前支持中文的分析器主要有 StandardAnalyzer,CJKAnalyzer,ChineseAnalyzer, IK_CAnalyzer。 StandardAnalyzer 和 ChineseAnalyzer 在对中文进行分词时,都是将每个汉字作为 一个词。但是,由于汉语中词条长度主要在 2 至 4 之间,所以 StandardAnalyzer 以及 ChineseAnalyzer 的词汇单元,与汉语中的词相差甚远,这样为分析器在处理同义词、 别名以及其它表示相同意义的词的时候带来了困难。CJKAnalyzer 根据汉语中词条长 度为 2 居多的特点,将每相邻的两个字作为词汇单元。这种虽然在某种程度上更符 合了汉语的习惯,但是这样分词是的几乎每个汉字都在两个词语中,使得词语的效 率只有 50%左右[18]。 根据以上分析,为了能够使得分析器功能更加符合汉语习惯,并提高分词的准 确性,使用基于词典的分词器是不错的选择。 IK_CAnalyzer 就网络上流传的基于词典的分词器,它的分词结果就明显更符合 汉语的习惯。但是由于其实现源代码没有公开,使得用户难以根据自己需要进行更 改。另外经过实验发现,IK_CAnalyzer 在建立索引、分词等方面速度都较其它分析 器慢了一两个数量级。 上海交通大学硕士学位论文 Lucene中文分析器改进 20 3.2 分析器实现 3.2.1 中文分词算法 现有的分词算法可分为三大类:基于字符串匹配的分词方法、基于理解的分词 方法和基于统计的分词方法。到底哪种分词算法的准确度更高,目前并无定论。对 于任何一个成熟的分词系统来说,不可能单独依靠某一种算法来实现,都需要综合 不同的算法。 ¾ 基于规则的分词方法 基于规则的分词方法,这种方法又叫做机械分词方法,它是按照一定的策略将 需要分析的汉字串与一个“充分大的”机器词典中的词条进行匹配,若在词典中找到 某个字符串,则匹配成功(识别出一个词)。常用的方法:正向(逆向)最大匹配法, 最小匹配算法,逐字匹配算法,联想回溯法,基于 N-最短路径分词算法,以及可以 相互组合。例如,可以将正向最大匹配方法和逆向最大匹配方法结合起来构成双向 匹配法等。 ¾ 基于理解的分词方法 这种分词方法是通过让计算机模拟人对句子的理解,达到识别词的效果。其基 本思想就是在分词的同时进行句法、语义分析,利用句法信息和语义信息来处理歧 义现象。它通常包括三个部分:分词子系统、句法语义子系统、总控部分。在总控 部分的协调下,分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧 义进行判断,即它模拟了人对句子的理解过程。这种分词方法需要使用大量的语言 知识和信息。由于汉语语言知识的笼统、复杂性,难以将各种语言信息组织成机器 可直接读取的形式,因此目前基于理解的分词系统还处在试验阶段。 基于多种知识源的汉语自动分词与纯规则方法不同,该方法利用字、词、上下 文、语法及语义等多种知识源对汉字串中每一种切分可能性进行考察,并在无法彻 底消除歧义的情况下通过模糊综合知识得出最可能的切分结果。用户可以根据需要 修改系统以适应不同文本的特征,并能接收前后词法、语法、语义分析阶段的反馈。 系统利用的知识比较多,如单字频、双字相邻频、字相邻频,汉语词汇与词性共现 频、单词频、双字词相邻频、单字词相邻频,词性一元、二元、三元共现频,交集 型与组合型歧义词共现频,词语搭配期望、语法语义期望词集,单字的词首频、词 中频、词尾频,上下文汉字串及汉词串频率等。汉语自动分词专家系统的总体设计 思想是将自动分词过程看作是基于知识的逻辑推理过程,用知识推理与语法分析替 代传统的“机械匹配分词歧义校正”的过程。 上海交通大学硕士学位论文 Lucene中文分析器改进 21 ¾ 基于统计的分词方法 越来越多的学者认识到,唾手可得的海量电子文本应成为自动分词的重要资源, 利用机器学习手段从生语料库中直接获取分词所需的某些适用知识则应成为自动分 词的重要补充手段。即分词过程中除需定性信息外,必须引入定量信息,分词处理、 分词词表的构造,应该和汉语语料库结合起来考虑。基于统计的分词方法所应用的 主要的统计量或统计模型有互信息、神经网络模型、隐模型和最大熵模型等。目前 基于统计的分词研究还处于尝试中,其目的为研制开放环境下健壮性好的分词系统 作充分准备。 基于统计的分词方法的优点是不受待处理文本的领域限制不需要一个机器可读 词典。缺点是需要大量的训练文本,用以建立模型的参数该方法的计算量都非常大 分词精度与训练文本的选择有关。 3.2.2 Lucene 中文分词算法选择 分词系统主要关心的是两个指标:切分速度和切分精度。由于搜索引擎与自然 语言的理解,自动翻译不同,在切分精度方面要求不是很严格,更注重切分速度[19]。 在 Lucene 中通常采用基于规则的分词方式。主要有单字切分,二分法。 单字切分,顾名思义,就是按照中文一个字作为一个词的方式进行分词。以这 种方式切分出来的词再进行索引,称之为字索引。很显然,这不是一种很好的分词 方式,因为随着索引的增大,相应索引条目的内容会不断增大,严重影响效率。另 外,当用户对索引进行检索时,如果用户输入 5 个字,则相当于要对索引进行 5 次 检索,严重的影响效率。单子切分除了影响索引效率和检索效率外还影响检索的结 果。比如说查询“上海”时,由于单子切分把“上海”切分成两个词:“上”和“海”, 这样“海上”也可能被检索出来。显然这结果并不是用户想要的。 所谓二分法,就是指每两个字进行一次切分。如对“天涯若比邻”这样一个词 组进行二分法切分,则结果如下;天涯/涯若/若比/比邻。这种切分方式完全不考虑词 义、语境、机械地对语句进行处理。虽然结果看起来有些可笑,然后,在很长一段 时间内,它一直是中文分词的一种很方便的方式[20]。根据这样分词效果建起来的索 引会存有大量垃圾词汇,有可能使用户根本不可能检索的词。因此,它也不是很好 的方式。 词库分词被认为是一种比较理想的中文分词方式。所谓词库分词其实就是用一 个已经建立好的词的集合按照某种算法去匹配目标,当遇上集合中已经存在的词时, 就将之切分出来。例如词库中已经存在“天涯若比邻”这个词时,分词器就会把它 上海交通大学硕士学位论文 Lucene中文分析器改进 22 当作是一个词条加入索引。 很显然,对于这种分词方式,词库的建立是关键。通常,词库的建立需要统计 大量的内容,然后根据各种词出现的频率、概率再来进行筛选,最终决定什么词应 当放入词库。另外,一些更加高级的词库还加入了语义和词性的标注,甚至还有不 同的权重[21]。 为了能够使得分析器功能更加符合汉语习惯,并提高分词的准确性,本文选择 采用前向最大匹配切分算法。并且根据汉语中词条分布情况,本文中将最长词条长 度设为 4。 最大匹配切分算法中规定最长词条长度 M。首先字符指针指向待切分字符串的 串首,读取前 M 位字符作为子串。到切分词典找查找该子串,如果不存在,则去除 子串中最后一位字符,将剩下的字符串作为子字符串,重复上面过程,直到在词典 中查找到子字符串或者子字符串长度变为 1,将子字符串作为词,然后字符指针指向 子字符串后面的第一位字符,继续上面过程,直到字符串扫描结束。例如,待处理 字符串为“汉字多为表意文字”,取字符串“汉语多为表”(假设比较的步长为 4,本文步 长 step 都取 4)与词典进行比较,没有与之对应的词,去除“表”字,用字段“汉语多为” 进行匹配,直至匹配到“汉语”为至,再取字符串“多为表意”,循环到切分出“文字” 一词。 3.2.3 词典构造 分词词典是汉语自动分词系统的一个基本组成部分,自动分词系统所需的各类 信息都要从分词词典中获取,分词词典的查询速度直接影响到分词系统的速度。 本文采用基于整词二分的分词词典机制,这是一种广为使用的分词词典机制[22]。 其结构可分为:首字散列表和词典正文两部分。由首字的散列值得到词典正文的位 置。词典的结构如表 3-3 所示。首字散列表为词语的首个汉字,通过计算其散列值可 以快速定位词典正文的位置。词典正文是以词为单位的有序表,通过整词的二分快 速查找可以快速找到所查询词的位置。 对于每个字符串,其散列值随散列算法不同而不同,由于 Lucene 中使用的是 UTF-8 编码,本文采用相应的散列算法。散列公式: ^^( ) [0]*31 ( -1) [1]*31 ( - 2) [ -1]HashCode s s n s n s n=+++" (3-1) 其中: []si表示字符串的第i 个字符的 Unicode 编码的值,n 是字符串的长度, ^ 表示求幂。 由于在 java 中一字符由双字节组成,每个汉字由一个字符表示。所以词典中首 上海交通大学硕士学位论文 Lucene中文分析器改进 23 字的散列值即为首字的 Unicode 编码。 由于选择的分词算法中,对长度超过 4 以及长度为 1 的词不进行查找,所以本 文的词典过滤了长度为 1 以及长度超过 4 的词。这样不仅减小词典所占据的内存空 间,同时提高了查询字典的效率,从而提高整体查询的速度[23]。 表 3-3 词典结构 词首(散列值) 词典正文 保(20445) 保护,保卫,保龄球,保龄球馆,…… …… … …… 平(24179) 平安,平安无事,平安保险,平白,平白无故,…… …… …… 勇(21191) 勇敢,勇冠三军,勇猛,勇气,勇士,勇往直前,…… 3.2.4 具体实现 Lucene 中实现自己的分析器,需要实现自己的 Analyzer,Filter,Tokenizer 类。 Tokenizer 对字符串进行分析得到词汇单元以及词汇单元的位置信息,即一系列的 Token, 然后 Filter 对得到的 Token 进行过滤,最后由 Analyzer 提供接口。 本文实现 MyAnalyzer,MyFilter,MyTokenizer 分别继承 Analyzer,Filter,Tokenizer 类。另外,因为本文实现基于词典的中文分词,所以提供了 WordLibService 类,来 实现关于词典相关的功能。 下面介绍 MyAnalyzer,MyFilter,MyTokenizer 以及 WordLibService 提供的功能。 MyTokenizer 主要完成分词功能,分词流程如图 3-2。其主要分析原理如下:将 字符分为三种类型:中文字符,英文字母或数字,其他字符。MyTokenizer 从字符串 中每次读入一个字符,如果该字符是中文字符或者英文字母或数字时,将该字符加 入缓存。当读入的字符是其他字符,或者读入的字符与缓存中字符类型不一致,或 者缓存中的字符数到达最大词长时,处理缓存。重复以上过程,直到处理完字符串。 其中处理缓存有两种情况:一、缓存中内容是中文字符,此时 MyTokenizer 根据最大 匹配切分算法对内容进行分析,得到一个词,并且从缓存移出该词;二、缓存内容 为英文字母或数字,此时处理操作为:该将该内容作为一个词汇,并且清空缓存。 上海交通大学硕士学位论文 Lucene中文分析器改进 24 图 3-2 分词流程图 Figure 3-2 Word segmentation flow MyFilter 主要功能为过滤停用词。MyFilter 中包含停用词列表,如果 MyTokenizer 分词得到的项中的词汇为停用词则过滤该项。根据中文语言的特点,本文实现的停 用词列表中补充了“啊”,“阿”,“哎”,哎呀“,哎哟”,“俺们”等中文词汇。 MyAnalyzer 向用户提供接口,返回 MyFilter 过滤后的项。 WordLibService 主要提供了三个功能:创建词典、载入词典、更新词典。创建词 典:将词库按照每行一词存储于文件中,程序将词库文件中的词读入内存,并且根 据以首字作为键,以该字为词首的词组成的有序列表作为值的结构组织成词典,以 HashMap 对象存储于内存中,然后将 HashMap 对象序列化存储于本地磁盘文件中。 上海交通大学硕士学位论文 Lucene中文分析器改进 25 词典中载入词典:将储存于本地磁盘文件凡序列化得到 HashMap 对象,即为以键值 对的形式的词典,读入内存。用来判断字符串是否存在于词典中。更新词典:用户 可以根据自己需要以每行一词的格式添加自己的词,更新词典时,程序会先在词典 中查找是否存在该词,如果不存在则将该词添加到词典中。 3.3 分析器比较 由于 ChineseAnalyzer 与 StandardAnalyzer 的分词结果一样,这里只对 StandardAnalyzer 作为比较。 3.3.1 分词结果示例 表 3-4 分词结果比较 StandardAnalyzer [一] [种] [面] [向] [搜] [索] [引] [擎] [Lucene] [的] [中] [文] [分] [词] [方] [法] CJKAnalyzer [一种] [种面] [面向] [向搜] [搜索] [索引][引擎] [Lucene] [的 中][中文] [文分] [分词][词方] [方法] IK_CAnalyzer [一种] [面向] [搜索引擎] [搜索] [索引] [引擎] [Lucene] [中文] [分词] [方法] MyAnalyzer [一种] [面向] [搜索引擎] [Lucene] [中文] [分词] [方法] 对“一种面向搜索引擎 Lucene 的中文分词方法”进行分析,得到的结果如表 3-4 所示。从表中结果不难发现,StandardAnalyzer 将每个汉字作为一个词。CJKAnalyzer 将每两相邻的汉字作为一个词,IK_CAnalyzer 是采用基于词典的全分词,MyAnalyzer 采用的基于词典的最大匹配切分算法分词。显然 MyAnalyzer 的分词结果更符合汉语 的习惯。 上海交通大学硕士学位论文 Lucene中文分析器改进 26 3.3.2 分词速度比较 表 3-5 分词速度比较(时间单位: 毫秒) 第一次 0KB 第二次 5.51MB 第三次 773MB StandardAnalyzer 31 5688 523890 CJKAnalyzer 0 4406 297596 IK_CAnalyzer 3203 492719 52096978 MyAnalyzer 1578 10922 923501 第一次分析结果是对空文本进行分析得到的数据,第二次分析是对一个大小为 5.51MB 的网络小说进行分析得到的数据,第三次是连续对近千部网络小说,共计 8975 个文本文件进行分析得到的数据。由于 IK_CAnalyzer 和 MyAnalyzer 在第一次 分词时,需要加载词典,所以对文本分词时间较长。而在实际应用中,分析器往往 会连续分析上兆次,并且由实验数据可以看出,当需要分词的文本够长时, MyAnalyzer 的分词所需要到时间约为机械分词所需时间的两倍,而与 IK_CAnalyzer 相比,速度提升了 50 多倍。 3.3.3 建立索引 表 3-6 建立索引速度以及占据存储空间比较 生成索引文件占据存储空间 生成索引文件需要的时间 StandardAnalyzer 118MB 446766 ms CJKAnalyzer 293MB 813219 ms IK_CAnalyzer 196MB 7345578 ms MyAnalyzer 140MB 497297 ms 这实验是对近千部网络小说,共计 8975 个文本文件,约为 773MB 的数据建立 索引,得到的实验数据。从实验结果可以发现 MyAnalyzer 建立索引的速度接近建立 索引最快的 StandardAnalyzer 并且与基于机械分词的分析器建立索引的速度,并且生 成索引文件占据的存储空间是最少的,基本达到 CJKAnalyzer 的一半。而 IK_CAnalyzer 在建立索引时,所需要的时间,是其它分析器建立索引时间的 20 倍左 右。 上海交通大学硕士学位论文 Lucene中文分析器改进 27 3.3.4 检索效果 表 3-7 检索效果比较(时间单位: 毫秒) 检索到文件数目 检索时间 StandardAnalyzer 1127713 253110 CJKAnalyzer 1154730 148157 IK_CAnalyzer 1884648 69375 MyAnalyzer 1841823 60156 这实验是对基于网页词频统计的词频最高的 10000 个词,利用分析器分别在各 自建立的索引文件中搜索得到的。检索到的文件数目为分别检索包含这 10000 个词 的总和。检索时间为对这 10000 个词进行检索所得到的时间总和。从中可以发现 MyAnalyzer 检索的检索速度是最快的。而且基于词典的分析器在检索的召回率方面 明显优于基于机械分词的分析器,并且在检索速度方面也明显优于基于机械分词的 分析器。 3.3.5 实验分析 从上面的实验结果进行分析,我们可以得出如下结论。 与 IK_CAnalyzer 相比,MyAnalyzer 建立索引的速度快 15 倍,分词速度快 56 倍, 而建立的索引文件占据空间节省约 1/3。检索速度占据优势, 而仅在召回文件数目 上少百分之二。因此同样基于词典的分析器,MyAnalyzer 的总体性能明显更优于 IK_CAnalyzer。 与 CJKAnalyzer 相比,MyAnalyzer 在检索结果,检索速度方面占有明显的优势。 并且在建立索引的速度,以及索引文件所占空间方面也都占有优势。而 CJKAnalyzer 仅在分词速度方面优于 MyAnalyzer,由于实际应用中,对于搜索引擎而言,检索速 度和检索效果才是用户最为关心的,所以 MyAnalyzer 在实际引用方面是比 CJKAnalyzer 更适合应用于中文搜索。 与 StandardAnalyzer 相比,虽然在分词速度,建立索引的速度,索引文件所占空 间方面稍逊于 StandardAnalyzer,但是 MyAnalyzer 的检索速度是 StandardAnalyzer 的 4 倍,而且检索找回的文件数目也是 StandardAnalyzer 的 1.5 倍。因此在实际应用 方面,MyAnalyzer 是一个更好的选择。 从上面分析可以得出,MyAnalyzer 是一个分词速度,建立索引等性能方面与基 于机械分词的分析器相当,并且具有明显优于基于机械分词的检索效果和检索速度。 上海交通大学硕士学位论文 Lucene中文分析器改进 28 3.4 小节 本文分析了 Lucene 分析器的作用,发现目前应用于 Lucene 的中文分析器的分 词不合符汉语习惯,从而影响了检索性能。本文根据正向最大匹配切分算法和采用 包括基本标准中文词语的词库,实现了自己的分析器。通过实验证明该分析器的分 词结果更符合汉语的习惯,并且在分词,建立索引等方面的性能非常接近基于机械 分词的分析器,另外在检索速度方面性能提升了 2-4 倍,在检索召回率方面性能提升 了 59%。 上海交通大学硕士学位论文 自然语言检索 29 第四章 自然语言检索 信息检索模块根据用户的查询在索引库中快速检索出文档,进行文档与查询的 相关度评价,对将要输出的结果进行排序,并实现某种用户相关性反馈机制。 所谓自然语言处理,就是利用计算机技术研究和处理语言的一门学科,即把计 算机作为语言研究的强大工具,在计算机的支持下对语言信息进行定量化的研究, 并提供可供人与计算机之间能共同使用的语言描写[24]。 4.1 检索模型 在检索技术的发展过程中,人们已经开发出多种检索模型以提高检索器的综合 性能。常用的检索模型有:布尔模型(Boolean Model)、模糊逻辑模型(Fuzzy Logic Model)、向量空间模型(Vector Space Model)、概率模型(Probability Model)以及扩展布 尔模型(Extended Boolean Model)等[25]。 ¾ 布尔模型 布尔逻辑模型是最简单的信息检索模型,用户可以根据检索项在文档中的布尔 逻辑关系提交查询,搜索引擎根据事先建立的倒排文件结构,确定查询结果[26]。标 准布尔逻辑模型为二元逻辑,所搜索的文档要么与查询相关,要么与查询无关。其 具体运算方式是,用检索状态值(Retrieval Status Value, RSV)来标定查询和文档是否 相关。若查询在文档中出现,则取值为 1,否则取值 0,因为所有被检中的文档都有 同样的 RSV,所以查询结果不进行相关性排序。 ¾ 模糊逻辑模型 模糊逻辑模型为了处理精度和复杂性之间的矛盾,引入了模糊逻辑模型,它以 [0,1]范围的模糊逻辑值为基础,以隶属函数概念来描述现象差异的中间过渡。在 查询结果处理过程中引入模糊逻辑运算,将所检索的文件信息和用户的查询要求进 行模糊逻辑比较,按照相关性的优先次序排出查询结果,在布尔检索中借助模糊逻 辑模型能够克服布尔逻辑查询结果的无序性。 ¾ 向量空间模型 向量空间模型中查询和文件都映射为同一个 n 维空间矢量。相似性的运算等同 于向量的夹角余弦,根据矢量空间的相似性,即可排列查询结果。矢量空间模型不 仅可以方便地产生有效的查询结果,而且能够提供查询结果分类,为用户提供准确 上海交通大学硕士学位论文 自然语言检索 30 定位所需的信息。 ¾ 概率模型 概率模型在信息检索中存在不确定性问题,对查询本身来说,它不能唯一地表 示信息需求,对于结果来说,定查询结果的正确与否。对于布尔检索也是如此,因 为查询本身就是一种不确切方式。为了解决在布尔检索模型中的不确定性问题,引 入了概率检索模型。该模型基于概率排队理论:当文件按相关概率递减原则排列时 可以获得最大的检索性能。 ¾ 扩展布尔模型 扩展布尔模型与向量空间模型一样,将文档表示为 n 维空间中的向量,在用两 个向量的标积衡量查询与文档相似度时,该模型提供了一个带有一般性意义的参数, 随着这个参数的变化,该模型可以转变为向量空间模型、模糊逻辑模型和普通的布 尔模型。 4.2 自然语言搜索引擎 作为自然语言应用的领域之一,搜索引擎的人机界面的友好程度是衡量搜索引 擎性能的重要指标之一。自然语言由于更加贴近人类的生活习惯,使检索系统与用 户的交流更为人性化。多数用户均不习惯使用复杂的布尔逻辑表达式来表述自己的 需求,而更倾向于用自然语言进行检索。目前的搜索引擎基本上只是使用关键词技 术,每次搜索时按照关键词进行匹配,因此返回的大量信息中有很大一部分不是用 户需要的,往往导致用户陷入信息泛滥的沼泽[27]。基于自然语言理解技术的智能搜 索引擎可以依靠自然语言理解技术对知识的理解和处理能力,将信息检索从目前基 于关键词的层面提高到基于知识(或概念)的层面,从而更大程度地了解用户的信息需 求,获得更易用、更准确、更智能的搜索结果。摆脱了传统搜索引擎基于关键词的 束缚,并能提供相关的、有参考价值的其他内容,因而具有信息服务的智能化、人 性化特征[28]。因此,将自然语言处理技术引入检索系统也是搜索引擎技术的一个重 要的研究方向,同时也是智能化搜索引擎的一个难点。 4.2.1 自然语言理解与处理的现状 自然语言处理是早期人工智能研究极其活跃的一个领域。从电子计算机问世, 人们就开始尝试利用计算机把一种语言翻译成另一种语言,但是由于当时主要采用 逐词翻译的简单技术,仅仅利用了语言中的语法信息,因而无法达到满意的翻译效 上海交通大学硕士学位论文 自然语言检索 31 果。自然语言最显著的一个特点是它的歧义性[29]。比如说,汉语句子“乒乓球拍卖 完了”,可以有两种解释。一种是“乒乓球/拍卖/完了”,另一种是“乒乓/球拍 /卖/完了”。人在阅读或会话时,可根据上下文及语言环境进行判断,但是计算机 孤立地分析这一句话是很难做出判断的。语言信息包括语法信息、语义信息和语用 信息三个层次,在这三个层次上,自然语言都表现出了各种各样的歧义,与此对应, 自然语言处理理论的研究也分别在这三个层次上展开,但是由于自然语言固有的复 杂性,迄今为止,自然语言处理仍然还只停留在语法信息的处理层次上[30]。 自然语言搜索引擎中现阶段的自然语言理解技术有两大研究方向,即基于规则 的分析方法(即所谓的理性主义)和针对大规模语料库的分析法(即所谓的经验主义)。 这两种方法都有自己的优点,但也存在一些薄弱的地方,主要体现在: (1)前者的核心是分析句子结构,利用规则自顶向下或自底向上的句法树生成过 程来分析。随着这些年的发展,具有代表性的有:词汇功能语法(LFG)、功能合一语 法(FUG)和广义短语结构语法(GPSG)等。这些方法基本上掌握了单个句子的分析技 术,但在处理大规模的非受限真实文本时很难覆盖全面,特别是对于整个段落或篇 章的理解还无从下手。 (2)后者充分利用计算机的高速处理能力和海量存储,大量相关的文本建立语料 库,然后在语料中标注各种记号,标注的内容包括每个词的词性、语义项、短语结 构、句型和句间关系等。随着标注程度的加深语料库逐渐熟化,成为一个分布的统 计意义上的知识源。利用这个知识源可以进行许多语言分析工作,如根据从已标注 语料中总结出的频度规律可以给新文本逐词标注词性,划分句子成分等。但语料库 提供的知识是用概率统计表示的,因而常常会出现答非所问的情况,并且语料库需 要耗费大员的时间和资源去建立、维护,成本很高。 4.2.2 自然语言查询 与传统的目录查询、关键词查询相比,自然语言查询更加贴近人类的生活习惯, 使这种人机交流更加人性化。因为大多数人都不习惯使用复杂的布尔逻辑表达式来 表述自己的需求,而是更倾向于以日常生活中的自然语言进行检索。更重要的是自 然语言查询技术可以避免陷入信息泛滥的沼泽,使信息查询更加方便、快速和精确。 与传统的目录查询、关键词查询模式相比,自然语言查询的优势体现在:一是 使网络交流更加人性化;二是使信息查询变得更加方便、快速和准确[31]。现在,已 经有越来越多的搜索引擎宣布支持自然语言搜索特性,但是要建立真正的基于自然 语言理解的智能答询系统,还存在很多的技术难点,如:如何理解自然语言及所代 上海交通大学硕士学位论文 自然语言检索 32 表的实际含义;如何根据问题找出用户实际想要的答案;如何建立大规模知识库等。 Ask Jeeves 是第一个实现了智能答询系统的搜索引擎。用户只需输入简单的疑问句, 如"Where can I find ..."、"How can I do ..."等。Ask Jeeves 在对提问进行结构和内容分 析之后,或直接给出问题的答案,或引导用户从几个可选择的问题中进行再选择。 为了弥补目前技术水平和知识库的不足,Ask Jeeves 同时提供目录搜索服务和元搜索 服务,可同时搜索多个独立的搜索引擎,并提供集成的搜索结果。Ask Jeeves 在开创 智能答询搜索引擎模式的同时,也为企业建立智能、在线、全天候的产品问答服务 系统奠定了基础,所以有人预言说,以后几年将是一个到处弥漫着"?"的年代。 基于自然语言的用户查询系统具有三个特点[32]。 (1)共同性:自然语言对我们人类或系统的变化容许度高,不同的人使用同样 的自然语言可以使用不同的对象系统,因而可以作为不同系统的统一查询系统。 (2)抽象性:要解决的问题用自然语言记述,如何解决由系统考虑。这样,可 以把系统的查询方法设计得便于任何人使用,而不管他是什么专业领域、具有何种 文化水平。 (3)模糊性:当用户的要求以及问题本身就不明确时,用自然语言记述能够反 映这种模糊性,可以交由系统去判断。 但是,自然语言如何进行分解取得准确的语义,这本身就是一个非常困难的问 题,目前只能够在一个很小的范围内使用。即使是由关键字描述的媒体数据,在检 索的时候对复杂的查询也是难以适应的,同样是关键字,但由于描述的程度不一样, 所描述的对象范围不一样,就会带来许多问题。对自然语言来说问题就更突出。例 如,一幅图像是足球比赛的场景,用自然语言描述:“足球场上运动员在进行足球比 赛”。在这里,“足球场上运动员在进行足球比赛”、“足球比赛”与“足球”、“运动 员”、“球场”显然不在一个层次上。如果能够用自然语言中抽取相同意义的关键词, 就可以支持复杂的查询要求,当用户查询这幅图像时,他可以根据不同的需求查询 出“足球”、“运动员”、“比赛”、“球”、“运动”等多个不同范畴的信息。这对系统 来说就需要能够做到自动关键词抽取和概念匹配。 中文与西文相比,最大的特点是不以标识进行分词,简单地说,就是西文的字 与字之间以空格或标点区分,而汉语是连贯的,一般情况下,只有语句结束,才用 标点加以标识[33]。这就为智能问答技术的本地化带来了一定的难度,事实上相当于 独立开发一套针对中文的系统。 上海交通大学硕士学位论文 自然语言检索 33 4.2.3 自然语言查询的处理过程 自然语言查询的开发分模型训练和模型匹配两个阶段进行。 ¾ 模型训练 在这个阶段的工作主要分为以下 4 个部分。 首先是进行概念的切分、抽取。如上所述,中文的特性使“概念切分”具有一 定的难度,尤其是对人名和地名的分词,但这又是比较关键的一步。北极星的研究 人员运用了马尔科夫模型算法进行无需词库的中文分词,准确率可以达到 99%以上。 并且非常好地解决了人名、地名的分词问题[34]。 第二部分为提取关键词。通过对大量文本,如新华字典、百科全书、报纸新闻 等(如果是企业内部使用,则专门对本企业的数据资源)进行统计,将出现频率满 足一定条件的词作为关键词提取出来。 第三部分为构造特征向量。根据关键词提取情况,以改进的 TF-IDF 的算法为每 一个问题构造一个特征向量。 最后为向量存储。就是将特征向量以高速多维索引文件的形式存入硬盘,以备 索取和查询。由于其使用了完全自主实现的索引算法,所以具有非常好的检索效率。 ¾ 模型匹配 第二阶段的工作除了操作对象不同外,最初的三步也是进行概念切分、提取关 键词、构造特征向量,只是最后的两个步骤有所区别[35]。第四步为匹配向量之间的 距离,运用余弦函数计算出向量之间的距离(即相似性)。在多维的索引文件中,可 以使用 k 近邻算法计算。最后一步是对相似性进行排序,列出前 n 名返回给用户, 用户通常会选择最合适的答案进行浏览,将用户选择的结果存入系统,则下次当同 样的问题出现时,系统直接返回给顾客较为精确的答案。这样的系统经过一段时间 的训练,就能达到更好的检索效果。 对于用户的问题,如果知识库中没有找到相似答案,则将该问题存入数据库, 在系统维护时人工添加进去。则当下次用户问同样或者是类似的问题时,就能找到 满意的答案了。中文智能系统的开发过程如图 4-1 所示。 上海交通大学硕士学位论文 自然语言检索 34 图 4-1 自然语言查询的处理流程 Figure 4-1 Work flow of natural language search 4.2.4 智能型交互式查询 “智能型交互式搜寻”,透过人工智能与知识分析技术,动态分析使用者输入的 关键词,能进一步主动分析用户的搜寻需求,提供真正能与使用者产生“互动”的 搜寻服务。“智能查询”能为使用者所输入的关键词先行自动判断,利用缩写展开、 同义联想、累赘字移除等方法,自动转换成更适当的查询字符串进行搜寻。例如输 入“交大”,以往只能找到“交大附中”、“交大新闻”等完全符合的结果。经此机制 的帮助,系统能自动展开字符串,查到含有“上海交通大学”,“西安交通大学”等 的结果。“智能查询”对于机关团体的名称或者多种解释的字符串的使用者不需多次 输入、不需自行寻思可能相同的字符串,就可得到更精准的输出结果。 “互动提示”功能在找不到符合资料时,会将关键词经过“自动同音”及“自 动容错”处理,由系统给予形近似词、拼音校正、模糊查询的建议,确保使用者即 使拼错字也能查到所需的资料。此外,在搜寻结果中亦提供相关词、同义词以及形 近词等多重提示功能,供使用者缩小范围或跳跃式联想的查询服务。 4.3 自然语言理解实现 本文的研究是应用于搜索引擎上的。用户查询所用的自然语言一般以单个提问 句为主或者简单的陈述句,相对来说句式较少,意思明确[36]。因此以使用基于规则 的分析方法为基础,中间词法分析采用基于语料库的分析法,形成互补,逐步积累 中文分词 提取核心 语义词汇 构造特征向量 建立索引 检索 用户 检索服务器 检索结果 上海交通大学硕士学位论文 自然语言检索 35 逐步探讨,进而扩展到其他句式,从而达到从点到面的目的。 系统设计的主要思想为:首先,对用户提交的以自然语言表述的问题进行分词 处理,去除相关辅助词,最后提取出核心词进行查询。 4.3.1 分词处理 分词由于句型模式分析后得到的语句片断是切分后得到的结果,所以它的灵活 性和多样性比真实的自然语言文本要差一些,这样当进行词法分析的时候出现歧义 的情况较少[37]。 目前,正向最大匹配方法作为一种基本的方法已被肯定下来,但是由于错误比 较大,一般不单独使用。如字符串“处理机器发生的故障”,在正向最大匹配方法中 会出现歧义切分,该字符串被分为:“处理机/器/发生/的/故障”,但是使用逆向匹配 就能得到有效的切分。逆向最大匹配的分词原理和过程与正向最大匹配相似,区别 在于前者从文章或者句子(字符串)的末尾开始切分,若不成功则减去最前面的一个 字。比如对于字符串“处理机器发生的故障”,第一步,从字符串的右边取长度以步 长为单位的字段“发生的故障”在词典中进行匹配,如果匹配不成功,再取字段“生的 故障”进行匹配,依次匹配,直到分出“故障”一词,最终使用逆向最大匹配分词方法 切分的结果为:故障、发生、机器、处理。该方法要求配备逆序词典。 一般来说根据汉语词汇构成的特点,从理论上说明了逆向匹配的精确度高于正 向匹配,汉语语句的特点一般中心语偏后。有研究数据,单纯使用正向最大匹配的 错误率为 1/169,单纯使用逆向最大匹配的错误率为 1/245[38]。实际应用中可以从下 面几方面改进。同时采取几种分词算法,来提高正确率,改进扫描方式,称为特征 扫描或标志切分,优先在需要分析字符串中识别和切分出一些带有明显特征的词, 以这些词作为断点,可将原字符串分为较小的字符串再进行机械分词,从而减少匹 配的错误率等[39] [40]。 本系统采用两种相结合的双向扫描的方法,如果两种算法得到的结果相同,就 认为这次切分是无歧义、正确的;如果两种算法得到的结果不相同,就认为这次切 分是有歧义的,再利用利用词句切分概率对歧义字段进行处理。 例如:“研究生物科学的学生”正向最大匹配后分词的结果为“研究生/物/科 学/的/学生”,而逆向最大匹配后分词的结果却为“研究/生物/科学/的/学 生”,这时候认为这次切分为歧义切分。出现这种情况时,可以利用词句切分概率对 歧义字段进行处理,具体做法如下: 定义, f(W)代表一个词的词频,它是 W 在语料库中出现的次数/语料库中各词 上海交通大学硕士学位论文 自然语言检索 36 出现的次数之和, )(SP 代表语句 S 的某一种切分形式出现的概率。 )()()()( 21 twfwfwfSP ×××= " (4-1) 其中t 为切分完后词的个数。定义 H 为信息熵的值,那么计算语句切分效率的基 本公式为 2log ( ( ))HPS= − (4-2) 通过计算得到 H 值,其中 H 值较小的切分即为正确切分。通过计算和比较之后, 认为“研究/生物/科学/的/学生”是正确切分。 4.3.2 去除辅助词 经过分词得到的词汇中,其中既包含了用户查询目的的核心词汇,但也掺杂了 一些构成句子所必需的辅助词,如“的”,“地”或一些动词等一系列无意义的词, 它们不能明确表示用户要查询的内容,反而会影响查询结果的准确性。 另外根据提问句式的特点,分词后的词汇中可能包含修饰量词的词汇如“多少”, “什么”等副词。这些次虽然是用户需要查询的内容,但是对查询结果没有帮助。 因此首先建立一个过滤词表,其中包括各种组成句子所必需但又无具体意义的 字、词;然后根据过滤词表对切分完后的结果进行分析,将提问中出现在过滤词表 中的词删去,抽取出核心语义项,形成查询主题突出、概念明确的短语集合。例如: “韩正/去/法国/访问”抽取出的核心语义项即为“韩正/法国/访问”。 4.3.3 具体实现 Lucene 中分词算法主要封装在 Tokenizer 类中,所以实现逆向最大匹配分词需要 实现自己的 Analyzer,Filter,Tokenizer 类。根据逆向最大匹配分词算法本文实现 MyReverseAnalyzer,MyReverseFilter,MyReverseTokenizer。由于 3.2.4 小节中,已 经介绍了 Analyzer,Filter,Tokenizer 类的功能,本节不再重复。本节主要讲述 MyReverseTokenizer 中逆向最大匹配分词算法的具体实现。 MyReverseTokenizer 主要完成分词功能,分词流程如图 4-2。 上海交通大学硕士学位论文 自然语言检索 37 图 4-2 逆向最大匹配分词算法分词流程图 Figure 4-2 Reverse Maximum Matching word segmentation algorithm flowchart 上海交通大学硕士学位论文 自然语言检索 38 其主要分析原理如下:将字符分为三种类型:中文字符,英文字母或数字,其 他字符。MyTokenizer 判断堆栈中是否存在项,若存在移除并返回第一个项。如果堆 栈中为空。则从字符串中每次读入一个字符,如果该字符是中文字符或者英文字母 或数字时,将该字符加入缓存。当读入的字符是其他字符,或者读入的字符与缓存 中字符类型不一致,处理缓存。重复以上过程,直到处理完字符串。其中处理缓存 有两种情况:一、缓存中内容是中文字符,此时 MyReverseTokenizer 根据逆向最大 匹配切分算法对内容进行分析,得到若干词,存入堆栈,并且从堆栈中移出第一个 词;并且清空缓存;二、缓存内容为英文字母或数字,此时处理操作为:该将该内 容作为一个词汇,并且清空缓存。 因为逆向最大匹配分词算法是逆向对整句进行切分,需要采取先进后出的策略 才能得到正确的分词顺序,所以本文选择堆栈数据结构。堆栈中存在项,就是按照 逆向对句子进行切分得到的项。句首的项首先返回,句尾的项最后返回。 该算法与前向最大匹配分词算法相似。不同之处在于,前向最大匹配分词算法 中,不需要储存分词得到的项,依次返回得到的项即可。另外,前向分词算法中缓 存中的中文字符串最大长度为 4,逆向分词算法中,缓存中中文字符串最大长度是不 受限制的,是不包括标点符号和英文字符等其他字符的连续汉字的长度。 4.4 小节 本章介绍了常见的检索模型。分析了目前两种自然语言搜索引擎中现阶段的自 然语言理解技术有两大研究方向,即基于规则的分析方法和针对大规模语料库的分 析法。通过对自然语言查询的过程进行研究,最后提出了一种基于 Lucene 的自然语 言搜索引擎系统。在该系统中,通过结合前向最大匹配分词算法和逆向最大匹配分 词算法,以及通过统计学规律来处理歧义,从而提取出自然语言查询语句的核心语 义词汇,达到理解自然语言的目的。 上海交通大学硕士学位论文 检索结果排序分析 39 第五章 检索结果排序分析 随着网络进一步的发展,人们面临的问题也在逐步改变。起初众多的网络用户 难以找到有用信息,所以搜索引擎应运而生。但是现在人们却是不知如何在冗长的 搜索结果列表中选择真正满足需求的信息。所以如何评估网页与用户所提交查询的 相关度以及如何判断网页的重要性已经成为搜索引擎所亟需解决的重要问题。另外 本文中除了讨论文档相关度、网页重要性之外,将相似网页检测技术引入到过滤检 索结果集并且分析引入了一种快速排序算法来处理返回结果中的排序问题。这也是 目前搜索引擎领域研究的一个热点。 5.1 文档相关度 如何确定一个文档和某个查询的相关性,在信息检索领域有许多经典模型如布 尔模型、向量空间模型、概率模型。其中向量模型得到最广泛的应用。 5.1.1 向量空间模型 向量空间模型(Vector Space Model)根据信息库中的文档参照特征项向量 ),,,( 21 mtttT ""= 标引成相应的文档向量 )( ,,2,1 mdddD ""= ,其中 id 表示文档 D 与特 征项 it 的相关度,把查询短语标引成向量 ),,,( 21 mqqqQ ""= ,其中 iq 表示查询短语Q 与特征项 it 的相关度[41]。 由此文档与查询短语的相关性问题则转化成了向量空间中 的矢量问题,向量间的夹角代表向量的相似度U : )]()[( 1 2 1 2/)( 2/1 1 ∑•∑∑ == =•= = m i m i iqdQDU i m i ii qd (5-1) 5.1.2 权值计算公式 目前最普遍的赋权重的方法是运用统计的方法,即用文本的统计信息,主要是 词频,来计算特征项的权重。 最初的特征项权重计算方法是 0,1 赋值法,也就是所谓的布尔权重(Boolean weighting)[42]。如果特征项出现次数为 0,则其权重为零;如果特征项出现次数大于 零,则其权重为 1。由于布尔权重无法体现这个特征项在文本中的作用程度,现在已 上海交通大学硕士学位论文 检索结果排序分析 40 经不再被使用。 目前主要的采用 /TF IDF (term frequency/inverse document frequency) 公式[43]。 其中 IDF 的计算公式为 ( ) log( )i i NIDF t ln= + (5-2) 相关度 id 的计算公式可以表示为: )log( ln Ntfd i ii += • (5-3) 式中 itf 表示特征项 it 在文档 D 中的出现频率,N 表示全部训练文本中的文档数, in 表示包含特征项 it 的文档数。 IDFTF / 算法的核心思想是,在大多数文档中都出现的特征项不如只在小部分 文档中出现的特征项重要。也就是如果一个词在一篇文档中出现,但同时它也出现 在很多文档中,则降低了这个词的重要性。如“科学”在社会科学类与自然科学类 的文档中都出现,对区别两类文档的帮助就不大。 IDFTF / 算法能够弱化一些在大 多数文档中都出现的高频特征项的重要度,同时增强一些在小部分文档中出现的低 频特征项的重要度。特征权重计算唯一的准则就是要最大限度的区分不同文档。因 此特征项频率与逆文档频率通常是联合使用的,也就是权重。在向量模型中,词语 的频率,即因子用来描述文献内容,逆文档频率则用来描述文献之间的差异。 5.2 PageRank 算法分析 PageRank 是基于“从许多优质的网页链接过来的网页,必定还是优质网页”三 的回归关系,来判定所有网页的重要性。 计算 PageRank 的公式: ))( )(...)1( )1(()1()( TnC TnPR TC TPRddPPR +++−= (5-4) 其中, 1,,nTT" 是指向网页 P 的其它网页,d 是指界于(0, 1)区间的衰减系数, )( nCT 是网页 nT 向外指出的链接数目。 Lawrence Page和Sergey Brin提出了用户行为的随机冲浪模型,来解释上述算法。 他们把用户点击链接的行为,视为一种不关心内容的随机行为。而用户点击页面内 的链接的概率,完全由页面上链接数量的多少决定的,这也是上面 ()/()iiPR T C T 的原 上海交通大学硕士学位论文 检索结果排序分析 41 因。一个页面通过随机冲浪到达的概率就是链入它的别的页面上的链接的被点击概 率的和。衰减系数 d 的引入,是因为用户不可能无限的点击链接,常常因劳累而随 机跳入另一个页面。d 可以视为用户无限点击下去的概率,(1-d)则就是页面本身所具 有的网页级别。 由此可见: (1)网页 PR 值不是由一个独立的页面决定。 (2)网页 PR 值由链向它的网页的决定,但每个链入页面的贡献的值是不同的。如 果 Ti 网页的 PR 值越高,链出越少,它对当前页面 P 的贡献就越大;相反,如果 Ti 网页的 P 值越低,链出越多,它对当前页面 P 的贡献就越小。 (3)衰减系数的使用,减少了其它页面对当前页面 P 的 PR 的贡献。 5.2.1 PageRank 算法偏重旧网页 分析公式(5-4),我们可以得出结论:该公式偏重旧的网页。从公式(5-4)可以看 出,决定一个网页 PR 值的主要因素是指向该网页的链接的个数。可是如果网页刚被 放到 Internet 上不久,由于时间短暂,许多其它网页还没有发现它,当然指向该网页 的超链接数目也就很少,通过公式(5-4)计算出的 PR 值也就很低。即使该网页搜索引 擎返回的结果会把它排在较后的位置,这样,返回结果可能正好与用户的需求恰恰 相反,因为大多数情况下,用户都想首先看到最新的网页。所以,该公式计算出的 网页 PR 值并不能很好的反映网页的重要性,当然也就不能很好的满足用户的需求。 因此在通过一个网页的指入超链接来计算该网页的 PR 值时,应该考虑到网页的 日期。如果一个网页的更新日期愈接近 Spider 获取到它时的日期,就应该对网页附 加愈多的 PR 值。 以 tW 表示网页关于日期这一因素的影响,C 表示搜索引擎对其库存 URL 列表索 取一遍所需要的时间,即一个访问周期。T 表示一个网页被 Spider 访问时间与网页 的更新时间相距的天数。则有: TDWt 1⋅= 其中 T >不存在 满足 其 中 R 表示过滤前的返回结果集。 (, )simhash x y T> , (, )simhash x y 为文网页相似度,T 为规定的阀值。 (, )Score x q ,表示对于搜索项 q ,网页 x 的得分。 具体算法如下: 1. 将返回结果集中的文档根据文档得分降序排序,及得分最高网页位于最前。 2. 依次处理排序后的文档, ,,(,)() ,,(,) true y V simhash x y Tboolean x false y V simhash x y T ∈>⎧= ⎨ ∈>⎩ 不存在 满足 存在 满足 若 ()boolean x 为true ,则说明网页 x 加入过滤后的结果集合,否则网页 x 被过滤 掉。继续处理下一个网页,直到处理完所有的网页。 上海交通大学硕士学位论文 检索结果排序分析 48 5.5 排序算法改进 上文中提到,需要根据搜索结果网页的得分来对网页进行排序。本文在分析比 较各种分析算法后,对快速排序算法进行改进。通过实验证明其与其他算法相比具 有更好的性能。 5.5.1 排序算法概述 如今为人们所熟知并在广泛应用的排序算法有:冒泡排序(Bubble Sort)、选择排 序(Selection Sort)、插入排序(Insertion Sort)、堆排序(Heap Sort)、归并排序(Merging Sort)、快速排序(Quick Sort)等[53]。 冒泡排序的基本思想是:将相邻的两个数据元素按关键字进行比较,如果反序, 则交换。对于一个待排序的数据元素序列,经一趟排序后最大值数据元素移到最大 位置,其它值较大的数据元素向也最终位置移动,此过程为一次起泡。然后对下面 的记录重复上述过程直到过程中没有交换为止,则已完成对记录的排序。冒泡排序 在最好情况、平均情况和最坏情况下比较次数都是相同的,均为 2(-1)/2 ( )nn On= 。 选择排序的基本思想是:设有 N 个数据元素的序列,第一趟排序,比较 N 个数 据元素,选择关键字最小的数据元素,将其交换到序列的第 1 个位置上;第 2 趟排 序,在余下的 N-1 个数据元素中,再选取关键字最小的数据元素,交换到序列的第 2 个位置上;继续进行,经过 N-1 趟排序,N 个数据元素则按递增次序排列完成。选 择排序在最好情况、平均情况和最坏情况下比较次数都是相同的,均为 2(-1)/2 ( )nn On= 。 直接插入排序的基本思想是:当插入第 i 个数据元素 k 时,由前 i-1 个数据元素 组成已排序的数据元素序列,将 k 的关键字与序列中各数据元素的关键字依次进行 比较后,找到该插入位置 j,并将第 j 以及后面的数据元素顺序后移一个位置,然后 将 k 插入到位置 j,使得插入后的数据元素序列仍是排序的。直接插入排序在最坏情 况下比较次数是 2(-1)/2 ( )nn On= 。 堆排序的基本思想是:在排序过程中,将记录数组 R[1…n]看成是一棵完全二叉 树的顺序存储结构,利用完全二叉树中双亲节点和孩子节点的内在关系用筛选法将 待排序的数据元素序列建成堆,则根节点的值即为最大值。将根节点值向后交换, 再将余下的节点调整成堆,重复进行直到排序完成。堆排序尽管需要在排序过程中 多次调整成堆,但是由于调整成堆的操作都是log n 的,在最坏情况下比较次数为 上海交通大学硕士学位论文 检索结果排序分析 49 (log)On n 。 归并排序的基本思想是:将一个数组的两个有序部分合并成一个有序数组。不 过必须先对这两部分进行排序,这仍需要合并这两部分的有序子数组。这个将数组 分解成两半的过程不断进行,直到数组元素少于两个为止。最坏情况下比较次数为 (log)On n 快速排序的基本思想是:原始数组被分成两个子数组,第一个子数组的元素都 小于等于某选定值,称作分界或枢轴。第二个数组包含的元素大于等于枢轴。这两 个字数组可以独立排序,但在此之前,需要对这两个数组重复分割处理。其结果是 为每个子数组阁选择一个新的枢轴。第一步中获得的每个子数组被分成两段,因此 创建了四个子数组。继续这个分割过程直到所有子数组均为不需要排序的一元数组。 快速排序在最坏情况下比较次数为 2()On ,最好情况下比较次数为 (log 1) ( log )nn Onn+= (log 1) ( log )nn Onn+= 。在平均情况下,计算表明只需要 (log)On n 次比较。 5.5.2 排序算法性能比较 在平均情况下快速排序、堆排序、归并排序的比较次数都为 (log)On n 。而冒泡 排序,选择排序,插入排序的比较次数都为 2()On 。为更清楚比较排序算法性能。做 如下实验。 实验一:根据给定数组大小,随机生成整数填充数组,然后对数组进行排序。 得到实验结果如图 5-2。 0 100 200 300 400 500 600 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 数组大小(单位:1) 耗时(单位:毫秒) 冒泡排序 选择排序 插入排序 快速排序 堆排序 归并排序 上海交通大学硕士学位论文 检索结果排序分析 50 图 5-2 排序算法性能比较 Figure 5-2 Sorting Algorithm Performance Comparison 可以得出结论:可以发现快速排序、堆排序、归并排序在性能方面的优势随着 数组增大越来越明显。另外冒泡排序相比选择排序,插入排序性能较慢。 实验二:比较快速排序、堆排序、归并排序。根据给定数组大小,随机生成整 数填充数组,然后对数组进行排序。 0 2000 4000 6000 8000 10000 12000 1 2 4 8 16 32 64 128 256 512 1024 数组大小(单位:10000) 耗时(单位:毫秒) 快速排序 堆排序 归并排序 图 5-3 排序算法性能比较 Figure 5-3 Sorting algorithm performance comparison 可以得出结论:得到实验结果如图 5-3。可以发现随着数组增大,快速排序的优 势逐渐体现出来。其性能优于归并排序和堆排序。 由于快速排序性能较其他排序算法,并且在排序过程中只需要一个额外空间。 所以得到了广泛的应用。 5.5.3 快速排序算法改进 由于快速排序本身是不稳定的。也就是说经过排序,原来序列中具有相同值的 记录的次序可能发生改变。在实际应用中,这种不稳定有时是不允许的。本文对快 速排序算法做了如下改进来保证其稳定性。 主要思想:选定分界(枢轴)值 K,分别从数组起始位置 start 和结束 end 扫描 数组。从 start 开始前向查找第一个大于 K 的数,在 end 逆向开始找到第一个小于 K 的数,交换两个之数。从 start 开始查找过程中,若遇到数等于 K,则交换该数与 start 中第一个不等于 K 的数。同样从 end 开始查找,若遇到数等于 K,则交换该数与 end 中逆向第一个不等于 K 的数。处理后得到的分界位置 M。 上海交通大学硕士学位论文 检索结果排序分析 51 位于 M 之前的数值小于等于 K,位于 M 之后对数值大于等于 K。交换从 start 开始的等于 K 的数到邻近 M 位置,这样得到 M1,M1 之前的数小于 K。同理交换 end 开始等于 K 的数到邻近 M 位置,得到 M2,M2 之后的数大于 K。M1 到 M2 之 间的数等于 K,且保持原来的次序。 另外对于小数组,插入排序算法性能优于快速排序算法,并且插入排序能够保 证序列的稳定性。比较 2(1)/2,lognn n n− 可以发现当 6n <= 时, 2(1)/2 lognn n n−< 。 因此当快速排序算法中把数组分解为小于特定值的数组时。采用插入排序来代替快 速排序。通过比较发现当 11n = 时,改进后的算法得到最好的性能。 实验三;比较快速排序与改进后的快速排序。改进后的快速排序在保证了序列 稳定性的同时,在性能方面也有了一定的提升。 0 500 1000 1500 2000 2500 3000 3500 1 2 4 8 16 32 64 128 256 512 1024 数组大小(单位:10000) 耗时(单位:毫秒) 快速排序 改进后的快速排序 图 5-4 快速排序算法性能比较 Figure 5-4 Quick sorting algorithm performance comparison 5.6 小节 本章分析了文档相关度、PageRank 算法、Lucene 评分机制、相似网页检测、网 页排序算法等方面内容。Lucene 的采用了一种基于空间向量模型的评分机制。该机 制侧重于文档相关度,而忽略了文档重要性、权威性等因素,所以本文提出将 PageRank 算法应用于 Lucene 评分机制,来解决这一问题。另外本章中提出将应用 于 Spider 系统的相似网页检测算法 simhash 应用于过滤检索结果,最后对网页排序 算法进行研究,改进快速排序,改进后的快速排序具有排序稳定性并且性能也有一 定提升。 上海交通大学硕士学位论文 中文自然语言搜索系统实现 52 第六章 中文自然语言搜索系统实现 本文实现中文自然语言搜索原型系统,并对上海交通大学网络资源建立索引。 测试说明系统具有良好的性能和搜索结果。 6.1 搜索系统结构 本文搜索系统由 Spider 系统、索引系统、检索系统、用户界面四部分组成。系 统结构如图 6.1 所示。系统工作机制:Spider 在网络中爬行搜索页面并递归下载所有 在爬行范围内的页面。索引系统对 Spider 爬行搜集的页面进行文本解析,并对文本 进行分析得到索引项并储存在索引文件中。用户界面给用户提供输入搜索语句的接 口,并对检索系统返回的结果进行处理,最后友好的返回给用户。检索系统通过对 搜索语句的分析,并在索引文件中检索匹配的索引项,得到检索结果,再有检索结 果处理系统进行网页排序,相似文档检测等,并将结果返回给用户界面。 图 6-1 中文自然语言搜索引擎系统框架 Figure 6-1 Structure of Chinese natrual language search engine system 6.2 Spider 系统 本文采用我 WebLech URL Spider 系统。WebLech 是由 Java 编写的多功能网络站 定下载工具。它的一些基本特性使其自身具备网站下载以及网络浏览功能。像其他 用户界面 搜索语句分析系统 检索结果分析系统 Lucene 检索系统 索引存储文件 Spider 系统 HTML 解析器 Lucene 索引系统 检索系统 索引系统 上海交通大学硕士学位论文 中文自然语言搜索系统实现 53 工具一样,WebLech 可以在网络中爬行搜索页面并递归下载所有在爬行范围内的页 面。 6.2.1 WebLech 的特性 WebLech 有一些值得关注的特性: ¾ 开源的 MIT 许可证:你可以免费得到它,使用它,并基于它进行进一步开 发。 ¾ 纯 java 代码:能够运行在任何可运行 java 程序的机器上。 ¾ 多线程:能同时下载大量文件。 ¾ 支持基本的 HTTP 认证:能够访问需要用户认证的网站。 ¾ HTTP 引用器:能够保持网站之间的链接信息。 ¾ 大量可选设置 — 搜索策略选择:深度优先/广度优先。 — URL 过滤器:可以选择在一个指定网站服务器,一个目录服务器甚至是 整个网络中进行爬行搜索。 — URL 优先级设置:能够在爬行搜索过程中赋予某些站点较高优先级而给 予另一些站点较低优先级。较高的优先级意味着在爬行搜索过程中首先 被搜索并下载。 — 可配置的下载文件缓冲区:支持断点续传 — 检查点:可以在 WebLech 运行爬行搜索过程中快照爬行状态,该状态称 为检查点。从检查点重新开始爬行将避免许多不必要的预处理。 6.2.2 Spider 系统搜索策略选择 由于 Internet 上文档数量巨大,所以 Spider 搜索整个 Internet 时,遍历的策略问 题非常重要,尤其是几乎不可能遍历整个 Internet 时。 遍历的基本算法有深度优先和广度优先,采用何种方式遍历,需根据具体情况 来确定。目前许多搜索引擎采用了广度优先算法。通过页面间的链接,Spider 完成在 页面间的移动。 广度优先遍历过程是从开始节点开始访问,并将访问所有子节点存入 FIFO(先 进先出)队列中。然后访问队列中移出第一个节点,访问该节点,并将其所有子节 点存入队列中,重复上面过程知道队列中不存在节点,遍历完成。广度优先搜索的 一个特征是:当发现目标节点时,我们已经找到了到达目标的一条最短路径。然而 上海交通大学硕士学位论文 中文自然语言搜索系统实现 54 广度优先搜索的一个缺点是它要求产生和存储一个大小是最浅目标节点深度的指数 的树。由于广度优先遵循的原则是 FIFO(先进先出)方式,即新获取的超链接加入 URL 列表的尾部。这一策略的优点是尽可能快速地访问各个 Web 站点,保证各站 点上至少有一份文档被下载,另一优点是对各站点的访问比较均匀,不会在短时间 内造成对某个站点服务器的巨大冲击。缺点是不能深入 Web 站点内部,因此也难以 发现站点内部的层次关系。 深度优先遍历是从开始节点开始访问,然后对访问节点的子树依次进行深度优 先遍历。递归完成上面过程知道所有节点都被遍历。实际应用中为了防止从开始节 点的搜索过程深度太深,需要一个深度约束(depth bound)。超过这个深度约束时不再 进行访问。深度优先算法使我们只保存搜索树的一部分,它由当前正在搜索的路径 和指示该路径上还没有完全展开的节点标志构成。因此,深度优先搜索的存储器要 求是深度约束的线性函数。深度优先搜索的一个缺点是当发现目标时,我们不能保 证找到的路径是最短长度。另一个缺点是如果只有一个很浅的目标,且该目标位于 搜索过程的后部时,也必须浏览大部分搜索空间。Spider 在对第一个文档进行分析后, 取回第一个链接所指向的页面,然后分析此页面,再取回其第一个链接所指向的文 档,反复执行下去。深度优先策略能够较好地发掘文档结构。但是采用这样的搜索 算法对网络和服务器的冲击较大,将长时间占用某段网络的带宽和服务器的资源。 不仅对网上其他用户使用带来影响,严重时甚至会发生网络拥塞和服务器崩溃。 由于本文并不需要完整索引 sjtu.edu.cn 的所有资源,对于站点内部的层次关系并 不关心,另外由于深度优先搜索会给校园网络、服务器,、以及其他用户带来影响本 系统中采用广度优先算法。 6.2.3 WebLech 系统配置 由于本文系统仅对上海交通大学网络资源进行全文索引。考虑到减少 Spider 对 网络造成的影响本系统采用单线程进行搜集网络资源。网络资源从 http://bbs.sjtu.edu.cn 开始搜索,仅搜集 URL 包含 sjtu.edu.cn 的网络资源。为控制网 络流量仅下载 htm、html、shtm、shtml 形式的资源。 设置配置文件如下: # Set the extensions the Spider should use to determine which # pages are of MIME type text/html. The Spider also learns new # types as it downloads them. htmlExtensions = htm,html,shtm,shtml # Similarly for MIME type image/* 上海交通大学硕士学位论文 中文自然语言搜索系统实现 55 imageExtensions = none # URL at which we should start the spider startLocation = http://bbs.sjtu.edu.cn/ # Whether to do depth first search, or the default breadth(width first search) # first search when finding URLs to download depthFirst = false # Maximum depth of pages to retrieve (the first page is depth # 0, links from there depth 1, etc). Setting to 0 is "unlimited" maxDepth = 4 # Basic URL filtering. URLs must contain this string in order # to be downloaded by WebLech urlMatch = sjtu.edu.cn # Number of download threads to start spiderThreads = 1 6.3 索引系统 本原型系统中的索引系统由 HTML 解析器和 Lucene 检索系统两部分组成。其中 HTML 解析器对 htm,html,shtm,shtml 文件进行解析,解析得到文本文件。再利 用 MyAnalyzer 分析器对文本信息进行分析,利用 Lucene 索引系统对分析结果进行 处理建立索引. 6.3.1 HTML 解析 HTML 文档是由 HTML 元素构成的文本文件。HTML 元素是通过使用 HTML 标签进行定义的。这个 HTML 元素由起始标签开始,以由终止标签结尾,中间为元 素的内容,通常为文本内容。 常见的 HTML 起始标签如、
、<body>、<div>、<table>、 <thead>、<tbody>、<tfoot>、<tr>、<td>,相对应的终止标签为</html>、</header>、 、、
、、、、、、。 HTML 解析器通过对 HTML 标签进行识别,提取需要的文本信息。文本中 HTML 解析器提取中的文本信息作为网页标题,提取中的文 本信息作为网页内容。 上海交通大学硕士学位论文 中文自然语言搜索系统实现 56 6.3.2 建立索引 本系统仅对网页正文进行分词,建立索引,将索引信息保存本地磁盘。对于网 页标题和网页 URL,并不进行索引,只是作为关键词保存在本地。伪代码如下: Document document = new Document(); document.add(new Field("url", url, Field.Store.YES, Field.Index.NO)); document.add(new Field("title",title,Field.Store.YES,Field.Index.TOKENIZED)); document.add(new Field("content", content, Field.Store.NO,Field.Index.TOKENIZED)); indexWriter.addDocument(document); Lucene 提供以下四种不同类型的域。 Keyword 域:不需要被分析,但是会被逐字地被索引并存储。该类型适用于原 始值,也就是需要被全部保留的域,如 URL、文件系统路径、日期、个人姓名、社 会保险号码、电话号码等。 UnIndexed 域:既不需要被分析也不需要进行索引,但是该值同样被存储在索引 文件中。该类型适用于需要和搜索结果一起被显示出来,但用户不会将它的值直接 用于搜索的情形。 UnStored 域:与 UnIndexed 类型域相反,该类型需要分析并索引,但是不需要 存储在索引文件中。该类型适用于索引那些不需要以其原始形式进行检索的大量数 据文本,比如网页的这个正文,或者其他类型的文本文档等。 Text 域:需要被分析且索引。这意味着该类型的域能够被搜索,但是要注意域 的大小。如果被索引的数据是一个字符串,它将会被存储起来,但是如果是数据来 自数据流对象,那么它将不会被存储在索引文件中。 6.4 检索器 本系统检索器由搜索语句分析系统、Lucene 检索器和检索结果分析系统三部分 组成。搜索语句分析系统对用户输入的语句进行理解,创建搜索项,然后由 Lucene 检索器负责检索并将检索结果交给检索结果分析系统进行处理,最后检索结果分析 系统对 Lucene 检索器检索的结果进行相似文件检测,根据网页得分排序然后以 HTML 文件形式返回给用户。 搜索语句分析系统主要负责对用户输入的语句进行解析,分析得到用户输入语 句核心语义词汇。首相根据正向最大匹配算法和逆向最大匹配算法对搜索语句进行 分词,如果分词结果进行停顿词过滤、得到用户核心语义词汇。如果正向最大匹配 算法和逆向最大匹配算法分词结果不同,可以利用词句切分概率对歧义字段进行处 理,具体做法如下:对公式 4-1,公式 4-2 进行简化得到切分效率的比较公式为: 上海交通大学硕士学位论文 中文自然语言搜索系统实现 57 '' ' 12 12 () () () () () ( ) t m f wfw fwV f wfw fw × ××= ××× " " (6-1) 其中 ()if w 表示前向最大匹配算法分词得到的第i 个词 iw 的词频, '()if w 表示逆 向最大匹配算法分词得到的第i 个词 ' iw 的词频。这里词频指语料库中出现的次数。 当计算结果 1V > 时采用前向最大匹配算法的分词结果,否则采用逆向最大匹配 算法的分词结果。 由于 Lucene 中索引是由文档为单位的,每个文档的项频率在.frq 文件中列出。 但是这不能帮助用户得到某关键字的词频。所以本文采用根据互联网中统计词频得 到的带词频的词典。 6.5 用户界面 用户界面是非常简洁的页面,由用户输入搜索语句,页面返回相应的链接。比 如搜索“上海交通大学校长”得到如下图 6-2 图 6-2 中文自然语言搜索引擎系统截图 Figure 6-2 Snap shot of Chinese natrual language search engine system 6.6 小节 本章实现了中文自然语言搜索引擎原型系统。通过采用开源 Spider 系统 上海交通大学硕士学位论文 中文自然语言搜索系统实现 58 WebLech,搜集域名包括 sjtu.edu.cn 的网页,通过 HTMLParser 对网页文件进行解析 得到文本内容,并对这些文本信息进行索引,得到索引文件。实现支持自然语言理 解的查询结构从而实现中文自然语言搜索引擎原型系统。 上海交通大学硕士学位论文 总结与展望 59 总结与展望 信息检索乃是人类智慧活动的基础,是人类的最重要的活动之一。搜索引擎技 术的研究可谓博大精深,综合了许多信息技术其它领域的理论和技术。在刘功申老 师的悉心指导下,以及同课题组的同学的热心支持下,通过两年的辛勤研究,作者 对搜索引擎技术有了一定的了解,并在 Lucene 搜索引擎技术的基础上,对本地化、 智能化等研究领域有了较为深入的研究,取得了一些成果。本文的研究内容主要包 括如下方面: ¾ 中文分析器的研究 针对目前应用于搜索引擎 Lucene 的中文分析器的分词不符合汉语习惯的现状, 本文根据正向最大匹配切分算法和采用包括基本标准中文词语的词库,实现了自己 的分析器。该分析器的分词结果更符合汉语的习惯,并且在分词,建立索引等方面 的性能非常接近基于机械分词的分析器,另外在检索速度方面性能提升了 2-4 倍,在 检索召回率方面性能提升了 59%。 ¾ 自然语言检索接口设计的研究。 自然语言查询比较于其他检索方式,更贴近人类的生活习惯,使这种人机交流更 加人性化。分析用户提交的自然语言检索,介绍了常见自然语言接口模式。并且提 出正向最大匹配切分算法、逆向最大匹配切分算法实现以及词频统计的方法来对用 户搜索语句中核心语义项的有效提取。 ¾ 检索结果排序的研究。 如何把用户需要的结果最好的展现给用户,是衡量一个系统好坏的重要依据。本 文通过对网页相关度、PageRank 算法、Lucene 评分系统进行研究,提出将 PageRank 算法引入 Lucene 评分系统,让系统能够将更重要的网页更好的返回给用户。同时利 用 simhash 算法来计算返回页面之间的相似度,检测过滤相似网页,使得返回用户的 信息没有冗余信息。并且通过对排序算法的研究,改进原有快速排序,这样能够更 快的将结果返回给用户。 ¾ 完成了自然语言搜索引擎原型系统的设计和实现。 原型系统对上海交通大学网络资源进行整合。试验证明,改原型系统具有较好的 性能和实用性,为后续相关的研究工作提供了良好的平台。 两年多的研究时间漫长而又短暂。由于时间、水平和资源等方面的原因,许多 工作有待于在现有研究成果上深入进行。我们认为,以下几个方面是急需做的,也 上海交通大学硕士学位论文 总结与展望 60 可能在不久的将来取得突破性进展: ¾ 搜索引擎技术的检索和索引都依赖与分析器,对于中文信息而言,分词效果是非 常重要的。本文的在索引,检索性能和效果方面都取得了一定进步。但是对于地 名、人名、特殊事件名等概念词典未登录的敏感特征词,模型如何更加合理的处 理,这些都有待于深入研究。 ¾ 基于向量空间模型,PageRank 算法和 Lucene 评分系统,本文提出将 PageRank 算法进行改进,并应用与 Lucene 搜索引擎系统。但是对于 PageRank 算法的研究 还不够深入,除文中提到的各种因素对 PageRank 值有影响外,还存在其他因素 对 PageRank 值存在影响,并且每种因素的影响是不同的,这些需要更多的实验 数据来衡量,得到更加接近用户实际使用习惯的 PageRank 算法。 ¾ 本文将 simhash 算法应用于过滤检索系统返回结果中的相似文档。一定程度上克 服在 spider 系统中应用检测相似文档过滤的困难。但是由于 spider 系统没有对相 似文档进行过滤,一定程度上还是需要增大了网络流量,给系统带来了更重的负 担。所以研究如何在 spider 系统中应用相似文档检测技术是值得深入的研究。 ¾ 本文的自然语言系统利用多种基于字典的分词算法相结合,对用户搜索语句进行 分词,虽然在一定程度上面能够实现正确的分词,并且提取出用户的核心词汇项。 这离真正理解用户的需要还是有很大的距离。如何理解用户所搜索的关键词的含 义以及多个关键词之间的关联,从而找出符合人类思维的真正的相关结果,仍然 是自然语言理解研究的重大课题,期待着进一步的研究。 物质、能源和信息是人类社会三项基本资源。目前,灰色的信息资源正在逐步 替代黑色的矿业资源和绿色的农业资源成为人们竞争的重点。信息已经成为一种新 的财富,掌握信息就能够掌握未来。随着信息的飞速增长,信息检索技术面临的挑 战将越来越严峻。网络信息检索的智能化、个性化,已成为互联网时代的大势所趋, 许多研究工作值得我们付出青春和智慧去求索。 上海交通大学硕士学位论文 参考文献 61 参考文献 [1]Sergey Brin,Lawrence Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine[C]. Comm. ACM 1997 [2]Moese S.Charikar. Similarity Estimation Techniques from Rounding Algorithms[C]. Comm. ACM 2002 [3]骆卫华 刘群 张俊林. 搜索引擎:性能提高遇到瓶颈[J] 计算机世界报 2006 第 30 期 [4]许欢庆. 个性化定题搜索引擎原型系统的研究 上海交通大学博士论文 2003: 5-6 [5]郎小伟 王申康. 搜索引擎技术研究与发展[J] 计算机工程 2006 第 2 期 [6]Otis Gospodnetic, Erik Hatcher 著, 谭鸿 黎俊鸿 周鹏等译. Lucene IN Action[M] 北京:电子工业出版社 2007:97-99 [7]Jiangfeng Gao, Mu Li, Andi Wu etc. Chinese Word Segentation: A Pragmatic Approach[J] Microsoft Research Novermber 2004 [8]张校乾 金玉玲 侯丽波. 一种基于 Lucene 检索引擎的全文数据库的研究与实 现[J] 信息检索技术 2005 [9]车东.开放源代码的全文检索引擎 Lucene www.lucene.com.cn [10]孙西全 马瑞芳 李燕灵. 基于 Lucene 的信息检索的研究与应用[J] 信息系统 2006 [11]Doug Cutting. Lucene lecture at Pisa http://lucene.sourceforge.net/talks/pisa/ [12]孙茂松 左正平 黄昌宁. 汉语自动分词词典机制的实验研究[J] 中文信息学 报 2003 年 2 月 [13]陈士杰 张玥杰. 基于 Lucene 的英汉跨语言信息检索[J] 计算机工程 2005 [14]高琰 谷士文 谭立球等. 基于 Lucene 的搜索引擎设计与实现[J] 微机发展 2004 [15]车东. 在应用中加入全文检索功能——基于 Java 的全文索引引擎 Lucene 简 介 http://www.chedong.com/tech/lucene.html 2003 [16]Otis Gospodnetic, Erik Hatcher 著, 谭鸿 黎俊鸿 周鹏等译. Lucene IN Action[M] 北京:电子工业出版社 2007:135-137 上海交通大学硕士学位论文 参考文献 62 [17]车东. 在应用中加入全文检索功能——基于 Java 的全文索引引擎 Lucene 简 介 http://www.chedong.com/tech/lucene.html 2003-09 [18]李振星 徐泽平 唐卫清等. 全二分最大匹配快速分词算法[J] 计算机工程与 应用 [19]Jianfeng Gao, Mu Li and Chang-Ning Huang Improved Source-Channel Models for Chinese Word Segmentation[J] Microsoft Research 2005 [20]王永成. 中文信息处理技术及其基础[M] 上海:上海交通大学出版社.1991 125-213. [21]张旭. 一个基于词典与统计的中文分词算法[J] 电子科技大学硕士学位论文 2007 年 11 月 [22]丁丰 董娜 林碧琴等. 自然语言处理系统中自动分词的研究[J] 北方交通大 学学报 1999 年 6 月 [23]欧振猛 余顺争. 中文分词算法在搜索引擎应用中的研究[J] 计算机工程与应 用 2000 [24]刘小冬. 自然语言理解综述[J] 统计与信息论坛 2007 [25]张岭. 智能信息检索中的 Web 挖掘研究 上海交通大学博士学位论文 2002 [26]姚天顺 朱靖波 张利. 自然语言理解:一种让机器懂得人类语言的研究 [M].北京:清华大学出版社 第二版,2002.212-253. [27]王献昌. 机器翻译与自然语言处理的现状与趋势[J] 计算机科学 1992 [28]王灿辉 张敏 马少平. 自然语言处理在信息检索中的应用综述[J] 中文信息 学报 2007 [29]殷杰 董佳蓉. 论自然语言处理的发展趋势[J] 自然辩证法研究 2008 [30]熊回香 夏立新. 自然语言处理技术在中文全文检索中的应用[J] 情报理论与 实践 2008 [31]吴江 中文自然语言理解技术与智能检索[J] 图书馆学研究 2006 [32]钱兵 王永成 高凯. 面向搜索引擎的自然语言理解的设计与实现[J] 计算机 应用研究 2006 年 [33]王梃 陈火旺. 一种自适应词性标注方法[J]. 软件学报,1997,8 (12) :937~943 [34]于江德 樊孝忠 尹继豪. 隐马尔可夫模型在自然语言处理中的应用[J] 计算 机工程与设计 2007 [35]何莘 王琬芜. 自然语言检索中的中文分词技术研究进展及应用[J] 情报科学 2008 上海交通大学硕士学位论文 参考文献 63 [36]James Allen.Natural Language Understanding(2nd edition)[M].The Benajmins Cummings Publishing Company Inc.2004.63-92. [37]刘群. 汉语词法分析和句法分析技术综述[C].第一届学生计算语言学研讨会 专题讲座,2002.32-37. [38]金澎 刘毅 王树梅. 汉语分词对中文搜索引擎检索性能的影响[J] 情报学报 2006 [39]Pscale Fung, Grace Ngai, Young Sheng Yang etc. A Maximum-Entropy Chinese Parser Augmented by Transformation-Based Learning[C] ACM 2004 [40]贺胜. 面向现代汉语文本处理的全文检索、自动分词通用系统 南京师范大学 硕士学位论文 2006 年 4 月 [41]Baeza-Yates R, Ribeiro-Neto B. Modern Information Retrieval[M]. 北京: 机械 工业出版社, 2004. [42]贾玉祥 昝红英 范明. 基于概率模型的网页相关度研究[J] 全国第八届计算 语言学联合学术会议 2005 年 [43]Singhal A. Modern Information Retrieval: A Brief Overview[EB/OL].(2001-11). http://www.cs.uiuc.edu/class/fao5/cs511/Spring05/lectures/ieee-2001, pdf. [44]Otis Gospodnetic, Erik Hatcher 著, 谭鸿 黎俊鸿 周鹏等译. Lucene IN Action[M] 北京:电子工业出版社 2007:72-74 [45]K. Bharat, A. Broder, J. Dean, etc. A comparison of techniques to find mirrored hosts on the WWW[C] Proceedings of the ACM Conference on Digital Libraries, 1999. [46]S. Schleimer, D. Wilkerson, A. Aiken. Winnowing. Local algorithms for document fingerprinting[C] ACM 2003 [47]Eui-Kyu Park, Seong-In Moon, Dong Yul Ra etc. Web Document Retrieval Using Sentence-query Similarity[C] Text REtrieval Conference 2002 [48]S. Chakrabarti. Mining the Web: Discovering Knowledge from Hypertext Data. Morgan-Kau_man, 2002. [49]M. Charikar. Similarity estimation techniques from rounding algorithms. In Proc. 34th Annual Symposium on Theory of Computing (STOC 2002), pages 380-388, 2002. [50]A. Gionis, D. Gunopulos, and N. Koudas. E_cient and tunable similar set retrieval. In Proc. SIGMOD 2001, pages 247-258, 2001. [51]J. Dean and S. Ghemawat. MapReduce: Simpli_ed data processing on large clusters. In Proc. 6th Symposium on perating System Design and Implementation (OSDI 2004), pages 137-150, Dec.2004. [52]Gurmeet Singh Manku, Arvind Jain, Anish Das SARMA. Detecting NearDuplicates for Web Crawling[C]. ACM 2007 上海交通大学硕士学位论文 参考文献 64 [53]Adam Drozdek 著 周祥译 数据结构与算法[M] 北京:机械工业出版社 第二 版 2006:349-370 上海交通大学硕士学位论文 致谢 65 致 谢 转眼间,两年半的时间过去了,我也即将完成硕士学业。在此,向过去一直关心 我,帮助我的老师们,同学们,朋友们表示我衷心的感谢。 首先,我要感谢我的导师刘功申副教授。在学习方面,刘老师以渊博的学科知识, 严谨的科学态度,精益求精的工作作风,深深的感染和激励着我们。在生活方面, 刘老师以平易近人的处世风格,无微不至的关心照顾我们每一个学生。本研究及学 位论文也是在刘老师的悉心指导下完成的。从课题的选择到项目的完成,刘老师都 始终给予了悉心的指导和不懈的支持。并且在论文写作阶段,刘老师多次认真阅读, 修改论文,并且提出了许多宝贵的修改意见。每当我研究和论文没有头绪的时候, 刘老师都会帮我理清思路,指明方向,正因为能这样,我才能顺利完成项目研究和 论文撰写。在此,谨向刘老师致以最诚挚的感谢和崇高的敬意。 同样感谢实验室的兄弟姐妹们,因为你们实验室才有良好的研究氛围;因为你们 实验室才充满欢声笑语;因为你们我才不再畏缩在寝室;因为你们我才学会了探讨。 我会记得我们之间的共同度过的美好日子。有的师兄师姐,已经离开学校,在各个 不同的工作岗位为祖国和任命奉献自己的青春。而我们也即将离开学校,奔赴到不 同的地方。在此,祝福所有的兄弟姐妹们身体健康,事业有成。 另外,我要感谢我的室友金晶同学。他在我刚来上海时候帮助我认识和适应了新 的生活环境和学习氛围。另外他帮助我提高英语听说读写的水平。在此,表示衷心 的感谢。 最后,感谢所有关心和支持我的朋友、家人。 上海交通大学硕士学位论文 攻读硕士学位期间发表的学术论文 66 攻读硕士学位期间发表的学术论文 发表论文 [1] 胡长春,刘功申 一种面向搜索引擎 Lucene 的中文分析器 计算机工程与应用 (已录用) 上海交通大学硕士学位论文 攻读硕士学位期间参加的科研项目 67 攻读硕士学位期间参加的科研项目 参加项目 [1] 国家自然科学基金项目:开放式文档同构引擎(ODIE)研究,编号:60502032 [2] 国家自然科学基金项目:网络舆论发展趋势分析核心技术研究,编号:60672068 基于Lucene的中文自然语言搜索引擎 作者: 胡长春 学位授予单位: 上海交通大学 本文链接:http://d.g.wanfangdata.com.cn/Thesis_D068668.aspx
还剩74页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 10 金币 [ 分享pdf获得金币 ] 3 人已下载

下载pdf