(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
于是根据编码规则得到我们最终想要的结果：
从上图中我们得到各个字符编码后的编码位：
代码示例：
哈夫曼树结构：
struct element { int weight; // 权值域 int lchild, rchild, parent; // 该结点的左、右、双亲结点在数组中的下标 }; weight保存结点权值；lchild保存该节点的左孩子在数组中的下标；rchild保存该节点的右孩子在数组中的下标；parent保存该节点的双亲孩子在数组中的下标。
哈夫曼算法的C++实现：
#include #include 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)
#include #include 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).同色区块的彩色图形
参阅资料：
https://blog.csdn.net/u012455213/article/details/45502573
https://www.cnblogs.com/smile233/p/8184492.html
说明：部分图源来自网络，感谢作者的分享。 --------------------- 作者：老樊Lu码 来源：CSDN 原文：https://blog.csdn.net/fanyun_01/article/details/80211799 版权声明：本文为博主原创文章，转载请附上博文链接！
在网络网络传输过程中，最关心的就是传输效率问题。而提高传输效率最有效的方法就是对传输的数据进行压缩。但压缩数据也要耗费一定的时间，是不是压缩后一定能提高效率呢？该如何选择合适的压缩算法呢？请看本文的具体分析。
1.数据传输时间 假设数据大小为D (MB)
网络带宽为 N (MBps) -------------注意这里是MBps，而不是通常说的Mbps, 1MBps = 10Mbps, 1000Mbps=100MBps.
那么数据传输时间T1 = D/N
2.压缩后的数据传输时间
假设压缩算法压缩率为 R ------------------ 即压缩后数据大小为D*R
压缩速度为 Vc MB/S
解压缩速度为 Vd MB/S
那么压缩后的数据传输时间 T2 = D/Vc + D*R/N + D/Vd = D/N * ( R + N/Vc + N/Vd)
3.分析 对比：
T1 = D/N
T2 = D/N*(R+N/Vc+N/vd)
发现：
如果R + N/Vc + N/Vd < 1,则压缩后传输要更快，否则压缩后传输反而更慢。
也就是压缩后传输能否更快是和压缩算法的 “压缩率”，“压缩/解压缩速度” 以及当前“带宽”相关
压缩率越小，压缩/解压缩越快，带宽越小，压缩后传输越能提高效率。而在带宽不变得情况下，压缩率越小，压缩/解压缩越快 越好。
而由于压缩率和压缩/解压缩速度成指数型反比（压缩率提高一点点，压缩/解压缩速度就大幅降低），所以在选用压缩算法时：
最好选择压缩/解压缩速度快的算法，而不必太关注压缩率（当然也不能完全不压缩）
4.常用压缩算法对比 这是来自网上一个常用压缩算法压缩比，压缩/解压缩速度对比图：
来源：http://blog.csdn.net/zhangskd/article/details/17009111
压缩率R为 图中的 1/Ratio。
那么带入到上面公式：
LZ4：1/2.084 + N/422 + N/1820 = 0.48 + N*0.0029 也就是说在带宽N<179MBps的情况下，采用LZ4压缩能提高传输效率。
zlib：1/3.099 + N/21 + N/300 = 0.32 + N*0.051 也就是说在带宽N<13.3Mbps的情况下，采用zlib压缩才能提高传输效率，如果带宽够高，就不要压缩了，否则会更慢
5.总结 一般客户端访问服务器，需进行压缩。 （目前客户端到服务器的带宽还是比较低的）
服务器间传输，可以不压缩，或者用LZ4压缩。 （服务器间的带宽一般是1000bps，即100MBps）
在带宽 N<3.3MBps的情况下， 使用zlib要比LZ4更快。
0-3.3MBps zlib压缩传输最快，lz4压缩传输次之，普通传输最慢
3.3 - 13.3MBps lz4压缩传输最快，zlib压缩传输次之，普通传输最慢
13.3-179MBps lz4压缩传输最快，普通传输次之，zlib压缩传输 反而更慢
大于179MBps 普通传输就可以，因为网络传输速度 远远高于压缩及解压缩速度了 --------------------- 作者：jmppok 来源：CSDN 原文：https://blog.csdn.net/jmppok/article/details/38121115 版权声明：本文为博主原创文章，转载请附上博文链接！
文章来源: blog.csdn.net，作者：隔壁老瓦，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/wxb880114/article/details/84065029