程序：数据压缩
写程序的时候 有同学问我 用WinRAR压缩为什么会压压越大
额 我当时觉得不可能吧 然后他就把他说的和我说了
实践一下，在桌面上新建一个记事本，名称为：1（注：其实文件名为“1.txt”），打开，输入“1”，保存，退出。你可以用鼠标放在上面看看文件大小，１字节。
朋友们的电脑上一定有压缩软件吧，将其压缩成 1.rar 吧：再看看新的文件，多少字节？我们压缩结果是74字节，文件经过压缩之后，压缩结果竟然是原来存储格式的７４倍，压缩率 7400% 这种压缩率可以吧？（事后和牛哥聊了下 发现错误 更正下 ：1 个字节并没有压缩成 74 字节 74 字节还包含 RAR 文件头、文件名、文件属性、校验码等信息）
所以说，我们这里讨论的压缩仅仅是“无损压缩”。既然无损，就需要有一定的压缩规则，传统的压缩中需要用到“数据字典”，就不是一个小问题，并且一般压缩文件中，还需要保存原来数据的文件格式：“txt”，３个字节，文件名“1”，文件分隔符“.”怎么样？一下子就占去了５个字节，并且压缩文件还有自己的文件头结构与一些算法规定，所以说，压缩仅仅是一种算法，而并非规定，必须越压越小。
我在早期也天真地想过，一个1G的文件，经过多次压缩，十次，一百次，一千次……，能否压成1M的文件呢？那么我们的电脑好像一下子就增容了，呵呵。
所以说，我们应该明白一点，就是压缩的数据量越大，我们的压缩率就会越高，我们再做个试验，将上面那个 1.rar 给删了，在 1.txt 中打进一串的“1”，越多越好，记得用复制/粘贴 啊，呵呵。
我用这种方法，制作了一个竟然达到 100kb 的文件，再压缩成 1.rar 压缩的结果令人吃惊，竟然压缩结果是 141字节。压缩率：0.138% 。
事实证明，rar很可能用了循环了，什么意思呢，也就是说其中应该有一种结构为：数据 循环长度，用这种办法来存储一串相同的数据，当然也可能不是，我只是猜测，我们既然是讲原理，讲算法，我们不涉及这些成品的软件，我们做自己的压缩方法。
既然是自己做的，我们就必须自己规定一套的原则，然后对自己的原则进行计算与编程。
压缩是建立在统计学的规律之上的，什么意思。我们知道，我们的汉字是３０００多个，而事实上一篇文章中，可能根本用不到那么多：
一片二片三四片
五片六片七八片
九片十片十一片
飞入草丛皆不见
海水朝朝朝朝朝朝朝落
浮云长长长长长长长消
上面是一首纪昀的诗与一幅好对联，共４８个字，可大伙一看就知道，用到的却很少，我们统计一下：
一二三四片五六七八九十飞入草丛皆不见海水朝落浮去长消
呵呵，正好２６个，我们可以使用字母来替代一下，我们知道，汉字是两个字节，而字母是一个字节，那么我们既然要替代，就必须有一张：对应的表：
一A
二B
三C
四D
片E
五F
六G
七H
八I
九J
十K
飞L
入N
草M
丛O
皆P
不Q
见R
海S
水T
朝U
落V
浮W
云X
长Y
消Z
那么上面的诗句对联就变成了：
AEBECDE
FEGEHIE
JEKEKAE
LMNOPQR
STUUUUUUUV
WXYYYYYYYZ
这样一来，我们知道，原来的文章占４８Ｘ２＝９６字节，而压缩后就变成了４８字节，少了一半。
当然这种代价也是惨痛的，背了一个26*3=78个字节的数据字典，于是，其实我们这次压缩是不成功的，我们压缩的文件就比原来的文件大了起来。
没办法，这是事实，事实上的压缩算法就是不能保证我们能够真正地达到压缩的目的，因为我们需要的压缩是“无损压缩”。
当然，我们知道，２６个数据，其实根本没有达到３２个，也就是说，其实没必要用一个字节来存储，而是可以使用五个字节就可以存储这４８个汉字了，也就是说：48*5/8=30 个字节就可以保存这４８个字符了，不过那种算法需要用到“位运算”，我们先去回避一下，先讲原理。
但其实我们也不需要害怕这些算法的可行性与可靠性，因为我们一旦算法固定，我们的压缩几乎是自动的，呵呵。
由于以上的压缩算法需要使用一个很长的数据字典，所以说，我们根据不同的原理，功能与应用就会形成不同的“库”，也就是说，将这些数据字典单独地拿出来，做成一个单独的文件，并且用一些专用的函数来使用这些数据，从而形成了各自独立的计算机系统库。
汉字库使得我们的电脑可以便当地使用汉字，Midi音色库使得我们可以用几百k的数据量去保存优秀美妙的音乐，语音库可以使得我们计算机能当播音员，甚至有些人工智能技术更是用到了好多的模拟库与存储库，以便实现一些人工识别与系统比对，例如手写输入中所使用的识别库，指纹识别中使用的指纹库，等等，使得我们的的电脑具备了好多的人工智能与压缩存储。
当然，我们很希望我们的一些库是单独存放，用软件来读取，并且使用此软件与我们需要压缩的文件去实现一种“库”的关系，从而实现这种很舒服的文件压缩。
好了，我们这里不希望出现位运算，所以我们还是使用上面的诗句与对联来具体实现一个压缩与解压的过程，当然如果你使用位运算，可以使得我们的文件可以被压缩成30字节的文件压缩格式。
实践一下，好玩，呵呵，因为我们就是试验程序，所以我们没有必要自己定义那么多扩展名，我们都用文本形式的扩展名好了，我们将上面的：
复制内容到剪贴板代码:
AEBECDE
FEGEHIE
JEKEKAE
LMNOPQR
STUUUUUUUV
WXYYYYYYYZ
部分存为一个文件：“压缩文件.txt”将上面的：一二三四片五六七八九十飞入草丛皆不见海水朝落浮去长消 存成一个文件：“数据字典.txt”，然后我们就开始我们的解压过程了，看程序：
我们在程序中需要打开三个文件，其中一个是压缩文件，一个是解压文件，一个是数据字典
复制内容到剪贴板代码:
#include <stdio.h>
void main()
{
FILE *fprar,*fp,*fpdic;
char ch[50],str[2];
int i;
fp=fopen("解压文件.txt","wb");
fprar=fopen("压缩文件.txt","rb");
fpdic=fopen("数据字典.txt","rb");
while(!feof(fprar))
{
fgets(ch,50,fprar);
for(i=0;(ch!=13)&&(ch!=0);i++)
{
fseek(fpdic,(ch-'A')*2,SEEK_SET);
fread(str,2,1,fpdic);
fwrite(str,2,1,fp);
}
str[0]=13;
str[1]=10;
fwrite(str,2,1,fp);
};
}
事实就是这样，很简单吧？其中我们将索引的定义改了改，什么意思呢？
一A
二B
……
长Y
消Z
这些，我们分别用 ABC...XYZ 来表示，我们当然也可以做这样的对应表，但事实上，A,B,C...,X,Y,Z是连续的，所以就不需要出现了，我们只需要存储一个顺序就一切OK了。所以我们的索引方式也可以分两种：
·一种是目录索引，就好像我们查字典一样，查到了某一个字，在第几页页，后面是页号，这通常用于每项索引大小不一样的情况。
·第二种索引为公式索引，也就是我们的索引项满足某种公式，于是，我们就可以根据索引值去用公式直接找到对应的索引位置，取得索引项的内容，我们这里的程序用的就是第二种索引办法，实现了数据的解压。
当然，压缩并不一定是将其两字节压缩成一个字节这样，有时候我们使用的数据并没有我们想像的那么多，我们也可以采用压缩技术来达到某些数据的压缩存储，例如，我们可以定义一个字母的子集，例如我们假设我们在网络应用中的某个数据应用，我们只使用[email=“@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]“@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\[/email]]^_”来表示数据，那么对于我们来说，就只需要五位数据就够了，于是乎，我们高三位就有可能不能用了，那么怎么办呢？想办法压缩呗，当然，我们压缩时，请大家注意，每一个数据的头三位是无效位，何况这些字符中，我们去看看其规律：
二进制 字符
01000000 @
01000001 A
01000010 B
01000011 C
01000100 D
01000101 E
01000110 F
01000111 G
...
01011101 ]
01011110 ^
01011111 _
请大家注意，前面的三位都是“010”，于是，我们在压缩时，就需要将之去了，而在解压时，需要将其加上，于是，就存在一个算法问题了，我们假设输入字符为 *in，输出字符为 *out
那么我们的程序就会变成：
*p=*in;
*q=*out;
*q=((*p & 0x1F)<<3) | ((*(p+1) & 0x1F)>>2);
q++;
*q=((*p & 0x1F)<<6) | ((*(p+1) & 0x18)<<1 | ((*(p+2) & 0x10)>>4);
...
...
程序没到底，也就是这个意思，我们其中的 0x1f 0x18 ... 这些东西我们称之为屏蔽字，需要屏蔽掉一些位，将字符变成五个，而其他的一些部分变为０，不影响移动，然后就将其他字符向前不断地移动，像上面这种五个字节的压缩，需要一直处理８个字节的内容，因为我们５与８的最大公约数是１，这没办法，所以一般我们做数据压缩时，不会将数据五位五位移动，而会宁可多一位冗余位，而六位六位地处理，那么我们的程序会大大地简洁。
大家玩过传奇吗？给大家发送一段解码程序：
int CodeGameCode( BYTE * in, int size, BYTE * out )
{
int i = 0,ilen = 0;
int idxout = 0;
int idxin = 0;
int reallen = 0;
ilen = size;
ilen = (size + 2)/3;
BYTE b1,b2,b3;
reallen = (size * 8 + 5) / 6;
(*(DWORD*)&in[size])=0;
for( i = 0;i < ilen;i ++ )
{
b1 = in[idxin++];
b2 = in[idxin++];
b3 = in[idxin++];
out[idxout++] = ((b1 & b11111100) >> 2)+'<';
out[idxout++] = (((b1 & b00000011) << 4)|((b2 & b11110000) >> 4))+'<';
out[idxout++] = (((b2 & b00001111) << 2)|((b3 & b11000000) >> 6))+'<';
out[idxout++] = (b3 & b00111111)+'<';
}
out[reallen]= '\0';
return 1;
}
大家看，上面的 b11111100 其实是一个宏定义：人家程序做得很令人佩服的
#define b00000000 0x0
#define b00000001 0x1
#define b00000010 0x2
......
#define b11111110 0xfe
#define b11111111 0xff
当然，用这些位运算，可以实现数据的压缩，数据的解压，数据的加密，数据的传输，好多地方可以用到，有些地方甚至可以使用这些运算在我们的原有文件中加入一些特殊的东西，例如数字水印什么的...
当然喽，我们压缩技术其实就是这样，因为我们不涉及任一款已经存在的压缩软件，所以我们并没有从实践的角度用自己的软件将一个现实的压缩文件解压，当然如果有一些内部资料，我们想做这些东西还是很简单的。
最后，再说一项压缩中的不定码压缩技术，这种技术就是完全建立在统计学的基础之上，原理就是，如果一篇文章中，如果某个数据出现次数过多，我们就可以用很短的码来表示这些字符，从而使得整篇文档得到压缩最小，当然这种技术需要一些理论基础，我们不作详细的过多的描述，总之，一个好的压缩算法的出炉也不是一件简单容易的事，编程很简单，我们学BASIC时，只有17句，到现在用得特别是API函数越来越多了，不过主要使用的和常用的关键字也不过是那么一点，不过一项优秀的技术的出炉可就不是那么一回事了。
计算机本身就是一个机器，能在计算机工作的，是我们的程序，计算机程序中跑的，就是各种各样的算法，所以从哪个方面来说，我们讨论算法意义可能比讨论其他技术的意义要更大，可惜的是，学习计算机的很多，做算法研究的很少，以使得我们现代的计算机的技术从根本上来说，其实是一种倒退。
计算机界，一种算法就可以改变历史，真的，不知什么时候，我们的计算机生活就被 rar 给改变了，也不知什么时候，我们的日常娱乐就被 Midi 技术给改变了，甚至好多压缩库都做成了硬件，而算法的应用都实现了自动化，例如MP4什么的等等.....
额 我当时觉得不可能吧 然后他就把他说的和我说了
实践一下，在桌面上新建一个记事本，名称为：1（注：其实文件名为“1.txt”），打开，输入“1”，保存，退出。你可以用鼠标放在上面看看文件大小，１字节。
朋友们的电脑上一定有压缩软件吧，将其压缩成 1.rar 吧：再看看新的文件，多少字节？我们压缩结果是74字节，文件经过压缩之后，压缩结果竟然是原来存储格式的７４倍，压缩率 7400% 这种压缩率可以吧？（事后和牛哥聊了下 发现错误 更正下 ：1 个字节并没有压缩成 74 字节 74 字节还包含 RAR 文件头、文件名、文件属性、校验码等信息）
所以说，我们这里讨论的压缩仅仅是“无损压缩”。既然无损，就需要有一定的压缩规则，传统的压缩中需要用到“数据字典”，就不是一个小问题，并且一般压缩文件中，还需要保存原来数据的文件格式：“txt”，３个字节，文件名“1”，文件分隔符“.”怎么样？一下子就占去了５个字节，并且压缩文件还有自己的文件头结构与一些算法规定，所以说，压缩仅仅是一种算法，而并非规定，必须越压越小。
我在早期也天真地想过，一个1G的文件，经过多次压缩，十次，一百次，一千次……，能否压成1M的文件呢？那么我们的电脑好像一下子就增容了，呵呵。
所以说，我们应该明白一点，就是压缩的数据量越大，我们的压缩率就会越高，我们再做个试验，将上面那个 1.rar 给删了，在 1.txt 中打进一串的“1”，越多越好，记得用复制/粘贴 啊，呵呵。
我用这种方法，制作了一个竟然达到 100kb 的文件，再压缩成 1.rar 压缩的结果令人吃惊，竟然压缩结果是 141字节。压缩率：0.138% 。
事实证明，rar很可能用了循环了，什么意思呢，也就是说其中应该有一种结构为：数据 循环长度，用这种办法来存储一串相同的数据，当然也可能不是，我只是猜测，我们既然是讲原理，讲算法，我们不涉及这些成品的软件，我们做自己的压缩方法。
既然是自己做的，我们就必须自己规定一套的原则，然后对自己的原则进行计算与编程。
压缩是建立在统计学的规律之上的，什么意思。我们知道，我们的汉字是３０００多个，而事实上一篇文章中，可能根本用不到那么多：
一片二片三四片
五片六片七八片
九片十片十一片
飞入草丛皆不见
海水朝朝朝朝朝朝朝落
浮云长长长长长长长消
上面是一首纪昀的诗与一幅好对联，共４８个字，可大伙一看就知道，用到的却很少，我们统计一下：
一二三四片五六七八九十飞入草丛皆不见海水朝落浮去长消
呵呵，正好２６个，我们可以使用字母来替代一下，我们知道，汉字是两个字节，而字母是一个字节，那么我们既然要替代，就必须有一张：对应的表：
一A
二B
三C
四D
片E
五F
六G
七H
八I
九J
十K
飞L
入N
草M
丛O
皆P
不Q
见R
海S
水T
朝U
落V
浮W
云X
长Y
消Z
那么上面的诗句对联就变成了：
AEBECDE
FEGEHIE
JEKEKAE
LMNOPQR
STUUUUUUUV
WXYYYYYYYZ
这样一来，我们知道，原来的文章占４８Ｘ２＝９６字节，而压缩后就变成了４８字节，少了一半。
当然这种代价也是惨痛的，背了一个26*3=78个字节的数据字典，于是，其实我们这次压缩是不成功的，我们压缩的文件就比原来的文件大了起来。
没办法，这是事实，事实上的压缩算法就是不能保证我们能够真正地达到压缩的目的，因为我们需要的压缩是“无损压缩”。
当然，我们知道，２６个数据，其实根本没有达到３２个，也就是说，其实没必要用一个字节来存储，而是可以使用五个字节就可以存储这４８个汉字了，也就是说：48*5/8=30 个字节就可以保存这４８个字符了，不过那种算法需要用到“位运算”，我们先去回避一下，先讲原理。
但其实我们也不需要害怕这些算法的可行性与可靠性，因为我们一旦算法固定，我们的压缩几乎是自动的，呵呵。
由于以上的压缩算法需要使用一个很长的数据字典，所以说，我们根据不同的原理，功能与应用就会形成不同的“库”，也就是说，将这些数据字典单独地拿出来，做成一个单独的文件，并且用一些专用的函数来使用这些数据，从而形成了各自独立的计算机系统库。
汉字库使得我们的电脑可以便当地使用汉字，Midi音色库使得我们可以用几百k的数据量去保存优秀美妙的音乐，语音库可以使得我们计算机能当播音员，甚至有些人工智能技术更是用到了好多的模拟库与存储库，以便实现一些人工识别与系统比对，例如手写输入中所使用的识别库，指纹识别中使用的指纹库，等等，使得我们的的电脑具备了好多的人工智能与压缩存储。
当然，我们很希望我们的一些库是单独存放，用软件来读取，并且使用此软件与我们需要压缩的文件去实现一种“库”的关系，从而实现这种很舒服的文件压缩。
好了，我们这里不希望出现位运算，所以我们还是使用上面的诗句与对联来具体实现一个压缩与解压的过程，当然如果你使用位运算，可以使得我们的文件可以被压缩成30字节的文件压缩格式。
实践一下，好玩，呵呵，因为我们就是试验程序，所以我们没有必要自己定义那么多扩展名，我们都用文本形式的扩展名好了，我们将上面的：
复制内容到剪贴板代码:
AEBECDE
FEGEHIE
JEKEKAE
LMNOPQR
STUUUUUUUV
WXYYYYYYYZ
部分存为一个文件：“压缩文件.txt”将上面的：一二三四片五六七八九十飞入草丛皆不见海水朝落浮去长消 存成一个文件：“数据字典.txt”，然后我们就开始我们的解压过程了，看程序：
我们在程序中需要打开三个文件，其中一个是压缩文件，一个是解压文件，一个是数据字典
复制内容到剪贴板代码:
#include <stdio.h>
void main()
{
FILE *fprar,*fp,*fpdic;
char ch[50],str[2];
int i;
fp=fopen("解压文件.txt","wb");
fprar=fopen("压缩文件.txt","rb");
fpdic=fopen("数据字典.txt","rb");
while(!feof(fprar))
{
fgets(ch,50,fprar);
for(i=0;(ch!=13)&&(ch!=0);i++)
{
fseek(fpdic,(ch-'A')*2,SEEK_SET);
fread(str,2,1,fpdic);
fwrite(str,2,1,fp);
}
str[0]=13;
str[1]=10;
fwrite(str,2,1,fp);
};
}
事实就是这样，很简单吧？其中我们将索引的定义改了改，什么意思呢？
一A
二B
……
长Y
消Z
这些，我们分别用 ABC...XYZ 来表示，我们当然也可以做这样的对应表，但事实上，A,B,C...,X,Y,Z是连续的，所以就不需要出现了，我们只需要存储一个顺序就一切OK了。所以我们的索引方式也可以分两种：
·一种是目录索引，就好像我们查字典一样，查到了某一个字，在第几页页，后面是页号，这通常用于每项索引大小不一样的情况。
·第二种索引为公式索引，也就是我们的索引项满足某种公式，于是，我们就可以根据索引值去用公式直接找到对应的索引位置，取得索引项的内容，我们这里的程序用的就是第二种索引办法，实现了数据的解压。
当然，压缩并不一定是将其两字节压缩成一个字节这样，有时候我们使用的数据并没有我们想像的那么多，我们也可以采用压缩技术来达到某些数据的压缩存储，例如，我们可以定义一个字母的子集，例如我们假设我们在网络应用中的某个数据应用，我们只使用[email=“@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]“@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\[/email]]^_”来表示数据，那么对于我们来说，就只需要五位数据就够了，于是乎，我们高三位就有可能不能用了，那么怎么办呢？想办法压缩呗，当然，我们压缩时，请大家注意，每一个数据的头三位是无效位，何况这些字符中，我们去看看其规律：
二进制 字符
01000000 @
01000001 A
01000010 B
01000011 C
01000100 D
01000101 E
01000110 F
01000111 G
...
01011101 ]
01011110 ^
01011111 _
请大家注意，前面的三位都是“010”，于是，我们在压缩时，就需要将之去了，而在解压时，需要将其加上，于是，就存在一个算法问题了，我们假设输入字符为 *in，输出字符为 *out
那么我们的程序就会变成：
*p=*in;
*q=*out;
*q=((*p & 0x1F)<<3) | ((*(p+1) & 0x1F)>>2);
q++;
*q=((*p & 0x1F)<<6) | ((*(p+1) & 0x18)<<1 | ((*(p+2) & 0x10)>>4);
...
...
程序没到底，也就是这个意思，我们其中的 0x1f 0x18 ... 这些东西我们称之为屏蔽字，需要屏蔽掉一些位，将字符变成五个，而其他的一些部分变为０，不影响移动，然后就将其他字符向前不断地移动，像上面这种五个字节的压缩，需要一直处理８个字节的内容，因为我们５与８的最大公约数是１，这没办法，所以一般我们做数据压缩时，不会将数据五位五位移动，而会宁可多一位冗余位，而六位六位地处理，那么我们的程序会大大地简洁。
大家玩过传奇吗？给大家发送一段解码程序：
int CodeGameCode( BYTE * in, int size, BYTE * out )
{
int i = 0,ilen = 0;
int idxout = 0;
int idxin = 0;
int reallen = 0;
ilen = size;
ilen = (size + 2)/3;
BYTE b1,b2,b3;
reallen = (size * 8 + 5) / 6;
(*(DWORD*)&in[size])=0;
for( i = 0;i < ilen;i ++ )
{
b1 = in[idxin++];
b2 = in[idxin++];
b3 = in[idxin++];
out[idxout++] = ((b1 & b11111100) >> 2)+'<';
out[idxout++] = (((b1 & b00000011) << 4)|((b2 & b11110000) >> 4))+'<';
out[idxout++] = (((b2 & b00001111) << 2)|((b3 & b11000000) >> 6))+'<';
out[idxout++] = (b3 & b00111111)+'<';
}
out[reallen]= '\0';
return 1;
}
大家看，上面的 b11111100 其实是一个宏定义：人家程序做得很令人佩服的
#define b00000000 0x0
#define b00000001 0x1
#define b00000010 0x2
......
#define b11111110 0xfe
#define b11111111 0xff
当然，用这些位运算，可以实现数据的压缩，数据的解压，数据的加密，数据的传输，好多地方可以用到，有些地方甚至可以使用这些运算在我们的原有文件中加入一些特殊的东西，例如数字水印什么的...
当然喽，我们压缩技术其实就是这样，因为我们不涉及任一款已经存在的压缩软件，所以我们并没有从实践的角度用自己的软件将一个现实的压缩文件解压，当然如果有一些内部资料，我们想做这些东西还是很简单的。
最后，再说一项压缩中的不定码压缩技术，这种技术就是完全建立在统计学的基础之上，原理就是，如果一篇文章中，如果某个数据出现次数过多，我们就可以用很短的码来表示这些字符，从而使得整篇文档得到压缩最小，当然这种技术需要一些理论基础，我们不作详细的过多的描述，总之，一个好的压缩算法的出炉也不是一件简单容易的事，编程很简单，我们学BASIC时，只有17句，到现在用得特别是API函数越来越多了，不过主要使用的和常用的关键字也不过是那么一点，不过一项优秀的技术的出炉可就不是那么一回事了。
计算机本身就是一个机器，能在计算机工作的，是我们的程序，计算机程序中跑的，就是各种各样的算法，所以从哪个方面来说，我们讨论算法意义可能比讨论其他技术的意义要更大，可惜的是，学习计算机的很多，做算法研究的很少，以使得我们现代的计算机的技术从根本上来说，其实是一种倒退。
计算机界，一种算法就可以改变历史，真的，不知什么时候，我们的计算机生活就被 rar 给改变了，也不知什么时候，我们的日常娱乐就被 Midi 技术给改变了，甚至好多压缩库都做成了硬件，而算法的应用都实现了自动化，例如MP4什么的等等.....