一种基于局域网的分布式搜索引擎设计与实现

打开文本图片集

摘要：以局域网内的分布式处理为立足点，分析了搜索引擎的基本原理，设计并实现了一种基于局域网的分布式搜索引擎。该引擎具有方便扩展、分布式处理、增量式索引和自动负载均衡等特点，适合于校园网和企业网等局域网内应用。

关键词：搜索引擎；分布式处理；爬虫；分词；索引

中图分类号：TP393

文献标识码：A 文章编号：1672-7800（2015）003-0117-02

0 引言

随着社会信息化的不断深入和互联网技术的快速发展，网络信息也以指数级别飞速增长。在日常工作和生活中，要在大量、纷繁的数据中找出有用信息，需要借助搜索引擎的帮助。但传统单服务器模式的搜索引擎由于计算能力限制，进入大数据时代后，其在应用中的不足越来越成为互联网搜索的瓶颈。因此，在海量的互联网信息中进行搜索，单靠服务器计算能力的增长已难以满足要求。为了解决搜索需求与搜索引擎服务器处理能力的矛盾，以分布式处理为技术支撑的分布式搜索引擎应运而生[1]。本文以局域网内的分布式处理为立足点，设计并实现了一种基于局域网的分布式搜索引擎。该引擎具有方便扩展、分布式处理、增量式索引和自动负载均衡等特点，适合于校园网和企业网等局域网内的网络搜索服务。

1 系统总体设计

1.1 搜索引擎系统框架

一个基本搜索引擎由4个主要部分构成：网页信息获取子系统、信息预处理子系统、索引子系统和检索子系统，分别进行网络爬虫信息获取、分词程序、倒排索引和内容检索等功能任务。网络爬虫是在网上爬取网页的一种程序。这里的“爬”指不停地抓取、下载网页并将网页内容分为3部分：网页标题、网页文档内容以及网页中的所有链接。在获取了所有链接后，遍历这些链接并将链接网页下载下来。不断重复上述过程，递归地将所有网页下载下来并存入存储数据库。第二个步骤是进行信息预处理，主要包括由分词程序进行分词，最后通过索引程序对其建立倒排索引。一般对于英文等拉丁语系的网页而言，句子中的单词已天然地被空格分隔好了，因此实现一个基本的搜索引擎无需进行特殊处理即可完成分词程序。然而，对于像中文、韩文或日文等语言来说，由于句子中的文字没有自然分隔，检索词和词组则变得非常繁琐。所谓分词指将一个汉字序列切分成一个个单独的词或词组，分词过程即是将句子中的连续字序列按照一定规范重新组合成词序列的过程。完成分词过程之后，再根据分词结果将文档建立索引，存入数据库。

1.2 搜索引擎模块设计

1.2.1 网络爬虫设计

网络爬虫程序一般包含以下几个模块：①保存种子URL和待抓取URL的数据结构；②保存已抓取过URL的数据结构，防止重复抓取；③页面获取模块；④对已获取的页面内容各个部分进行抽取的模块；⑤负责分布式的模块。

爬虫是从种子URL开始下载网页的，称该种子URL为initial_page，如在initial_page=这个种子链接中，爬虫看到了该页面引向的各种链接，从而爬取到页面首页内容，并将整个网页存储起来。在该首页中，还有种子initial_page的URL，因此要做个记录，避免重复爬取，否则会陷入无休止的循环。所以每次在爬取新网页时，要先检查是否爬过这个网页。如果使用普通的哈希表存储，其时间复杂度为O（logn），互联网上的网页数以千万，若使用这种方法，效率会非常低下。因此，在本文的设计中，使用一种称为布隆过滤器（Bloom Filter）的特殊数据结构来判断该网页是否存储过，其时间复杂度仅为常数O（1）。

1.2.2 分词程序设计

中文分词算法大概分为两大类，第一类是基于字符串匹配，即扫描字符串。如果发现字符串的子串和词相同，即认为找到了一个匹配。在匹配时可以使用KMP算法或BM算法。这类分词通常会加入一些启发式规则，如“正向/反向最大匹配”、“长词优先”等策略，这类算法优点是速度快，时间复杂度都为O（n），实现简单，效果良好。缺点在于对歧义和未登录词处理不好；第二类是基于统计学习和机器学习的分词方法，这类分词基于人工标注的词性和统计特征，对中文进行建模，根据观测到的数据（标注好的语料）对模型参数进行训练。在分词阶段再通过模型计算各种分词出现的概率，将概率最大的分词结果作为最终结果。常见的序列标注模型有HMM和CRF。这类分词算法能很好地处理歧义和未登录词问题，效果比第一类算法好，但是需要大量人工标注数据，另外，分词速度也较慢。在分词效果评价时，除了标注量、准确率等，分词粒度也是一个需要考虑的指标。使用单一粒度的分词往往无法找到合理匹配，多粒度多层次匹配可以达到更好效果。

1.2.3 索引设计

搜索引擎的索引一般采用倒排索引的方法，倒排索引（Inverted index）也常被称为反向索引、置入档案或反向档案，用来存储在全文搜索下某个单词在一个或一组文档中存储位置的映射，是文档检索系统中最常用的数据结构[2]。以英文为例，表1所示是被索引的文本，则倒排索引如表2所示。如果检索条件为："you"、"are"、"good"，则结果将对应集合：{1，2，3}∩{1，3}∩{2，3}={3}。基于以上思想，可以先抓取页面，每个页面抓取完成后在数据库中建立该页面的URL与文档号的满射关系。将要抓取的页面都抓取完后进行分词，然后将分词结果存入数据库，并且根据该结果，建立倒排索引存入数据库。然后按照词语在文档中的频率（PageRank），将每个词语对应的文档进行排序。

2 主要功能模块实现

2.1 爬虫模块实现

如上文所述，爬虫先从种子链接的URL开始，递归地下载并保存网页。本文在实现爬虫的时候参考了开源库Jcrawl和Scrapy等[3]。Scrapy是使用Python开发的一个快速高层次的屏幕抓取与Web抓取框架，用于抓取Web站点并从页面中提取结构化数据。Scrapy用途广泛，可以用于数据挖掘、监测和自动化测试，用户能方便地根据需求进行修改。它也提供了多种类型爬虫的基类，如BaseSpider、Sitemap爬虫等。所以本文使用Scrapy作为爬虫的核心，配合使用布隆过滤器来判断是否访问过该URL。在本文实现时，定义一个Spider类，这个类即是一个爬虫，是scrapy.Spider的子类。刚开始执行该Spider时，response是访问start_urls后的响应，里面包括了URL、源码、header等信息，然后回到Spider的parse函数。该函数有几个目的：如果抓取正确，则生成一个item，并将后续需要抓取的链接添加到爬虫的request队列中；然后获取item的信息，通过使用xpath语句，提取出需要的数据，生成item；随后，再通过yield scrapy.Request（newurl， callback=self.parse）在爬取队列中添加新的URL。

2.2 分词模块实现

中文与英文不同，在字与字之间一般没有空格。汉语是以字为基本单位，所以要实现中文关键字的搜索，需要从连续的字中切分出与所需关键词尽可能接近的词语。中文分词即对中文断句，这样一方面可以消除文字的部分歧义，另一方面还可以进行更多加工。中文分词可以分为如下几个子任务：①分词：把输入的标题或文本内容切分成词；②词性标注：为分出来的词标注上名词或动词等词性，从而部分消除词的歧义；③语义标注：把每个词标注上语义编码。

很多分词的方法是使用词库。词库的来源是语料库或词典。中文分词有两类方法：机械匹配法（如正向最大长度匹配和逆向最大程度匹配等）和统计法（例如最大概率分词方法和最大熵分词方法）。本文在实现分词的过程中使用了jieba Segment[4]。通过基于前缀词典实现高效的词图扫描，将句子中汉字的所有成词可能生成有向无环图（DAG）；采用了动态规划查找最大概率路径， 找出基于词频的最大切分组合；对于未登录词，采用基于汉字成词能力的HMM模型，并使用了Viterbi算法。

2.3 检索模块实现

建立搜索引擎检索模块的过程就是建立倒排索引的过程。首先，对于每个分出的词而言，去寻找文档中是否包含这个词，如果包含则在数据库中该词对应的记录中记录该文档的文档编号。文档编号还有一个属性，即关于这个词的词频，然后通过该词频计算PageRank值。原则上，一个文章的标题是文章中心思想的概括，所以在文档中词频相同的情况下，标题词频PageRank值应为正文词频PageRank值的10倍。整个页面的PageRank值=标题PageRank值+正文PageRank值，然后根据最后的PageRank值决定搜索时的排序。

3 结语

本文分析了局域网内搜索引擎和单服务器模式引擎面临的主要问题，引入以分布式处理为核心的分布式搜索引擎。从原理上分析了分布式搜索引擎的基本工作模式后，在参考一些开源库的基础上设计并实现了一种基于局域网的分布式搜索引擎。本文实现的引擎具有分布式处理、增量式索引和自动负载均衡等特点，而且便于后续扩展，在校园网和企业网等局域网条件下具有很好的应用前景。

参考文献：

[1] 曾剑平，吴承荣，龚凌晖.面向分布式搜索引擎的索引库动态维护算法[J].山东大学学报：理学版，2011（5）：24-27.

[2] 罗刚.使用C#开发搜索引擎[M].北京：清华大学出版社，2012：20-100.

[3] A fast and powerful scraping and web crawling framework[EB/OL]. http：//scrapy.org/.

[4] Jieba.Chinese text segmentation[EB/OL]. https：//github.com/fxsjy/jieba/tree/jieba3k.

（责任编辑：黄 健）