哈夫曼编码

哈夫曼编数的构造还是比较简单的，但是要写一个能运行的小demo，也就是能把一个文本压缩，并且能够把这个文本解压，然后保持数据不变。也就是实现《算法（第4版）》中对应章节的demo。

首先就是关于单个bit的读写问题，我个人简单的实现了一个，效率不高，但胜在简单。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<string>
#include<vector>
#include<queue>
using namespace std;

#define CHARACTER_SET_SIZE 256

void writeBit(FILE *file, char bit,bool reset = false){
    static int index = 8;
    static char c = 0x00;
    // static FILE *pre = NULL;
    // if(file != pre){
    //     index = 0;
    //     c = 0x00;
    //     pre = file;
    // }
    if(reset == true){
        index = 8;
        c = 0x00;
        return;
    }
    if(index == 8){
        index = 0;
        c = 0x00;
        fwrite(&c,1,1,file); /* write a blank */
    }
    if(bit == '1'){
        c = c | (0x01 << (7-index));
    }
    index++;
    fseek(file,-1,SEEK_END);
    fwrite(&c,1,1,file);
}

bool readBit(FILE *file,bool reset = false){
    static int index = 8;
    static char c = 0x00;
    // static FILE *pre = NULL;
    // if(pre != file){
    //     index = 8;
    //     c = 0x00;
    //     pre = file;
    //     cout<<"read file changed"<<endl;
    // }
    if(reset == true){
        index = 8;
        c = 0x00;
        return false;
    }
    if(index == 8){
        fread(&c,1,1,file);
        index = 0;
    }
    if(((c<<index)&0x80) != 0){
        index++;
        return true;
    }else{
        index++;
        return false;
    }
}

刚开始我是用FILE指针来指示读写的是不是新文件，后来发现有一个奇怪的bug，如果把读关闭，解压后会出现乱码，观察乱码，发现只是写的时候，前面多了1个bit；但是如果不把读关闭，就没有这个问题。后面想了很久，想起了UNIX的文件系统，想到可能window的文件可能也是有类似的机制。就是FILE指针指向的类似于UNIX中的文件描述符，当把读指针关了的时候，写指针打开的位置可能有和上次一样了，所以有上次遗留的数据还在里面。所以不能保存FILE指针来标识是否是和上一个文件是同一个文件。

哈夫曼压缩主要有以下的步骤：

• 读取输入。
• 将输入中的每个char值的出现频率制成表格。
• 根据频率构造相应的哈夫曼树。
• 构造编译表，将输入中的每个char值和一个比特字符串相关联。
• 将单词查找树编码为比特字符串并写入输出流。
• 将单词总数编码为比特字符串并写入输出流。
• 使用编译表翻译每个输入字符。

下面是代码：

struct Node 
{
    char ch;
    int freq;
    Node *left;
    Node *right;

    Node(char ch,int freq,Node *left,Node *right)
        :ch(ch),freq(freq),left(left),right(right){
    }        
};

struct cmp{
    bool operator()(Node *n1,Node *n2){
        return n1->freq > n2->freq; /* n1's priority is lower than n2 if retrun true */
    }
};

void releaseTrie(Node *root){
    if(root == NULL){
        return;
    }
    releaseTrie(root->left);
    releaseTrie(root->right);
    delete root;
}

Node* buildTrie(vector<int> &freq){
    int len = freq.size();
    priority_queue<Node*,vector<Node*>,cmp> q;
    for(int i=0;i<len;i++){
        if(freq[i] > 0){
            cout<<(char)i << " "<<freq[i]<<endl;
            q.push(new Node(i,freq[i],NULL,NULL));
        }
    }
    while(q.size() > 1){
        Node *x = q.top();
        q.pop();
        Node *y = q.top();
        q.pop();
        q.push(new Node('\0',x->freq + y->freq,x,y));
    }
    return q.top();
}

void buildCode(vector<string> &v,Node *node,string s){
    if(node->left == NULL && node->right == NULL){
        v[node->ch] = s;
        return;
    }
    buildCode(v,node->left,s+'0');
    buildCode(v,node->right,s+'1');
}



void writeTrie(FILE *file,Node *root){
    if(root->left == NULL && root->right == NULL){
        writeBit(file,'1');
        char c = root->ch;
        for(int i=0;i<8;i++){
            if(((c<<i) & 0x80) != 0){
                 writeBit(file,'1');
            }else{
                writeBit(file,'0');
            }
        }
        return;
    }
    writeBit(file,'0');
    writeTrie(file,root->left);
    writeTrie(file,root->right);
}

void encode(const char *input,const char *output){
    readBit(NULL,true);
    FILE *in = fopen(input,"rb");
    vector<int> freq(CHARACTER_SET_SIZE,0);
    char c;
    int len = 0;
    while((fread(&c,1,1,in))>0){
        freq[c]++;
        len ++ ;
    }
    Node *root = buildTrie(freq);
    vector<string> code(CHARACTER_SET_SIZE,"");
    buildCode(code,root,"");
    for(int i=0;i<code.size();i++){
        if(code[i] != ""){
            cout<<(char)i<<" "<<code[i]<<endl;
        }
    }

    writeBit(NULL,NULL,true);
    FILE *out = fopen(output,"wb+");
    writeTrie(out,root);
    for(int i=0;i<32;i++){
        if((len & 0x80000000) != 0){
            writeBit(out,'1');
        }else{
            writeBit(out,'0');
        }
        len = len<<1;
    }
    fseek(in,0,SEEK_SET);
    while((fread(&c,1,1,in))>0){
        for(int i=0;i<code[c].size();i++){
            writeBit(out,code[c][i]);
        }
    }
    releaseTrie(root);
    fclose(in);
    fclose(out);
}

这个里面比较难理解的是读写单词树的过程，写的时候是先序遍历，如果不是叶子节点，就写0，如果是叶子节点，就写入1，然后再写入该节点的ASCII编码。

解码的过程是：

• 读取单词树。
• 读取需要解码的字符数量。
• 使用单词查找树将比特流解码。

下面是代码：

Node *readTrie(FILE *file){
    if(readBit(file) == true){
        char c = 0x00;
        for(int i=0;i<8;i++){
            if(readBit(file) == true){
                c = c | (0x1 << (7 - i));
            }
        }
        return new Node(c,0,NULL,NULL);
    }
    return new Node('\0',0,readTrie(file),readTrie(file));
}

void decode(const char *input,const char *output){
    readBit(NULL,true);
    FILE *in = fopen(input,"rb");
    Node *root = readTrie(in);
    vector<string> code(CHARACTER_SET_SIZE,"");
    buildCode(code,root,"");
    for(int i=0;i<code.size();i++){
        if(code[i] != ""){
            cout<<(char)i<<" "<<code[i]<<endl;
        }
    }
    unsigned int len = 0;
    for(int i=0;i<32;i++){
        if(readBit(in) == true){
            len = len | (0x1 << (31 - i));
        }
    }
    
    writeBit(NULL,NULL,true);
    FILE *out = fopen(output,"wb+");
    for(int i=0;i<len;i++){
        Node *node = root;
        while(node->left != NULL || node->right != NULL){
            if(readBit(in) == true){
                node = node->right;
            }else{
                node = node->left;
            }
        }
        char c = node->ch;
        for(int j=0;j<8;j++){
            if((c & 0x80) != 0){
                writeBit(out,'1');
            }else{
                writeBit(out,'0');
            }
            c = c << 1;
        }     
    } 
    
    releaseTrie(root);
    fclose(in);
    fclose(out);
}

测试代码：

int main(){
    encode("input.txt","huffman.data");
    decode("huffman.data","output.txt");
    return 0;
}

相当于保存一下代码，很多解释都没有写。有空再补上吧。