基于哈夫曼树的文件压缩和解压

Jun 16, 2010

主要思想: 遍历文件,统计每个ASCII码出现的次数(为了解决写压缩文件时不能对齐的问题,人为定义第128号字符,并设定它出现的频率最高,对应的哈夫曼编码为0),根据ASCII码出现的次数创建哈夫曼编码。 读入要压缩的文件,对应每个字符遍历一次哈夫曼树,得到哈夫曼编码,并以字节为单位写到压缩文件中去,最后对不齐的地方用0补齐。

以字符为单位读压缩文件,把每个字符转换为二进制串并遍历哈夫曼树找到其对应的字符。若遇到哈夫曼编码为0的字符则忽略。

/*
  This programme was compliced by g++ in UBUNTU SYSTEM;

  Firstly, input filename which you want to compress.
  Then I will give you a file called "Huffman_List.txt" which records the HUFFMAN VALUE of the ASCII from 0 to 127;
  By the way,a compressed file will be created called "zip.txt";
  Also, another file called "unzip.txt" which decompressed from "zip.txt" will be created.
*/

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>

FILE *fp, *wp;
int List[258], parent[258], data[258], buf[129], table[129], Lson[258], Rson[258];
int min_1, min_2, min, num = 129, par = 129, pt, pt_1, pt_2, head, wurm, now = -1;
char filename[40];

/*-------------------Initialize----------------------*/
void Init(){
    int i = 0;

    for(i = 0; i < 258; ++i){
        List[i] = 0;
        parent[i] = -1;
        data[i] = -1;
        Rson[i] = -1;
        Lson[i] = -1;
    }
    List[128] = INT_MAX - 1;     /*Create a inexistence ASCII whose value is 128,
                                  Let List[128] MAX, to make sure its Huffman value still be 0*/
}

/*----------Find out the min value of List[]---------*/
void Min(){
    min = INT_MAX;
    int i;

    for(i = 0; i < par; i++){
        if(min > List[i]){
            min = List[i];
            pt = i;
        }
    }
    List[pt] = INT_MAX;
}

/*---------Create Huffman value of each ASCII--------*/
void huffman(){
    while(num != 1){

        Min();
        min_1 = min;
        pt_1 = pt;
        Min();
        min_2 = min;
        pt_2 = pt;

        num--;

        data[pt_1] = 1;
        data[pt_2] = 0;

        List[par] = min_1 + min_2;

        parent[pt_1] = par;
        parent[pt_2] = par;

        Lson[par] = pt_1;
        Rson[par] = pt_2;

        head  =par;

        par++;
    }
}

/*----When file open error the programme will exit----*/

void Error(int i){
    switch(i){
        case 1:
        printf("%s open failed!\n", filename);
        exit(0);
        break;
        case 2:
        printf("Huffman_List open failed!\n");
        exit(0);
        break;
        case 3:
        printf("zip.txt open failed!\n");
        exit(0);
        break;
        case 4:
        printf("unzip.txt open fialed!\n");
        exit(0);
        break;
        default:
        break;
    }
}

/*--------Count the frequence of each ASCII----------*/
void ReadFile(FILE* fp){
    int str;

    while((str = getc(fp)) != EOF){
        List[str]++;
    }
    fclose(fp);
}

void Format(int n){
    switch(n){
        case 1:
        putc(' ', fp);
        putc(' ', fp);
        putc(' ', fp);
        break;
        case 2:
        putc('\n', fp);
        break;
        default:
        break;
    }
}

void Alter(int n){
    int nn = 0;
    char out;

    while(n != -1){
        table[nn] = buf[n--];
        out = table[nn] + '0';
        putc(out, fp);
        nn++;
    }
}

/*---Write Huffman value of each ASCII into file Huffman_List---*/
void Print(){
    int i;
    if((fp = fopen("Huffman_List.txt", "w+")) == NULL){
        Error(2);
    }

    for(i = 0; i < 128; i++){
        int a = i;
        int p = 0;
        char out = i;
        putc(out, fp);
        Format(1);
        while(parent[a] != -1){
            buf[p++] = data[a];
            a = parent[a];
        }
        Alter(p - 1);
        Format(2);
    }
    fclose(fp);
}

/*----------Store the string in opposite direction----------*/
void Change(int p){
    int a = 0;

    while(parent[p] != -1){
        buf[a++] = data[p];
        p = parent[p];
    }
    a--;
    while(a != -1){
        table[++now] = buf[a--];
    }
}

/*-----------------Change char to libary---------------------*/
unsigned char Int_to_bit(){
    int i;
    unsigned char out = table[0];
    int nn = 0;

    for(i = 1; i < 8; ++i){
        out = (out << 1);
        if(table[i] == 1){
            out += 1;
        }
    }
    return out;
}

void Left(){
    int i;

    for(i = 0; i < now; ++i){
        table[i] = table[i + 1];
    }
    now--;
}

/*-------------Get ASCII from it's Huffman value------------*/
void Tran(){

    while(now != -1){
        if(Lson[wurm] == -1 || Rson[wurm] == -1){
            if(wurm != 128){
                putc(wurm, wp);
            }
            wurm = head;
        }
        if(table[0] == 0){
            wurm = Rson[wurm];
        }
        else{
            wurm = Lson[wurm];
        }
        Left();
    }
}

void Char_to_bit(unsigned char ch){
    int temp;
    int i = 0;
    do{
        temp = ch % 2;
        ch /= 2;
        buf[i] = temp;
        ++i;
    }while(ch != 0);
    while(i != 8){
        buf[i] = 0;
        ++i;
    }
    while(i != 0){
        table[++now] = buf[--i];
    }
}

void Unzip(){
    int temp;
    unsigned char Get;
    now = -1;
    if((wp = fopen("unzip.txt", "w+")) == NULL){
        Error(4);
    }
    if((fp = fopen("zip.txt", "r")) == NULL){
        Error(3);
    }
    wurm = head;
    while((temp = getc(fp)) != EOF){
        Get = temp;
        Char_to_bit(Get);
        Tran();
    }
    fclose(fp);
    fclose(wp);
}

void Write(){
    if((wp = fopen("zip.txt", "w+")) == NULL){
        Error(3);
    }
    if((fp = fopen(filename, "r")) == NULL){
        Error(1);
    }
    int Get, nn;
    unsigned char out;
    while(((Get = getc(fp)) != EOF) || (now >= 7)){
        if(Get != EOF){
            Change(Get);
        }
        if(now >= 7){
            out = Int_to_bit();
            for(nn = 0; nn < now - 7; nn++){
                table[nn] = table[nn + 8];
            }
            now -= 8;
            putc(out, wp);
        }
    }
    fclose(fp);
    if(now != -1){
        while(now != 7){
            table[++now] = 0;
        }
        out = Int_to_bit();
        putc(out, wp);
    }
    fclose(wp);
}

void Scanf(){
    printf("Input file's name: ");
    scanf("%s", filename);
}

int main(){

    Scanf();
    Init();

    if((fp = fopen(filename, "r")) == NULL){
        Error(1);
    }
    ReadFile(fp);
    huffman();
    Print();
    Write();
    Unzip();

    return 0;
}

Get In Touch With Us ...