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

1. #include <iostream>
2. #include <cstdio>
3. #include <cstring>
4. #include <map>
5. #include <algorithm>
6. #include <vector>
7. using namespace std;
8. long len=0;//原字符串的長度
9. long loc=0;//去重之後字符串的長度
10. map<string,long> dictionary;
11. vector <long> result;
12. #define MAX 100;
13. void LZWcode(string a,string s)
14. {
15. //memset(&result,0,sizeof(int));
16. string W,K;
17. for(long i=0;i<loc;i )
18. {
19. string s1;
20. s1=s[i];//将單個字符轉換為字符串
21. dictionary[s1]=i 1;
22. }
23. W=a[0];
24. loc =1;
25. for(int i=0;i<len-1;i )
26. {
27. K=a[i 1];
28. string firstT=W;
29. string secontT=W;
30. if(dictionary.count(firstT.append(K))!=0)//map的函數count(n),返回的是map容器中出現n的次數
31. W=firstT;
32. else
33. {
34. result.push_back(dictionary[W]);
35. dictionary[secontT.append(K)]=loc ;
36. W=K;
37. }
38. }
39. if(!W.empty())
40. result.push_back(dictionary[W]);
41. for(int i=0;i<result.size();i )
42. cout<<result[i];
43. }
45. void LZWdecode(int *s,int n)
46. {
47. string nS;
48. for(int i=0;i<n;i )
49. for(map<string,long>::iterator it=dictionary.begin(); it!=dictionary.end();it )
50. if(it->second==s[i])
51. {
52. cout<<it->first<<" ";
53. }
54. for(map<string,long>::iterator it=dictionary.begin(); it!=dictionary.end();it )//輸出壓縮編碼的字典表
55. cout<<it->first<<" "<<it->second<<endl;
56. }
57. int main(int argc, char const *argv[])
58. {
59. cout<<"本程序的解碼是根據輸入的編碼字符進行的解碼，并不是全256 的字符"<<endl;
60. cout<<"選擇序号："<<endl;
61. cout<<"1.壓縮編碼 2.解碼"<<endl;
62. int n;
63. while(scanf("%d",&n)!=EOF)
64. {
65. switch(n)
66. {
67. case 1:
68. {
69. char s[100],a[100];
70. cout<<"輸入一串字符："<<endl;
71. cin>>s;
72. len=strlen(s);
73. for(int i=0;i<len;i )
74. a[i]=s[i];
75. sort(s,s len);//排序
76. loc=unique(s,s len)-s;//去重
77. LZWcode(a,s);
78. break;
79. }
80. case 2:
81. {
82. cout<<"輸入解碼數組的長度:"<<endl;
83. int changdu;
84. cin>>changdu;
85. cout<<"輸入解碼數串（每個數串以空格隔開）:"<<endl;
86. int s[changdu];
87. for(int i=0;i<changdu;i )
88. cin>>s[i];
89. LZWdecode(s, changdu);
90. break;
91. }
92. default:
93. cout<<"你的輸入不正确，請從重新開始"<<endl;
94. }
95. if(n==2)
96. {
97. auto iter=result.begin(); // 每次正确輸入結束後對結果進行清零
98. while(iter!=result.end())
99. result.erase(iter );
100. }
101. }
102. return 0;
103. }

(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

1. struct element
2. {
3. int weight; // 權值域
4. int lchild, rchild, parent; // 該結點的左、右、雙親結點在數組中的下标
5. };

weight保存結點權值；lchild保存該節點的左孩子在數組中的下标；rchild保存該節點的右孩子在數組中的下标；parent保存該節點的雙親孩子在數組中的下标。

哈夫曼算法的C 實現：

[cpp] view plain copy

1. #include<iostream>
2. #include <iomanip>
4. using namespace std;
5. // 哈夫曼樹的結點結構
6. struct element
7. {
8. int weight; // 權值域
9. int lchild, rchild, parent; // 該結點的左、右、雙親結點在數組中的下标
10. };
11. // 選取權值最小的兩個結點
12. void selectMin(element a[],int n, int &s1, int &s2)
13. {
14. for (int i = 0; i < n; i )
15. {
16. if (a[i].parent == -1)// 初始化s1,s1的雙親為-1
17. {
18. s1 = i;
19. break;
20. }
21. }
22. for (int i = 0; i < n; i )// s1為權值最小的下标
23. {
24. if (a[i].parent == -1 && a[s1].weight > a[i].weight)
25. s1 = i;
26. }
27. for (int j = 0; j < n; j )
28. {
29. if (a[j].parent == -1&&j!=s1)// 初始化s2,s2的雙親為-1
30. {
31. s2 = j;
32. break;
33. }
34. }
35. for (int j = 0; j < n; j )// s2為另一個權值最小的結點
36. {
37. if (a[j].parent == -1 && a[s2].weight > a[j].weight&&j != s1)
38. s2 = j;
39. }
40. }
41. // 哈夫曼算法
42. // n個葉子結點的權值保存在數組w中
43. void HuffmanTree(element huftree[], int w[], int n)
44. {
45. for (int i = 0; i < 2*n-1; i ) // 初始化，所有結點均沒有雙親和孩子
46. {
47. huftree[i].parent = -1;
48. huftree[i].lchild = -1;
49. huftree[i].rchild = -1;
50. }
51. for (int i = 0; i < n; i ) // 構造隻有根節點的n棵二叉樹
52. {
53. huftree[i].weight = w[i];
54. }
55. for (int k = n; k < 2 * n - 1; k ) // n-1次合并
56. {
57. int i1, i2;
58. selectMin(huftree, k, i1, i2); // 查找權值最小的倆個根節點，下标為i1,i2
59. // 将i1，i2合并，且i1和i2的雙親為k
60. huftree[i1].parent = k;
61. huftree[i2].parent = k;
62. huftree[k].lchild = i1;
63. huftree[k].rchild = i2;
64. huftree[k].weight = huftree[i1].weight huftree[i2].weight;
65. }
67. }
68. // 打印哈夫曼樹
69. void print(element hT[],int n)
70. {
71. cout << "index weight parent lChild rChild" << endl;
72. cout << left; // 左對齊輸出
73. for (int i = 0; i < n; i)
74. {
75. cout << setw(5) << i << " ";
76. cout << setw(6) << hT[i].weight << " ";
77. cout << setw(6) << hT[i].parent << " ";
78. cout << setw(6) << hT[i].lchild << " ";
79. cout << setw(6) << hT[i].rchild << endl;
80. }
81. }
82. int main()
83. {
84. int x[] = { 5,29,7,8,14,23,3,11 }; // 權值集合
85. element *hufftree=new element[2*8-1]; // 動态創建數組
86. HuffmanTree(hufftree, x, 8);
87. print(hufftree,15);
88. system("pause");
89. return 0;
90. }

說明：

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

1. #include<stdio.h>
2. #include<string.h>
3. char a[1001];
4. int main()
5. {
6. char t;
7. int i;
8. gets(a);
9. int g=1;
10. int k=strlen(a);
11. if(a[0]>='a'&&a[0]<='z')
12. a[0]-=32;
13. t=a[0];
14. for(i=1;i<=k;i )
15. {
16. if(a[i]>='a'&&a[i]<='z')
17. a[i]-=32;
18. if(a[i]==t)
19. g ;
20. if(a[i]!=t)
21. {
22. printf("(%c,%d)",t,g);
23. g=1;
24. t=a[i];
25. }
26. }return 0;
27. }

應用場景：

(1).區域單色影像圖

(2).紅外識别圖形

(3).同色區塊的彩色圖形

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!