关于压缩机制

想必大家都用过压缩文件吧（图片或文件压缩），压缩文件的扩展名有zip 跟rar等，为什么同一文件压缩后就可以使得大小缩减到原来的n倍，想想真不可思议，下面来看看文件的压缩机制吧。

文件是将数据存储在磁盘等存储媒介中的一种形式，程序文件中存储数据的单位是字节，文件大小之所以用xxKB xxMB来表示，就是因为文件是以字节（B = Byte）为单位来存储的
文件就是字节数据的集合，用1字节（=8位）表示的字节数据有256种，用二进制表示则范围是00000000~11111111；

1.RLE行程长度编码压缩算法

是一个简单高效的无损数据压缩算法，其基本思路是把数据看成一个线性序列，而这些数据序列组织方式分成两种情况：一种是连续的重复数据块，另一种是连续的不重复数据块。

如AAAAAABBCDDEEEEEF就可以用 A6B2C1D2E5F1表示
A6B2C1D2E5F1 = 12字符 = 12字节
因此文件压缩12字节 % 17字节 =70%

缺点：（文本文件压缩，文件反而增大）
如: “This is a pen.”
压缩后=》T1h1i1s1 1i1s1 1a1 1p1e1n1.1 = 28字节 = 压缩前的2倍

2.（摩尔斯电码）莫尔斯编码来看哈夫曼算法（并不太突出）

莫尔斯编码不是通过语言，而是通过“嗒嘀嗒嘀”这些长点和短点的组合来传递文本信息

如AAAAAABBCDDEEEEEF =（ A x 6次 + B x 2次 + C x 1次 + D x 2次 + E x 5次+ F x 1次 + 字符间隔 x 16 ）=（ 4位 x 6次 + 8位 x 2次 + 9位 x 1次 + 6位 x 2次 + 1位 x 5次 + 8位 x 1次 + 2位 x 16次）= 106位 = 14字节
压缩比例：14%17=82% （并不太突出）
（附图如下）：

3.二叉树实现哈夫曼编码(最佳)

该方法完全依据字符出现概率来构造出平均长度最短的编码，称之为最优编码。哈夫曼编码常被用于数据文件压缩中，其压缩率通常在20%～90%之间。你的任务是对从键盘输入的一个字符串求出它的ASCII编码长度和哈夫曼编码长度的比值。

AAAAAABBCDDEEEEEF = 0000000000001001001101011010101010101111 = 40位 = 5字节
压缩比例：5字节 % 17字节= 29%
（附图如下）：

代码实现：

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
char a[10000];
int b[1000];
struct cmp
{
    bool operator()(const int &a,const int &b)
    {
        return a>b;
    }
};
int main()
{
    int i,j,n,m,k,t,x1,x2;
    priority_queue<int,vector<int>,cmp>que;
    while(scanf("%s",a)!=EOF)
    {
        k=0;
        memset(b,0,sizeof(b));
        n=strlen(a);
        m=n*8;
        for(i=0;i<n;i++)
            b[a[i]]++;
        for(i=0;i<150;i++)
            if(b[i]!=0)
            que.push(b[i]);
        while(!que.empty())
        {
           x1=que.top();
           que.pop();
           if(!que.empty())
           {
               x2=que.top();
           que.pop();
           k+=(x1+x2);
           que.push(x1+x2);
           }
        }
        printf("%d %d %.1lf\n",m,k,1.0*m/k);
        }
}

补充说明：
关于数码相机JPEG有三种压缩形式：（附图如下）
tpys