随着信息时代的到来,由于数据的海量性、计算机存储资源和网络带宽的有限性,数据压缩已经成为数据存储和传输过程中不可或缺的部分。数据压缩是一种在保证重要信息的基础上,降低数据的存储容量,提高计算机资源利用率的技术。熵编码是数据压缩的一种有效手段,大多数用于图像、语音、视频的压缩系统使用自适应预测器或去相关变换,将原始数据块映射为低熵的整数块以便于熵编码过程。常见的熵编码算法有香农编码、Huffman编码、Lempel-Ziv编码、Golomb编码和ANS编码,其中Golomb编码是一种无损数据压缩方法,当输入序列中的符号概率服从几何分布时,使用Gololmb编码可以得到最优的前缀码。给定一个待编码的正整数N,Golomb编码使用一个参数M将其分成两部分:商部分和余数部分。当M不是2的幂次时,这两部分的码字均采用可变长度编码。与固定长度编码相比,可变长度编码的编译码复杂度较高,实现速度较慢。此外,Golomb编码只能采用二进制编码。迄今为止,没有文献研究任意n进制的Golomb编码。ANS编码是一种新的熵编码方法,它有两个主要的实现:rangeANS(rANS)和tabledANS(tANS),其中rANS需要一些复杂的算术运算,包括整数乘法和整数除法,计算复杂度较大。tANS将整个行为(包括重正化)固定到一个查找表中以避免乘法运算,在编码速度与Huffman编码相当的情况下,可以达到算术编码的压缩性能。然而,tANS需要耗费较大空间来存放整个查找表,对CPU的内存要求比较高。Golomb编码和ANS编码都属于可变长度编码,可变长度编码的主要局限性在于缺乏有效的随机访问能力。在数据库领域,经常遇到需要以压缩的形式随机地访问或修改某一个条目的情况。目前国内外在这方面的研究大致可分为两类:(1)基于采样的随机访问机制研究;(2)基于辅助的数据结构的随机访问机制研究。然而,现有的研究都需要开辟额外的空间,额外空间的使用将损失部分压缩性能。本文主要研究文本压缩中的熵编码技术,包括Golomb编码、ANS编码以及可变长度编码中的随机访问应用。首先,本文指出了传统Golomb编码存在的问题,然后提出了一种新的、Golomb编码的变体,它对于任意的M值,始终采用固定长度编码余数部分的码字。此外,本文将二进制的Golomb编码和所提出的编码拓展到任意n进制。接着,针对tANS编码速度快,但查找表耗费空间大的问题,本文提出了一种查找表空间较小的tANS算法,在避免了复杂度较高的乘法运算的同时,解决了内存占用大问题。最后,在不损失压缩性能的前提下,本文提出了一种新的、不需要辅助空间且支持随机访问的解决方案,显著提高了算法的随机访问效率。本文的贡献点如下:1.本文提出了一种Golomb编码的变体,它在不损失压缩性能的前提下,对于任意的M值,始终使用固定长度编码余数部分的码字,显著降低了编译码的复杂度。此外,本文提出了n进制的Golomb编码和n进制所提出的编码。实验结果显示,与传统的Golomb编码相比,所提出的方案编码时减少了20%加法运算、40%的乘法运算,增加了20%的位运算。译码时减少了40%的加法运算、10%的乘法运算,增加了20%的分支判断。2.本文提出了一种查找表空间较小的tANS算法,它在避免乘法运算的同时,减少了查找表所占的空间。此外,本文提出了一种一次可解码多个符号的快速译码算法。实验结果显示,在压缩比略微降低(大约损失0.5%)的情况下,我们的方法在编码(译码)时的吞吐量比rANS大约高25%(60%)。3.本文提出了一种前缀码流的重排方法,它在不需要使用额外空间的情况下,可支持高效的随机访问。实验结果显示,与传统方法相比,所提出的方案随机访问一个元素时需要读取的比特数目大约减少了两个数量级。此外,对于码字长度可由前缀确定的前缀码,如CanonicalHuffman编码,我们的方法可以进一步提高随机访问效率。