马 飞

（宁夏大学信息工程学院， 宁夏 银川 750021）

提到索引，首先想到的是最常用的百度搜索和google搜索。目前，搜索引擎面对海量的数据，需要解决的是如何能在海量的数据下快速找到用户所需要的文档，满足用户需求。面对如此大型的数据集，数据库一般很难做到有效地管理。而搜索引擎的数据操作简单，通常仅需要增、删、改、查功能，并且底层以特定的结构存储数据，可以针对该结构设计出简单高效的应用程序。搜索引擎需要面对的是多用户检索需求，这对搜索引擎的搜索速度提出挑战，即需要快速响应用户的请求。而通常使用的传统数据库很难承受大规模用户的请求，而且在检索响应时间和检索并发度上都不及多处理器下设计的索引系统，文章研究了基于Map/Reduce框架实现的倒排索引文本检索。

1 相关工作简介

1.1 Map/Reduce工作原理

MapReduce[1]是由Google提出的云计算核心计算模型，Hadoop[2]计划将它实现开源化。Hadoop[2]的Map/Reduce实现、Common及HDFS一起，构成了Hadoop初期的三个组件。在分布式计算模型中，对大规模数据集的分析和处理主要通过开源计算模型Map/Reduce完成。

Map/Reduce的工作原理如图1所示。当向Map/Reduce框架提交相应的计算作业时，该框架首先进行计算作业的拆分，分成若干个Map任务后，将不同任务部署到多个计算节点上执行。通常每个Map任务对部分输入数据进行处理，当相应的Map任务完成后，该过程会生成相应的中间文件，而Reduce任务主要以这些中间文件作为其输入。Reduce函数设计的主要目标是对前面若干个Map的输出进行汇总计算并将最终的结果进行输出。

图1 Map/Reduce的工作原理图

从逻辑设计方面对分布式计算模型进行分析，Map/Reduce计算框架在运行过程中主要分为五个阶段：输入分片、map处理、combiner阶段、shuffle阶段和reduce合并。其中，Map/Reduce计算模型的核心函数Map和Reduce主要通过用户自己设定完成。Map和Reduce函数的主要功能是进行键值对的相互转换，通过前期分析设定相应的映射规则，将输入的键值对＜key, value＞转换成相应的＜key, value＞键值对输出。Map函数对输入数据进行处理后生成＜key, value＞类型的输出列表。在Reduce函数处理过程中，将Map函数处理阶段的输出列表作为Reduce函数的输入列表，随后将key值相同的value生成一个聚集值，作为最后的输出，最终需要将不同Map任务重所有相同key值的列表交换到同一个Reduce任务中。最终结果存储在HDFS上。

1.2 索引系统定义

一般在搜索引擎[3]中，每个搜索对象都被抽象成一组特征项，即P={w1, w2, …wn}。从网页里提取特征项的过程就是文章分析，通过定义函数Pextract来描述[4]这个过程：

其中，集合P={w1, w2, …wn}用于表示特征项词典，网页集合T(P)表示当前保存的整个网页系统，通过定义集合表示系统的索引表：

其中，集合D={w1, w2, …wn}表示文档系统的特征项词典，r表示相关度函数，r(w, p)代表词汇w和网页p的相关度，如果网页p的某个特征项用w表示，通过使用相关度算法会给出相应的正值。

1.3 倒排索引定义及结构

在实际应用中，查找的记录如果需要根据属性值来判断，则可以使用倒排索引查找。通过该索引表的建立的数据结构中，每个数据项中都包括对应的属性值和包含该属性值的每条记录的地址。因为该数据结构不是通过记录来查找相应的属性值，而是由对应的属性值来确定需要查找记录的位置，因此，将这种查找方式称为倒排索引[4]（inverted index）。通过这种索引方式对文件结构进行组织后，通常称该文件为倒排索引文件，简称倒排文件（inverted file）。

倒排索引的另一种称谓为反向索引、置入档案或反向档案[5]。该方式在搜索引擎中很常见，通常在已知所有的数据项中，搜索某个关键字在一组文档中的存储位置的映射，这种数据结构常用于文档检索系统之中。通过倒排索引进行文件查找时，主要根据关键词匹配技术获取包含该关键词的所有文档列表。因此从逻辑结构方面理解倒排索引主要由两个部分组成：“单词词典”和“倒排文件”。

通常利用倒排索引对文本检索时，将每个索引词对应的文档表按文档编号增序排序，通过这种方式进行数据的压缩保存。数据结构如图2所示。

图2 索引结构示意图

左侧为词典中的某个索引词t，右侧为t的倒排表内容，它包含ft项，即为文档集合中含有词t的文档的个数。每一项包括di文档编号，文档的权值wdt，以及该词在文档内出现的位置序列loc。

在倒排索引中，利用单词词典对文档进行结构存储，通过单词词典记录每个单词及所在文档的相关信息，同时用包括该单词对应的文件在倒排索引中的位置信息。在进行搜索时，通过用户给定的关键词，在单词词典中进行查询，这样可以快速获得相应的倒排列表，并以此作为后续排序的基础。对于规模的较大的文档集合来说，包含几十万甚至上百万的不同单词，能否快速对查找单词进行定位，这对搜索过程中响应速度有直接影响，所以需要对单词词典借助高效的数据结构进行构建和查找，倒排索引中常用的数据结构包括哈希加链表结构和树形词典结构。

2 倒排索引算法实现文本检索

在Map/Reduce实现的倒排索引主要包含Map、Combine及Reduce三个过程[6]。在Map过程中，通过分布式文件系统hdfs存储需要处理文档，首先通过Hadoop中的核心类TextInputFormat对输入的文件进行处理，通过处理后可以得到文件中每行对应的偏移量和内容，将偏移量及内容构成的键值对＜偏移量，内容＞作为map的输入。map函数的关键是对key和value的进行设置以适应Map/Reduce框架，从而得到正确的结果。对于文件inverted1.txt与inverted2.txt，搜索关键词的详细设计过程如图3所示。

设计过程中首先需要对整个文档进行切分，得到单词、所属的文档URL及词频，文中设计key=单词＋URL，value=词频。即map的输出为＜单词＋URL，词频＞。

图3 map过程输入／输出

通过map函数处理后的输出的数据中，键值＜单词＋URL，词频＞做为combine过程的输入，该过程需要将同一文档中Key值相同的value值进行累加，如图4所示。

图4 Combine过程输入/输出

在最后reduce处理阶段，是对最终结果进行合并的阶段，需要对不同文档中相同的key值进行处理，该过程根据倒排索引需要的格式进行输出，输出结果为＜单词，URL+词频＞，如图5所示。

图5 Reduce过程输入/输出

3 试验结果与分析

试验中，对比了利用Hadoop集群与集中式搜索两种方式实现倒排索引文本检索的耗时，同时也比较了利用不同数目主机搭建的Hadoop集群实现的倒排索引文本检索速度，试验中，设定主题为“找工作”，分别爬取15、50、100、300、500个网页，以“工程师”为关键字检索与该职位相关的招聘信息，数据采集如表1所示。

表1 不同方式实现的倒排索引文本检索速度表

图6对比了利用Hadoop集群实现的Map/Reduce倒排索引文本平均检索速度与集中式文本检索速度，试验结果表明，当抓取网页数量达到70个时，通过Hadoop集群与集中式实现的倒排索引耗时均接近75 000 ms。当爬取的网页数量为15个时，利用集中式实现的倒排文本索引检索耗时低于Hadoop集群的耗时，而平均检索速度则优于分布式集群。而随着抓取网页的数量增长到500个时，利用集中式实现的文本检索耗时呈比例增长，而通过Hadoop集群进行检索速度明显优于集中式实现的文本检索，造成该现象的主要原因在于集群启动时需要一定的时间，在对网页数据进行分片、复制及不同主机间通信时会消耗大量时间。随着集群所需要的准备工作完毕，利用集群实现的倒排索引文本检索速度远优于集中式文本检索速度。

图6 集中式与分布式文本平均检索速度对比

图7 试验结果表明当抓取网页数量少于70个时，集群主机数越少，主机间通信耗时越少，这是造成集群中利用不同数目主机检索速度不相同的主要原因，当集群中主机间通信的完成时，随着主机数的增加，利用Map/Reduce实现的倒排索引文本检索速度更快，完成文本检索的整个过程中耗时会更少。通过分布式集群实现的Map/Reduce倒排索引文本检索算法在未来搜索引擎中拥有良好的应用空间，该方式会使人们更快的从网络中获取所需要的知识。

图7 不同数目分布式集群实现文本检索对比

4 结语

文本检索在现实应用中是一个重要而迫切的问题，使用倒排索引的文本检索技术可以解决这个问题。而面对现在海量的数据，使用单处理器进行文本检索已无法满足现实的需要。因此，通过Map/Reduce框架，将多个文本交给多个处理器进行检索，不仅提升了文本检索的速度和索引更新速度，同时也减轻了单处理器处理时内存和处理器的压力。