论文部分内容阅读
信息检索系统是互联网中最常见的应用之一,例如Web搜索引擎、在线文献检索系统等等。在这些系统中,倒排索引是最常见也最重要的数据结构。倒排索引文件通常比较大,需要耗费大量存储空间和传输时间,因此往往要对倒排索引文件进行压缩。而倒排索引压缩的效率又会很大程度上影响整个检索系统的效率。为此,相关研究人员提出了多种倒排索引压缩编码。在这些编码中,IPC(Binary Interpolative Coding,也称BIC)编码是一种压缩率突出的树形编码,经常被用于对存储空间要求比较高的场景。但是,IPC编码的解压速度比较慢,这大大限制了IPC编码的进一步应用。因此,本文主要研究IPC编码的优化技术,从压缩率、解压速度与线上查询处理效率等多个方面进行深入的探索,目标是在提高或不降低压缩率的前提下提高IPC编码的解压速度和线上查询处理效率。本文主要有如下三个贡献: 提出了一种基于部分解压的IPC编码线上处理方法PDIPC。在检索过程中,IPC编码在线上处理的主要时间消耗在解压过程。通过分析IPC编码中元素的顺序,本文发现IPC编码在存储时所有的子树的取值区间都可以根据双亲节点的取值来确定,因此IPC编码在线上处理流程中并不需要解压所有节点,部分子树可以被略过。这种部分解压的策略可以减少解压节点的数目从而提高线上处理速度。实验表明,部分解压可以将布尔AND查询的线上处理速度提高约40%,将排序查询的处理速度提高约10%。 提出了一种基于最优分块的IPC编码的改进方案OBIPC。本文通过分析IPC编码的结构与各元素的编码长度,发现倒排表中的过长差值是IPC编码压缩率进一步提高的瓶颈。这些超长的差值会影响IPC编码树中多个节点的编码长度,而根据超长差值拆开原列表将显著降低列表整体的编码长度。本文提出了两种拆开列表的方案,并为方案一找到了全局最优解。实验表明,方案一能够在解压速度降低仅仅1%的同时将IPC编码的压缩率提高约13%,方案2则能在提高约4%的压缩率的前提下略微提高解压速度。 提出了一种基于分步的IPC编码快速解压方法FDIPC。本文通过分析IPC编码的解压流程,发现它速度慢的根本原因在于解压时要为编码树中每个节点计算大量相关信息。分析表明,如果不解压每个节点的值,而只解压差值列表,需要计算的信息的量则会大大降低,而且差值列表可以很快累加为原始列表。基于上述思想,本文提出了两种分步解压的方案,它们都首先解压出差值列表然后累加差值列表。实验表明,方案二能将布尔AND查询、布尔WAND查询及排序查询的线上处理速度提高约14%,方案一则能在不改变编码结构的前提下将上述三类查询的处理速度提高约6%。 在上述工作的基础上,提出了一种将上述方法进行组合优化的方案。用户可根据问题的具体要求选择优化技术的组合。其中,PDIPC、OBIPC方案2与FDIPC方案1的组合方案在提高了约12%的压缩率的前提下,将布尔AND、布尔WAND与排序查询的查询处理速度分别提高了44%、12%与11%。优化后的IPC编码在WAND查询和排序查询上的解压速度得到显著提升,在布尔AND查询上的处理速度也与其他主流编码相当,与此同时,编码的压缩率得到进一步提升。