深入解析数据压缩算法
hanfox 2018-06-09
1、为什么要做数据压缩？
数据压缩的主要目的还是减少数据传输或者转移过程中的数据量。
2、什么是数据压缩？
是指在不丢失信息的前提下，缩减数据量以减少存储空间，提高传输、存储和处理效率的一种技术方法。或者是按照一定的算法对数据进行重新组织，减少数据的冗余和存储的空间。
3、常见的数据压缩算法
(1).LZW压缩
LZW压缩是一种无损压缩，应用于gif图片。适用于数据中存在大量重固子串的情况。
原理：
LZW算法中，首先建立一个字符串表，把每一个第一次出现的字符串放入串表中，并用一个数字来表示，这个数字与此字符串在串表中的位置有关，并将这个数字存入压缩文件中，如果这个字符串再次出现时，即可用表示它的数字来代替，并将这个数字存入文件中。压缩完成后将串表丢弃。如"print" 字符串，如果在压缩时用266表示，只要再次出现，均用266表示，并将"print"字符串存入串表中，在图象解码时遇到数字266，即可从串表中查出266所代表的字符串"print"，在解压缩时，串表可以根据压缩数据重新生成。
编码过程：
编码后输出：41 42 52 41 43 41 44 81 83 82 88 41 80。输入为17个7位ASC字符，总共119位，输出为13个8位编码，总共104位，压缩比为87%。
解码过程：
对输出的41 42 52 41 43 41 44 81 83 82 88 41 80进行解码，如下表所示：
解码后输出：
ABRACADABRABRABRA
特殊标记：
随着新的串(string)不断被发现，标号也会不断地增长，如果原数据过大，生成的标号集（string table)会越来越大，这时候操作这个集合就会产生效率问题。如何避免这个问题呢?Gif在采用lzw算法的做法是当标号集足够大的时候，就不能增大了，干脆从头开始再来，在这个位置要插入一个标号，就是清除标志CLEAR，表示从这里我重新开始构造字典，以前的所有标记作废，开始使用新的标记。
这时候又有一个问题出现，足够大是多大？这个标号集的大小为比较合适呢？理论上是标号集大小越大，则压缩比率就越高，但开销也越高。 一般根据处理速度和内存空间连个因素来选定。GIF规范规定的是12位，超过12位的表达范围就推倒重来，并且GIF为了提高压缩率，采用的是变长的字长。比如说原始数据是8位，那么一开始，先加上一位再说，开始的字长就成了9位，然后开始加标号，当标号加到512时，也就是超过9为所能表达的最大数据时，也就意味着后面的标号要用10位字长才能表示了，那么从这里开始，后面的字长就是10位了。依此类推，到了2^12也就是4096时，在这里插一个清除标志，从后面开始，从9位再来。
GIF规定的清除标志CLEAR的数值是原始数据字长表示的最大值加1，如果原始数据字长是8，那么清除标志就是256，如果原始数据字长为4那么就是16。另外GIF还规定了一个结束标志END，它的值是清除标志CLEAR再加1。由于GIF规定的位数有1位（单色图），4位（16色）和8位（256色），而1位的情况下如果只扩展1位，只能表示4种状态，那么加上一个清除标志和结束标志就用完了，所以1位的情况下就必须扩充到3位。其它两种情况初始的字长就为5位和9位。
代码示例：
[cpp] view plain copy
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <map>
- #include <algorithm>
- #include <vector>
- using namespace std;
- long len=0;//原字符串的长度
- long loc=0;//去重之后字符串的长度
- map<string,long> dictionary;
- vector <long> result;
- #define MAX 100;
- void LZWcode(string a,string s)
- {
- //memset(&result,0,sizeof(int));
- string W,K;
- for(long i=0;i<loc;i++)
- {
- string s1;
- s1=s[i];//将单个字符转换为字符串
- dictionary[s1]=i+1;
- }
- W=a[0];
- loc+=1;
- for(int i=0;i<len-1;i++)
- {
- K=a[i+1];
- string firstT=W;
- string secontT=W;
- if(dictionary.count(firstT.append(K))!=0)//map的函数count(n),返回的是map容器中出现n的次数
- W=firstT;
- else
- {
- result.push_back(dictionary[W]);
- dictionary[secontT.append(K)]=loc++;
- W=K;
- }
- }
- if(!W.empty())
- result.push_back(dictionary[W]);
- for(int i=0;i<result.size();i++)
- cout<<result[i];
- }
- void LZWdecode(int *s,int n)
- {
- string nS;
- for(int i=0;i<n;i++)
- for(map<string,long>::iterator it=dictionary.begin(); it!=dictionary.end();it++)
- if(it->second==s[i])
- {
- cout<<it->first<<" ";
- }
- for(map<string,long>::iterator it=dictionary.begin(); it!=dictionary.end();it++)//输出压缩编码的字典表
- cout<<it->first<<" "<<it->second<<endl;
- }
- int main(int argc, char const *argv[])
- {
- cout<<"本程序的解码是根据输入的编码字符进行的解码，并不是全256 的字符"<<endl;
- cout<<"选择序号："<<endl;
- cout<<"1.压缩编码 2.解码"<<endl;
- int n;
- while(scanf("%d",&n)!=EOF)
- {
- switch(n)
- {
- case 1:
- {
- char s[100],a[100];
- cout<<"输入一串字符："<<endl;
- cin>>s;
- len=strlen(s);
- for(int i=0;i<len;i++)
- a[i]=s[i];
- sort(s,s+len);//排序
- loc=unique(s,s+len)-s;//去重
- LZWcode(a,s);
- break;
- }
- case 2:
- {
- cout<<"输入解码数组的长度:"<<endl;
- int changdu;
- cin>>changdu;
- cout<<"输入解码数串（每个数串以空格隔开）:"<<endl;
- int s[changdu];
- for(int i=0;i<changdu;i++)
- cin>>s[i];
- LZWdecode(s, changdu);
- break;
- }
- default:
- cout<<"你的输入不正确，请从重新开始"<<endl;
- }
- if(n==2)
- {
- auto iter=result.begin(); // 每次正确输入结束后对结果进行清零
- while(iter!=result.end())
- result.erase(iter++);
- }
- }
- return 0;
- }
(2).霍夫曼压缩
哈夫曼编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号，长度由特殊符号出现的频率决定。常见的符号需要很少的位来表示，而不常见的符号需要很多位来表示。哈夫曼算法在改变任何符号二进制编码引起少量密集表现方面是最佳的。然而，它并不处理符号的顺序和重复或序号的序列。
原理：
利用数据出现的次数构造Huffman二叉树，并且出现次数较多的数据在树的上层，出现次数较少的数据在树的下层。于是，我们就可以从根节点到每个数据的路径来进行编码并实现压缩。
编码过程：
假设有一个包含100000个字符的数据文件要压缩存储。各字符在该文件中的出现频度如下所示：
在此，我会给出常规编码的方法和Huffman编码两种方法，这便于我们比较。
常规编码方法：我们为每个字符赋予一个三位的编码，于是有：
此时，100000个字符进行编码需要100000 * 3 = 300000位。
Huffman编码：利用字符出现的频度构造二叉树，构造二叉树的过程也就是编码的过程。
这种情况下，对100000个字符编码需要：(45 * 1 + (16 + 13 + 12 + 9)*3 + (9 + 5)*4) * 1000 = 224000
孰好孰坏，例子说明了一切！好了，老规矩，下面我还是用上面的例子详细说明一下Huffman编码的过程。
首先，我们需要统计出各个字符出现的次数，如下：
接下来，我根据各个字符出现的次数对它们进行排序，如下：
好了，一切准备工作就绪。
在上文我提到，huffman编码的过程其实就是构造一颗二叉树的过程，那么我将各个字符看成树中将要构造的各个节点，将字符出现的频度看成权值。Ok，有了这个思想，here we go！
构造huffman编码二叉树规则：
从小到大，
从底向上，
依次排开，
逐步构造。
首先，根据构造规则，我将各个字符看成构造树的节点，即有节点a、b、c、d、e、f。那么，我先将节点f和节点e合并，如下图：
于是就有：
经过排序处理得：
接下来，将节点b和节点c也合并，则有：
于是有：
经过排序处理得：
第三步，将节点d和节点fe合并，得：
于是有：
继续，这次将节点fed和节点bc合并，得：
于是有：
最后，将节点a和节点bcfed合并，有：
以上步骤就是huffman二叉树的构造过程，完整的树如下：
二叉树成了，最后就剩下编码了，编码的规则为：左0右1
于是根据编码规则得到我们最终想要的结果：
从上图中我们得到各个字符编码后的编码位：
代码示例：
哈夫曼树结构：
[cpp] view plain copy
- struct element
- {
- int weight; // 权值域
- int lchild, rchild, parent; // 该结点的左、右、双亲结点在数组中的下标
- };
weight保存结点权值；lchild保存该节点的左孩子在数组中的下标；rchild保存该节点的右孩子在数组中的下标；parent保存该节点的双亲孩子在数组中的下标。
哈夫曼算法的C++实现：
[cpp] view plain copy
- #include<iostream>
- #include <iomanip>
- using namespace std;
- // 哈夫曼树的结点结构
- struct element
- {
- int weight; // 权值域
- int lchild, rchild, parent; // 该结点的左、右、双亲结点在数组中的下标
- };
- // 选取权值最小的两个结点
- void selectMin(element a[],int n, int &s1, int &s2)
- {
- for (int i = 0; i < n; i++)
- {
- if (a[i].parent == -1)// 初始化s1,s1的双亲为-1
- {
- s1 = i;
- break;
- }
- }
- for (int i = 0; i < n; i++)// s1为权值最小的下标
- {
- if (a[i].parent == -1 && a[s1].weight > a[i].weight)
- s1 = i;
- }
- for (int j = 0; j < n; j++)
- {
- if (a[j].parent == -1&&j!=s1)// 初始化s2,s2的双亲为-1
- {
- s2 = j;
- break;
- }
- }
- for (int j = 0; j < n; j++)// s2为另一个权值最小的结点
- {
- if (a[j].parent == -1 && a[s2].weight > a[j].weight&&j != s1)
- s2 = j;
- }
- }
- // 哈夫曼算法
- // n个叶子结点的权值保存在数组w中
- void HuffmanTree(element huftree[], int w[], int n)
- {
- for (int i = 0; i < 2*n-1; i++) // 初始化，所有结点均没有双亲和孩子
- {
- huftree[i].parent = -1;
- huftree[i].lchild = -1;
- huftree[i].rchild = -1;
- }
- for (int i = 0; i < n; i++) // 构造只有根节点的n棵二叉树
- {
- huftree[i].weight = w[i];
- }
- for (int k = n; k < 2 * n - 1; k++) // n-1次合并
- {
- int i1, i2;
- selectMin(huftree, k, i1, i2); // 查找权值最小的俩个根节点，下标为i1,i2
- // 将i1，i2合并，且i1和i2的双亲为k
- huftree[i1].parent = k;
- huftree[i2].parent = k;
- huftree[k].lchild = i1;
- huftree[k].rchild = i2;
- huftree[k].weight = huftree[i1].weight + huftree[i2].weight;
- }
- }
- // 打印哈夫曼树
- void print(element hT[],int n)
- {
- cout << "index weight parent lChild rChild" << endl;
- cout << left; // 左对齐输出
- for (int i = 0; i < n; ++i)
- {
- cout << setw(5) << i << " ";
- cout << setw(6) << hT[i].weight << " ";
- cout << setw(6) << hT[i].parent << " ";
- cout << setw(6) << hT[i].lchild << " ";
- cout << setw(6) << hT[i].rchild << endl;
- }
- }
- int main()
- {
- int x[] = { 5,29,7,8,14,23,3,11 }; // 权值集合
- element *hufftree=new element[2*8-1]; // 动态创建数组
- HuffmanTree(hufftree, x, 8);
- print(hufftree,15);
- system("pause");
- return 0;
- }
说明：
parent域值是判断结点是否写入哈夫曼树的唯一条件，parent的初始值为-1，当某结点加入时，parent域的值就设置为双亲结点在数组的下标。构造哈夫曼树时，首先将n个权值的叶子结点存放到数组haftree的前n个分量中，然后不断将两棵子树合并为一棵子树，并将新子树的根节点顺序存放到数组haftree的前n个分量的后面。
(3).游程编码（RLC）
游程编码又称“运行长度编码”或“行程编码”，是一种无损压缩编码，JPEG图片压缩就用此方法，很多栅格数据压缩也是采用这种方法。
栅格数据如图3-1所示：
3-1 栅格数据
原理：
用一个符号值或串长代替具有相同值的连续符号（连续符号构成了一段连续的“行程”。行程编码因此而得名），使符号长度少于原始数据的长度。只在各行或者各列数据的代码发生变化时，一次记录该代码及相同代码重复的个数，从而实现数据的压缩。
常见的游程编码格式包括TGA，Packbits，PCX以及ILBM。
例如：5555557777733322221111111
行程编码为：（5，6）（7，5）（3，3）（2，4）（1，7）。可见，行程编码的位数远远少于原始字符串的位数。
并不是所有的行程编码都远远少于原始字符串的位数，但行程编码也成为了一种压缩工具。
例如：555555 是6个字符 而（5，6）是5个字符，这也存在压缩量的问题，自然也会出现其他方式的压缩工具。
在对图像数据进行编码时，沿一定方向排列的具有相同灰度值的像素可看成是连续符号，用字串代替这些连续符号，可大幅度减少数据量。
游程编码记录方式有两种：①逐行记录每个游程的终点列号：②逐行记录每个游程的长度（像元数）
第一种方式:
上面的栅格图形可以记为：A,3 B,5 A,1 C,4 A,5
第二种就记作：A,3 B,2 A,1 C,3 A,1
行程编码是连续精确的编码，在传输过程中，如果其中一位符号发生错误，即可影响整个编码序列，使行程编码无法还原回原始数据。
代码示例：
根据输入的字符串，得到大小写不敏感压缩后的结果（即所有小写字母均视为相应的大写字母）。输入一个字符串，长度大于0，且不超过1000，全部由大写或小写字母组成。输出输出为一行，表示压缩结果，形式为：
(A,3)(B,4)(C,1)(B,2)
即每对括号内部分别为字符（都为大写）及重复出现的次数，不含任何空格。
样例输入：aAABBbBCCCaaaaa
样例输出：(A,3)(B,4)(C,3)(A,5)
[cpp] view plain copy
- #include<stdio.h>
- #include<string.h>
- char a[1001];
- int main()
- {
- char t;
- int i;
- gets(a);
- int g=1;
- int k=strlen(a);
- if(a[0]>='a'&&a[0]<='z')
- a[0]-=32;
- t=a[0];
- for(i=1;i<=k;i++)
- {
- if(a[i]>='a'&&a[i]<='z')
- a[i]-=32;
- if(a[i]==t)
- g++;
- if(a[i]!=t)
- {
- printf("(%c,%d)",t,g);
- g=1;
- t=a[i];
- }
- }return 0;
- }
应用场景：
(1).区域单色影像图
(2).红外识别图形
(3).同色区块的彩色图形
