資料壓縮算法

資料壓縮算法

一、 概念：

資料壓縮是指在不丢失有用資訊的前提下，縮減資料量以減少存儲空間，提高其傳輸、存儲和處理效率，或按照一定的算法對資料進行重新組織，減少資料的備援和存儲的空間的一種技術方法。

在計算機科學和資訊論中，資料壓縮或者源編碼是按照特定的編碼機制用比未經編碼少的資料位元（或者其他資訊相關的單元）表示資訊的過程。

二、 算法編碼（哈夫曼壓縮算法編碼）：

哈夫曼壓縮算法編碼是無損壓縮當中最好的方法。它使用預先二進制描述來替換每個符号，長度由特殊符号出現的頻率決定。常見的符号需要很少的位來表示，而不常見的符号需要很多來表示。

哈夫曼算法在改變任何符号二進制編碼引起少量密集表現方面是最佳的。然而，它并不處理符号的順序和重複或序号的序列。

1、 概念：

哈夫曼樹是一種樹形結構，用哈夫曼樹的方法解程式設計題的算法叫做哈夫曼算法。

路徑：從樹種一個節點到另一個節點之間的分支構成這兩個節點之間的路徑

路徑長度：路徑上的分支數目稱作路徑長度

Huffman算法是一種基于統計的壓縮方法。它的本質就是對文本檔案中的字元進行重新編碼，對于使用頻率越高的字元，其編碼也越短。但是任何2個字元的編碼， 是不能出現向前包含的。也就是說字元A(假設為00)的編碼的前段，不可能為字元B（則B的編碼不可能為001，因為這裡B的編碼中包含了A的前段00，這會給解碼難帶來不必要的困難，是以這是不允許的）的編碼。經過編碼後的文本檔案，主要包含2個部分：Huffman碼表部分和壓縮内容部分。解壓縮的時候，先把Huffman碼表取出來，然後對壓縮内容部分各個字元進行逐一解碼,形成源檔案。

        哈夫曼編碼生成步驟：

        ①掃描要壓縮的檔案，對字元出現的頻率進行計算。

        ②把字元按出現的頻率進行排序，組成一個隊列。

        ③把出現頻率最低（權值）的兩個字元作為葉子節點，它們的權值之和為根節點組成一棵樹。

        ④把上面葉子節點的兩個字元從隊列中移除，并把它們組成的根節點加入到隊列。

        ⑤把隊列重新進行排序。重複步驟③④⑤直到隊列中隻有一個節點為止。

        ⑥把這棵樹上的根節點定義為0（可自行定義0或1）左邊為0，右邊為1。這樣就可以得到每個葉子節點的哈夫曼編碼了。

2、 定義：

它是由n個帶權葉子結點構成的所有二叉樹中帶權路徑長度最短的二叉樹

3、 概述：

（1） 初始化：根據給定的n個權值{w1,w2,…,wn}構成n棵二叉樹的集合F={T1,T2,…,Tn}，其中每棵二叉樹Ti中隻有一個帶權wi的根結點，左右子樹均空。

（2） 找最小樹：在F中選擇兩棵根結點權值最小的樹作為左右子樹構造一棵新的二叉樹，且至新的二叉樹的根結點的權值為其左右子樹上的根結點的權值之和。

（3） 删除與加入：在F中删除這兩棵樹，并将新的二叉樹加入F中。

（4） 判斷：重複前兩步，直到F中隻含一棵樹為止。

4、 編碼流程：

壓縮： 

        1、将要壓縮的檔案一個一個位元組的讀出來即掃描要壓縮的檔案，并統計每個位元組的權值即出現的頻率。

        2、以每個位元組的權值來構造哈夫曼樹，并給每個位元組進行哈夫曼編碼。

        3、将每個位元組和其對應得哈夫曼編碼存放進一個Map中，即碼表。

        4、以這個碼表為依照，将檔案中的所有位元組一一進行編碼（生成10字元串），最後在把所有位元組的編碼依次末尾相加合成一個10字元串。

        5、将這個10字元串重新組合，8個為一組，若最後一組不足8個則補0，并記錄補0的個數，将每一組的10字元串轉化為一個位元組，

并将所有的10字元串合成一個位元組數組，數組的最後一個元素存放補0的個數。

        6、建立一個壓縮檔案，先将碼表的大小寫入檔案，再将碼表寫入檔案（碼表裡還有每個位元組的哈夫曼編碼長度的資訊）。

        7、最後将之前生成的位元組數組寫入檔案（檔案的主要資訊）。

解壓縮： 

        1、将壓縮的檔案同樣一個一個位元組的讀出來。

        2、先讀出碼表的大小，再通過碼表的大小讀出碼表，并将碼表的資訊存放進一個Map。

        3、再接着讀出後面的所有位元組，并轉化成一個10字元串。

        4、通過與碼表的比對，從10字元串的第一個字元開始讀，若讀到的子字元串與碼表的某個位元組的的編碼相同，解壓出相應的位元組，把該位元組儲存起來。

并把上面的子字元串從編碼中删除，重複上一步驟，直到該項編碼解析完成，最後将此10字元串還原成原來的檔案的一個個位元組。

        5、再将這些位元組寫入一個新的檔案，字尾名改成和原來檔案一樣，就能打開了。

5、 代碼實作：

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <math.h>

#define N 100

#define M 2*N-1

typedef char* HuffmanCode[2*M];

typedef struct

{

int weight;

int parent;

int LChild;

int RChild;

}HTNode,Huffman[M+1];

typedef struct Node

{

int weight;

char c;

int num;

}WNode,WeightNode[N];

void CreateWeight(char ch[],int *s,WeightNode CW,int *p)

{

int i,j,k;

int tag;

*p = 0;

for(i=0;ch[i]!='\0';i++)

{

tag = 1;

for(j=0;j<i;j++)

if(ch[j] == ch[i])

{

tag = 0;

break;

}

if(tag)

{

CW[++*p].c = ch[i];

CW[*p].weight = 1;

for(k = i+1;ch[k]!='\0';k++)

if(ch[i] == ch[k])

CW[*p].weight++;

}

}

*s = i;

}

void CreateHuffmanTree(Huffman ht,WeightNode w,int n)

{

int i,j;

int s1,s2;

for(i=1;i<=n;i++)

{

ht[i].weight = w[i].weight;

ht[i].parent = 0;

ht[i].LChild = 0;

ht[i].RChild = 0;

}

for(i=n+1;i<=2*n-1;i++)

{

ht[i].weight = 0;

ht[i].parent = 0;

ht[i].LChild = 0;

ht[i].RChild = 0;

}

for(i=n+1;i<=2*n-1;i++)

{

for(j=1;j<=i-1;j++)

if(!ht[j].parent)

break;

s1=j;

for(;j<=i-1;j++)

if(!ht[j].parent)

s1 = ht[s1].weight > ht[j].weight?j:s1;

ht[s1].parent = i;

ht[i].LChild = s1;

for(j=1;j<=i-1;j++)

if(!ht[j].parent)

break;

s2 = j;

for(;j<=i-1;j++)

if(!ht[j].parent)

s2 = ht[s2].weight > ht[j].weight?j:s2;

ht[s2].parent = i;

ht[i].RChild = s2;

ht[i].weight = ht[s1].weight + ht[s2].weight;

}

}

void CrtHuffmanNodeCode(Huffman ht,char ch[],HuffmanCode h,WeightNode weight,int m,int n)

{

int i,c,p,start;

char *cd;

cd = (char*)malloc(n*sizeof(char));

cd[n-1]='\0';

for(i=1;i<=n;i++)

{

start = n-1;

c = i;

p = ht[i].parent;

while(p)

{

start--;

if(ht[p].LChild == c)

cd[start] = '0';

else

cd[start] = '1';

c =  p;

p = ht[p].parent;

}

weight[i].num = n-start;

h[i] = (char*)malloc((n-start)*sizeof(char));

strcpy(h[i],&cd[start]);

}

free(cd);

system("pause");

}

void CrtHuffmanCode(char ch[],HuffmanCode h,HuffmanCode hc,WeightNode weight,int n,int m)

{

int i,k;

for(i=0;i<m;i++)

{

for(k=1;k<=n;k++)

if(ch[i] == weight[k].c)

break;

hc[i] = (char*)malloc((weight[k].num)*sizeof(char));

strcpy(hc[i],h[k]);

}

}

void TrsHuffmanTree(Huffman ht,WeightNode w,HuffmanCode hc,int n,int m)

{

int i=0,j,p;

printf("***StringInformation***\n");

while(i<m)

{

p = 2*n-1;

for(j=0;hc[i][j]!='\0';j++)

{

if(hc[i][j] == '0')

p = ht[p].LChild;

else

p = ht[p].RChild;

}

printf("%c",w[p].c);

i++;

}

}

void FreeHuffmanCode(HuffmanCode h,HuffmanCode hc,int n,int m)

{

int i;

for(i=1;i<=n;i++)

free(h[i]);

for(i=0;i<m;i++)

free(hc[i]);

}

void main()

{

int i,n=0;

int m = 0;

char ch[N];

Huffman ht;

HuffmanCode h,hc;

WeightNode weight;

printf("\t***HuffmanCoding***\n");

printf("please input information:");

gets(ch);

CreateWeight(ch,&m,weight,&n);

printf("***WeightInformation***\n Node");

for(i=1;i<=n;i++)

printf("%c",weight[i].c);

printf("\nWeight");

for(i=1;i<=n;i++)

printf("%d",weight[i].weight);

CreateHuffmanTree(ht,weight,n);

printf("\n***HuffamnTreeInformation***\n");

    printf("\ti\tweight\tparent\tLChild\tRChild\n");

for(i=1;i<=2*n-1;i++)

printf("\t%d\t%d\t%d\t%d\t%d\n",i,ht[i].weight,ht[i].parent,ht[i].LChild,ht[i].RChild);

CrtHuffmanNodeCode(ht,ch,h,weight,m,n);

printf(" ***NodeCode***\n");

for(i=1;i<=n;i++)

{

printf("\t%c:",weight[i].c);

printf("%s\n",h[i]);

}

CrtHuffmanCode(ch,h,hc,weight,n,m);

printf("***StringCode***\n");

for(i=0;i<m;i++)

printf("%s",hc[i]);

system("pause");

TrsHuffmanTree(ht,weight,hc,n,m);

FreeHuffmanCode(h,hc,n,m);

system("pause");

}