【毕业学位论文】(Word原稿)搜索引擎的基本原理及中文分词的设计与实现-计算机网络技术

i 摘要 :随着因特网的迅猛发展、 息的增加，而人们越来越依靠网络来查找他们所需要的信息，用户要在如此浩瀚的信息海洋里查找信息，就象大海捞针一样，所以如何有效的去发现我们所需要的信息，就成了一个很关键的问题。为了解决这个问题，搜索引擎随之诞生。因而也成为除了电子邮件以外最多人使用的网上服务。 但是，随着信息多元化的增长，千篇一律的给所有用户提供同一个入口显然已经不能满足特定用户更深入的查询需求。我们需要分类细致精确、对硬件要求低，数据全面深入、更新及时的搜索引擎，因而搜索引擎技术成为计算机工业界和学术界争相 研究、开发的课题。 本文阐述了搜索引擎的基本原理，着重分析了中文分词的设计与实现。 关键词 ： 互联网；搜索引擎；中文分词 of of EB on to Its to so so to we a To It to in of we is a is in So of to In I of of 目录 前言 . 1 第 一章 搜索引擎概述 . 2 展现状 . 2 发展历程 . 2 . 3 信息分布 . 3 索引擎简介 . 4 索引擎的发展 . 5 一代搜索引擎 . 5 二代搜索引擎 . 6 三代搜索引擎 . 6 四代搜索引擎 . 7 索引擎的分类 . 7 文搜索引擎 . 7 录索引 . 8 搜索引擎 . 9 他非主流的引擎 . 9 第 二章 搜索引擎的结构介绍 . 11 索器 . 11 引器 . 12 索器 . 12 户接口 . 12 结 . 13 第 三章 基于 研究 . 14 3.1 索引擎介绍 . 14 特性分析 . 15 心部分 索引排序 . 15 2 相关度积分公式 . 17 其他特性 . 18 性 . 18 . 19 字 . 19 排序 . 19 化 . 20 为查询 优化索引 (. 20 并发操作 制 . 20 . 20 档结构 . 21 念详细介绍 . 21 本数据类型（ . 23 索引包含的文件（ . 24 词原理 . 30 第 四章 中文分词 . 34 中文分词简介 . 34 什么是中文分词 . 34 中文分词和搜索引擎 . 34 中文分词技术 . 35 基于字符串匹配的分词方法 . 35 于理解的分词方法 . 36 基于统计的分词方法 . 37 分词中的难题 . 37 歧义识别 . 37 新词识别 . 38 写简单的中文分词程序 . 39 计思路 . 39 第 五章 搜索引擎的未来与展望 . 44 参考文献 . 46 感谢 . 47 第 1 页 共 47 页 前言 随着信息技术的不断发展，特别是互联网应用技术的不断普及，互联网提供的内容不断丰富，中国搜索引擎市场也出现了蓬勃发展的生机，搜索引擎成为人们获取信息的重要途径。 搜索引擎经过几年的发展和摸索，越来越贴近人们的需求，搜索引擎的技术也得到了很大的发展。搜索引擎的最新技术发 展包括以下几个方面： 一、提高搜索引擎对用户检索提问的理解 二、对检索结果进行处理 三、确定搜索引擎信息搜集范围，提高搜索引擎的针对性 四、将搜索引擎的技术开发重点放在对检索结果的处理上，提供更优化的检索 结果 一个开放源程序的搜寻器引擎，利用它可以轻易地为 件加入全文搜寻功能。 最主要工作是替文件的每一个字作索引，索引让搜寻的效率比传统的逐字比较大大提高， 供一组解读，过滤，分析文件，编排和使用索引的 的强大之处除了高效和简单外，是最重要的是使 使用者可以随时应自已需要自订其功能，本设计就是在 础上开发。 第 2 页 共 47 页 第一章 搜索引擎概述 随着因特网的迅猛发展、 息的增加，用户要在信息海洋里查找信息，就象大海捞针一样，搜索引擎技术恰好解决了这一难题（它可以为用户提供信息检索服务）。目前，搜索引擎技术正成为计算机工业界和学术界争相研究、开发的对象。 搜索引擎（ 随着 息的迅速增加，从 1995 年开始逐渐发展起来的技术。据发表在科学杂志 1999 年 7 月的文章 息的可访问性估计，全球目前的网页超过 8 亿，有效数据超过 9T，并且仍以每 4 个月翻一番的速度增长。用户要在如此浩瀚的信息海洋里寻找信息，必然会“大海捞针”无功而返 。 搜索引擎正是为了解决这个“迷航”问题而出现的技术。搜索引擎以一定的策略在互联网中搜集、发现进行理解、提取、组织和处理，并为用户提供检索服务，从而起到信息导航的目的。搜索引擎提供的导航服务已经成为互联网上非常重要的网络服务，搜索引擎站点也被美誉为“网络门户”。搜索引擎技术因而成为计算机工业界和学术界争相研究、开发的对象。 展现状 发展历程 前身是美国国防部高级研究计划署的研究试验性网络 1983 年 P 成为 唯一的正式协议。此后， 连接的网络、机器和用户快速增长。 1988 年 联，它的规模以指数增长，很多地区网络开始加入，并且开始与加拿大、欧洲和太平洋地区的网络连接。 后来形成 90 年代初到现在，是 长最迅速的时期。 1993 年，增长速度是 341%。截止到 1996 年 7 月， 连接了 134336第 3 页 共 47 页 个网络，入网主机 1228 万台，以及数以亿计的用户。到 1998 年 7 月， 27 万个网址， 4300 万个域名， 台主机和 个网页，其规模大概每年翻一番。 全球性的网络信息系统。一九八九年，位于瑞士的先开始 了 研究工作。随后，许多其他的研究机构、大学和公司也加入 究者的行列，并相继开发出各自的 件。这些 件的运行平台覆盖了目前主流的计算机硬件和操作系统。在此过程中， 不断完善和发展。同时，为了保证不同 件之间的互操作性，一系列 议和标准也正在使用和完善之中。 2005 年 7 月 21 日，中国互联网络信息中心 (京发布“第十六次中国互联网络发展状况统计报告”。报告显示，截至到 6 月 30 日，我国上网用户总数突破 1 亿，为 人，半年增加了 900 万人，和上年同 期相比增长 其中宽带上网的人数增长迅猛，首次超过了网民的一半，达到 5300 万人，增长率为 这也是宽带用户首次超过了拨号上网用户人数。我国网民数和宽带上网人数均仅次于美国，位居世界第二。 信息分布 的信息资源随着 发展而呈现出以下特点： 信息量大而且分散 自治性强 信息资源多种多样 不一致和不完整性 这些特点对网络软件的性能提出了很高的要求。网络的快速发展给信息挖掘带来了挑战。 信息呈现爆炸性的指数增长，同时伴随着上网 经验不足、不第 4 页 共 47 页 太晓得如何查找信息的新用户的加入。用户很可能最大程度的运用超链来在网上冲浪，他们通常从以下两类网站开始： 第一类是目录系统，其典型代表是 ）， 它通过有专业知识的网页编辑人员对网上的网页进行精选，建立一个索引目录，来给用户提供服务。这类 通过手工维护得很好的 系统的优点是提供的网页准确率高，可以有效的覆盖所有热门的主题，但它们的缺点是过于主观，而且需要高昂的代价来建立和维护，更 新改进的慢，同时不能很好的覆盖所有深奥的主题 。 第二类是搜索引擎系统， 比如天网（ ）， 它通过程序自动地从网上搜集和分析网页，建立索引，为用户服务。这类 通过关键词匹配实现查找的自动更新的搜索引擎 优点是涵盖的网页数量巨大，但 通常返回太多的低质量相关性不大的结果。 索引擎简介 搜索引擎的基本原理是通过网络机器人定期在 页上爬行，然后发现新的网页，把它们取回来放到本地的数据库中，用户的查询请 求可以通过查询本地的数据库来得到。如 天会找到大约 500 万个新的网页 搜索引擎一般都有一个 期的访问一些站点，来检查这些站点的变化，同时查找新的站点。一般站点有一个 件用来说明服务器不希望问的区域， 必须遵守这个规定。如果是自动索引的话， 要对该页面根据其内容进行索引，根据它的关键字的情况把它归到某一类中。页面的信息是通过元数据的形式保存的，典型的元数据包括标题、 址、一个该页面的简要的介绍，关键字或者是索引短语、文 件的大小和最后的更新的日期。尽管元数据有一定的标准，但是很多站点都采用自己的模板。文档提取机制和索引策略对 索引擎的有效性有很大的关系。高级的搜索选项一般包括：布尔方法或者是短语匹配和自然语言处理。一个查询所产生的结果按照提取机制被分成不同的等级提交给用户。最相关的放在最前面。每一个第 5 页 共 47 页 提取出来的文档的元数据被显示给用户。同时包括该文档所在的 址。 另外有一些关于某一个主题的专门的引擎，它们只对某一个主题的内容进行搜索和处理，这样信息的取全率和精度相对就比较高。 同时，有一类搜索引擎，它本身不用 定期的采集网页。象 通过向多个搜索引擎同时发出询问并对结果进行综合返回给用户实现搜索功能。当然实际上象 够对各个搜索引擎的功能进行分析和比较，根据不同的用户查询提交给不同的搜索引擎进行处理，当然用户自己也可以指定利用哪一个搜索引擎。 一个优秀的搜索引擎必须处理以下几个问题： 1 网页的分类 2 自然语言的处理 3 搜索策略的调度和协作 4 面向特定用户的搜索。所以很多搜索引擎不同程度的使用了一些人工智能的技术来解决这些方面的问题 。 面对浩瀚的网络资源，搜索引擎为所有网上冲浪的用户提供了一个入口，毫不夸张的说，所有的用户都可以从搜索出发到达自己想去的网上任何一个地方。因此它也成为除了电子邮件以外最多人使用的网上服务。 索引擎的发展 搜索引擎技术伴随着 发展是引人注目的。搜索引擎大约经历了三代的更新发展： 一代搜索引擎 第一代搜索引擎出现于 1994 年。这类搜索引擎一般都索引少于 1， 000， 000个网页，极少重新搜集网页并去刷新索引。而且其检索速度非常慢，一般都要等待 10 秒甚至更长的时间。在实现技术上也 基本沿用较为成熟的 网络、数据库等技术，相当于利用一些已有技术实现的一个 的应用。在 1994 年 3 月到 4 月，网络爬虫 均每天承受大约 1500 次查询。 第 6 页 共 47 页 二代搜索引擎 大约在 1996 年出现的第二代搜索引擎系统大多采用分布式方案（多个微型计算机协同工作）来提高数据规模、响应速度和用户数量，它们一般都保持一个大约 50， 000， 000 网页的索引数据库，每天能够响应 10， 000， 000 次用户检索请求。 1997 年 11 月，当时最先进的几个搜索引擎号称能建立从 2， 000， 000 到100， 000， 000 的网页索引。 索引擎声称他们每天大概要承受 20， 000，000 次查询。 三代搜索引擎 自 1998 年到现在，出现了一个搜索引擎空前繁荣的时期，我们统称这一时期的搜索引擎为第三代搜索引擎。第三代搜索引擎的发展有如下几个特点： 1. 索引数据库的规模继续增大，一般的商业搜索引擎都保持在几千万甚至上亿个网页。 2. 除了一般意义上的搜索以外，开始出现主题搜索和地域搜索。很多小型的垂直门户站点开始使 用该技术。 3. 由于搜索返回数据量过大，检索结果相关度评价成为研究的焦点。相关的研究又可以分为两类：一类是对超文本链的分析，在这方面 学的统 7和 统 8作出了很大的贡献；另一类是用户信息的反馈， 统采用的就是这种方法。 4. 开始使用自动分类技术。 在一定程度上使用了该技术。 2000 年搜索引擎 2000 年大会上，按照 司总裁 演讲，在用 3,000 台运行 统的个人电脑在搜集 的网页，而且以每天 30 台的速度向这个微机集群里添加电脑，以保持与网络的发展相同步。每台微机运行多个爬虫程序搜集网页的峰值速度是每秒 100 个网页，平均速度是每秒 网页，一天可以搜集超过 4， 000， 000 网页。 第 7 页 共 47 页 四代搜索引擎 随着信息多元化的增长，千篇一律的给所有用户同一个入口显然已经不能满足特定用户更深入的查询需求。同时，这样的通用搜索引擎在目前的硬件条件下，要及时更新以得到互联网上较全面的信息是不太可能的。针对这种情况 ，我们需要一个分类细致精确、数据全面深入、更新及时的面向主题的搜索引擎。 由此第四代搜索引擎 主题搜索引擎诞生了，它运用了人工分类以及特征提取等智能化策略，因此比上面提到的前三代的搜索引擎将更加有效和准确。 索引擎的分类 搜索引擎按其工作方式主要可分为三种，分别是全文搜索引擎（ 目录索引类搜索引擎（ 元搜索引擎（ 文搜索引擎 全文搜索 引擎是名副其实的搜索引擎，国外具代表性的有 ，国内著名的有百度（ 它们都是通过从互联网上提取的各个网站的信息（以网页文字为主）而建立的数据库中，检索与用户查询条件匹配的相关记录，然后按一定的排列顺序将结果返回给用户，因此他们是真正的搜索引擎。搜索引擎的自动信息搜集功能分两种： 一种是定期搜索，即每隔一段时间（比如 般是 28 天），搜索引擎主动派出“蜘蛛”程序，对一定 址范围内的 互联网站进行检索，一旦发现新的网站，它会自动提取网站的信息和网址加入自己的数据库。 另一种是提交网站搜索，即网站拥有者主动向搜索引擎提交网址，它在一定时间内（ 2 天到数月不等）定向向你的网站派出“蜘蛛”程序，扫描你的网站并将有关信息存入数据库，以备用户查询。 第 8 页 共 47 页 由于近年来搜索引擎索引规则发生了很大变化，主动提交网址并不保证你的网站能进入搜索引擎数据库，因此目前最好的办法是多获得一些外部链接，让搜索引擎有更多机会找到你并自动将你的网站收录。 当用户以关键词查找信息时，搜索引擎会在数据库中进行搜 寻，如果找到与用户要求内容相符的网站，便采用特殊的算法 通常根据网页中关键词的匹配程度，出现的位置 /频次，链接质量等 计算出各网页的相关度及排名等级，然后根据关联度高低，按顺序将这些网页链接返回给用户，从搜索结果来源的角度，全文搜索引擎又可细分为两种：一种是拥有自己的检索程序（ 俗称“蜘蛛”（ 序或“机器人”（ 序，并自建网页数据库，搜索结果直接从自身的数据库中调用，如上面提到的 7 家引擎；另一种则是租用其他引擎的数据库，并按自定的格式排列搜索结果，如 擎。 录索引 目录索引虽然有搜索功能，但在严格意义上算不上是真正的搜索引擎，仅仅是按目录分类的网站链接列表而已。用户完全可以不用进行关键词（ 询，仅靠分类目录也可找到需要的信息。目录索引中最具代表性的莫过于大名鼎鼎的 虎。其他著名的还有 。国内的搜狐、新浪、网易搜索也都属于这一类。与全文搜索引擎相比，目录索引有许多不同之处： 首先，搜索引擎属于自动网站检索，而目录索引则完全依 赖手工操作。用户提交网站后，目录编辑人员会亲自浏览你的网站，然后根据一套自定的评判标准甚至编辑人员的主观印象，决定是否接纳你的网站。 其次，搜索引擎收录网站时，只要网站本身没有违反有关的规则，一般都能登录成功。而目录索引对网站的要求则高得多，有时即使登录多次也不一定成功。尤其象 样的超级索引，登录更是困难。 此外，在登录搜索引擎时，我们一般不用考虑网站的分类问题，而登录目录第 9 页 共 47 页 索引时则必须将网站放在一个最合适的目录（ 最后，搜索引擎中各网站的有关信息都是从用户网页中自动提取的， 所以用户的角度看，我们拥有更多的自主权；而目录索引则要求必须手工另外填写网站信息，而且还有各种各样的限制。更有甚者，如果工作人员认为你提交网站的目录、网站信息不合适，他可以随时对其进行调整，当然事先是不会和你商量的。 目前，搜索引擎与目录索引有相互融合渗透的趋势。原来一些纯粹的全文搜索引擎现在也提供目录搜索，如 借用 录提供分类查询。而象 这些老牌目录索引则通过与 搜索引擎合作扩大搜索范围，不过在默认搜索模式下，其目录中匹配的网站永远排在搜 索引擎的网页查询结果之前。 在这方面，国内几家著名的搜索引擎网站开始借鉴国外的做法，比如搜狐、新浪就有网站搜索和网页搜索（来源于百度搜索引擎）之分，用户可自行选择。选择网站搜索时，它们是目录索引，搜索范围仅限于自身注册的网站；而选择网页搜索时，它们又成了搜索引擎。 搜索引擎 元搜索引擎 (接受用户查询请求时，同时在其他多个引擎上进行搜索，并将结果返回给用户。著名的元搜索引擎有 （元搜索引擎列表），中文 元搜索引擎中具代表性的有搜星搜索引擎。在搜索结果排列方面，有的直接按来源引擎排列搜索结果，如 的则按自定的规则将结果重新排列组合，如 他非主流的引擎 除上述三大类引擎外，还有以下几种非主流形式： 1、集合式搜索引擎：如 2002 年底推出的引擎。该引擎类似 区别在于不是同时调用多个引擎进行搜索，而是由用户从提供的 4第 10 页 共 47 页 个引擎当中选择，因此叫它“集合式”搜索引擎更确切些。 2、门户搜索引擎：如 虽然提供搜索服务，但自身即没有分类目录也没有网页数据库，其搜索结果完全来自其他引擎。 3、免费链接列表（ 称 这类网站一般只简单地滚动排列链接条目，少部分有简单的分类目录，不过规模比起 目录索引来要小得多。 由于上述网站都为用户提供搜索查询服务，为方便起见，我们通常将其统称为搜索引擎。 第 11 页 共 47 页 第二章 搜索引擎的结构介绍 一个搜索引擎由搜索器、索引器 、检索器和用户接口等四个部分组成。下面是四部分在搜索引擎中的一些功能。 搜索引擎首先尽可能多的从互联网中抓取网址，然后把搜索到的网址存放到数据库中，然后通过对这些网址进行分析，去除网页当中不用的信息，把中文与英文分开处理，因为英文一个个单词都是用空格分开，所以在处理时直接按原来结构。中文就要对他进行切词，把一个个词分开处理，每个词中间用空格或标点符号隔开，通过分析每个网页都生成一个分词文件，分词文件由中文词，英文单词，数字和标点符号组成。每个中文词，英文单词，数字之间用标点符号隔开。然后对这些分词文件进行处 理，把每个词所在的网页及其在网页中的位置标记下来存放到索引表中，最后根据用户提供的所要查询的词在索引表中查找，把符合查询条件的词所在的网页列出来，并把词在网页中的位置的前一部分和后一部分的分别列出来提供给用户。 索器 搜索器的功能是在互联网中漫游，发现和搜集信息。它常常是一个计算机程序，日夜不停地运行。它要尽可能多、尽可能快地搜集各种类型的新信息，同时因为互联网上的信息更新很快，所以还要定期更新已经搜集过的旧信息，以避免死连接和无效连接 。目前有两种搜集信息的策略： 1从一个起始 合开始，顺着这些 的超链（ 以宽度优先、深度优先或启发式方式循环地在互联网中发现信息。这些起始 以是任意的 常常是一些非常流行、包含很多链接的站点（如 。 2将 间按照域名、 址或国家域名划分，每个搜索器负责一个子空间的穷尽搜索。 第 12 页 共 47 页 搜索器搜集的信息类型多种多样，包括 章、件、字处理文档、多媒体信息。 搜索器的实现常常用分布式、并行计算技术，以提 高信息发现和更新的速度。商业搜索引擎的信息发现可以达到每天几百万网页。 搜索器在分析一个网页的时候，可以得到这个网页上的所有超链接 于每一个 索器都给它赋予一定的权值，才返回给主控程序，以便主控程序按照一定的顺序在下一轮发给搜索器。 引器 索引器的功能是理解搜索器所搜索的信息，从中抽取出索引项，用于表示文档以及生成文档库的索引表。 索引器可以使用集中式索引算法或分布式索引算法。当数据量很大时，必须实现即时索引（ 否则不能够跟上信息量急剧增加 的速度。索引算法对索引器的性能（如大规模峰值查询时的响应速度）有很大的影响。一个搜索引擎的有效性在很大程度上取决于索引的质量。 索器 检索器的功能是根据用户的查询在索引库中快速检出文档，进行文档与查询的相关度评价，对将要输出的结果进行排序，并实现某种用户相关性反馈机制。 检索器常用的信息检索模型有集合理论模型、代数模型、概率模型和混合模型四种。 户接口 用户接口的作用是输入用户查询、显示查询结果、提供用户相关性反馈机制。主要的目的是方便用户使用搜索引擎，高效率、多方式地从搜 索引擎中得到第 13 页 共 47 页 有效、及时的信息。用户接口的设计和实现使用人机交互的理论和方法，以充分适应人类的思维习惯。 用户输入接口可以分为简单接口和复杂接口两种： 简单接口只提供用户输入查询串的文本框； 复杂接口可以让用户对查询进行限制，如逻辑运算（与、或、非； 、 -）、相近关系（相邻、 域名范围（如 出现位置（如标题、内容）、信息时间、长度等等。目前一些公司和机构正在考虑制定查询选项的标准。 结 本小节介绍了搜索引擎的是如何对用户所要查询的词在网页中进行搜索的流程， 并且分别对每个模块进行简单的介绍。 第 14 页 共 47 页 第三章 基于 研究 3.1 索引擎 介绍 是一个完整的全文索引应用，而是是一个用 的全文索引引擎工具包，它可以方便的嵌入到各种应用中实现针对应用的全文索引 /检索功能。 作者： 贡献者 一位资深全文索引 /检索专家，曾经是 索引擎 ( 作系统的成就之一 )的主要开发者，后在 任高级系统架构设计师，目前 从事于一些 层架构的研究。他贡献出的 目标是为各种中小型应用程序加入全文检索功能。 发展历程：早先发布在作者自己的 来发布在2001 年年底成为 金会 一个子项目：，比较著名的有： 坛系统； 件列表 档 /浏览 /查询系统，本文的主要参考文档“ 者就是 统的主要开发者之一，而 已经成为目前 目的主要邮件列表归档系统。 于 布框架，全文检索部分使用了 于 开放开发平台，帮助部分的全文索引使用了 于中文用户来说，最关心的问题是其是否支持中文的全文检索。但通过后面对于 结构的介绍，你会了解到由于 好架构设计，对中文的支持只需对其语言词法分析接口进行扩展就能实现对中文检索的支持。 第 15 页 共 47 页 特性分析 心部分 索引排序 索引排序是使用了倒排序原理。 该结构及相应的生成算法如下： 设有两篇文章 1 和 2 文章 1 的内容为： 文章 2 的内容为： He 1. 由于 基于关键词索引和查询的，首先我们要取得这两篇文章的关键词，通常我们需要如下处理措施 a. 我们现在有的是文章内容，即一个字符串，我们先要找出字符串中的所有单词，即分词。英文单词由于用空格分隔，比较好处理。中文单词间是连在一起的需要特殊的分词处理。 b. 文章中的 ” “词没有什么实际意义，中文中的 “的 ”“是 ”等字通常也无具体含义， 这些不代表概念的词可以过滤掉，这个也就是在 细分析中所讲的 c. 用户通常希望查 “能把含 “ “文章也找出来，所以所有单词需要统一大小写。 d. 用户通常希望查 “能把含 “ “文章也找出来，所以需要把“ “原成 “ e. 文章中的标点符号通常不表示某种概念，也可以过滤掉 ,在 以上措施由 完成 ,经过上面处理后 : 文章 1 的所有关键词为： 文章 2 的所有关键词为： 2. 有了关键词后，我们就可以建立倒排索引了 上面的对应关系是： “文章号 ”对 “文章中所有关键词 ”。倒排索引把这个关系倒过来，变成： “关键词 ”对 “拥有该关键词的所有文章号 ”。文章 1， 2 经过倒排后变第 16 页 共 47 页 成 ： 关键词 文章号 1 2 i 1 1,2 2 1 通常仅知道关键词在哪些文章中出现还不够，我们还需要知道关键词在文章中出现次数和出现的位置，通常有两种位置： a)字符位置，即记录该词是文章中第几个字符（优点是关键词亮显时定位快）； b)关键词位置，即记录该词是文章中第几个关键词（优点是节约索引空间、词组（ 询快）， 记录的就是这种位置。 加上 “出现频率 ”和 “出现位置 ”信息后，我们的索引结构变为： 关键词 文章号 出现频率 出现位置 12 3， 6 21 1 i 11 4 12,21 2， 5， 2 21 3 11 1 以 行为例我们说明一下该结构： 文章 1 中出现了 2 次，文章 2中出现了一次，它的出现位置为 “2,5,2”这 表示什么呢？我们需要结合文章号和出现频率来分析，文章 1 中出现了 2 次，那么 “2,5”就表示 文章 1 中出现的两个位置，文章 2 中出现了一次，剩下的 “2”就表示 文章 2 中第 2 个关键字。 以上就是 引结构中最核心的部分。我们注意到关键字是按字符顺序第 17 页 共 47 页 排列的（ 有使用 B 树结构），因此 以用二元搜索算法快速定位关键词。 实现时 上面三列分别作为词典文件（ 频率文件(位置文件 (存。其中词典文件不仅保存有每个关键词，还保留了指向频率文件和位置文件的指针，通过指针可以找到该关键字的频率信息和位置信息。 使用了 概念，用于表达信息所在位置（如标题中，文章中，），在建索引中，该 息也记录在词典文件中，每个关键词都有一个息 (因为每个关键字一定属于一个或多个 为了减小索引文件的大小， 索引还使用了压缩技术。首先，对词典文件中的关键词进行了压缩，关键词压缩为 ，例如：当前词为 “阿拉伯语 ”，上 一个词为 “阿拉伯 ”，那么 “阿拉伯语 ”压缩为 。其次大量用到的是对数字的压缩，数字只保存与上一个值的差值（这样可以减小数字的长度，进而减少保存该数字需要的字节数）。例如当前文章号是 16389（不压缩要用 3 个字节保存），上一文章号是 16382，压缩后保存 7（只用一个字节）。 下面我们可以通过对该索引的查询来解释一下为什么要建立索引。 假设要查询单词 “ 对词典二元查找、找到该词，通过指向频率文件的指针读出所有文章号，然后返回结果。词典通常非常小，因而，整个过程的时间是毫秒级的。 而用普