歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

基於Huffman編碼的C語言解壓縮文件程序

基於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

------------------------------------------分割線------------------------------------------

Copyright © Linux教程網 All Rights Reserved