霍夫曼編輯壓縮信源碼PPT

『壹』 已知6個符號的信源A={a1，a2，……a6}，若其概率分布為P={0.30, 0.25, 0.25, 0.10}1、寫出Huffman編碼（要

1、寫出Huffman編碼

a6和a5組成n1節點，權重0.14

a4和n1組成n2節點，權重0.26

a3和a2組成n3節點，權重0.42

n2和a1組成n4節點，權重0.58

n3和n4組成n5節點，權重1，即為根節點

Huffman編碼：

a1: 11

a2: 01

a3: 00

a4: 100

a5: 1011

a6: 1010

2、Huffman編碼的平均編碼長度

2 * (0.32 + 0.25 + 0.17) + 3 * 0.12 + 4 * (0.09 + 0.05)

= 1.48 + 0.36 + 0.56

= 2.4

3、壓縮比

如果不用Huffman編碼，則6個符號需要3個二進制符號，編碼長度是3，所以壓縮比是3 / 2.4 =1.25

擴展內容

哈夫曼編碼(Huffman Coding)原理

設某信源產生有五種符號u1、u2、u3、u4和u5，對應概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。首先，將符號按照概率由大到小排隊，如圖所示。

編碼時，從最小概率的兩個符號開始，可選其中一個支路為0，另一支路為1。這里，我們選上支路為0，下支路為1。再將已編碼的兩支路的概率合並，並重新排隊。多次重復使用上述方法直至合並概率歸一時為止。

赫夫曼碼的碼字（各符號的代碼）是異前置碼字，即任一碼字不會是另一碼字的前面部分，這使各碼字可以連在一起傳送，中間不需另加隔離符號，只要傳送時不出錯，收端仍可分離各個碼字，不致混淆。

長遊程的主碼和基碼均用赫夫曼規則進行編碼，這稱為修正赫夫曼碼，其結果有表可查。該方法已廣泛應用於文件傳真機中。

『貳』 霍夫曼編碼

霍夫曼(Huffman)在1952年提出
是一種從下到上的編碼方法，即從葉子逐步往上生成編碼樹
編碼演算法實際上是一個構造霍夫曼樹的過程（根據資料出現頻率的多寡來建造的樹，霍夫曼樹的樹葉節點用以儲存資料元素 ( Data Element ) ，若該元素出現的頻率越高，則由該元素至樹根所經過的節點數越少）
(1) 對資料中出現過的每一元素各自產生一外部節點，並賦予外部節點該元素之出現頻率。
(2) 令 L 是所有外部節點所成之集合。
(3) 產生一個新節點 N 。令 N 為 L1 和 L2 的父節點，L1 和 L2 是 L 中出現頻率最低的兩個節點。令 N 節點的出現頻率等於 L1 和 L2 的出現頻率總和。由 L 中刪除 L1 和 L2 ，並將 N 加入 L 中。
(4) 重復步驟 (3) 的動作，直到 | L | = 1 。
(5) 標示樹中各節點的左子樹鏈結為 0 ，右子樹鏈結為 1 。（不一定，只要一枝為0一枝為1）
是碼長可變的編碼
霍夫曼演算法和香農范諾演算法的編碼都不需要額外的同步碼（解釋）
霍夫曼樹是最小二叉樹，編碼效率比香農范諾高
霍夫曼編碼對錯誤敏感，錯一位，可能導致後面的解碼都是錯誤的，而且計算機也無法糾錯，我們稱為錯誤傳播
霍夫曼編碼是變長編碼，整個編碼結果是一個整體，無法隨意解壓縮其中的某一個部分

『叄』 Huffman(霍夫曼)編碼是如何運算的

霍夫曼（Huffman）編碼原理
霍夫曼（Huffman）編碼是1952年為文本文件而建立，是一種統計編碼。屬於無損壓縮編碼。
霍夫曼編碼的碼長是變化的，對於出現頻率高的信息，編碼的長度較短；而對於出現頻率低的信息，編碼長度較長。這樣，處理全部信息的總碼長一定小於實際信息的符號長度。

步驟進行：
l）將信號源的符號按照出現概率遞減的順序排列。
2）將兩個最小出現概率進行合並相加，得到的結果作為新符號的出現概率。
3）重復進行步驟1和2直到概率相加的結果等於1為止。
4）在合並運算時，概率大的符號用編碼0表示，概率小的符號用編碼1表示。
5）記錄下概率為1處到當前信號源符號之間的0，l序列，從而得到每個符號的編碼。

例：
設信號源為 s＝｛s1, s2, s3, s4, s5｝
對應的概率為p＝｛0.25，0.22，0.20, 0.18，0.15｝。

根據字元出現的概率來構造平均長度最短的異字頭碼字。
霍未曼編碼通常採用兩次掃描的辦法，第一次掃描得到統計結果，第二次掃描進行編碼。

霍夫曼編碼具有一些明顯的特點：
1) 編出來的碼都是異字頭碼，保證了碼的唯一可譯性。
2) 由於編碼長度可變。因此解碼時間較長，使得霍夫曼編碼的壓縮與還原相當費時。
3) 編碼長度不統一，硬體實現有難度。
4) 對不同信號源的編碼效率不同，當信號源的符號概率為2的負冪次方時，達到100％的編碼效率；若信號源符號的概率相等，則編碼效率最低。
5) 由於"0"與"1"的指定是任意的，故由上述過程編出的最佳碼不是唯一的，但其平均碼長是一樣的，故不影響編碼效率與數據壓縮性能。

『肆』 利用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==================

祝你好運！

『伍』 利用huffman編碼對文件進行壓縮，不同文件類型壓縮率有差別的原因

怎麼沒人回答呢 我來回答吧 我想從壓縮文件的原理能得到你這個問題的答案（有點長，請耐心看，絕對長知識）： 壓縮文件的運行原理 如果您從互聯網上下載了許多程序和文件，可能會遇到很多ZIP文件。這種壓縮機制是一種很方便的發明，尤其是對網路用戶，因為它可以減小文件中的比特和位元組總數，使文件能夠通過較慢的互聯網連接實現更快傳輸，此外還可以減少文件的磁碟佔用空間。在下載了文件後，計算機可使用WinZip或Stuffit這樣的程序來展開文件，將其復原到原始大小。如果一切正常，展開的文件與壓縮前的原始文件將完全相同。
乍一聽好像很神秘：您是怎樣減少比特和位元組的數量並將它們原封不動地還原回去的呢？等一切水落石出之後，您會發現這個過程背後的基本理念其實非常簡單明了。在本文中，我們將討論這種通過簡單壓縮來明顯減小文件的方法。
大多數計算機文件類型都包含相當多的冗餘內容——它們會反復列出一些相同的信息。文件壓縮程序就是要消除這種冗餘現象。與反復列出某一塊信息不同，文件壓縮程序只列出該信息一次，然後當它在原始程序中出現時再重新引用它。
以我們熟悉的信息類型——單詞——為例子。
肯尼迪（John F. Kennedy）在1961年的就職演說中曾說過下面這段著名的話：
Ask not what your country can do for you——ask what you can do for your country.（不要問國家能為你做些什麼，而應該問自己能為國家做些什麼。）
這段話有17個單詞，包含61個字母、16個空格、1個破折號和1個句點。如果每個字母、空格或標點都佔用1個內存單元，那麼文件的總大小為79個單元。為了減小文件的大小，我們需要找出冗餘的部分。
我們立刻發現：
如果忽略大小寫字母間的區別，這個句子幾乎有一半是冗餘的。九個單詞（ask、not、what、your、country、can、do、for、you）幾乎提供了組成整句話所需的所有東西。為了構造出另一半句子，我們只需要拿出前半段句子中的單詞，然後加上空格和標點就行了。
大多數壓縮程序使用基於自適應字典的LZ演算法來縮小文件。「LZ」指的是此演算法的發明者Lempel和Ziv，「字典」指的是對數據塊進行歸類的方法。
排列字典的機制有很多種，它也可以像編號列表那樣簡單。在我們檢查肯尼迪這句著名講話時，可以挑出重復的單詞，並將它們放到編號索引中。然後，我們直接寫入編號而不是寫入整個單詞。
因此，如果我們的字典是：
ask
what
your
country
can
do
for
you
我們的句子現在就應該是這樣的：
1 not 2 3 4 5 6 7 8-- 1 2 8 5 6 7 3 4
如果您了解這種機制，那麼只需使用該字典和編號模式即可輕松重新構造出原始句子。這就是在展開某個下載文件時，計算機中的解壓縮程序所做的工作。你可能還遇到過能夠自行解壓縮的壓縮文件。若要創建這種文件，編程人員需要在被壓縮的文件中設置一個簡單的解壓縮程序。在下載完畢後，它可以自動重新構造出原始文件。
但是使用這種機制究竟能夠節省多少空間呢？「1 not 2 3 4 5 6 7 8——1 2 8 5 6 7 3 4」當然短於「Ask not what your country can do for you-- ask what you can do for your country.」，但應注意的是，我們需要隨文件一起保存這個字典。
在實際壓縮方案中，計算出各種文件需求是一個相當復雜的過程。讓我們回過頭考慮一下上面的例子。每個字元和空格都佔用1個內存單元，整個原句要佔用79個單元。壓縮後的句子（包括空格）佔用了37個單元，而字典（單詞和編號）也佔用了37個單元。也就是說，文件的大小為74個單元，因此我們並沒有把文件大小減少很多。
但這只是一個句子的情況！可以想像的是，如果用該壓縮程序處理完肯尼迪講話的其餘部分，我們會發現這些單詞以及其他單詞重復了更多次。而且，正如下一節所言，為了得到盡可能高的組織效率，可以對字典進行重寫。
在上一個的例子中，我們挑出了所有重復的單詞並將它們放在一個字典中。對於我們來說，這是最顯而易見的字典編寫方法。但是壓縮程序卻不這樣認為：它對單詞沒有概念——它只會尋找各個模式。為了盡可能減小文件的大小，它會仔細挑選出最優模式。
如果從這個角度處理該句子，我們最終會得到一個完全不同的字典。
如果壓縮程序掃描肯尼迪的這句話，它遇到的第一個冗餘部分只有幾個字母長。在ask not what your中，出現了一個重復的模式，即字母t後面跟一個空格——在not和what中。如果壓縮程序將此模式寫入字典，則每次出現「t」後面跟一個空格的情況時，它會寫入一個「1」。但是在這個短句中，此模式的出現次數不夠多，不足以將其保留為字典中的一個條目，因此程序最終會覆蓋它。
程序接下來注意到的內容是ou，在your和country中都出現了它。如果這是一篇較長的文檔，將此模式寫入字典會節省大量空間——在英語中ou是一個十分常見的字母組合。但是在壓縮程序看完整個句子後，它立即發現了一個更好的字典條目選擇：不僅ou發生了重復，而且your和country整個單詞都發生了重復，並且它們實際上是作為一個短語your country一起發生重復的。在本例中，程序會用your country條目覆蓋掉字典中的ou條目。
短語can do for也發生了重復，一次後面跟著your，另一次跟著you，因此我們又發現can do for you也是一種重復模式。這樣，我們可以用一個數字來代替15個字元（包含空格），而your country只允許我們用一個數字代替13個字元（包含空格），所以程序會用r country條目覆蓋your country條目，然後再寫入一個單獨的can do for you條目。程序通過這種方式繼續工作，挑出所有重復的信息，然後計算應該將哪一種模式寫入字典。基於自適應字典的LZ演算法中的「自適應」部分指的就是這種重寫字典的能力。程序執行此工作的過程實際上非常復雜。
無論使用什麼方法，這種深入搜索機制都能比僅僅挑出單詞這種方法更有效率地對文件進行壓縮。如果使用我們上面提取出的模式，然後用「__」代替空格，最終將得到下面這個更大的字典：
ask__
what__­
you
r__country
__can__do__for__you
而句子則較短：
「1not__2345__--__12354」
句子現在佔用18個內存單元，字典佔用41個單元。所以，我們將文件總大小從79個單元壓縮到了59個單元！這僅僅是壓縮句子的一種方法，而且不一定是最高效的方法。（看看您能找到更好的方法嗎！）
那麼這種機制到底有多好呢？文件壓縮率取決於多種因素，包括文件類型、文件大小和壓縮方案。
在世界上的大多數語言中，某些字母和單詞經常以相同的模式一起出現。正是由於這種高冗餘性，而導致文本文件的壓縮率會很高。通常大小合適的文本文件的壓縮率可以達到50%或更高。大多數編程語言的冗餘度也很高，因為它們的命令相對較少，並且命令經常採用一種設定的模式。對於包含大量不重復信息的文件（例如圖像或MP3文件），則不能使用這種機制來獲得很高的壓縮率，因為它們不包含重復多次的模式。
如果文件有大量重復模式，那麼壓縮率通常會隨著文件大小的增加而增加。從我們的例子中就可以看出這一點——如果我們摘錄的肯尼迪講話再長一些，您會發現又多次出現了我們字典中的模式，因此能夠通過每個字典條目節省更多的文件空間。此外，對於更大的文件，還可能出現具有更大普遍性的模式，從而能夠創建出效率更高的字典。
此外，文件壓縮效率還取決於壓縮程序使用的具體演算法。有些程序能夠在某些類型的文件中更好地尋找到模式，因此能更有效地壓縮這些類型的文件。其他一些壓縮程序在字典中又使用了字典，這使它們在壓縮大文件時表現很好，但是在壓縮較小的文件時效率不高。盡管這一類的所有壓縮程序都基於同一個基本理念，但是它們的執行方式卻各不相同。程序開發人員始終在嘗試建立更好的壓縮機制。
有損壓縮和無損壓縮
我們在上文中討論的壓縮類型稱為無損壓縮，因為您重新創建的文件與原始文件完全相同。所有無損壓縮都基於這樣一種理念：將文件變為「較小」的形式以利於傳輸或存儲，並在另一方收到它後復原以便重新使用它。
有損壓縮則與此大不相同。這些程序直接去除「不必要」的信息，對文件進行剪裁以使它變得更小。這種類型的壓縮大量應用於減小點陣圖圖像的文件大小，因為點陣圖圖像的體積通常非常龐大。為了了解有損壓縮的工作原理，讓我們看看你的計算機如何對一張掃描的照片進行壓縮。
對於此類文件，無損壓縮程序的壓縮率通常不高。盡管圖片的大部分看起來都是相同的——例如，整個天空都是藍色的——但是大部分像素之間都存在微小的差異。為了使圖片變得更小同時不降低其解析度，您必須更改某些像素的顏色值。如果圖片中包含大量的藍色天空，程序會挑選一種能夠用於所有像素的藍色。然後，程序重寫該文件，所有天空像素的值都使用此信息。如果壓縮方案選擇得當，您不會注意到任何變化，但是文件大小會顯著減小。
當然，對於有損壓縮，在文件壓縮後您無法將其復原成原始文件的樣子。您必須接受壓縮程序對原始文件的重新解釋。因此，如果需要完全重現原來的內容（例如軟體應用程序、資料庫和總統就職演說），則不應該使用這種壓縮形式。

『陸』 C語言編寫huffman編碼（資訊理論基礎教程里的上級作業）

#includestdio.h> #includestdlib.h> #includestring.h> #includemalloc.h> #define N 20
#define M 2*N-1
#define Min 1000 /*最小值*/ typedef struct
{
char ch; /*權值對應的字元*/ int weight; /*權值*/ int parent; /*雙親位置*/ int Lchild; /*左孩子位置*/ int Rchild; /*右孩子位置*/ }HTNode,Huffmantree[M+1];
char hc[N+1][N+1];
void OutputHuffmancode(Huffmantree ht, int n); void CrtHuffmancode(Huffmantree ht, int n); void OutputHuffmantree(Huffmantree ht,int n); void select(Huffmantree ht,int a,int *s1,int *s2) {
int i;
int c1=Min; int c2;
for(i=1;i=a;i++) {
if (ht.parent==0&&ht.weightc1) {
*s1=i; c1=ht.weight; } }
c2=Min;
for(i=1;i=a;i++) {
if (ht.parent==0&&(*s1!=i)&&c2>ht.weight) {
*s2=i; c2=ht.weight; }
} }
void CrtHuffmantree(Huffmantree ht,int w[],char elem[],int n)

{
int i; int m; int s1,s2; m=2*n-1;
ht=(HTNode *)malloc((m)*sizeof(HTNode));
for(i=1;i=n;i++) {
ht.ch=elem[i-1]; ht.weight=w[i-1]; ht.parent=0; ht.Lchild=0; ht.Rchild=0; }
for(i=n+1;i=m;i++) {
ht.ch='\0'; ht.weight=0; ht.parent=0; ht.Lchild=0; ht.Rchild=0; }
/*初始化完畢*/
for(i=n+1;i=m;i++) {
select( ht,i-1,&s1,&s2); /*返回最小值和次小值的位置*/ ht.weight=ht[s1].weight+ht[s2].weight; ht[s1].parent=i;
ht[s2].parent=i; ht.Lchild=s1;
ht.Rchild=s2;/*建立樹完畢*/ }
OutputHuffmantree( ht,m);
printf("now begin crthuffman code\n"); CrtHuffmancode( ht, n);
printf("crthuffman code end\n"); OutputHuffmancode(ht, n); }
void OutputHuffmantree(Huffmantree ht,int n)
{
int i;
printf("\nnumber---weight---parent---Lchild---Rchild---huffman char\n \n");

for(i=1;i=n;i++)
printf("%d\t%d\t%d\t%d\t%d\t%c\n",i,ht.weight,ht.parent,ht.Lchild,ht.Rchild,ht.ch); }
void CrtHuffmancode(Huffmantree ht, int n) /*建立編碼*/ {
int i,c,p; int start; char *cd;
cd=(char *) malloc((n+1)*sizeof(char)); memset(cd,'\0',sizeof(cd));
for(i=1;i=n;i++) {
start=n;
cd[start]='\0';
c=i;
p=ht.parent; while(p!=0) {
start--;
if(ht[p].Lchild==c) cd[start]='0'; else
cd[start]='1';
c=p;
p=ht[p].parent; }
//cd[start] = '\0';
printf("cd is %s\n start is %d\n", cd+start, start);
sprintf(hc, "%s", cd+start); /*將已存在的編碼復制到code中*/ } free(cd); }
void OutputHuffmancode(Huffmantree ht,int n) {
int i;
printf("\nweight_char---weight---huffmancode\n \n"); for(i=1;i=n;i++)
printf(" %c\t%4d\t%s\n",ht.ch,ht.weight,hc); }
int main()

{
int n = 6;/*記錄了權值個數*/ Huffmantree hfm;
int w[] = {45,13,12,16,9,5}; char elem[] = {'a','b','c','d','e','f'};
CrtHuffmantree( hfm, w,elem, n); return 0; }

『柒』 霍夫曼 解壓縮

哈夫曼編碼(Huffman Coding)是一種編碼方式，以哈夫曼樹—即最優二叉樹，帶權路徑長度最小的二叉樹，經常應用於數據壓縮。 在計算機信息處理中，「哈夫曼編碼」是一種一致性編碼法（又稱"熵編碼法"），用於數據的無損耗壓縮。這一術語是指使用一張特殊的編碼表將源字元（例如某文件中的一個符號）進行編碼。這張編碼表的特殊之處在於，它是根據每一個源字元出現的估算概率而建立起來的（出現概率高的字元使用較短的編碼，反之出現概率低的則使用較長的編碼，這便使編碼之後的字元串的平均期望長度降低，從而達到無損壓縮數據的目的）。這種方法是由David.A.Huffman發展起來的。 例如，在英文中，e的出現概率很高，而z的出現概率則最低。當利用哈夫曼編碼對一篇英文進行壓縮時，e極有可能用一個位(bit)來表示，而z則可能花去25個位（不是26）。用普通的表示方法時，每個英文字母均佔用一個位元組（byte），即8個位。二者相比，e使用了一般編碼的1/8的長度，z則使用了3倍多。倘若我們能實現對於英文中各個字母出現概率的較准確的估算，就可以大幅度提高無損壓縮的比例。

本文描述在網上能夠找到的最簡單，最快速的哈夫曼編碼。本方法不使用任何擴展動態庫，比如STL或者組件。只使用簡單的C函數，比如：memset，memmove，qsort，malloc，realloc和memcpy。
因此，大家都會發現，理解甚至修改這個編碼都是很容易的。

背景
哈夫曼壓縮是個無損的壓縮演算法，一般用來壓縮文本和程序文件。哈夫曼壓縮屬於可變代碼長度演算法一族。意思是個體符號（例如，文本文件中的字元）用一個特定長度的位序列替代。因此，在文件中出現頻率高的符號，使用短的位序列，而那些很少出現的符號，則用較長的位序列。
編碼使用
我用簡單的C函數寫這個編碼是為了讓它在任何地方使用都會比較方便。你可以將他們放到類中，或者直接使用這個函數。並且我使用了簡單的格式，僅僅輸入輸出緩沖區，而不象其它文章中那樣，輸入輸出文件。
bool CompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen);
bool DecompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen);
要點說明
速度
為了讓它(huffman.cpp)快速運行，我花了很長時間。同時，我沒有使用任何動態庫，比如STL或者MFC。它壓縮1M數據少於100ms（P3處理器，主頻1G）。
壓縮
壓縮代碼非常簡單，首先用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;
}

『捌』 霍夫曼演算法

霍夫曼演算法的步驟是這樣的：

·從各個節點中找出最小的兩個節點，給它們建一個父節點，值為這兩個節點之和。
·然後從節點序列中去除這兩個節點，加入它們的父節點到序列中。

重復上面兩個步驟，直到節點序列中只剩下唯一一個節點。這時一棵最優二叉樹就已經建成了，它的根就是剩下的這個節點。

仍以上面的例子來看霍夫曼樹的建立過程。
最初的節點序列是這樣的：
a(6) b(15) c(2) d(9) e(1)

把最小的c和e結合起來
| (3)
a(6) b(15) d(9) +------+------+
| |
c e

不斷重復，最終得到的樹是這樣的：

根
|
+-----33-----+
| |
15 +----18----+
| |
9 +------9-----+
| |
6 +--3--+
| |
2 1

這時各個字元的編碼長度和前面我們說過的方法得到的編碼長度是相同的，因而文件的總長度也是相同的： 3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63

考察霍夫曼樹的建立過程中的每一步的節點序列的變化：

6 15 2 9 1
6 15 9 3
15 9 9
15 18
33

下面我們用逆推法來證明對於各種不同的節點序列，用霍夫曼演算法建立起來的樹總是一棵最優二叉樹：

對霍夫曼樹的建立過程運用逆推法：
當這個過程中的節點序列只有兩個節點時（比如前例中的15和18），肯定是一棵最優二叉樹，一個編碼為0，另一個編碼為1，無法再進一步優化。
然後往前步進，節點序列中不斷地減少一個節點，增加兩個節點，在步進過程中將始終保持是一棵最優二叉樹，這是因為：
1.按照霍夫曼樹的建立過程，新增的兩個節點是當前節點序列中最小的兩個，其他的任何兩個節點的父節點都大於（或等於）這兩個節點的父節點，只要前一步是最優二叉樹，其他的任何兩個節點的父節點就一定都處在它們的父節點的上層或同層，所以這兩個節點一定處在當前二叉樹的最低一層。
2.這兩個新增的節點是最小的，所以無法和其他上層節點對換。符合我們前面說的最優二叉樹的第一個條件。
3.只要前一步是最優二叉樹，由於這兩個新增的節點是最小的，即使同層有其他節點，也無法和同層其他節點重新結合，產生比它們的父節點更小的上層節點來和同層的其他節點對換。它們的父節點小於其他節點的父節點，它們又小於其他所有節點，只要前一步符合最優二叉樹的第二個條件，到這一步仍將符合。

這樣一步步逆推下去，在這個過程中霍夫曼樹每一步都始終保持著是一棵最優二叉樹。

由於每一步都從節點序列中刪除兩個節點，新增一個節點，霍夫曼樹的建立過程共需 (原始節點數 - 1) 步，所以霍夫曼演算法不失為一種精巧的編碼式壓縮演算法。

附：對於 huffman 樹，《計算機程序設計藝術》中有完全不同的證明，大意是這樣的：
1．二叉編碼樹的內部節點（非葉子節點）數等於外部節點（葉子節點）數減1。
2．二叉編碼樹的外部節點的加權路徑長度（值乘以路徑長度）之和，等於所有內部節點值之和。（這兩條都可以通過對節點數運用數學歸納法來證明，留給大家做練習。）
3．對 huffman 樹的建立過程運用逆推，當只有一個內部節點時，肯定是一棵最優二叉樹。
4．往前步進，新增兩個最小的外部節點，它們結合在一起產生一個新的內部節點，當且僅當原先的內部節點集合是極小化的，加入這個新的內部節點後仍是極小化的。（因為最小的兩個節點結合在一起，並處於最低層，相對於它們分別和其他同層或上層節點結合在一起，至少不會增加加權路徑長度。）
5．隨著內部節點數逐個增加，內部節點集合總維持極小化。

2．實現部分
如果世界上從沒有一個壓縮程序，我們看了前面的壓縮原理，將有信心一定能作出一個可以壓縮大多數格式、內容的數據的程序，當我們著手要做這樣一個程序的時候，會發現有很多的難題需要我們去一個個解決，下面將逐個描述這些難題，並詳細分析 zip 演算法是如何解決這些難題的，其中很多問題帶有普遍意義，比如查找匹配，比如數組排序等等，這些都是說不盡的話題，讓我們深入其中，做一番思考。