8. Bit-Aligned Code Unary Code: 使用 k 个 1 对数字 k 编码，结尾使用 0 终止使编码无歧义（可解码）。 Unary Code 压缩小数字是可以的，大数字则可以采用二进制编码，但是有歧义。
9. Bit-Aligned Code Elias- γ Code 结合了一元编码和二进制编码。编码数字 k 需要计算两个值： k d 是二进制数，用一元编码， k r 采用二进制编码 虽然 Elias- γ Code 对一元编码进行改进，但是仍然对大数字编码并不理想，总共需要 2?log 2 k?+1 位。
10. Bit-Aligned Code Elias- δ Code 通过改变 k d 的编码方式，将 k d 分解为 ： K dd 使用一元编码， k dr 用二进制编码， k r 仍然用二进制编码 Elias- δ Code 有效对大数字编码，但是牺牲了小数字功效。总共需要 2log 2 log 2 k+log 2 k 位。
12. Golomb Code Golomb 编码中，整数 x 用两部分来表示，商和余 数。商的计算公式为 q = ?(x-1)?/k ，余数的计算公式为 r =( q*k )-1 ，在这里 k 是 Golomb 编码算法的基础 。 如果 r < p, 整 数可以用 ? log 2 k? 位来存储 ， 否则 它将需要 , 在这里 P 是分界点，计算方法为 p=2 ?log2k?+1 -k 。 当 r < p 时 ,Golomb 编 码用 q 个 0 ， 1 个 1, 还有 r 的二进制表示。否则表示方法为 q 个 0 ， 1 个 1 ，以及 r + p 的二进制表示。这样，整数 9 可用 k = 3 编码为 00,1,11 。
13. Golomb Code 参数 k 的选择是至关重要的。如果选择得不好 ，编码后的整数会变得非常大 ，需要很长时间来解压 。 Witten et al.(1994) 认为假定倒排表 中的整数符合 Bernoulli 模型， 则一列整数 a 的 k 值用 k ≈ 0.69x 平均值 (a) 来计算。 Williams 和 Zobel 描述了对 Golomb 编码实施优化的方法，并且认为常规的对整数的 Golomb 编码比 Elias gamma 编码和 Elias delta 编码解码更快并且更加节省空间。
14. Binary Interpolative Code Binary Interpolative Coding for Effective Index Compression - Moffat,Stuiver 2000 二进制插入编码用相邻数的信息来 编码一个单调递增的整数数列 。 如果在整数数列 X 1 中，对于任一给定的整数 x i ，前一个数 x i-1 和后一个数 x i-2 是已知的， x i 的大小是在 (x i-1 +1, x i-2 -1) 的范 围内，所需的最大位数为 log 2 (x i-1 -x i-2 -2) 。解码时需要 x i-1 和 x i-2 的信息，所以数列 X 2 是从原先的 X 1 得到的，也就是说每个从表 X 1 得到的整数都在 X 2 中， 这样也就可以递归地进行编码 。
16. 其他压缩方法相关论文 Inverted Index Compression Using Word-Aligned Binary Codes - Anh V, Moffat A.2005 ( 基于字行的二进制编码方式 ) Inverted index compression and query processing with optimized document ordering - Yan H , Ding S , Suel T ． 2009 Performance of Compressed Inverted List Caching In Search Engines - Zhang Jiang-Gong ， Lone Xiao Hui ， Suel T.2008
#8: Word count data is good candidate for compression many small numbers and few larger numbers encode small numbers with small codes Document numbers are less predictable but differences between numbers in an ordered list are smaller and more predictable Delta encoding : encoding differences between document numbers ( d-gaps ) Inverted list (without counts) Differences between adjacent numbers Differences for a high-frequency word are easier to compress, e.g., Differences for a low-frequency word are large, e.g.,
#17: 基于字行的二进制编码方式 (Word-Aligned Binary Code ， WABC) 对索引进行压缩；该编码具有字节操作的优点，其紧凑的二进制特性不仅保证了索引的压缩性能，而且提高了查询时倒排列表的解码速度 . Performance of Compressed Inverted List Caching In Search Engines 中同时考虑了搜索引擎中的索引压缩与索引缓存机制，并对变比特编码等几种压缩算法的性能进行了比较分析．为了进一步提高检索性能 . Inverted index compression and query processing with optimized document ordering 对倒排列表文档标识 (Identity ， ID) 整数集的升序特征进行了研究，通过更加紧凑的表示方法、快速求交集算法以及对文档 ID 顺序进行优化，提高查询效率
#19: 《 Self-Indexing Inverted Files for Fast Text Retrieval 》提出了一种有效的忽略倒排文 件 ( S k i p p e d I n v e r t e d F i l e ， S I F ) 自索引 ( S e l f - i n d e x ) ； S I F 将倒排列表分成多个子块， 通过在相邻子块间 插入少量的忽略信息 ( S k i p p i n g i n f o r ma t i o n ) ， 使得 查询时只需对压缩索引进行部分解码 ， 从而提高检 索的时间效率； 当选择合适的子块大小并以递归方式 对倒排列表进行压缩时， 可以提高存储空间与查询时 间效率 ； 但该方法存在以下问题 ： ( 1 ) 加入的辅助信息 增加了索引的空间消耗， 尤其是当子块较小时， 辅助 信息所造成的额外空间开销将不可忽略， 空间效率将 大大下降； ( 2 ) 无法找到合适的子块大小使得空间效 率与连接布尔查询、 排序查询等性能同时提高．
#20: 为了在提高索引空间效率的同时 ， 支持高效 的 连接布尔查询和排序查询 ， 提 出的倒排文件 自索引 RAB I F 的思想是： 将倒排列表进行分块 ， 构造一种 具有随机访问功能的分块倒排列表． 每个子块 由两 部分组成 ： 第一部分为定位部分． 采用 d — g a p 压缩方 式 ， 实现压缩索引查询的快速定位 ， 使得压缩索引在 不解压的情况下具有子块级的随机访 问能力， 以提 高查询时间效率 ； 第二部分为信息部分． 以部分解码 的方式支持连接布尔查询与排序查询 ， 并 以高效的 二进制内插编码方式进行压缩， 在不需要插入任何 辅助信息的前提下 ， 实现查询时子块内信息的随机 访问与快速定位功能 ， 在减少空间消耗 的同时提高 查 询效 率．
![倒排索引结构 倒排索引由 字典文件 (dictionary) 和 记录文件 (postings file) 两部分组成。 字典 (dictionary) 主要是由 term, 包含该 term 的文档数目 f t ，以及指向该记录表 (postings list) 的指针组成。 dictionary: <term,f t ,pointer> [postings list] 记录 (posting) 主要是记录 term 所在的文档 (docID) ， term 在文档中出现的次数，以及在文档中的位置，文档长度等信息。（文档级 : 无位置信息；单词级 : 有位置信息） posting: <docID, f d,t ,<position1,… positionf d,t >>](https://image.slidesharecdn.com/random-110831102418-phpapp02/85/-5-320.jpg)
