一种高效的文字检索系统

王浩鹏

在互联网中，文字检索是被广泛需要的功能。本文采用倒排索引和多级缓存技术，构建一个文字检索系统。重点在于高效性和经济性。实现了根据输入文字进行文档检索的功能。

【关键词】检索；倒排；缓存

1 引言

随着互联网的发展，用户在不同的需求场景中，对信息检索的需求也逐渐多样化和个性化。当前在信息检索方面已经存在的经典系统，或者性能强大然而对服务器的消耗也十分巨大，又或者只需很少机器但是功能简陋性能不足。本文设计了一种简洁的文字检索系统，旨在利用很少的机器满足大量的检索请求，提出既高效又经济的文字检索解决方案。

2 整体设计方案

系统分为离线和在线两个部分。离线部分主要功能是对已有的检索基础数据建立索引。在线部分的主要功能是根据用户输入的关键词对索引进行检索。

3 离线索引建立

倒排关系的记录方式，即倒排索引。在建立倒排关系的过程中，为了方便动态追加，在内存中采用链式结构；存储到硬盘上时，为了高效读取，采用顺序存储。我们把倒排索引数据称之为倒排拉链。为了高效建立索引结构，我们主要考虑下面两个重点：

3.1 分层建立索引

首先，以一定数目的对象为一组建索引，保证对每组对象建索引的过程能够在内存中完成而不需要存取中间数据到硬盘；然后，将各组结果进行合并，得到最终的倒排索引数据。

3.2 注重内存的使用和硬盘数据的存取

尽量申请足够的大内存块，然后在整个进程周期内重复使用。为了方便对各组索引合并，每组数据输出到硬盘时，将term表排序，索引拉链进行顺序存储。合并时，尽量利用辅助结构，避免大块内存的频繁复制。读取索引拉链时，按块读取。

4 在线检索

在线检索需要处理用户的输入关键词，然后在索引中检索符合关键词的内容。涉及到如下幾个过程：

4.1 关键词的切分

在线检索面临的第一个问题就是处理用户输入（query）。这里用到一个开源的中文分词工具——FNLP。FNLP是采用线性模型（linear model）分词。较于对数线性模型（log-linear model）HMM/CRF所不同的是，线性模型没有归一化因子而直接建模Score函数。我们使用FNLP工具，将用户的输入query切分成多个term。比如query为『周润发的眼镜』，那么会被切分为三个term『周润发』『的』『眼镜』。

4.2 拉链归并

每一个term对应一个倒排拉链，这个拉链代表着索引内与这个term相关的内容集合。那么对于多个term——即用户query的变体——我们需要对多个term的拉链进行归并。这里我们使用字典归并的方式。字典是一个用HASH表实现的数据结构，目的是建立键与值之间的映射关系。键在这里就是拉链文档id，而值是这个id出现在各个拉链中的次数。当id出现在每一个拉链中时，就可以认为这个id符合交的要求，可以加入到结果队列中。理论上可以在O（1）的时间内找到这种映射关系。由于字典本身就是一个无序的数据结构，所以字典归并不要求待归并队列必须有序。

经过拉链归并之后，即可得到一个与query有关的内容拉链，可以经过简单的处理之后返回给用户展现。

4.3 多级缓存

考虑到文本内容的确定性和用户query的重合性，尤其是如果用户群体或者目的较为单一，query的重合概率极高。所以我们设计多级缓存以便减轻后端归并的请求量，达到节省机器的目的。多级缓存包括内存缓存、硬盘缓存和集群缓存。

内存缓存直接使用一个map结构进行多线程的存储共享实现缓存。硬盘缓存采用LRU策略，把磁盘空间分为大小分别为1K， 2K， 4K...多个块的链表来管理，插入缓存时尽量fit，“多余”的块重新插入。

集群缓存系统采用开源的memcache系统。Memcache是一个基于内存中的hash表实现的分布式缓存系统。我们可以在自己的服务器上面根据需要部署。

在获取到检索内容之后，将用户query作为key，内容拉链进行protobuf打包，作为value，存放到内存map表或者硬盘或者memcache中。用protobuf打包目的是节省缓存的内存和传输带宽。具体存放到哪一级的缓存中，视该query的频次而定：频次越高的query，越是向内存中转移；频次越低的query，越趋向于存放到集群缓存中。

在收到用户请求query之后，系统会首先去请求各级缓存，查看缓存中是否存有该query的内容拉链，如果有，那么终止对下级缓存的请求并直接获取并提供给用户。如果各级缓存都没有，则进行拉链归并。

5 结论

本文设计了一个简洁高效经济的文字检索系统。用nginx作为web服务器的话，可以支持很高的并发。同时在线模块运用缓存系统和字典归并，能快速处理用户请求。而离线系统建立的倒排索引，进一步从组织方式上对检索过程进行了优化。

有别于一般的产品驱动的系统设计，本系统属于性能需求驱动的。故相比于产品类系统堆砌功能，本系统重点在于满足传统功能的基础上，构建一个性能非常出色的系统。故本文的重点在于系统的性能。相较于功能，本文更关注系统的速度、规模、可用性和扩展性。力求用较小的成本实现最出色的性能。

参考文献

[1]郭欣著.构建高性能Web站点[M].电子工业出版社，2012.

[2]Erich Gamma，RichardHelm，RalphJohnson，JohnVlissides著.李英军，马晓星，蔡敏，刘建中译.设计模式：可复用面向对象软件的基础[M].机械工业出版社，2000.

[3]伽玛著.设计模式[M].机械工业出版社，2007.

[4]Stanley B.Lippman，JoséeLajoi， Barbara E. Moo著.王刚， 杨巨峰译.C++ Primer[M].电子工业出版社，2013.

[5]丁明一著.Linux运维之道[M].电子工业出版社，2014.

[6]阿尔斯帕瓦/罗宾斯著.网站运维[M].电子工业出版社，2011.

作者单位

河北省张家口市宣化区第一中学（高三7班） 河北省张家口市 075100endprint