Microsoft Word doc

Size: px

Start display at page:

Download "Microsoft Word - 140214.doc"

竺郁
7 years ago
Views:

1 第 40 卷 Vol.40 第 2 期 No.2 计算机工程 Computer Engineering 2014 年 2 月 February 2014 体系结构与软件技术文章编号 : (2014) 文献标识码 :A 中图分类号 :TP301.6 基于 64 位体系结构的倒排索引压缩算法张旭东 1, 孙志明 2, 刘亚宁 1, 单栋栋 1, 闫宏飞 (1. 北京大学网络与信息系统研究所, 北京 ;2. 哈尔滨医科大学附属第一医院信息中心, 哈尔滨 ) 摘要 : 在 64 位体系结构的 CPU 中, 字长从 32 位扩展到 64 位, 处理器每次可以处理的数据也增加到 64 位这对搜索引擎使用的核心数据结构倒排索引的压缩与解压缩带来一定的影响针对当前 32 位整数字对齐压缩算法 Simple 不适用于 64 位系统的问题, 对其进行改进, 并提出 3 种基于 64 位的字对齐压缩算法, 即 SimpleX64-16 SimpleX64-32 和 SimpleX 种算法都采用多种压缩模式, 并对每个模式进行压缩空间的优化在 64 位机器上 GOV2 和 ClueWeb09B 数据集的倒排索引实验结果表明, 与传统的基于 32 位字对齐的压缩算法相比,3 种基于 64 位字对齐的算法在解压速度方面最多提高 14.5%, 在压缩率方面最多提高 2.5% 关键词 : 倒排索引 ; 索引压缩 ;64 位体系结构 ; 搜索引擎 ; 信息检索 Inverted Index Compression Algorithms Based on 64-bit Architecture ZHANG Xu-dong 1, SUN Zhi-ming 2, LIU Ya-ning 1, SHAN Dong-dong 1, YAN Hong-fei 1 (1. Institute of Network Computing and Information Systems, Peking University, Beijing , China; 2. Information Center of the First Affiliated Hospital of Harbin Medical University, Harbin , China) Abstract In the 64-bit architecture of the CPU, the word length extends from 32 bit to 64 bit, and the data which CPU can process each time also increases to 64 bit. Few studies are performed to date to answer what influences 64-bit systems have on the compression and decompression of inverted index, which is the primary data structure in search engines. Some compression algorithms of posting lists work well on 32-bit machines, but are inefficient on 64-bit machines. This paper proposes three word-aligned compression algorithms on 64-bit system, namely, SimpleX64-16, SimpleX64-32 and SimpleX It adopts more modes and optimizes each mode for each algorithm. Experiments based on inverted index of GOV2 and ClueWeb09B show that those algorithms can improve compression ratio by 2.5% and decompression rate by 14.5%, compared with the traditional 32-bit word-aligned compression algorithms, on 64-bit machines. Key words inverted index; index compression; 64-bit architecture; search engine; information retrieval DOI: /j.issn 概述搜索引擎作为网络时代的信息检索工具, 目前已成为用户获取网络信息的主要途径之一, 其核心数据结构是倒排索引搜索引擎通常利用倒排索引压缩技术来提升查询处理速度该技术除了能够减少倒排索引占用的磁盘空间外, 还能减少内存占用, 提高 CPU 缓存的命中率 [1] 为了不断提升搜索引擎的性能, 人们越来越多地采用 64 位体系结构在 64 位体系结构中, 字长从 32 bit 扩展到了 64 bit, 处理器每次可以处理的数据也增加到了 64 bit 一些倒排链的压缩算法在 32 位系统上性能很好, 但移植到 64 位系统上时不能充分发挥出 64 位机器的性能本文在 32 位系统 Simple [2-4] 系列算法的基础上, 提出 64 位体系结构下的算法 SimpleX64 系列 2 相关工作 2.1 倒排索引和 d-gap 操作倒排索引由词典 (dictionary) 和倒排表 (posting lists)2 个部分组成倒排表包含若干个倒排链 (posting list), 每个倒排链包含一组倒排记录 (posting) 对于文档 m 和词项 t, 其对应的倒排记录一般包含以下信息 :<DocID, tf t, [pos 1, pos 2,, pos tf ]> 其中,DocID 指的是 m 的文档编号 ;tf t 指词 t 在文档中出现的次数 (term frequency),pos i 指词 t 在文档 m 中的每个出现位置,i=1,2,,tf t 这些信息都由一系列非负整数组成倒排索引的结构如图 1 所示在实际存储时, 通常把倒排链中各个倒排记录的文档号 DocID 存储在基金项目 : 国家自然科学基金资助项目 ( , ); 人人游戏基金资助项目 (QXWJ-YX ) 作者简介 : 张旭东 (1989-), 男, 硕士研究生, 主研方向 : 网络数据挖掘, 信息检索 ; 孙志明, 工程师 ; 刘亚宁, 硕士研究生 ; 单栋栋, 博士研究生 ; 闫宏飞, 副教授收稿日期 : 修回日期 : zxd@net.pku.edu.cn

哈尔滨医科大学附属第一医院信息中心, 哈尔滨 150001) 摘要 : 在 64 位体系结构的 CPU 中, 字长从 32 位扩展到 64 位, 处理器每次可以处理的数据也增加到 64 位这对搜索引擎使用的核心数据结构倒排索引的压缩与解压缩带来一定

2 72 计算机工程 2014 年 2 月 15 日一起, 词频 tf 存储在一起, 位置信息 pos 存储在一起, 以提高存储空间利用率和倒排链读取速度图 1 倒排索引结构通常, 倒排链中的各个倒排记录是按照文档号 (DocID) 递增排序的在压缩倒排索引之前, 通常会对待压缩的数字做序列转换, 使得待压缩的序列的整体值变小, 从而提升压缩率 d-gap 操作是常用的序列转换操作之一, 它适用于处理递增的序列 : 对于一个严格递增的正整数序列 d 1,d 2,,d n,d-gap 操作对每个数字使用 d i =d i d i 1 1(i>1,d 0 =0) 进行替换也就是说,d-gap 操作将一组递增文档号序列转换成相邻文档号之差组成的非负整数序列例如, 对文档号序列进行 d-gap 操作后, 转化为序列在倒排索引中, 索引词对应的文档号和索引词在文档中出现的位置通常是递增的, 所以可以使用 d-gap 操作以减少待压缩数字的大小本文中对倒排链的压缩均指的是对文档号序列的压缩 2.2 倒排索引压缩问题倒排索引压缩问题是指 : 给定 n 个以固定位数 (32 bit 或 64 bit) 表示的非负整数, 设计一种算法将它们转变成一个二进制编码序列, 使得转换后所有数字的编码总长度比输入时的二进制编码总长度更少对应的解压缩问题则为 : 设计算法将二进制编码还原成若干固定字长的非负整数 2.3 常见的倒排压缩技术倒排索引的压缩算法主要可以分成以下 3 类 :(1) 比特对齐的压缩算法, 指对每个压缩的整数用若干比特表示, 代表算法有 Elias Gamma [5] Golomb [6] Rice [7] Elias- Fibonacci [8] 等 ;(2) 字节对齐压缩算法, 指对每个压缩整数用若干个字节表示, 代表算法有 Variable Byte [9] Group Variable Byte [10] SIMD-GVB [11] 等 ;(3) 字对齐压缩算法, 指在一个字 (32 bit 或 64 bit) 中压缩多个整数, 代表算法有 Simple [2-4] 系列 ; 另外, 还有一些对固定比特长度的数字进行压缩的算法, 如 PForDelta [12] AFOR [13] 本文的 SimpleX64 算法就是在字对齐压缩算法 Simple 系列的基础上提出的在 Simple-9 [3-4] 算法中, 一个 32 bit 的字被分成 2 个部分 :4 bit 的模式段和 28 bit 的数据段它使用 9 种不同的模式来区分 28 bit 数据中的整数组合 :28 个 1 bit 整数,14 个 2 bit 整数,9 个 3 bit 整数,7 个 4 bit 整数,5 个 5 bit 整数, 4 个 7 bit 整数,3 个 8 bit 整数,2 个 14 bit 整数,1 个 28 bit 整数在解压缩时, 只需要读取前 4 bit 的值就能推算出后 28 bit 数据中压缩了多少个整数, 以及这些整数各占多少比特这个压缩算法的主要缺点是, 在一些情况下 28 bit 中的一些位不能充分利用, 如在 5 个 5 bit 中就有 3 bit 没有被使用, 所以其在存储空间的利用上不是很紧凑另外, 该算法对于大于 28 bit 的数字无法进行编码文献 [2] 在 Simple-9 的基础上提出了 Simple-16 算法, 其模式段仍是 4 bit, 但使用了 16 种的模式, 而且每种模式都完全利用到了 28 bit 的数据段他们增添了一些复杂的模式, 例如 3 个 6 bit 数字和 2 个 5 bit 整数的组合 10 个 2 bit 整数和 8 个 1 bit 整数的组合等文献 [14] 实现了 Simple 系列 Carry 系列 Slide 系列等压缩算法的 64 位版本, 并对上述各算法的压缩率和解压缩速度进行了比较, 其基于 64 位的 Simple 压缩算法的性能相比于其他算法的性能效果指标都要好在 Simple 算法实现中, 一个 64 bit 字被划分为 4 bit 的模式段和 60 bit 的数据段, 但是只使用了 14 种模式与 Simple-9 一样, 该算法对一些模式的存储空间不够紧凑目前, 国内对于倒排索引压缩的研究较为有限文献 [15] 将倒排索引压缩技术应用于 RDBMS 全文检索中文献 [16] 提出了 Star-Scan 算法, 该算法利用聚类技术将相似文档排在一起, 从而减少文档之间 d-gap 所需要的字节数, 达到提高索引压缩率的效果文献 [17] 对目前几种倒排索引压缩技术进行分析和研究, 对比了各个算法的压缩比压缩与解压缩的时间和对文件读取和查询所花费的时间 3 64 位体系结构上的 SimpleX64 压缩算法 3.1 SimpleX64 算法原理本文在 64 位体系结构上实现了改进后的 Simple 压缩算法, 将其命名为 SimpleX64 该压缩算法根据一定的模式, 每次将若干个非负整数进行编码, 使得他们能够放入一个 64 bit 的字中这里的 SimpleX64 压缩算法使用了更多可选模式 (16 种 32 种 64 种 ), 相应的每个字中模式段所占位数也会发生变化 ( 分别为 4 bit 5 bit 6 bit) 本文将 SimpleX64 系列的 16 种 32 种 64 种模式 3 个版本分别称为 SimpleX64-16 SimpleX64-32 SimpleX64-64 基于最大熵原则 [18], 在只掌握关于未知分布的部分知识时, 应该选取符合这些知识但熵值最大的概率分布, 因而在每种模式下各个整数的所占位数要平均表 1 给出了 SimpleX64 的 16 种模式的具体情况其中, 表示一列中的 3 (9,8)+9 指一个 64 bit 字中有 7 个整数, 每个整数的最大比特长度分别为也就是说它们的最大值分别是采用更多模式的理由是 : 当字长从 32 bit 增加到 64 bit 时, 字中数据段长度相应翻倍, 可容纳的数字个数变多, 数字的多样性也更大, 这时需要使用更多的模式来处理更多种类的数字组合当然也要考虑模式增加和数据段长度占整个字长比例的减少对压缩率和解压缩速度的综合影响

作之一, 它适用于处理递增的序列 : 对于一个严格递增的正整数序列 d 1,d 2,,d n,d-gap 操作对每个数字使用 d i =d i d i 1 1(i>1,d 0 =0) 进行替换也就是说,d-gap 操作将一组递增文档号序列转换成相邻文档号之差组成的非

3 第 40 卷第 2 期张旭东, 孙志明, 刘亚宁, 等 : 基于 64 位体系结构的倒排索引压缩算法 73 表 1 SimpleX64 的 16 种模式编号数量表示 /bit 编号数量表示 /bit (8,7) (1,2) (9,8) (2,3) SimpleX64 算法工作过程 SimpleX64 算法的工作过程和 Simple9 基本相似以 SimpleX64-32 为例 ( 模式段长 5 bit, 数据段长 59 bit) 描述该算法的工作过程算法中各个模式按照以下方式排列 : 随着模式编号的增加, 模式中 59 bit 数据段可以容纳整数个数逐渐变少, 而每个整数的范围逐渐增加算法的压缩和解压缩过程分别如下 : 压缩过程分为 2 个步骤 : (1) 按照模式序号递增的顺序遍历 32 个模式, 直至找到一个模式, 使得待压缩整数都在该模式中各个整数可表示范围内这样可以在一个压缩后的 64 bit 字中保存尽可能多的整数如给定这样一组包含 23 个整数的文档号 d-gap 的序列 :0,1,2,1,3,2,1,3,2,0,5,7,4,3,7, 5,6,6,6,5,4,7,7 按照模式序号递增顺序遍历模式时, 发现模式 59 个 1 bit 无法表示第 3 个整数 2, 模式匹配失败, 选下一个模式从头匹配, 以此类推, 直至发现模式 10 个 2 bit 和 13 个 3 bit 恰好可以表示以上 23 个整数时, 模式匹配成功 (2) 依照模式使用位操作, 将该模式序号和各个整数的压缩后的二进制编码按顺序放入一个 64 bit 字中例如, 将第 1 个整数 0 编码成 00, 第 2 个整数 1 编码成 01, 第 3 个整数 2 编码成 10, 以此类推编码后的 64 bit 字如图 2 所示 3.3 SimpleX64 算法中的模式选择当 SimpleX64 可选模式增加至 32 甚至 64 个之后, 如何确定模式具体内容将是一个重要的问题应通过分析真实网页集合的倒排索引来确定模式本文采用 GOV2 和 ClueWeb09B 的数据集建立了随机倒排索引和有序倒排索引 GOV2 是美国国家标准与技术研究院 (NIST) 于 2004 年上半年从.gov 域名下的网站抓取的万左右的网页集合 ClueWeb09B 是 TREC09(the Text Retrieval Conference) 评测试用的数据集, 包含万左右的英文网页随机索引指事先将原始网页集中网页之间的顺序打乱后再建立索引 ; 有序索引是指事先将原始网页集中的网页按照 URL 站点部分的反转字符串排好序后, 使得同一站点的网页集中在一起, 再建立索引对于上述 4 个倒排索引, 其文档号序列的 d-gap 分布如图 3 所示横坐标表示一个非负整数恰好需要的比特个数, 纵坐标是这类整数在索引的 d-gap 序列中的比例具体地讲, 落在区间 [2 b 1, 2 b 1] 内整数对应的横坐标是 b 例如, 十进制整数 7 的二进制表示为 111, 最少需要 3 bit 来表示, 因此对应的横坐标是 3 本文规定, 整数 0 对应的横坐标都是 1 可以发现,GOV2 和 ClueWeb09B 的同类型索引的 d-gap 分布基本一致对于 GOV2 和 ClueWeb09B 的随机索引, 在为 [0,1] 内的整数最多, 次多的是在 [2 3, 2 4 1] 之间在 2 4 之后,d-gap 分布随着数字的增大而逐渐减少图 3 GOV2 和 ClueWeb09B 索引文档号 d-gap 序列分布在建立索引时, 遍历网页的顺序不同将会影响到文档号的分配, 进而影响到文档号序列的 d-gap 的分布在 GOV2 图 2 SimpleX64_32 的一个编码例子解压缩过程也分为 2 个步骤 :(1) 对于压缩后每个长度为 64 bit 的数据块, 先读取最高的 5 bit( 模式段 ), 取得模式序号, 进而确定对应模式包含的整数个数和各整数的表示范围 (2) 使用位操作对数据块的低 59 bit( 数据段 ) 进行解码和 ClueWeb09B 的有序索引中, 文档号的 d-gap 比例随着比特位的增加而急剧下降 : 值为 0 或 1 的整数占到了 50% 以上, 而值为 2 或 3 的整数比例只有不到 10% 这是因为在将文档按照 URL 顺序建立的索引中, 一个词在若干篇文档号连续的文档中出现的可能性更高, 使得低数值的 d-gap 的数量会更多从对这几个索引的文档号序列 d-gap 分析中可以发现一个共同点 : 恰好能用 b 表示 d-gap 的数量会随着 b 的增加而逐渐减少因此, 在 SimpleX64-32 SimpleX64-64 算法中, 应该适当增加针对小数值整数的一些模式在

2 SimpleX64 算法工作过程 SimpleX64 算法的工作过程和 Simple9 基本相似以 SimpleX64-32 为例 ( 模式段长 5 bit, 数据段长 59 bit) 描述该算法的工作过程算法中各个模式按照以下方式排列 : 随着模式编号的增加, 模式中 59

4 74 计算机工程 2014 年 2 月 15 日 SimpleX64-16 中, 允许的最大整数比特长度为不超过 6 的模式有 8 种 ( 即表 1 中的模式编号 0~7), 占到模式总个数的 50%; 而在 SimpleX64-64 中, 允许的最大整数比特长度为不超过 6 的模式有 49 种, 占到模式总个数的 76% 4 实验结果与分析 4.1 实验环境和方法实验使用了 2 台机器 : 一台是具有 48 GB 内存,CPU 频率 2.4 GHz(Intel(R) Xeon(R) E5645) 的 64 位 Linux 服务器 ; 另一台是 8 GB 内存,CPU 频率 1.6 GHz(Intel(R) Xeon(R) E5310) 的 32 位 Linux 服务器各个压缩算法均采用 C++ 实现, 并使用 O2 的编译优化级别实验使用 GOV2 和 ClueWeb09B 2 个数据集, 对其中标题和正文 2 个部分建立倒排索引使用数据集对应的 500 个查询串, 取出其中所有不重复的词, 并过滤掉其中常用的停用词后作为查询词集合然后对查询词集合中每个词对应的倒排链中的 d-gap 序列进行压缩和解压操作, 再将各个倒排链的解压速度和压缩率进行平均, 得到最终结果在压缩率和解压缩速度 2 个指标上, 本文将 SimpleX64-16 SimpleX64-32 SimpleX64-64 和 Simple-9 Simple-16 以及文献 [14] 提出的算法 ( 这里称为 SimpleX64-14) 进行了比较其中,SimpleX64-16 SimpleX64-32 SimpleX64-64 均采用了分支选择判断的实现方式在 64 位机器上的实验结果如图 4 和图 5 所示, 在 32 位机器上的实验结果如图 6 所示其中, 解压速度越大越好, 压缩率越小越好 ;S-9 S-16 SX-14 SX-16 SX-32 SX-64 分别是 Simple-9 Simple-16 SimpleX64-14 SimpleX64-16 SimpleX64-32 SimpleX64-64 算法的缩写图 4 各个压缩算法在 64 位机器上解压速度的比较图 5 各个压缩算法在 64 位机器上压缩率的比较图 6 各个压缩算法在 32 位机器上解压速度的比较 4.2 结果分析针对本文的研究目的, 本节将重点分析各压缩算法在 64 位机器上的性能对于 GOV2 数据集, 从图 4 和图 5 中可以发现, 本文提出的 3 种算法 SimpleX64-16 SimpleX64-32 SimpleX64-64, 无论在解压速度还是在压缩率上都比文献 [14] 提出的 64 位 Simple 算法 (SimpleX64-14) 效果要好相比于文献 [14] 的 Simple 算法, 这些算法中各个模式没有浪费任何数据位, 使得压缩率变得更好而更好的压缩率使得待解压的 64 bit 数据块的个数变得更少, 使解压速度得到提升在改进的 SimpleX64 系列算法中, 随着模式数量的增加, 压缩效果变得更好 ( 在 64 位机 GOV2 随机索引上, SimpleX64-64 压缩率比 Simple-16 算法要好 2.5%) 由于模式数量增至 64 种时, 相比于 16 种模式可以应对更多的相邻数字组合但在解压速度上, 既要考虑压缩率变好带来的带解压数据量的减少, 又要考虑模式数量增加时模式判定开销的增加综合 2 个方面因素, 发现 SimpleX64-32 速度较快 ( 在 64 位机 GOV2 随机索引上, 比非 SimpleX64 系列中解压速度最好的 Simple-9 要快 14.5%) 下面将改进的 SimpleX64 系列算法和 32 位的字对齐算法 Simple-9 Simple-16 在 64 位机器上进行比较在解压缩速度方面 : 如图 4 所示, 在 GOV2 索引上, SimpleX64 系列算法的解压速度普遍好于 32 位 Simple 算法这是因为在 SimpleX64 中, 一次可以解压出 64 bit 的数据, 而在 Simple-9 和 Simple-16 中, 同样的 64 bit 数据平均需要分成 2 次解压在 64 位系统下,CPU 的通用寄存器是 64 bit, 处理的操作数最大可以为 64 bit, 因此在 SimpleX64 算法中, 一个压缩后的 64 bit 字只要一次就能读取 ; 而 Simple-9 和 Simple-16 算法在 64 位系统上运行时,2 个连续的 32 bit 字需要 CPU 读取 2 次, 每次只读取 32 bit, 导致 CPU 的数据读取与解压次数增加, 因而解压开销也增加了在压缩率方面 : 如图 5 所示, 在 GOV2 索引上 SimpleX64 系列中最好的 SimpleX64-64 算法比非 SimpleX64 系列中最好的 Simple-16 要好一些首先, 在 SimpleX64 系列算法中, 在压缩后的数据里模式段即控制部分所占的比例, 均比 Simple 系列算法要小具体而言, 在 Simple-9 和 Simple-16

6 GHz(Intel(R) Xeon(R) E5310) 的 32 位 Linux 服务器各个压缩算法均采用 C++ 实现, 并使用 O2 的编译优化级别实验使用 GOV2 和 ClueWeb09B 2 个数据集, 对其中标题和正文 2 个部分建立倒排索引使用数据集对应的 500 个查询

5 第 40 卷第 2 期张旭东, 孙志明, 刘亚宁, 等 : 基于 64 位体系结构的倒排索引压缩算法 75 的每个 32 bit 字中, 模式段占 4 bit, 控制部分比例为 4/32= 12.5%; 而在 SimpleX64 系列中, 即使采用最多的 64 种模式, 控制部分最多也只占 6 bit, 控制位所占比例至多为 6/64=9.375% 另外,SimpleX64-32 和 SimpleX64-64 使用了更多的模式, 可以覆盖更多的整数序列组合但是, 字长从 32 位扩展到 64 位也会对压缩效果有影响因为从直观上看, 当一串数字个数增多时, 数字的多样性会增加, 即各个数字的差别可能会更大字长扩展到 64 bit 时, 虽然模式数量增加了, 但仍不能比 2 个 32 bit 的字容纳更多的数字如图 7 所示, 有 30 个整数, 即 A B 以及 28 个连续的 1 其中, A B 分别需要 14 bit 表示图 7(a) 表示, 在 Simple-9 或者 Simple-16 算法中,A B 可以一起用一个 32 bit 的字编码, 剩下 28 个 1 用另一个 32 bit 字来编码, 共 64 bit 图 7(b) 表示, 在 SimpleX64-32 中, 最好的模式 ( bit) 的一个 64 bit 的字只能装入前 4 个数字 A B 1 1, 剩下的 26 个 1 需要放入下一个字中, 所以至少需要 2 个 64 bit 字在 GOV2 有序索引的一个倒排链中, 倒排记录是按照 URL 排序的, 相同站点网页对应的相邻倒排记录之间的 d-gap 会很小 (0 或 1), 但不同站点网页对应的相邻倒排记录的 d-gap 会很大这是因为一个词可能在某个站点的网页中频繁出现, 但在和此站点 URL 上相邻的网站内根本不出现上述情形将导致 d-gap 值序列出现一个很大的突变, 使得小数值整数的模式无法满足它根据图 7 的解释, 这种突变情况给 SimpleX64 算法的压缩率带来的损失要大于 Simple 算法, 因为有更多的大数值整数模式未得到充分利用 ( 本可以容纳下一个很大的整数, 但实际只装了一个小的整数 ) 因此, 字长的扩展对压缩率的影响既有正面的, 也有负面的缩率 2 个指标上的优劣程度均与 GOV2 的对应索引下的情况一致这说明 SimpleX64 系列各个算法较为稳定, 并让上述 GOV2 索引上的实验结果分析更具有说服力, 可扩展到其他数据集上从以上实验分析可以看到 : 在 64 位机器上, 本文提出的 SimpleX64 系列算法中, 在解压速度上 SimpleX64-32 效果最好 ; 而在压缩率上,SimpleX64-64 效果最好由于随机索引中 d-gap 分布比有序索引更为平滑, 大数值整数对应模式被充分利用的可能性更大, 使得 SimpleX64 系列算法在随机索引上的性能相比于有序索引可以得到更好的提升而在 32 位机器上, 改进的 SimpleX64 算法解压速度, 包括文献 [14] 的 SimpleX64-14 均不及 32 位 Simple 算法 ( 见图 6) 这一结果也说明,Simple 算法适合 32 位体系结构, 而本文 SimpleX64 算法更适合于 64 位体系结构 4.3 实现方式在 Simple-9 Simple-16 SimpleX64-16 这 3 种算法中, 由于可选的模式不超过 16 种, 可以使用一组选择判断来完成 ( 如 C++ 的 Switch-Case 语句 ) 而对于 SimpleX64-32 和 SimpleX64-64 算法, 由于模式数量增加到了 32 bit 和 64 bit, 使用选择判断语句的话代码将会较为冗长, 可以使用预定义数组来记录下各个模式的信息本文对 SimpleX64-16 SimpleX64-32 SimpleX64-64 分别使用分支判断和查表 2 种实现版本, 在 64 位机器上比较了它们的性能实验结果如图 8 所示在算法名称中, 后缀 S 表示选择判断的实现方式,T 表示查表的实现方式 (a)simple-9/16 编码示例 (b)simplex64-32 编码示例图 7 d-gap 突变的例子在 ClueWeb09B 的随机 / 有序 2 个索引中,Simple 系列和 SimpleX64 系列各个算法在 64 位机器上的解压速度和压图 8 SimpleX64 系列算法在不同实现机制下解压速度的比较从实验结果中可以发现, 使用选择判断实现方法的解压速度均比使用查表实现高出 50% 以上这是因为使用查表的实现方式, 在每次查表时需要从内存或缓存额外加载对应的表项到 CPU 中, 而表项数量很多, 这可能会影响 CPU 的缓存命中率另外在解压的过程中还需要遍历表项来解压特定的数值, 而使用选择判断的实现方式则不会碰到这个问题 5 结束语本文研究了以往倒排链上 Simple 系列压缩算法的工作

375% 另外,SimpleX64-32 和 SimpleX64-64 使用了更多的模式, 可以覆盖更多的整数序列组合但是, 字长从 32 位扩展到 64 位也会对压缩效果有影响因为从直观上看, 当一串数字个数增多时, 数字的多样性会增加, 即各个数字的差别可

6 76 计算机工程 2014 年 2 月 15 日流程, 指出它们在 64 位系统上的不足, 并据此提出 64 位体系结构下的 SimpleX64 系列算法, 添加了更多模式, 其中相当一部分模式是适用于小数值整数的在基于 GOV2 和 ClueWeb09B 的倒排索引上的测试结果表明,SimpleX64 系列算法相比于 Simple 算法在解压速度和压缩率上均有所提升今后将在此基础上继续改进 SimpleX64 中的模式选择方案, 并进行 SimpleX64 并行解压缩的尝试参考文献 [1] Manning C D, Raghavan P, Schütze H. An Introduction to Information Retrieval[M]. New York, USA: Cambridge University Press, [2] Zhang Jiangong, Long Xiaohui, Suel T. Performance of Compressed Inverted List Caching in Search Engines[C]//Proc. of the 17th International Conference on World Wide Web. New York, USA: ACM Press, [3] Anh V N, Moffat A. Inverted Index Compression Using Word-aligned Binary Codes[J]. Information Retrieval, 2005, 8(1): [4] Anh V N, Moffat A. Improved Word-aligned Binary Compression for Text Indexing[J]. Knowledge and Data Engineering, 2006, 18(6): [5] Elias P. Universal Codeword Sets and Representations of the Integers[J]. IEEE Transactions on Information Theory, 1975, 21(2): [6] Witten I H, Moffat A, Bell T C. Managing Gigabytes: Compressing and Indexing Documents and Images[M]. 2nd ed. San Francisco, USA: Morgan Kaufmann, [7] Rice R. Plaunt J. Adaptive Variable-length Coding for Efficient Compression of Spacecraft Television Data[J]. IEEE Transactions on Communication Technology, 1971, 19(6): [8] Walder J, Kratky M, Baca R, et al. Fast Decoding Algorithms for Variable-lengths Codes[J]. Information Sciences, 2012, 183(1): [9] Scholer F, Williams H, Yiannis J, et al. Compression of Inverted Indexes for Fast Query Evaluation[C]//Proc. of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. Tampere, Finland: ACM Press, [10] Dean J. Challenges in Building Large-scale Information Retrieval Systems: Invited Talk[C]//Proc. of the 2nd ACM International Conference on Web Search and Data Mining. New York, USA: ACM Press, [11] Stepanov A A. SIMD-based Decoding of Posting Lists[C]//Proc. of the 20th ACM International Conference on Information and Knowledge Management. Glasgow, UK: ACM Press, [12] Heman S. Super-scalar Database Compression Between RAM and CPU-cache[C]//Proc. of the 22nd International Conference on Data Engineering. Amsterdam, Holland: [s. n.], [13] Delbru R, Campinas S, Tummarello G. Searching Web Data: An Entity Retrieval and High-performance Indexing Model[J]. Web Semantics, 2012, 10(1): [14] Anh V N, Moffat A. Index Compression Using 64-bit Words[J]. Software: Practice and Experience, 2010, 40(2): [15] 朱虹, 吴林. 倒排索引压缩及在 RDBMS 全文检索中的实现 [J]. 华中科技大学学报 : 自然科学版, 2005, 33(4): 7-9. [16] 纪蕾, 陈英. 基于文档重排的索引压缩技术 [J]. 清华大学学报 : 自然科学版, 2005, 45(S1): [17] 王虎, 王潜平, 对几种倒排文件压缩技术的研究与分析 [J]. 计算机工程与应用, 2006, 42(7): [18] Berger A L, Stephen A, Pietra D, et al. A Maximum Entropy Approach to Natural Language Processing[J]. Computational Linguistics, 1996, 22(1): 编辑任吉慧 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ( 上接第 70 页 ) [7] Ichikawa S, Akinaka M, Hata H. An FPGA Implementation of Hard-wired Sequence Control System Based on PLC Software[J]. IEEE Transactions on Electrical and Electronic Engineering, 2011, 6(4): [8] Du Daoshan, Liu Yadong, Guo Xingu, et al. Study on LD- VHDL Conversion for FPGA-based PLC Implementation[J]. The International Journal of Advanced Manufacturing Technology, 2009, 40(11/12): [9] Ranganath V P, Amtoft T, Banerjee A, et al. A New Foundation for Control Dependence and Slicing for Modern Program Structures[J]. ACM Transactions on Programming Languages and Systems, 2007, 29(5): [10] Polychronopouios G. Automatic Extraction of Functional Parallelism from Ordinary Programs[J]. IEEE Transactions on Parallel and Distributed Systems, 1992, 3(2): [11] Tallam S, Gupta R. Unified Control Flow and Data Dependence Traces[J]. ACM Transactions on Architecture and Code Optimization, 2007, 4(3): [12] Jeanne F, Karl O. The Program Dependence Graph and Its Use in Optimization[J]. ACM Transactions on Programming Languages and Systems, 1987, 9(3): [13] Ohata F, Nishimatsu A, Inoue K. Analyzing Dependence Locality for Efficient Construction of Program Dependence Graph[J]. Information and Software Technology, 2000, 42(13): [14] 赵营, 严义. 基于梯形图复杂依赖关系的分解研究 [J].

Schütze H. An Introduction to Information Retrieval[M]. New York, USA: Cambridge University Press, 2008. [2] Zhang Jiangong, Long Xiaohui, Suel T.

7 2 计算机工程 2014 年 2 月 15 日机电工程, 2012, 29(5): 编辑陆燕菲

说明为了反映教运行的基本状态, 为校和院制定相关政策和进行教建设与改革提供据依据, 校从程资源 ( 开类别开量规模 ) 教师结构程考核等维度, 对 2015 年春季期教运行基

说明为了反映教运行的基本状态, 为校和院制定相关政策和进行教建设与改革提供据依据, 校从程资源 ( 开类别开量规模 ) 教师结构程考核等维度, 对 2015 年春季期教运行基内部资料东北师范大教运行基本状态据报告 2015 年春季期教务处 2015 年 10 月 27 日说明为了反映教运行的基本状态, 为校和院制定相关政策和进行教建设与改革提供据依据, 校从程资源 ( 开类别开量规模 ) 教师结构程考核等维度,