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