关键词:
倒排索引
遗传算法
聚类算法
搜索引擎
索引压缩
摘要:
在分布式存储系统中,搜索引擎是快速检索文件的主要工具,其中,倒排索引是大规模搜索引擎的核心数据结构,它本质上是一个被称为倒排列表的有序整数序列集合。由于此类引擎索引的文件过多,且查询的重负荷有着严格的性能要求,倒排索引中有着数十亿的整数,查询过程必须对此有效地进行检索。压缩倒排索引有两个好处,时间上,在更快的内存结构中可以放入更多数据,加快查询速度;空间上,减少存储索引所需要的机器数量,节省存储空间。索引压缩算法的性能需要综合考虑算法的编码速度,压缩率和查询时间等指标。本文以Partitioned Elias-Fano索引压缩算法为研究对象,基于以上性能指标展开研究,本文工作主要有以下三个方面:(1)针对PEF索引编码过程过慢的问题,提出一种基于遗传算法的PEF(Partitioned Elias-Fano)算法。该算法将PEF算法中倒排列表的划分问题看作求解图的最短路径问题,采用基于优先级的方式将划分方案编码为遗传算法过程中的染色体,经过多轮遗传操作,在线性时间可以大概率获得次优划分方案,小概率获得最优划分方案。实验结果表明,基于遗传算法的PEF与原算法相比,索引生成速度提高了 28%,并保持了与PEF算法相似的压缩率查询时间权衡。(2)针对PEF算法每次只能编码单个倒排列表,未能利用列表间的相似子集减少冗余的问题,提出了一种基于Mean Shift聚类的PEF算法。该算法对倒排列表进行聚类,并为每个的簇构建一个临时的参考列表,簇中的列表都使用Elias-Fano算法进行编码。同时设计了两种启发式构建参考列表的算法,二者在将倒排列表元素添加到参考列表的方式有所不同:根据在簇中出现的频率;根据编码需要的比特数。实验结果表明,与PEF算法相比,平均每个元素可以节省0.5比特,同时并不影响查询时间。(3)为实现分布式系统的文件资源检索功能,设计并实现了一个针对该系统的搜索引擎。其主要包括六个模块,分别为用户注册模块,用户登录模块,索引构建模块,索引压缩模块,文件资源检索模块和个人信息管理模块。系统已通过了相关功能性测试,相关功能基本已实现,并将性能较好的几种倒排索引压缩算法应用其中。