《互联网信息检索系统的研究与实现本科毕业论文.doc》由会员分享，可在线阅读，更多相关《互联网信息检索系统的研究与实现本科毕业论文.doc（59页珍藏版）》请在三一办公上搜索。
1、毕业论文互联网信息检索系统的研究与实现摘 要互联网信息检索系统(搜索引擎)是专门提供信息检索服务的平台，它将互联网上大量的网页数据采集到服务器，经过处理形成的信息数据库和索引数据库，实现对用户提出的各种信息检索作出响应。本系统使用Microsoft Visual Studio 2005为主要开发工具，以Windows Server 2003操作系统为运行环境，主要实现了网页数据的抓取，网页数据存储，数据的索引，数据的检索，日志管理等功能。本文对互联网信息检索统中几个关键技术的设计和实现进行了研究。从理论上对这些关键技术进行了详细的讨论，并完成了基于L互联网信息检索系统的实现。文章从下面几个方面
2、进行了讨论：首先，本文介绍搜索引擎的市场需求和研究状态。这一部分阐述了搜索引擎丰富的历史背景和客观的用户需求，自身的特点，以及人们对搜索引擎的关注程度。其次，本文讨论了搜索引擎中基本结构、实现的理论基础和实现方法。这一部分研究了搜索引擎的关键技术，将中文分词技术、数据采集技术和数据索引技术有机的结合起来，并对全文检索引擎L进行分析和研究。最后，详细描述了一个基于L的互联网信息检索系统的设计与实现。关键词 搜索引擎；L；数据存储；信息检索ABSTRACTInternet information retrieval system (search engine) is designed to pro
3、vide a platform for information retrieval services.It will collect a lot of pages data on the Internet to the server,and processed form of the information database and index database.Made to achieve the user to respond to the various information retrieval. The system uses Microsoft Visual Studio 200
4、5 as the main development tool, to run Windows Server 2003 operating system environment, the main achievement of the web crawl data, web data storage, data indexing, data retrieval, logging management and other functions.In this paper, several Internet information retrieval system design and impleme
5、ntation of key technologies were studied. Theory on these key technologies are discussed in detail, and completed the Internet information retrieval system based on L realization. The article discussed the following aspects:First of all, the article describes the search engine market demand and rese
6、arch status.This part discusses the search engine rich historical background and objective of the user requirements, its own characteristics, as well as people paid more attention to search engine.Secondly, the article discusses the basic structure of search engines, to achieve the theoretical basis
7、 and implementation methods. This part of the search engines key technology, Chinese word segmentation, data acquisition and data indexing technology combine organic, and full-text search engine L on analysis and research.Finally, a detailed description of an Internet-based L Information Retrieval S
8、ystem Design and Implementation.Keywords Search Engine;L;Data Storage;Information Retrieval毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得 及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。作 者 签 名： 日 期： 指导教师签名：
9、 日期： 使用授权说明本人完全了解 大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。作者签名： 日 期： 目 录1 绪论11.1 互联网信息检索系统的市场需求11.2 搜索引擎技术现状及发展动向21.2.1 搜索引擎技术现状21.2.2 搜索引擎技术发展方向41.3 研究目的和研究内容61.4 文章内容安排62 搜索引擎技术82.1 搜索引擎体系结构82.1
10、.1 Crawler82.1.2 Indexer102.1.3 Searcher112.2 搜索引擎的性能指标122.3 中文分词算法132.3.1 基于字符串匹配的分词方法132.3.2 基于理解的分词方法162.3.3 基于统计的分词方法162.4 实际系统研究172.4.1 Google的整体结构172.4.2 Google的工作过程173 L的分析研究203.1 L介绍203.2 L系统结构分析213.2.1 系统结构组织213.2.2 索引文件分析233.2.3 数据流分析253.3 基于L的应用开发274 系统设计304.1 系统特点304.2 系统总体结构设计304.2.1 配置
11、管理模块304.2.2 数据抓取模块314.2.3 数据索引模块314.2.4 数据检索模块314.2.5 日志管理模块314.3 系统处理流程设计324.3.1 数据抓取处理流程324.3.2 数据索引处理流程334.3.3 数据检索处理流程345 系统实现365.1 多线程网页数据抓取365.1.1 数据抓取主界面设计365.1.2 多线程的实现375.1.3 网页文件下载395.2 HTML文档的扫描与分析415.3 数据的索引425.3.1 数据索引主界面设计425.3.2 索引网页数据435.4 数据的检索455.4.1 数据检索主界面设计455.3.2 检索索引数据456 系统测试
12、476.1 测试基础476.2 测试内容476.2.1 模块测试476.2.2 集成测试48结束语50致 谢51参考文献52互联网信息检索系统的设计与实现1 绪论随着互联网(Internet)的出现和普及，人们的信息来源得到了极大的丰富，互联网成为了人们获取信息的主要来源之一。在Internet信息不断增长的情况下，如何快速准确的获取所需信息成为研究热点之一。搜索引擎技术(Search Engine)就是在这种需求背景下发展起来的。传统的信息检索技术是从一定规模的文档库中获取用户需求的信息，其核心是重要文本信息的索引和检索。在信息量不大的情况下，传统的信息检索能够满足需求。当面对Interne
13、t上分散存储，动态变化的海量数据时，传统的信息检索技术就无法让用户快速找到所需要的信息了。搜索引擎技术作为传统IR(Information Retrieval)技术在Internet上的扩展，涉及到Web数据的采集，中文分词技术，倒排索引，海量数据存储，用户行为分析等关键技术。从功能上讲，搜索引擎重要由信息的采集，索引和查询三部分组成。搜索引擎首先通过信息采集器(Crawler，又名网络蜘蛛)从Internet中采集网页数据，然后通过索引器(Indexer)对采集的数据进行分析，并创建索引。检索器(Searcher)负责接受用户查询的请求，一般采用Web形式，通过索引找到相关信息的网页数据，返
14、回给用户。为了满足系统的稳定性、可靠性及缩短系统开发周期，本系统采用Microsoft Studio Visual 2005作为开发平台，以PC机和Windows Server 2003为测试环境，借助L实现了互联网信息检索的基本功能。1.1 互联网信息检索系统的市场需求随着信息技术的快速发展，互联网得到了飞速的发展，成为人们学习、工作、生活中的最重要的知识和信息来源。关于网页的数目没有具体的统计数据，但根据CNNIC第23次报道，中国当前拥有的网页数己经超过160亿。Internet上的信息资源随着Internet的发展而呈现出以下特点：(1) 信息量大而且分散(2) 自治性强(3) 信息资
15、源多种多样(4) 不一致和不完整性为了获取所需的信息，用户需要借助一定的工具，他们通常使用以下两类网站：第一类是目录系统，其典型代表是Yahoo!。它通过有专业知识的网页编辑人员对网上的网页进行精选，建立一个索引目录，来给用户提供服务。这类通过手工维护得很好的系统的优点是提供的网页准确率高，可以有效的覆盖热门的主题，但它们的缺点是过于主观，而且需要高昂的代价来建立和维护，更新改进的慢，同时不可能覆盖所有的主题。第二类是搜索引擎，搜索引擎通过程序自动地从网上搜集和分析网页，建立索引，为用户提供服务。这类自动更新的搜索引擎优点是涵盖的网页数量巨大，同时拥有基于关键字的全文索引，它为所有网上冲浪的用
16、户提供了一个入口，用户可以从搜索引擎出发到达自己想去的网上任何一个地方。搜索引擎对用户是这样的重要，自然成为了用户上网的常用服务，根据中国互联网络发展状况统计报告，用户经常使用的网络服务是：电子邮箱(92.6%)、搜索引擎(68.3%)、软件上传或下载服务(45.3%)、信息查询(42.2%)。1.2 搜索引擎技术现状及发展动向1.2.1 搜索引擎技术现状由于搜索引擎巨大的商业价值和学术研究价值，各大公司都在投巨资进行搜索引擎的研制开发，不断地涌现出新的具有不同特色的搜索引擎产品。同时，各大科研机构和大学纷纷展开对搜索引擎技术相关领域的学术研究。作为IR领域中最重要的会议之一，TREC(Tex
17、t REtrieval Conference)从1999年11月的第8届开始增加Web Track竞赛项目，考察Web文档与其它类型文档在性质上的不同之处，测试在大规模的Web文档集上进行信息检索的算法性能。在IEEE主办的国际万维网会议(International World Wide Web Conference)和ACM主办的人机交互会议(Computer Human Interaction，CHI)等重要学术会议上，发表了越来越多的关于搜索引擎技术研究的文章。搜索引擎己经成为信息检索领域中最活跃的研究方向。Stanford大学在其DLI项目中开发了Google搜索引擎，在Web高效搜索
18、、大规模索引、文档的相关度评价等方面作了深入的研究，提出了一种基于链接的网页排名算法(PageRank算法)来计算网页的排名，并同时利用锚文本(Anchors)信息进行网页相关度评价。IBM Almaden研究中心研制了Clever系统，提出了类似于PageRank的HITS算法，主要不同是将网页分为Authority和Hub两类，并就HITS算法在相关度评价、网页分类、主题搜索等方面的作用进行了研究。NEC美国研究所开发了一个专门用于搜索学术文章的Research Index。其目的是建立一个网上图书馆，只收集科技人员广泛使用的PDF和Postscript文件，用“PDF”，“ Postsc
19、ript”等检索项组成查询送往其他著名的搜索引擎，对返回的结果进行信息提取(主题、摘要、作者、引用文献等)，组成了一个27万篇文献的索引库，供科技人员查询。现在，NEC开始致力于下一代元搜索引擎Inquirus的开发。国内先后有北京大学、清华大学、华南理工大学、国家智能研究中心等高校和研究单位对搜索引擎技术进行了研究，开发出了几个实用的系统。清华大学开发的“网络指南针”，利用智能、高效的网络搜索算法收集网页，自动识别和转换常见的中文编码，向用户提供中文、英文、拼音、英汉翻译、BIG5码等多种输入查询服务，并提供普通分类、学科分类、图书分类查询，共计3900多个分类目录，收集的网页超过20万页。
20、北大的“天网”中英文搜索引擎，在系统规模及系统性能方面达到了国外中型搜索引擎系统的技术水平，目前天网搜索引擎维护的文档数量达到 6亿之多，并正在以平均每月一千万页文档的数量扩大着规模。天网搜索的中文文档数量超过4亿，其中包括html、txt、pdf、doc、ps、ppt等多种类型的文档和资源。在功能、性能、查准率、查全率等方面基本达到了实用。华南理工大学的“木棉”搜索引擎，分Web检索和FTP检索两大部分。Web检索支持中英文混合查询、布尔查询、结构属性查询、模糊查询等多种查询方式。FTP检索实现基于文件主要属性的结构查询，以及模糊匹配等。目前系统收集约50万网页。1.2.2 搜索引擎技术发展
21、方向经过了多年的发展，现在的搜索引擎功能越来越强大，提供的服务也越来越全面。据研究统计，目前Internet上搜索引擎已达数千种之多。然而，随着多元化信息的增长，统一的用户入口己经不能满足用户的更深入的查询需求，搜索引擎将向智能化、个性化、精确化、专业化、交叉语言检索、多媒体检索等适应不同用户需求的方向发展。(1) 智能化搜索智能化是搜索引擎未来的发展方向。搜索引擎的智能化体现在两方面：一是对搜索请求的理解，二是对网页内容的分析。通过智能代理技术对用户的查询计划、意图、兴趣方向进行推理，自动进行信息搜集过滤，将用户感兴趣的信息返回给用户。这其中也包含了对服务多项化、个性化，结果精确化，交叉语言
22、检索等方面的功能。(2) 个性化搜索个性化搜索引擎的核心是通过跟踪分析用户的搜索行为，充分地利用这些信息来提高用户的搜索效率。这种搜索行为分析技术是一种正在发展中的很有前途的搜索引擎人机界面技术。(3) 提高检索的有效性解决查询结果过多的现象目前有以下几种方法：a)构建基于内容的搜索引擎。基于内容的搜索不是根据字形，而是试图理解用户的请求，同时根据文档的内容选出符合用户要求的文档。即通过各种方法获得用户没有在查询语句中表达出来的真正用途，实现自然语言的智能查询功能。中文搜索引擎中当前比较成熟的解决方案是依靠语义网络、汉语分词、句法分析、处理同义词等中文信息处理技术最大程度地了解用户需求。b)将
23、用户提问转化为系统己知的问题，然后对已知问题进行解答，以求降低对自然语言理解技术的依赖性。c)用正文分类技术将结果分类，使用可视化技术显示分类结构，用户可以只浏览自己感兴趣的类别。d)进行站点类聚或内容类聚，减少信息的总量。e)让用户对返回结果进行选择，进行二次查询是一种非常有效的手段。(4) 实现交叉语言的检索搜索引擎对多种语言的数据库进行交叉语言信息检索，返回能够回答用户问题的所有语言的文档。若配上机器翻译，就可使返回结果以用户熟悉的语言显示。虽然该技术日前还处于初步研究阶段，其难点在于语言之间在表达方式和语义对应上的不确定性，但也是一种发展方向。(5) 提供对自然语言检索的支持为了提高搜
24、索引擎对用户检索提问的理解，就必须有一个好的检索提问语言，为了克服关键词检索和目录查询的缺点，现在已经出现了自然语言智能答询。如Google有专用于回答问题的Google Answer，微软有AnswerBot等。用户可以输入简单的疑问句，比如“how can kill virus of computer?”。搜索引擎在对提问进行结构和内容的分析之后，或直接给出提问的答案，或引导用户从几个可选择的问题中进行再选择。自然语言的优势在于，一是使网络交流更加人性化，二是使查询变得更加方便、直接、有效。就以上面的例子来讲，如果用关键词查询，多半人会用“virus”这个词来检索，结果中必然会包括各类病毒
25、的介绍、病毒是怎样产生的等等许多无效信息，而用“how can kill virus of computer?”，搜索引擎会将怎样杀病毒的信息提供给用户，提高了检索效率。(6) 多媒体数据搜索网络资源丰富多彩，具有很多类型的信息，用户需要的信息也不完全是网页的形式，从用户的角度来看，必然要求搜索引擎能够覆盖更多的网络资源。现在有很多搜索引擎已经提供了网页、新闻、图片、音乐等资源搜索，当然范围还可以更广，再如可以搜索视频、音频等。(7) 专业化搜索主题搜索引擎是为了专门收录某一行业、某一学科、某一主题和某一地区的信息而建立，非常实用，如有商务查询、企业查询、人名查询、电子邮件地址查询和招聘信息查
26、询等。(8) 桌面型搜索用户不用打开浏览器，而是直接通过只要通过它就能完全实现搜索过程，更甚者它可以同时搜索本地、局域网和互联网上的信息。它完全越过传统的搜索模式，越过浏览器，真正实现让搜索无处不在。搜索引擎脱离浏览器是一个发展趋势，Google、 Yahoo等己经推出桌面型搜索软件，而微软在2005年也同样有了自己的桌面搜索软件。此外还有一些其它值得注意的技术发展，如元搜索引擎，移动代理和XML技术，语音检索技术等。随着技术的不断发展进步，搜索引擎将会在信息检索中发挥更大的作用。1.3 研究目的和研究内容互联网的快速发展，对搜索引擎提出了更高的要求。巨大的使用需求推动了搜索引擎技术的发展，各
27、种新技术纷纷应用到搜索引擎中。搜索引擎是这些技术的基础和平台，它决定着这些技术的开发和应用。但一般的研究机构不可能拥有和商业搜索引擎一样规模的计算机资源，因此需要一种对资源要求低、体系开放的搜索引擎来作为各种新技术的平台。本文在深入分析网页获取、索引生成、级别系统、索引检索等搜索引擎核心技术的基础上，设计并实现互联网信息检索系统。该系统在微软.NET平台进行开发，使用C#进行代码的编写。采用多线程进行网页数据采集并写入数据库；通过使用L、中文分词、无用词汇删除、词典等技术建立索引数据；Cache技术的使用提高了用户访问效率.开放的体系结构使搜索引擎成为相关技术可靠和灵活的平台。1.4 文章内容
28、安排本文主要研究了搜索引擎实现中所涉及到的相关技术，最终实现一个基于.NET平台下的互联网信息检索系统。具体内容安排如下：第二章：介绍了搜索引擎总体结构，各组成部分实现功能及关键技术，相关算法，并对Google的体系结构进行分析；第三章：剖析开源的全文检索引擎L，分析其组织架构，索引数据格式等，对源码分析，二次开发应用；第四章：设计实现一个基于微软.NET平台的互联网信息检索系统，借助L相关技术进行实现，在本文论述的理论思想基础上，最终实现设计目标；第五章：介绍互联网信息检索系统的具体实现，核心技术的解决方法。第六章：对互联网信息检索系统进行测试，总结整个论文的完成情况，对研究工作进行总结和展
29、望。2 搜索引擎技术2.1 搜索引擎体系结构典型的搜索引擎结构一般由以下三个模块组成：信息采集模块(Crawler)，索引模块(Indexer)，查询模块(Searcher)。搜索引擎典型体系结构如图2-1所示。Crawler日志分析器控制器原始数据库索引数据库IndexerSearcher用户接口用户www日志数据库图2-1 搜索引擎体系结构图(1) Crawler从Web中采集网页数据；(2) Indexer对Crawler采集数据进行分析生成索引；(3) Searcher接受查询请求，通过一定的检索算法获取查询结果，排序后返回给用户。2.1.1 CrawlerCrawler负责页面信息的
30、采集，它的工作实现基于以下设想：既然所有网页都可能链接到其他网站，那么从一个网站开始，跟踪所有网页上的所有链接，就有可能检索整个互联网。Crawler工作原理如图2-2所示。WWW网页存储初始化抓取网页获取URL提取URL待访问的URL已访问的URL图2.2 Crawler工作原理图Crawler首先从待访问URL队列中获取URL，根据URL从Web中抓取网页数据；然后对网页进行分析，从中提取出所有的URL链接，并把它们加入到待访问URL队列中，同时将已访问URL移至已访问URL队列中。不断重复上面的过程，所有采集到的网页保存到页面存储中进行下一步处理。Crawler利用HTTP协议读取Web
31、页面并沿着HTML文档中的超链接自动获取WWW资源。可以将WWW作为一个有向图来处理，将每一个页面看作图中的一个节点，将页面中的超链接看做图中的有向边。因此可以采取有向图的遍历算法(深度优先或者广度优先算法)来对WWW进行遍历。由于Web信息具有的分布性，非结构化，不稳定性等特点，Crawler存在以下的关键问题：(1) 多线程抓取时的任务调度问题搜索引擎会产生多个Crawler同时对网页进行抓取，这里需要一个好的分布式算法，使得既不重复抓取网页，又不漏掉重要的站点。(2) 网页评估在抓取网页时存在一定的取舍，一般只会抓20%左右的网页。评估算法中典型的油Google发明的PgaeRank。(
32、3) 更新策略每经过一段时间，Crawler对以抓取的数据经行更新，保证索引网页是最新的。(4) 压缩算法网页抓取后，通过一定的压缩机制保存到本地，从而减少存储容量，同时也减少各服务器之间的网络通信开销。2.1.2 Indexer搜索引擎在完成用户查询请求时，并不是即时检索互联网上的数据，搜索的数据实际是预先采集的网页数据。要实现对采集页面的快速访问，必须通过某种索引机制来完成。页面数据可以用一系列关键词来表示，从检索目的来说，这些关键词描述了页面的内容。只要找到页面，便可以找到其中的关键词。反过来，如果按关键词建立到页面的索引，便可以根据关键词快速地检索到相关页面。具体地，关键词被存储在索引
33、文件(index file)中，对于每个关键词，都有一个指针链表，该表中的每一个指针指向与关键词相关的某个页面，所有指针链表构成置入文件(posting file)。这种倒排文件的方法几乎被当前所有的商用IR系统所采用。Indexer负责对Crawler采集的数据生成索引数据，基本结构如图2-3所示。页面数据服务器中间数据索引数据图2-3 Indexer索引数据结构图Indexer首先从页面存储器中获取页面数据，对其进行分析，通过词典识别网页中的词，通过停用词(stop words)表删除其中的停用词，生成检索词序列，并最后生成索引数据。Indexer中存在的问题：(1) 索引存储一般来讲，数
34、据量和索引量的比例接近1:1。索引的存储一般采用分布式策略，检索的数据分布在不同的服务器上。Google存储索引的服务器大概有1000多台。(2) 索引更新页面数据更新时，索引数据必须相应的更新。更新策略一般采用增量索引方式。(3) 索引压缩索引也存在数据压缩的问题。索引压缩是通过对具体索引格式的研究实现压缩。(4) 网页相似性支持索引的结构还必须为网页相似性分析提供支持。(5) 多语言，多格式支持网页数据具有多种编码格式，通过Unicode，索引支持多种编码查询。同时索引还必须有对Word，Excel等文件格式进行分析的功能。2.1.3 SearcherSearcher是直接与用户进行交互的
35、模块，在接口上有多种实现方式，常见的主要是Web方式，另外还可以通过无线接入方式(如手机)进行查询。Searcher基本结构如图2-4所示。Searcher索引数据页面数据用户接口图2-4 Searcher基本结构图Searcher通过某种接口方式，接收用户查询，对查询进行分词(stemming)处理，获取查询关键字。通过Indexer获取与查询关键字匹配的网页数据，经过排序后返回给用户。Searcher中存在的问题：(1) 检索结果的排序由于搜索引擎返回结果非常多，检索结果是否按用户预期的顺序排列是评价搜索引擎的重要指标之一。一些新的尝试，比如对用户偏好的分析技术都可以运用到这里，对不同的用
36、户采用不同的排序策略。(2) 排序结果排重排重可以提高结果数据的质量。检索结果的数量给排重带来资源上的开销及速度上的影响。搜索引擎需要在其中作出权衡。(3) 检索结果的相似性分析主要用在类似网页功能中，需要在索引结构中提供支持。(4) 检索的速度主要依赖索引结构的设计。同时在体系结构上还有很多技术可以用来提升速度。如：Cache，负载均衡等。2.2 搜索引擎的性能指标我们可以将Web信息的搜索看作一个信息检索问题，即在由web网页组成的文档库中检索出与用户查询相关的文档。所以我们可以用衡量传统信息检索系统的性能参数一召回率(recall)和精度(pricision)衡量一个搜索引擎的性能。召回
37、率是检索出的相关文档数和文档库中所有的相关文档数的比率，衡量的是检索系统(搜索引擎)的查全率；精度度是检索出的相关文档数与检索出的文档总数的比率，衡量的是检索系统(搜索引擎)的查准率。对于一个检索系统来讲，召回率和精度不可能两全其美，召回率高时，精度低，精度高时，召回率低。对于搜索引擎系统来讲，因为没有一个搜索引擎系统能够搜集到所有的Web网页，所以召回率很难计算。目前的搜索引擎系统都非常关心精度。影响一个搜索引擎系统性能和精度有很多因素，最主要的是信息检索模型，包括文档和查询的表示方法、评价文档和用户查询相关性的匹配策略、查询结果的排序方法和用户进行相关度反馈的机制。提高搜索引擎精度的关键是
38、研究最优的页面优先度算法，提供具有较高用户相关度的网页页面优先度排序。研究搜索引擎的页面优先度算法，需要从客观和主观两方面进行研究。客观上，从网页页面本身的信息和链接情况分析，提高信息量大、链接度高的网页页面的优先度排序;主观上，从互联网用户使用搜索引擎的行为模式分析，提高用户点击率高和浏览时间长的网页页面的优先度排序。2.3 中文分词算法众所周知，英文是以词为单位的，词和词之间是靠空格隔开，而中文是以字为单位，句子中所有的字连起来才能描述一个意思。例如，英文句子“I am a student”，用中文则为：“我是一个学生”。计算机可以很简单通过空格知道student是一个单词，但是不能很容易
39、明白“学”、“生”两个字合起来才表示一个词。把中文的汉字序列切分成有意义的词，就是中文分词，有些人也称为切词。2.3.1 基于字符串匹配的分词方法这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功(识别出一个词)。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大(最长)匹配和最小(最短)匹配；按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的几种机械分词方法如下：(1) 正向最大匹配法(由左到右的方向)首先将待
40、拆分的字符串从左向右进行分词，然后将分词与机器字典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功。实现流程如图2-5所示。S是否为单字S2=S2+S+”/”S1=S1-S是是是否否否带切分字符 S1，输出字符 S2最大词长 MaxLenS1是否为空输出 S2最大词长 MaxLen从S1左侧开始，取出候选字符串S，S的长度不大于MaxLan查看字典，判断S是否在字典中将S最右边一个字去掉最大词长 MaxLen开始结束图2-5正向最大匹配法实现流程图(2) 逆向最大匹配法(由右到左的方向)首先将待拆分的字符串从右向左进行分词，然后将分词与机器字典中的词条进行匹配，若在词典中找到某个字符串，
41、则匹配成功。实现流程如图2-6所示。S是否为单字S2=S2+S+”/”S1=S1-S是是是否否否带切分字符 S1，输出字符 S2最大词长 MaxLenS1是否为空输出 S2最大词长 MaxLen从S1右侧开始，取出候选字符串S，S的长度不大于MaxLan查看字典，判断S是否在字典中将S最左边一个字去掉最大词长 MaxLen开始结束图2-6逆向最大匹配法实现流程图(3) 最少切分(使每一句中切出的词数最小)。还可以将上述各种方法相互组合，例如，可以将正向最大匹配方法和逆向最大匹配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小匹配和逆向最小匹配一般很少使用。一般说来，逆向匹配的切分精
42、度略高于正向匹配，遇到的歧义现象也较少。统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245。但这种精度还远远不能满足实际的需要。实际使用的分词系统，都是把机械分词作为一种初分手段，还需通过利用各种其它的语言信息来进一步提高切分的准确率。一种方法是改进扫描方式，称为特征扫描或标志切分，优先在待分析字符串中识别和切分出一些带有明显特征的词，以这些词作为断点，可将原字符串分为较小的串再来进机械分词，从而减少匹配的错误率。另一种方法是将分词和词类标注结合起来，利用丰富的词类信息对分词决策提供帮助，并且在标注过程中又反过来对分词结果进行检验、调整，从而极大地
43、提高切分的准确率。2.3.2 基于理解的分词方法这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。其基本思想是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。它通常包括三个部分：分词子系统、句法语义子系统、总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方法需要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形式，因此目前基于理解的分词系统还处在试验阶段。2.3.3 基于统计的分词方法从形式上看，词是稳定的字的组合，因此
44、在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互现信息。定义两个字的互现信息，计算两个汉字X、Y的相邻共现概率。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进行统计，不需要切分词典，因而又叫做无词典分词法或统计取词方法。但这种方法也有一定的局限性，会经常抽出一些共现频度高、但并不是词的常用字组，例如“这一”、“之一”、“有的”、“我的”、“许多的”等，并且对常用词的识别精度差
45、，时空开销大。实际应用的统计分词系统都要使用一部基本的分词词典(常用词词典)进行串匹配分词，同时使用统计方法识别一些新的词，即将串频统计和串匹配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。2.4 实际系统研究下面通过Google实现流程说明搜索引擎的具体工作过程。2.4.1 Google的整体结构Google的整体结构如图2-7所示。因为效率的缘故Google使用C和C+实现大部分模块。图2-7 Google体系结构图与其他搜索引擎类似，Google在整体结构上也主要有Crawler，Indexer，Searcher等部分组成，在
46、模块设计上更为细致。2.4.2 Google的工作过程Google工作流程可以分为信息采集，数据索引，查询请求三个方面进行分析：信息采集：Google中信息采集是由分布式的Crawler完成。URL数据由URL Server模块负责维护。URL Server向Crawler提供待抓取的URL列表。Crawler根据获取URL列表进行网页抓取，已抓取的网页被送往Store Server进行保存。Google中使用了Store Server模块专门负责网页数据的存储，并且在存储时使用了压缩算法进行数据压缩，以减少数据量。每个网页都有一个独一无二的docID，在Google早期设计中，docID被定义为32位的整数，也即意味着最多能保存40亿个网页数据，Google现在的数据量已经达到了80亿，如此规模的数据量也是Google设计者始料未及的。数据索引数据索引由Indexer模块，URL Resolver模块和Sorter模块共同完成。Indexer首先通过S
