哈夫曼壓縮文本

A. 如何用哈夫曼編碼實現英文文本的壓縮和解壓縮

哈夫曼壓縮是個無損的壓縮演算法，一般用來壓縮文本和程序文件。哈夫曼壓縮屬於可變代碼長度演算法一族。意思是個體符號（例如，文本文件中的字元）用一個特定長度的位序列替代。因此，在文件中出現頻率高的符號，使用短的位序列，而那些很少出現的符號，則用較長的位序列。有人用C函數寫了這個編碼，見下面鏈接

http://ke..com/view/189694.htm

B. 用哈夫曼編碼壓縮一個word文檔,文件沒有變小,反而還變大了

提問者尼壕，
哈夫曼編碼是可以應用於數據壓縮
但可能文件本身被壓縮，比如docx文件，本身已經被壓縮le，所以基本沒有效果，甚至變大
好比7z壓縮一個avc mp4一樣，只會變大
但doc應該有一定效果

有問題請追問撒QAQ

C. 哈夫曼編碼法的壓縮和解壓縮怎麼實現

建立一棵赫夫曼樹，設每個父節點的左子節點為1，右子節點為0，然後由根節點到所要編碼的字元的葉節點的路徑確定字元的編碼。比如要編碼a，假設a在第三層，則由根節點到a的路徑為：根節點——右子節點（0）——左子節點（1）。那麼a的編碼就為01。就這樣把所有字元進行編碼，建立一個赫夫曼編碼表。利用這個編碼表把字元串編碼就是壓縮了，解壓縮就是把參照赫夫曼編碼表把編碼轉為字元串。

D. 利用huffman樹實現文件的壓縮與解壓

這是本人寫的動態哈夫曼壓縮演算法實現，壓縮與解壓縮時，
根據文件內容自動生成哈夫曼樹，並動態調整節點的權重
和樹的形狀。900MHZ的PIII賽揚每秒鍾可以壓縮的好幾MB
的數據，只是壓縮率不高，文本文件的壓縮後容量一般可
以減少25%，比RAR差遠了。

源文件共三個，你在VC6.0中新建一個空的命令行項目，
將它們加進去，編譯完就可以用了。

===========hfm.cpp===================

#include <stdio.h>
#include <string.h>
#include <io.h>
#include <sys/stat.h>
#include <fcntl.h>
#include "Huffman.h"

int wh;
int rh;

bool Write(unsigned char *s,int len){
_write(wh,s,len);
return true;
}

bool OpenFile(char* source,char* target){
int w_flag=_O_WRONLY | _O_CREAT | _O_EXCL | _O_BINARY;
int r_flag=_O_RDONLY | _O_BINARY;

rh=_open(source,r_flag,_S_IREAD | _S_IWRITE);
wh=_open(target,w_flag,_S_IREAD | _S_IWRITE);

if(rh==-1 || wh==-1){
if(rh!=-1){
_close(rh);
printf("\n打開文件：'%s'失敗!",target);
}
if(wh!=-1){
_close(wh);
printf("\n打開文件：'%s'失敗!",source);
}

return false;
}else{
return true;
}
}

void PrintUsage(){
printf("\n以動態哈夫曼演算法壓縮或解壓縮文件。\n\n");
printf("\thfm -?\t\t\t\t顯示幫助信息\n");
printf("\thfm -e -i source -o target\t壓縮文件\n");
printf("\thfm -d -i source -o target\t解壓縮文件\n\n");
}

void main(int argc,char *args[]){
int mode,i,j,K=0;
char src[4096];
char target[4096];
unsigned char buffer[BUFFER_SIZE];
Huffman *h;

mode=0;
for(i=1;i<argc;i++){
if(args[i][0]=='-' || args[i][0]=='/'){
switch(args[i][1]){
case '?':
mode=0;//幫助
break;
case 'e':
case 'E':
mode=1;//壓縮
break;
case 'd':
case 'D':
mode=2;//解壓縮
break;
case 'o':
case 'O':
if(i+1>=argc){
mode=0;
}else{//輸出文件
j=0;
while(args[i+1][j]!='\0' && j<4096){
target[j++]=args[i+1][j];
}
if(j==4096){
mode=0;
}else{
target[j]='\0';
K |= 1;
}
}
break;
case 'i':
case 'I':
if(i+1>=argc){
mode=0;
}else{//輸入文件
j=0;
while(args[i+1][j]!='\0' && j<4096){
src[j++]=args[i+1][j];
}
if(j==4096){
mode=0;
}else{
src[j]='\0';
K |=2;
}
}
break;
}
}
}

if(K!=3)mode=0;

switch(mode){
case 0:
PrintUsage();
return;
case 1://壓縮
if(!OpenFile(src,target))return;
h=new Huffman(&Write,true);
i=BUFFER_SIZE;
while(i==BUFFER_SIZE){
i=_read(rh,buffer,BUFFER_SIZE);
h->Encode(buffer,i);
}
delete h;
_close(rh);
_close(wh);
printf("壓縮完畢!");
break;
case 2://解壓縮
if(!OpenFile(src,target))return;
h=new Huffman(&Write,false);
i=BUFFER_SIZE;
while(i==BUFFER_SIZE){
i=_read(rh,buffer,BUFFER_SIZE);
h->Decode(buffer,i);
}
delete h;
_close(rh);
_close(wh);
printf("解壓縮完畢!");
break;
}

}

=======end of hfm.cpp=======================

=======Huffman.cpp=============================
// Huffman.cpp: implementation of the Huffman class.
//
//////////////////////////////////////////////////////////////////////

#include "Huffman.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

Huffman::Huffman(Output *output,bool mode)
{
Hbtree *tmp;
int i;

this->mode=mode;

//設置輸出函數，當緩沖區滿時，將調用該函數輸出
this->output=output;

//初始化列表
for(i=0;i<LIST_LENGTH;i++)this->list[i]=NULL;

//初始化哈夫曼樹
this->root=this->NewNode(NOT_CHAR,LEFT,NULL);
this->current=this->root;
tmp=this->NewNode(CODE_ESCAPE,RIGHT,root);
tmp->count=1;
tmp=this->NewNode(CODE_FINISH,LEFT,root);
tmp->count=0;
root->count=root->child[LEFT]->count+root->child[RIGHT]->count;

//設置緩沖區指針
this->char_top=BOTTOM_BIT;
this->bit_top=TOP_BIT;
this->buffer[0]=0;

//重構哈夫曼樹的最大計數值
this->max_count=MAX_COUNT;
this->shrink_factor=SHRINK_FACTOR;
this->finished=false;
}

Huffman::~Huffman()
{
if(this->mode==true){//如果是編碼
//輸出結束碼
this->OutputEncode(CODE_FINISH);
this->char_top++;
}

//強制清空緩沖區
this->Flush();

//釋放空間
this->ReleaseNode(this->root);
}

Hbtree * Huffman::NewNode(int value, int index, Hbtree *parent)
{
Hbtree *tmp=new Hbtree;
tmp->parent=parent;
tmp->child[0]=NULL;
tmp->child[1]=NULL;
tmp->count=(1 << SHRINK_FACTOR);
tmp->index=(index==0) ? 0 : 1;
tmp->value=value;

if(value!=NOT_CHAR)this->list[tmp->value]=tmp;
if(parent!=NULL)parent->child[tmp->index]=tmp;
return tmp;
}

void Huffman::ReleaseNode(Hbtree *node)
{
if(node!=NULL){
this->ReleaseNode(node->child[LEFT]);
this->ReleaseNode(node->child[RIGHT]);
delete node;
}
}

//輸出一位編碼
int Huffman::OutputBit(int bit)
{
unsigned char candidates[]={1,2,4,8,16,32,64,128};

if(bit!=0)
this->buffer[this->char_top] |= candidates[this->bit_top];
this->bit_top--;
if(this->bit_top < BOTTOM_BIT){
this->bit_top=TOP_BIT;
this->char_top++;

if(this->char_top >= BUFFER_SIZE){//輸出緩沖區
this->output(this->buffer,BUFFER_SIZE);
this->char_top=0;
}

this->buffer[this->char_top]=0;
}
return 0;
}

//輸出緩沖區
int Huffman::Flush()
{
this->output(this->buffer,this->char_top);
this->char_top=0;
return 0;
}

int Huffman::Encode(unsigned char c)
{
int value=c,
candidates[]={128,64,32,16,8,4,2,1},
i;

if(this->list[value]==NULL){//字元不存在於哈夫曼樹中
//輸出轉義碼
this->OutputEncode(CODE_ESCAPE);
//輸出字元
for(i=0;i<8;i++)this->OutputBit(value & candidates[i]);

this->InsertNewNode(value);

}else{
//輸出字元編碼
this->OutputEncode(value);

//重新調整哈夫曼樹
this->BalanceNode(this->list[value]->parent);
}

//重組哈夫曼樹
if(this->root->count>=this->max_count)
this->RearrangeTree();

return 0;
}

void Huffman::BalanceNode(Hbtree *node)
{
Hbtree *parent,*child,*brother;
int i,j;

parent=node->parent;
if(parent==NULL)return;//根節點無需調整

if(node->value==NOT_CHAR){//非葉子節點
child=node->child[LEFT]->count > node->child[RIGHT]->count ?
node->child[LEFT] : node->child[RIGHT];

if(child->count > parent->count - node->count){
//失衡

i=!(node->index);
j=child->index;
node->count=parent->count - child->count;
brother=parent->child[i];

node->child[j]=brother;
brother->index=j;
brother->parent=node;

parent->child[i]=child;
child->index=i;
child->parent=parent;
}
}
this->BalanceNode(parent);
}

//輸出一個字元的編碼
int Huffman::OutputEncode(int value)
{
int stack[CODE_FINISH+2],top=0;
Hbtree *tmp=this->list[value];

//輸出編碼
if(value<=MAX_VALUE){//字元
while(tmp!=NULL){
stack[top++]=tmp->index;
tmp->count++;
tmp=tmp->parent;
}
}else{//控制碼
while(tmp!=NULL){
stack[top++]=tmp->index;
tmp=tmp->parent;
}
}
top--;
while(top>0){
this->OutputBit(stack[--top]);
}

return 0;
}

void Huffman::PrintNode(Hbtree *node,int level)
{
int i;
if(node){
for(i=0;i<level*3;i++)printf(" ");
printf("%p P:%p L:%p R:%p C:%d",node,node->parent,node->child[0],node->child[1],node->count);
if(node->value!=NOT_CHAR)printf(" V:%d",node->value);
printf("\n");

this->PrintNode(node->child[LEFT],level+1);
this->PrintNode(node->child[RIGHT],level+1);
}
}

int Huffman::Encode(unsigned char *s, int len)
{
int i;
for(i=0;i<len;i++)this->Encode(s[i]);
return 0;
}

void Huffman::PrintTree()
{
this->PrintNode(this->root,0);
}

int Huffman::RecountNode(Hbtree *node)
{
if(node->value!=NOT_CHAR)return node->count;
node->count=
this->RecountNode(node->child[LEFT]) +
this->RecountNode(node->child[RIGHT]);
return node->count;
}

void Huffman::RearrangeTree()
{
int i,j,k;
Hbtree *tmp,*tmp2;

//所有非控制碼的計數值右移shrink_factor位，並刪除計數值為零的節點
for(k=0;k<=MAX_VALUE;k++){
if(this->list[k]!=NULL){
tmp=this->list[k];
tmp->count >>= this->shrink_factor;
if(tmp->count ==0){
this->list[k]=NULL;
tmp2=tmp->parent;
i=tmp2->index;
j=!(tmp->index);
if(tmp2->parent!=NULL){
tmp2->parent->child[i]=tmp2->child[j];
tmp2->child[j]->parent=tmp2->parent;
tmp2->child[j]->index=i;
}else{
this->root=tmp2->child[j];
this->current=this->root;
this->root->parent=NULL;
}
delete tmp;
delete tmp2;
}
}
}

//重新計數
this->RecountNode(this->root);

//重新調整平衡
for(i=0;i<=MAX_VALUE;i++){
if(this->list[i]!=NULL)
this->BalanceNode(this->list[i]->parent);
}
}

void Huffman::InsertNewNode(int value)
{
int i;
Hbtree *tmp,*tmp2;

//將字元加入哈夫曼樹
tmp2=this->list[CODE_FINISH];
tmp=this->NewNode(NOT_CHAR, tmp2->index, tmp2->parent);
tmp->child[LEFT]=tmp2;
tmp2->index=LEFT;
tmp2->parent=tmp;

tmp2=this->NewNode(value,RIGHT,tmp);
tmp->count=tmp->child[LEFT]->count+tmp->child[RIGHT]->count;
i=tmp2->count;
while((tmp=tmp->parent)!=NULL)tmp->count+=i;
//從底向上調整哈夫曼樹
this->BalanceNode(tmp2->parent);
}

int Huffman::Decode(unsigned char c)
{
this->Decode(c,7);
return 0;
}

int Huffman::Decode(unsigned char *s,int len)
{
int i;
for(i=0;i<len;i++)this->Decode(s[i]);
return 0;
}

int Huffman::Decode(unsigned char c, int start)
{
int value=c,
candidates[]={1,2,4,8,16,32,64,128},
i,j;
Hbtree *tmp;

if(this->finished)return 0;

i=start;
if(this->current==NULL){//轉義狀態下
while(this->remain >= 0 && i>=0){
if((candidates[i] & value) !=0){
this->literal |= candidates[this->remain];
}
this->remain--;
i--;
}

if(this->remain < 0){//字元輸出完畢

//輸出字元
this->OutputChar(this->literal);
//將字元插入哈夫曼樹
this->InsertNewNode(literal);
//重組哈夫曼樹
if(this->root->count>=this->max_count)
this->RearrangeTree();

//設置環境
this->current=this->root;
}
}else{
j=((value & candidates[i])!=0)?1:0;
tmp=this->current->child[j];
i--;
while(tmp->value==NOT_CHAR && i>=0){
j=((value & candidates[i])!=0)?1:0;
tmp=tmp->child[j];
i--;
}

if(tmp->value==NOT_CHAR){//中間節點
this->current=tmp;
}else{
if(tmp->value<=MAX_VALUE){//編碼內容
j=tmp->value;
this->OutputChar((unsigned char)j);

//修改計數器
tmp=this->list[j];
while(tmp!=NULL){
tmp->count++;
tmp=tmp->parent;
}
//調整平衡度
this->BalanceNode(this->list[j]->parent);

//重組哈夫曼樹
if(this->root->count>=this->max_count)
this->RearrangeTree();

//設置環境
this->current=this->root;
}else{
if(tmp->value==CODE_ESCAPE){//轉義碼
this->current=NULL;
this->remain=7;
this->literal=0;
}else{//結束碼
this->finished=true;
return 0;
}
}
}

}

if(i>=0)this->Decode(c,i);
return 0;
}

int Huffman::OutputChar(unsigned char c)
{
this->buffer[this->char_top++]=c;
if(this->char_top>=BUFFER_SIZE){//輸出緩沖區
this->output(this->buffer,BUFFER_SIZE);
this->char_top=0;
}
return 0;
}

========end of Huffman.cpp==================

========Huffman.h============================
// Huffman.h: interface for the Huffman class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(NULL)
#include <stdio.h>
#endif

#if !defined(AFX_HUFFMAN_H__B1F1A5A6_FB57_49B2_BB67_6D1764CC04AB__INCLUDED_)
#define AFX_HUFFMAN_H__B1F1A5A6_FB57_49B2_BB67_6D1764CC04AB__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#define MAX_COUNT 65536 //最大計數值，大於此值時
#define MAX_VALUE 255 //編碼的最大值
#define CODE_ESCAPE MAX_VALUE+1 //轉義碼
#define CODE_FINISH MAX_VALUE+2 //結束碼
#define LIST_LENGTH MAX_VALUE+3 //編碼列表長度
#define SHRINK_FACTOR 2 //減小的比例，通過右移位實現
#define LEFT 0 //左孩子索引
#define RIGHT 1 //右孩子索引
#define NOT_CHAR -1 //非字元

#define TOP_BIT 7 //字元最高位
#define BOTTOM_BIT 0 //字元最低位
#define BUFFER_SIZE 81920 //緩沖區大小

//輸出函數
typedef bool (Output)(unsigned char *s,int len);

//哈夫曼樹的節點定義
typedef struct Hnode{
int count;//計數器
int index;//父節點的孩子索引（0--左孩子，1--右孩子）
Hnode* child[2];
Hnode* parent;
int value;
}Hbtree;

class Huffman
{
private:
//輸出一個解碼的字元
int OutputChar(unsigned char c);
//從指定位置開始解碼
int Decode(unsigned char c,int start);
//插入一個新節點
void InsertNewNode(int value);
//重新調整哈夫曼樹構型
void RearrangeTree();
//對各節點重新計數
int RecountNode(Hbtree *node);
//列印哈夫曼樹節點
void PrintNode(Hbtree *node,int level);
//輸出一個值的編碼
int OutputEncode(int value);
//調節哈夫曼樹節點使之平衡
void BalanceNode(Hbtree *node);
//輸出一位編碼
int OutputBit(int bit);
//釋放哈夫曼樹節點
void ReleaseNode(Hbtree *node);
//新建一個節點
Hbtree *NewNode(int value,int index, Hbtree *parent);
//輸出函數地址
Output *output;
//哈夫曼樹根地址
Hbtree *root;
//哈夫曼編碼單元列表
Hbtree *list[LIST_LENGTH];
//輸出緩沖區
unsigned char buffer[BUFFER_SIZE];
//緩沖區頂
int char_top,bit_top;
//收縮哈夫曼樹參數
int max_count,shrink_factor;
//工作模式，true--編碼，false--解碼
bool mode;
//解碼的當前節點
Hbtree *current;
int remain;//當前字元剩餘的位數
unsigned char literal;//按位輸出的字元
bool finished;

public:

//解碼指定長度的字元串
int Decode(unsigned char *s,int len);
//解碼一個字元
int Decode(unsigned char c);
//列印哈夫曼樹
void PrintTree();
//編碼指定長度的字元串
int Encode(unsigned char *s,int len);
//編碼一個字元
int Encode(unsigned char c);
//清空緩沖區
int Flush();

//output指輸出函數，mode指工作模式，true--編碼，false--解碼
Huffman(Output *output,bool mode);

//析構函數
virtual ~Huffman();
};

#endif // !defined(AFX_HUFFMAN_H__B1F1A5A6_FB57_49B2_BB67_6D1764CC04AB__INCLUDED_)

================end of Huffman.h==================

祝你好運！

E. 求助：用java實現哈夫曼編碼壓縮與解壓縮演算法。

你好，由於內容比較多，先概述一下先。如圖所示，為我寫的一個壓縮軟體，原理是利用哈弗曼演算法實現的。我將資料整理好稍後就發到你郵箱，但在這里簡要說明一下代碼。

請看我的空間

http://hi..com/%D2%B6%BF%C6%C1%BC/blog

中的文章共5篇（太長了）

http://hi..com/%D2%B6%BF%C6%C1%BC/blog/item/93c35517bb528146f2de32fd.html

1.HuffmanTextEncoder類完成壓縮功能，可直接運行，壓縮測試用文本文件。

2.HuffmanTextDecoder類完成解壓縮功能，可直接運行，解壓縮壓縮後的文本文件。

3.BitReader,工具類，實現對BufferedInputStream的按位讀取。

4.BitWriter,工具類，實現按位寫入的功能。該類來自網路。

5.MinHeap<T>,模板工具類，實現了一個最小堆。生成Huffman樹時使用。

F. （哈夫曼壓縮）將01字元串轉換為二進制文件的方法

//你沒說什麼語言！如果需要其它的話，我再翻譯一下滑老！
//沒什麼效率，但是滿足需求了
importjava.io.*;

publicclassZ{
	
	publicstaticvoidmain(String[]args)throwsException{
		//System.out.println(decode(encode("00001000")));
		//System.out.println(decode(encode("11111000")));
		writeHuffman("011");
		System.out.println(read()Huffman());
	}
	
	//每次傳進去的字元串都是8個字元長度，剛好能夠表示一個byte
	publicstaticbyteencode(Strings){
		inta=0;
		for(inti=0;i<8;i++){
			charch=s.charAt(i);
			a=a<<信塌升1;
			if(ch=='1'){
				a=a|0x1;
			}
		}
		return(byte)a;
	}
	
	//上一步的逆操作
	publicstaticStringdecode(byteb){
		StringBuildersb=newStringBuilder();
		for(inti=0;i<8;i++){
			sb.append((b&(0x1<<(7-i)))>0?'1':'0');
		}
		returnsb.toString();
	}
	
	//再寫一下文件操作
	//假設你已經得到了通過huffman樹編碼的字元串，那麼就這樣寫寫入文件
	publicstaticvoidwriteHuffman(Strings)throwsException{
		//因為huffman編碼字元串不總是8個字元的倍數，那麼我們不足8時補0，並記錄我們到底補了幾個。
		//我們把補位數放在文件的第一個位元組
		int衫賣z=8-s.length()%8;
		if(z==8){
			z=0;
		}
		byte[]buffer=newbyte[1024];
		buffer[0]=(byte)z;
		intpos=1,nBytes=(int)(Math.ceil(s.length()/((double)8)));
		Filef=newFile("test.huffman");
		FileOutputStreamos=newFileOutputStream(f);
		for(inti=0;i<nBytes;i++){
			Stringss;
			if(s.length()>=(i+1)*8){
				ss=s.substring(i*8,(i+1)*8);
			}else{
				ss=s.substring(i*8);
				while(ss.length()<8){
					ss=newStringBuilder(ss).append('0').toString();
				}
			}
			buffer[pos]=encode(ss);
			pos++;
			if(pos==1024){
				os.write(buffer);
				pos=0;
			}
		}
		if(pos>0){
			os.write(buffer,0,pos);
		}
		os.close();
	}
	
	
	//我們把壓縮過的文本放在test.huffman裡面
	publicstaticStringreadHuffman()throwsException{
		Filef=newFile("test.huffman");
		FileInputStreamfs=newFileInputStream(f);
		byte[]buffer=newbyte[1024];
		intlen=0;
		StringBuildersb=newStringBuilder();
		bytez=(byte)fs.read();
		while((len=fs.read(buffer))!=-1){
			for(inti=0;i<len;i++){
				sb.append(decode(buffer[i]));
			}
		}
		fs.close();
		returnsb.substring(0,sb.length()-z);
	}
	
}

c++ 版本

#include"stdafx.h"
#include<stdio.h>
#include<iostream>
#include<string>
#include<cmath>

usingnamespacestd;

unsignedcharencode(constchar*s){
	inta=0;
	for(inti=0;i<8;i++){
		if(s[i]=='1'){
			a=a|(0x1<<(7-i));
		}
	}
	return(unsignedchar)a;
}

voiddecode(unsignedchara,char*buf){
	for(inti=0;i<8;i++){
		buf[i]=(((a>>(7-i))&0x1)!=0)?'1':'0';
	}
}

voidwriteHuffman(conststring&s){
	unsignedcharz=8-s.length()%8;
	if(z==8){
		z=0;
	}
	unsignedcharbuffer[1024];
	buffer[0]=z;

	intpos=1,nBytes=(int)(ceil(s.length()/((double)8)));
	constchar*ps=s.c_str();
	FILE*fp=fopen("test.huffman","wb");
	charextended[8];
	for(inti=0;i<nBytes;i++){
		constchar*p;
		if(s.length()>=(i+1)*8){
			p=ps+i*8;
		}
		else{
			char*pp=extended;
			for(intj=i*8;j<s.length();j++){
				*pp=s[j];
				pp++;
			}
			for(intj=0;j<z;j++){
				*pp='0';
				pp++;
			}
			p=extended;
		}
		buffer[pos]=encode(p);
		pos++;
		if(pos==1024){
			fwrite(buffer,sizeof(unsignedchar),1024,fp);
			pos=0;
		}
	}

	if(pos>0){
		fwrite(buffer,sizeof(unsignedchar),pos,fp);
	}

	fclose(fp);

}

string&readHuffman(){
	FILE*fp=fopen("test.huffman","rb");
	fseek(fp,0L,SEEK_END);
	size_tfileSize=ftell(fp);
	rewind(fp);

	unsignedcharbuffer[1024];
	fread(buffer,sizeof(unsignedchar),1,fp);
	unsignedcharz=buffer[0];

	size_tstringSize=(fileSize-1)*8;
	char*ptr=newchar[stringSize+1];
	char*optr=ptr;
	size_tlen;
	while((len=fread(buffer,sizeof(unsignedchar),1024,fp))!=0){
		for(inti=0;i<len;i++){
			decode(buffer[i],ptr);
			ptr=ptr+8;
		}
	}
	fclose(fp);
	ptr=ptr-z;
	*ptr='';
	string*str=newstring(optr);
	delete[]optr;
	return*str;
}

intmain(void)
{
	writeHuffman("00010");
	cout<<readHuffman()<<endl;
	getchar();
	return0;
}

G. 如何寫壓縮軟體，運用哈夫曼演算法實現

到文件壓縮大家很容易想到的就是rar,zip等我們常見的壓縮格式。然而，還有一種就是大家在學習數據結構最常見到的哈夫曼樹的數據結構，以前還不知道他又什麼用，其實他最大的用途就是用來做壓縮，也是一些rar,zip壓縮的祖先，稱為哈弗曼壓縮（什麼你不知道誰是哈弗曼，也不知道哈弗曼壓縮，不急等下介紹）。

隨著網路與多媒體技術的興起，人們需要存儲和傳輸的數據越來越多，數據量越來越大，以前帶寬有限的傳輸網路和容量有限的存儲介質難以滿足用戶的需求。

特別是聲音、圖像和視頻等媒體在人們的日常生活和工作中的地位日益突出，這個問題越發顯得嚴重和迫切。如今，數據壓縮技術早已是多媒體領域中的關鍵技術之一。

一、什麼是哈弗曼壓縮

Huffman(哈夫曼)演算法在上世紀五十年代初提出來了，它是一種無損壓縮方法，在壓縮過程中不會丟失信息熵，而且可以證明Huffman演算法在無損壓縮演算法中是最優的。Huffman原理簡單，實現起來也不困難，在現在的主流壓縮軟體得到了廣泛的應用。對應用程序、重要資料等絕對不允許信息丟失的壓縮場合，Huffman演算法是非常好的選擇。

二、怎麼實現哈弗曼壓縮

哈夫曼壓縮是個無損的壓縮演算法，一般用來壓縮文本和程序文件。哈夫曼壓縮屬於可變代碼長度演算法一族。意思是個體符號（例如，文本文件中的字元）用一個特定長度的位序列替代。因此，在文件中出現頻率高的符號，使用短的位序列，而那些很少出現的符號，則用較長的位序列。

故我們得了解幾個概念：

1、二叉樹：在計算機科學中，二叉樹是每個結點最多有兩個子樹的有序樹。通常子樹的根被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。2、哈夫曼編碼(Huffman Coding)：是一種編碼方式，哈夫曼編碼是可變字長編碼(VLC)的一種。uffman於1952年提出一種編碼方法，該方法完全依據字元出現概率來構造異字頭的平均長 度最短的碼字，有時稱之為最佳編碼，一般就叫作Huffman編碼。三、哈夫曼編碼生成步驟：

①掃描要壓縮的文件，對字元出現的頻率進行計算。

②把字元按出現的頻率進行排序，組成一個隊列。

③把出現頻率最低（權值）的兩個字元作為葉子節點，它們的權值之和為根節點組成一棵樹。

④把上面葉子節點的兩個字元從隊列中移除，並把它們組成的根節點加入到隊列。

⑤把隊列重新進行排序。重復步驟③④⑤直到隊列中只有一個節點為止。

⑥把這棵樹上的根節點定義為0（可自行定義0或1）左邊為0，右邊為1。這樣就可以得到每個葉子節點的哈夫曼編碼了。

既如 (a)、(b)、(c)、(d)幾個圖，就可以將離散型的數據轉化為樹型的了。

如果假設樹的左邊用0表示右邊用1表示，則每一個數可以用一個01串表示出來。

則可以得到對應的編碼如下：
1-->110
2-->111
3-->10
4-->0
每一個01串，既為每一個數字的哈弗曼編碼。
為什麼能壓縮：
壓縮的時候當我們遇到了文本中的1、2、3、4幾個字元的時候，我們不用原來的存儲，而是轉化為用它們的01串來存儲不久是能減小了空間佔用了嗎。（什麼01串不是比原來的字元還多了嗎？怎麼減少？）大家應該知道的，計算機中我們存儲一個int型數據的時候一般式佔用了2^32-1個01位，因為計算機中所有的數據都是最後轉化為二進制位去存儲的。所以，想想我們的編碼不就是只含有0和1嘛，因此我們就直接將編碼按照計算機的存儲規則用位的方法寫入進去就能實現壓縮了。
比如：
1這個數字，用整數寫進計算機硬碟去存儲，佔用了2^32-1個二進制位
而如果用它的哈弗曼編碼去存儲，只有110三個二進制位。
效果顯而易見。

H. 哈夫曼編碼的壓縮實現

壓縮代碼非常簡單，首先用ASCII值初始化511個哈夫曼節點：
CHuffmanNode nodes[511];
for(int nCount = 0; nCount < 256; nCount++)
nodes[nCount].byAscii = nCount;
其次，計算在輸入緩沖區數據中，每個ASCII碼出現的頻率：
for(nCount = 0; nCount < nSrcLen; nCount++)
nodes[pSrc[nCount]].nFrequency++;
然後，根據頻率進行排序：
qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare);
哈夫曼樹，獲取每個ASCII碼對應的位序列：
int nNodeCount = GetHuffmanTree(nodes); 構造哈夫曼樹非常簡單，將所有的節點放到一個隊列中，用一個節點替換兩個頻率最低的節點，新節點的頻率就是這兩個節點的頻率之和。這樣，新節點就是兩個被替換節點的父節點了。如此循環，直到隊列中只剩一個節點（樹根）。
// parent node
pNode = &nodes[nParentNode++];
// pop first child
pNode->pLeft = PopNode(pNodes, nBackNode--, false);
// pop second child
pNode->pRight = PopNode(pNodes, nBackNode--, true);
// adjust parent of the two poped nodes
pNode->pLeft->pParent = pNode->pRight->pParent = pNode;
// adjust parent frequency
pNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency; 有一個好的訣竅來避免使用任何隊列組件。ASCII碼只有256個，但實際分配了511個(CHuffmanNode nodes[511])，前255個記錄ASCII碼，而用後255個記錄哈夫曼樹中的父節點。並且在構造樹的時候只使用一個指針數組(ChuffmanNode *pNodes[256])來指向這些節點。同樣使用兩個變數來操作隊列索引(int nParentNode = nNodeCount;nBackNode = nNodeCount –1)。
接著，壓縮的最後一步是將每個ASCII編碼寫入輸出緩沖區中：
int nDesIndex = 0;
// loop to write codes
for(nCount = 0; nCount < nSrcLen; nCount++)
{
*(DWORD*)(pDesPtr+(nDesIndex>>3)) |=
nodes[pSrc[nCount]].dwCode << (nDesIndex&7);
nDesIndex += nodes[pSrc[nCount]].nCodeLength;
}
(nDesIndex>>3): >>3 以8位為界限右移後到達右邊位元組的前面
(nDesIndex&7): &7 得到最高位.
此外，在壓縮緩沖區中，必須保存哈夫曼樹的節點以及位序列，這樣才能在解壓縮時重新構造哈夫曼樹（只需保存ASCII值和對應的位序列）。 解壓縮比構造哈夫曼樹要簡單的多，將輸入緩沖區中的每個編碼用對應的ASCII碼逐個替換就可以了。只要記住，這里的輸入緩沖區是一個包含每個ASCII值的編碼的位流。因此，為了用ASCII值替換編碼，我們必須用位流搜索哈夫曼樹，直到發現一個葉節點，然後將它的ASCII值添加到輸出緩沖區中：
int nDesIndex = 0;
DWORD nCode;
while(nDesIndex < nDesLen)
{
nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7);
pNode = pRoot;
while(pNode->pLeft)
{
pNode = (nCode&1) ? pNode->pRight : pNode->pLeft;
nCode >>= 1;
nSrcIndex++;
}
pDes[nDesIndex++] = pNode->byAscii;
}