深入解析數據壓縮演算法

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).同色區塊的彩色圖形

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！