数据压缩是一个减少数据存储空间的过程。

数据压缩包括两个过程：一个过程是，压缩或编码数据，数据大小减小；另一个过程是，解压缩或解码数据，还原到数据本身的状态。

根据信息的内容，所有的数据都会表现出一定的特性，称为熵（从热力学借用的一个术语）。压缩是可能的，因为绝大多数数据所表现出来的容量都大于其熵所建议的最佳容量。为了衡量压缩的效率，通常用1减去压缩数据大小除以原始数据大小的值。这个值称为数据的压缩率。

从广义上讲，数据压缩的方法分为两大类：有损压缩和无损压缩。在有损压缩中，我们接受数据有一定的损失来换取更大的压缩比。在某些应用中，一定的损失是可以接受的，比如图像或音频的处理，因为这种损失不会影响其效果并且会受到严格控制。然而，我们通常使用的是无损压缩，它能够保证解压缩时准确的还原原始数据。

我们重点介绍无损压缩，实现无损压缩主要有两种方法：最小冗余编码和基于字典的方法。最小冗余编码使用更少的位对出现更为频繁的字符进行编码，用较长的位对出现频繁较低的字符进行编码。在基于字典的方法中，其通过对数据进行符号编码，来代替那些重复多余的短语。

位操作是数据压缩的重要组成部分，因为绝大多数方法在某种程度上都需要对数据的位进行操作。C语言本身提供了一些位操作的接口，可以用这些接口来实现一些扩展的位操作类。

我们先来看一下数据压缩的头文件(在数据压缩介绍中必不可少，包括各种符号常量、压缩、解压缩的接口等)：

/*compress.h  数据压缩的头文件*/
#ifndef COMPRESS_H
#define COMPRESS_H

#include "bitree.h"

/*定义霍夫曼树的节点数据结构*/
typedef struct HuffNode_
{
    unsigned char symbol;
    int          freq;
}HuffNode;

/*定义霍夫曼代码表中条目的数据结构*/
typedef struct HuffCode_
{
    unsigned char  used;
    unsigned char  code;
    unsigned char  size;
}HuffCode;

/*定义LZ77令牌成员所需要的位数*/
#define LZ77_TYPE_BITS  1
#define LZ77_WINOFF_BITS 12
#define LZ77_BUFLEN_BITS 5
#define LZ77_NEXT_BITS  8

/*定义滑动窗口的大小和LZ77的超前缓冲区.
每个都必须小于或等于2，分别提高到LZ77_WINOFF_BITS和LZ77_BUFLEN_BITS。
*/
#define LZ77_WINDOW_SIZE  4096
#define LZ77_BUFFER_SIZE  32

/*定义LZ77短语标记的位数*/
#define LZ77_SYMBOL_BITS  (LZ77_TYPE_BITS + LZ77_WINOFF_BITS + LZ77_NEXT_BITS + LZ77_BUFLEN_BITS)

/*函数接口*/
int huffman_compress(const unsigned char *original, unsigned char **compressed, int size);
int huffman_uncompress(const unsigned char *compressed, unsigned char **original);
int lz77_compress(const unsigned char *original, unsigned char **compressed, int size);
int lz77_uncompress(const unsigned char *compressed, unsigned char **original);

#endif // COMPRESS_H

在压缩和解压缩数据时，常常要在小于一个字节的数量级上进行数据操作。所以，在学习各种数据压缩的方法之前，必须熟悉一些对数据位进行的操作，这非常重要。本节展示的方法包含了对任意位的缓冲区的操作。当然，这里介绍的位操作只是一部分，只是定义了现在数据压缩和后续的数据加密中所要用到的操作。

bit_get

int bit_get (const unsigned char *bits, int pos);

返回值：相应位所处的状态：0或1。

描述：获取缓冲区bits中处于位置pos的位的状态。缓冲区最左边的位置为0。返回的状态值为0或1。

复杂度：O（1）

bit_set

void bit_set (unsigned char *bits, int pos, int state);

返回值：无

描述：设置缓冲区bits中处于位置pos的位的状态（根据state值来设置）。缓冲区最左边的位设置为0。状态值必须为0或1。

复杂度：O（1）

bit_xor

void bit_xor (const unsigned char *bits1, const unsigned char *bits2, unsigned char *bitsx, int size);

返回值：无

描述：按位计算两个缓冲区bits1和bits2的异或值，其中每个缓冲区包含size个位，然后将结果返回bitsx中。异或的过程是将两个二进制操作数进行运算，如果操作数据处于位置i的两位相同，得到0；如果处于位置i的两位不同，则返回1。例如：11010 异或 01011 = 10001。bitsx所需要的存储空间由函数调用者来管理。

复杂度：O（B），其中B为每个缓冲区中位的个数。

bit_rot_left

void bit_rot_left (unsigned char *bits, int size, int count);

返回值：无

描述：轮转缓冲区bits（含size位），将位值向左移动count位。此操作完成后，处于最左端的count位移动到缓冲区的最右端，而且其他的位也相应的轮转。

复杂度：O（nB），其中B为每个缓冲区中位的个数，n为要轮转到左边的位数。

每个位操作都可操作缓冲区中的数据，缓冲区由无符号字符作为指针来指定。该指针指向足够多的字节来表示缓冲区中的位数。如果缓冲区中的位数不是8的倍数，那么说明最后一个字节的某些位没有使用。

bit_get

bit_get操作获取缓冲区中一个位的状态。要做到这一点，首先要确定位所在的字节，然后通过一个掩码从字节中获取相应的位。掩码中设置为1的位是将要从字节中读出的位，用一个循环操作将此位移动到适当的位置，通过索引bits中相应的字节，并应用调用后的掩码，可以获取所需的位。

bit_get的时间复杂度为O（1）。这是因为获取缓冲区中的位的状态所进行的操作都能够在固定的时间内完成。

bit_set

bit_set 操作设置缓冲区中的一个位的状态。此操作与bit_get的工作方式相似，只是它是利用掩码设置指定的位的状态，而bit_get是获取指定位的状态。

bit_set的时间复杂度为O（1）。这是因为获取缓冲区中位的状态所进行的所有操作都能够在固定的时间内完成。

bit_xor