哈夫曼编码
2019-02-03 本文已影响0人
漫游之光
哈夫曼编数的构造还是比较简单的，但是要写一个能运行的小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;
}
相当于保存一下代码，很多解释都没有写。有空再补上吧。
