数据压缩是一个减少数据存储空间的过程。
数据压缩包括两个过程：一个过程是，压缩或编码数据，数据大小减小；另一个过程是，解压缩或解码数据，还原到数据本身的状态。
根据信息的内容，所有的数据都会表现出一定的特性，称为熵（从热力学借用的一个术语）。压缩是可能的，因为绝大多数数据所表现出来的容量都大于其熵所建议的最佳容量。为了衡量压缩的效率，通常用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);
返回值：无