基於Huffman編碼的C語言解壓縮文件程序
C++使用優先隊列來構建huffman樹[哈夫曼樹] http://www.linuxidc.com/Linux/2012-01/52790.htm
Huffman編碼實現（詳細實現） http://www.linuxidc.com/Linux/2012-01/51730.htm
Huffman編碼與解碼的實現 http://www.linuxidc.com/Linux/2014-08/105644.htm
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
//極大值用於生成Huffman樹
#define MAXSIZE 100000000
//用於生成相應葉子節點Huffman編碼的二維字符數組
typedef char* HCode;
//Huffman樹節點
typedef struct node
{
int weight;
int data;
int parent,lchild,rchild;
}Node;
//count 葉子節點數的計算 sum_bit 記錄被壓縮文件編碼後的編碼總長度
int sum_bit,count;
//Huffman葉子節點，最多不過256個（以字節為單位）
Node huffmanNode[260];
//解壓縮的時候記錄每次讀取到編碼（0....1..）
int num[8];
//對應詞頻信息表的信息，用ASCII值表示
int code[260];
//二維字符數組
HCode *HC;
//統計詞頻時用於查找是否已經記錄過,記錄過的話返回下標，沒有則返回0
int isInNode(int value)
{
int i = 1;
for(;i<=count;i++)
{
if(huffmanNode[i].data == value)
{
return i;
}
}
return 0;
}
//獲取文件詞頻，記錄在Node huffmanNode[260]的節點數組當中
void calWeight(char *file)
{
count = 0;
FILE *f;
int a;
//以二進制方式打開文件，為了讀取到換行符
f = fopen(file,"rb");
if(f == NULL)
{
printf("文件不存在！打開失敗！");
return ;
}
while(!feof(f))
{
a = fgetc(f);
if(a==EOF) break;
if(!isInNode(a)) //count從1開始計數
{
count++;
huffmanNode[count].weight = 1;
huffmanNode[count].data = a;
}
else
{
int i = isInNode(a);
huffmanNode[i].weight++;
}
}
fclose(f);
}
/*得到待壓縮文件的總字節數，權值為幾就代表著有多少個字節*/
int getSumBytes()
{
int i=1;
int result = 0;
for(;i<=count;i++)
{
result +=huffmanNode[i].weight;
}
return result;
}
//獲取壓縮後文件的總bit數
int getSumBits()
{
int i = 1;
int result = 0;
for(;i<=count;i++)
{
result+=huffmanNode[i].weight * strlen(HC[i]);
}
return result;
}
//建立huffman樹 根據huffman樹的特性,具有n個節點的huffman樹的具有2n-1個節點
//n值由全局變量count值來確定，該函數主要用來初始化Huffman樹的所有節點信息
void createHufmanTree(Node * huffmanTree)
{
int m = 2*count - 1;
int m1,m2,x1,x2,i,j;
//初始化結點信息，從1--count這count個節點信息為葉子節點的信息
for(i=1;i<=count;i++)
{
huffmanTree[i].data = huffmanNode[i].data;
huffmanTree[i].lchild = -1;
huffmanTree[i].rchild = -1;
huffmanTree[i].parent = -1;
huffmanTree[i].weight = huffmanNode[i].weight;
}
//從count---2*count-1這些節點首先初始化為空
for(;i<=m;i++)
{
huffmanTree[i].data = 0; huffmanTree[i].weight = 0;
huffmanTree[i].lchild = -1; huffmanTree[i].rchild = -1;
huffmanTree[i].parent = -1;
}
//構造huffman樹，按照huffman樹構建原理
for(i=count+1;i<=m;i++)
{
/*m2,m1分別存儲倒數第二小的權值和倒數第一小的權值
x2,x1分別存儲倒數第二小的下標和倒數第一小的下標*/
m1 = m2 = MAXSIZE;
x1 = x2 = 0;
for(j=1;j<i;j++)
{
if(huffmanTree[j].parent == -1&&huffmanTree[j].weight <m1)
{
m2 = m1; x2 = x1;
m1 = huffmanTree[j].weight; x1 = j;
}
else if(huffmanTree[j].parent == -1&&huffmanTree[j].weight<m2)
{
m2 = huffmanTree[j].weight;
x2 = j;
}
}
/*合並成一顆新的樹*/
huffmanTree[x1].parent = i; huffmanTree[x2].parent = i;
huffmanTree[i].lchild = x1; huffmanTree[i].rchild = x2;
huffmanTree[i].weight = m1+m2;
}
}
/*字符編碼，從構建好的Huffman樹當中讀取每個葉子節點的huffman編碼，並將葉子節點的信息放入到code[]中*/
HCode * getHuffmanCode(Node * huffmanTree,HCode *HC,int code[])
{
int i = 1,c,start,f;
//構造了字符編碼的字符數組共有count+1個 通過讀取一個復制一個的方式完成編碼獲取
char * cd = (char *)malloc((count+1)*sizeof(char));
//還是這個問題的
cd[count] = '\0';
for(;i<=count;i++)
{
start = count;
for(c=i,f=huffmanTree[i].parent;f!=-1;c=f,f=huffmanTree[f].parent)
{
if(huffmanTree[f].lchild == c) cd[--start] = '0';
else cd[--start] = '1';
}
//為每個字符數組分配相應的數量 由於范圍的問題要仔細考慮的
HC[i] = (char *)malloc((count+1-start)*sizeof(char));
//參數均為char *
strcpy(HC[i],&cd[start]);
code[i] = huffmanTree[i].data;
}
return HC;
}
/*
將編碼表寫入默認文件當中,並在結尾存入葉子節點數（count）與壓縮後文件的總bit數
1111000 27
...........
...........
#sum_bit##count#
*/
void freToFile(int code[],HCode *HC)
{
int i;
//打開默認文件
FILE *fe = fopen("C:\\dic.txt","wb");
//將編碼信息和葉子節點信息寫入詞典
for(i=1;i<=count;i++)
{
fprintf(fe,"%s %d\n",HC[i],code[i]);
}
char c = '#';
//寫入sum_bit
fprintf(fe,"%c",c);
fprintf(fe,"%d",getSumBits());
fprintf(fe,"%c",c);
//寫入count
fprintf(fe,"%c",c);
fprintf(fe,"%d",count);
fprintf(fe,"%c",c);
fclose(fe);
}
//由於詞頻表是按照字符串方式存儲的葉子節點信息,讀取出來的字符串需要轉換成int值再使用
//其中需要使用pow函數，由於pow函數有精度損失，自己寫了一個使用
int powmy(int a,int b)
{
if(b==0) return 1;
int i = 0;
int result = 1;
for(;i<b;i++)
{
result *=a;
}
return result;
}
/*從編碼表文件讀取相應信息以用來解壓文件，讀取信息包括編碼和葉子信息*/
HCode* freFromFile(int code[],HCode *HC)
{
int i;
FILE *fe = fopen("C:\\dic.txt","rb");
if(fe==NULL)
{
printf("詞典文件不存在！");
return NULL;
}
int k;
int num[10];
int m;
int flag = 0;
char * cd = (char *)malloc((256+1)*sizeof(char));
//讀取一個字節
char c = fgetc(fe);
for(i=1;flag!=1;i++)
{
//如果讀取到#號鍵，就跳出循環，繼續讀取sum_bit和count值
if(c=='#') break;
//每一行的讀取直到讀到空格，然後就完成了一條huffman編碼的讀取
int j = 0;
while(c!=' ')
{
cd[j++] = c;
c = fgetc(fe);
}
cd[j] = '\0';
//將讀取到的huffman編碼存入相應的二維字符數組當中去
HC[i] = (char *)malloc((j+1)*sizeof(char));
strcpy(HC[i],&cd[0]);
//下面直到讀取到空格鍵為止，讀取huffman葉子節點信息，讀取到的是字符，需要轉換成int值
c = fgetc(fe);
k = 0;
while(c!='\n')
{
num[k++] = c-'0';
c = fgetc(fe);
}
code[i] = 0;
m = 0;
//轉換成int值，存入code[]數組當中
for(k=k-1;k>=0;k--)
{
code[i]+=num[k]*powmy(10,m);
m++;
}
//繼續向下讀取
c = fgetc(fe);
}
//獲取壓縮文件的總bit數，以用來判斷最後一次讀取的是不是足夠8位
c = fgetc(fe);
k = 0;
while(c!='#')
{
num[k++] = c-'0';
c = fgetc(fe);
}
//同樣將讀取到的char轉換成int
m = 0;
sum_bit = 0;
for(k=k-1;k>=0;k--)
{
sum_bit+=(num[k]*powmy(10,m));
m = m + 1;
}
c = fgetc(fe); c = fgetc(fe);//頭一個讀取#，後一個才開始讀取數據
k = 0;
while(c!='#')
{
num[k++] = c-'0';
c = fgetc(fe);
}
//將讀取到的char轉換成int
m = 0; count = 0;
for(k=k-1;k>=0;k--)
{
count+=num[k]*pow(10,m);
m++;
}
fclose(fe);
return HC;
}
/*壓縮文件*/
void compress_file(char* file1,char*file2)
{
int i,sum = 0,flag = 0,j,k = 0;
//數組開設的不夠大是最後的一個bug的成因，因為有可能這個Huffman編碼很長很長
int eight[1000];
memset(eight,0,1000*sizeof(int));
FILE *fo = fopen(file1,"rb");
FILE *fw = fopen(file2,"wb");
if(fo == NULL||fw == NULL)
{
printf("文件讀取失敗！");
return;
}
//統計已經壓縮的字節總數，用於計算壓縮百分比
int aa = 0;
int sum_bytes = getSumBytes();
while(!feof(fo))
{
sum = 0;
int a = fgetc(fo);
//每次讀取一個字節就+1
aa++;
//讀取了一個字節之後就與編碼表進行比較，查找對應的編碼
for(i=1;i<=count;i++)
{
if(code[i] == a)
{
//flag作為計數器，當湊夠8位之後就作為一個字節寫入壓縮文件
flag+=strlen(HC[i]);
int len = strlen(HC[i]);
//flag 小於8的時候繼續累加，直到湊夠8個
if(flag<8)
{
for(j=0;j<len;j++)
eight[k++] = HC[i][j]-'0';/*我們存儲的是字符串，是多少就是多少*/
}
//當flag>=8的時候，將8位寫進壓縮文件，同時將剩余的沒有寫入的huffman編碼重新移到
//eight【】數組前面去，同時修改flag
else if(flag>=8)
{
//將匹配到的huffman編碼寫進8位數組，直到k值為8，k值始終代表現在eight【】數組的長度
for(j=0;k<8;j++)
eight[k++] = HC[i][j]-'0';
//將匹配到的huffman編碼的沒有完全寫進去的添加到後面。
for(;j<len;j++)
eight[k++] = HC[i][j]-'0';
//計算8位對應的int值，寫入文件
sum+=eight[0]*128+eight[1]*64+eight[2]*32+eight[3]*16+eight[4]*8
+eight[5]*4+eight[6]*2+eight[7]*1;
//前8為置0
for(j=0;j<8;j++)
eight[j] = 0;
//將後面的移植到前面去
for(j=8;j<k;j++)
eight[j-8] = eight[j];
//重置flag與k
k = flag = j-8;
//寫進文件
char c = sum;
fputc(c,fw);
if(aa%1000==0)
{
printf("\r正在進行壓縮，請稍等……%6.2f%%",(double)aa/sum_bytes*100.0);
}
fflush(fw);
i = count+1;
}
}
}
}
aa = sum_bytes;
printf("\r正在進行壓縮，請稍等……%6.2f%%",(double)aa/sum_bytes*100.0);
printf("壓縮成功！");
/*考慮到最後可能沒有湊夠八位的情況*/
if(flag)
{
sum+=eight[0]*128+eight[1]*64+eight[2]*32+eight[3]*16+eight[4]*8
+eight[5]*4+eight[6]*2+eight[7]*1;
char c = sum;
fputc(c,fw);
sum_bit +=flag;
fflush(fw);
}
fclose(fw);
fclose(fo);
}
/*用於在解壓的時候將讀取到的ASCII碼轉換為二進制數*/
int swap(int data)
{
int i = 0;
while(data)
{
num[i++] = data%2;
data = data/2;
}
return i;
}
/*進行文件的解壓*/
void uncompress_file(char* file1,char* file2)
{
FILE *fo = fopen(file1,"rb");
FILE *fw = fopen(file2,"wb");
if(fo==NULL ||fw == NULL)
{
printf("文件打開失敗！");
return;
}
char str[1000];
int i,j,k,temp = 0;
int index;
int sum_bit2 = sum_bit;
//直到讀取到文件結尾
while(!feof(fo))
{
if(sum_bit2<0) break;
//讀取一次，減去8位
sum_bit2 -=8;
int data = fgetc(fo);
if(data == -1) break;
//index用來在sum_bit2小於0的時候設置讀取為位數（也就是說最後不用讀取8位了）
if(sum_bit2<0)
{
index = 0-sum_bit2;
}
else
{
index = 0;
}
if(data == -1) break;
memset(num,0,sizeof(num));
//將讀取到的data轉換成二進制數
swap(data);
i = temp;
//將轉換後的二進制數變為字符串，注意順序
//是一位一位的往裡面填，填進去一位立即進行比較，當找到相應的信息就調出來
for(k=7;k>=index;i++,k--)
{
if(num[k])
str[i] = '1';
else
str[i] = '0';
str[i+1] ='\0';
//查找編碼表當中與該字符串（編碼）相同的信息，然後將葉子信息寫入解壓文件
for(j=1;j<=count;j++)
{
if(strcmp(str,HC[j])==0)
{
//將葉子信息寫入到文件（寫入的是int值，是該int值表示的字符）
fputc(code[j],fw);
if((sum_bit-sum_bit2)%1500==0)
{
printf("\r文件正在解壓中,請耐心等待……%6.2f%%",(double)(sum_bit-sum_bit2)/sum_bit*100.0);
}
fflush(fw);
j = count+1;
i = -1;
}
}
}
if(i)
{
temp = i;
}
else
{
temp = 0;
}
}
sum_bit2 = 0;
printf("\r文件正在解壓中,請耐心等待……%6.2f%%",(double)(sum_bit-sum_bit2)/sum_bit*100.0);
printf("解壓成功！");
fclose(fw);
fclose(fo);
}
int main(int argc, char **argv)
{
if(strcmp(argv[1],"-c")==0)
{
//獲取文件的詞頻
calWeight(argv[2]);
//申請Huffman樹的內存，已經獲得葉子節點數，根據節點總數與葉子節點數的關系分配內存
Node *huffmanTree = (Node *)malloc((2*count-1+1)*sizeof(Node));
//創建Huffman樹
createHufmanTree(huffmanTree);
//為Huffman編碼表申請一個二維的字符數組指針
HC = (HCode *)malloc((count+1)*sizeof(HCode));
//向指針賦值，getHuffmanCode()函數返回編碼表
HC = getHuffmanCode(huffmanTree,HC,code);
//根據編碼表HC和編碼對應的data表code壓縮文件
compress_file(argv[2],argv[3]);
//將編碼存入到默認的編碼表當中（C:\\dic.txt）
freToFile(code,HC);
}
else if(strcmp(argv[1],"-u")==0)
{
//為編碼表分配內存，由於不知道葉子節點數，分配257
HC = (HCode *)malloc(257*sizeof(HCode));
//從詞頻表當中獲取編碼
HC = freFromFile(code,HC);
//根據編碼表和data表解壓文件
uncompress_file(argv[2],argv[3]);
}
return 0;
}
一份基於huffman編碼的文件解壓縮程序(C語言，源碼）下載
------------------------------------------分割線------------------------------------------
免費下載地址在 http://linux.linuxidc.com/
用戶名與密碼都是www.linuxidc.com
具體下載目錄在 /2014年資料/8月/18日/基於Huffman編碼的C語言解壓縮文件程序
下載方法見 http://www.linuxidc.com/Linux/2013-07/87684.htm
------------------------------------------分割線------------------------------------------
