0023算法筆記-【貪心算法】哈夫曼編碼問題

0023算法筆記——【貪心算法】哈夫曼編碼問題

1、問題描述

哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%～90%之間。哈夫曼編碼\o"算法與數(shù)據(jù)結(jié)構(gòu)知識(shí)庫"算法用字符在文件中出現(xiàn)的頻率表來建立一個(gè)用0，1串表示各字符的最優(yōu)表示方式。一個(gè)包含100,000個(gè)字符的文件，各字符出現(xiàn)頻率不同，如下表所示。

有多種方式表示文件中的信息，若用0,1碼表示字符的方法，即每個(gè)字符用唯一的一個(gè)0,1串表示。若采用定長編碼表示，則需要3位表示一個(gè)字符，整個(gè)文件編碼需要300,000位；若采用變長編碼表示，給頻率高的字符較短的編碼；頻率低的字符較長的編碼，達(dá)到整體編碼減少的目的，則整個(gè)文件編碼需要（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000位，由此可見，變長碼比定長碼方案好，總碼長減小約25%。

前綴碼：對(duì)每一個(gè)字符規(guī)定一個(gè)0,1串作為其代碼，并要求任一字符的代碼都不是其他字符代碼的前綴。這種編碼稱為前綴碼。編碼的前綴性質(zhì)可以使譯碼方法非常簡單；例如001011101可以唯一的分解為0,0,101,1101，因而其譯碼為aabe。

譯碼過程需要方便的取出編碼的前綴，因此需要表示前綴碼的合適的\o"算法與數(shù)據(jù)結(jié)構(gòu)知識(shí)庫"數(shù)據(jù)結(jié)構(gòu)。為此，可以用二叉樹作為前綴碼的數(shù)據(jù)結(jié)構(gòu)：樹葉表示給定字符；從樹根到樹葉的路徑當(dāng)作該字符的前綴碼；代碼中每一位的0或1分別作為指示某節(jié)點(diǎn)到左兒子或右兒子的“路標(biāo)”。

從上圖可以看出，表示最優(yōu)前綴碼的二叉樹總是一棵完全二叉樹，即樹中任意節(jié)點(diǎn)都有2個(gè)兒子。圖a表示定長編碼方案不是最優(yōu)的，其編碼的二叉樹不是一棵完全二叉樹。在一般情況下，若C是編碼字符集，表示其最優(yōu)前綴碼的二叉樹中恰有|C|個(gè)葉子。每個(gè)葉子對(duì)應(yīng)于字符集中的一個(gè)字符，該二叉樹有|C|-1個(gè)內(nèi)部節(jié)點(diǎn)。

給定編碼字符集C及頻率分布f,即C中任一字符c以頻率f(c)在數(shù)據(jù)文件中出現(xiàn)。C的一個(gè)前綴碼編碼方案對(duì)應(yīng)于一棵二叉樹T。字符c在樹T中的深度記為dT(c)。dT(c)也是字符c的前綴碼長。則平均

具體代碼實(shí)現(xiàn)如下：

(1)4d4.cpp，程序主文件[cpp]

\o"viewplain"viewplain

\o"copy"copy//4d4

貪心算法

哈夫曼算法

#include

"stdafx.h"

#include

"BinaryTree.h"

#include

"MinHeap.h"

#include

<iostream>

using

namespace

std;

const

int

N

=

6;

template<class

Type>

class

Huffman;

template<class

Type>

BinaryTree<int>

HuffmanTree(Type

f[],int

n);

template<class

Type>

class

Huffman

{

friend

BinaryTree<int>

HuffmanTree(Type[],int);

public:

operator

Type()

const

{

return

weight;

}

//private:

BinaryTree<int>

tree;

Type

weight;

};

int

main()

{

char

c[]

=

{'0','a','b','c','d','e','f'};

int

f[]

=

{0,45,13,12,16,9,5};//下標(biāo)從1開始

BinaryTree<int>

t

=

HuffmanTree(f,N);

cout<<"各字符出現(xiàn)的對(duì)應(yīng)頻率分別為："<<endl;

for(int

i=1;

i<=N;

i++)

{

cout<<c[i]<<":"<<f[i]<<"

";

}

cout<<endl;

cout<<"生成二叉樹的前序遍歷結(jié)果為："<<endl;

t.Pre_Order();

cout<<endl;

cout<<"生成二叉樹的中序遍歷結(jié)果為："<<endl;

t.In_Order();

cout<<endl;

t.DestroyTree();

return

0;

}

template<class

Type>

BinaryTree<int>

HuffmanTree(Type

f[],int

n)

{

//生成單節(jié)點(diǎn)樹

Huffman<Type>

*w

=

new

Huffman<Type>[n+1];

BinaryTree<int>

z,zero;

for(int

i=1;

i<=n;

i++)

{

z.MakeTree(i,zero,zero);

w[i].weight

=

f[i];

w[i].tree

=

z;

}

//建優(yōu)先隊(duì)列

MinHeap<Huffman<Type>>

Q(n);

for(int

i=1;

i<=n;

i++)

Q.Insert(w[i]);

//反復(fù)合并最小頻率樹

Huffman<Type>

x,y;

for(int

i=1;

i<n;

i++)

{

x

=

Q.RemoveMin();

y

=

Q.RemoveMin();

z.MakeTree(0,x.tree,y.tree);

x.weight

+=

y.weight;

x.tree

=

z;

Q.Insert(x);

}

x

=

Q.RemoveMin();

delete[]

w;

return

x.tree;

}

(2)BinaryTree.h二叉樹實(shí)現(xiàn)[cpp]

\o"viewplain"viewplain

\o"copy"copy#include<iostream>

using

namespace

std;

template<class

T>

struct

BTNode

{

T

data;

BTNode<T>

*lChild,*rChild;

BTNode()

{

lChild=rChild=NULL;

}

BTNode(const

T

&val,BTNode<T>

*Childl=NULL,BTNode<T>

*Childr=NULL)

{

data=val;

lChild=Childl;

rChild=Childr;

}

BTNode<T>*

CopyTree()

{

BTNode<T>

*nl,*nr,*nn;

if(&data==NULL)

return

NULL;

nl=lChild->CopyTree();

nr=rChild->CopyTree();

nn=new

BTNode<T>(data,nl,nr);

return

nn;

}

};

template<class

T>

class

BinaryTree

{

public:

BTNode<T>

*root;

BinaryTree();

~BinaryTree();

void

Pre_Order();

void

In_Order();

void

Post_Order();

int

TreeHeight()const;

int

TreeNodeCount()const;

void

DestroyTree();

void

MakeTree(T

pData,BinaryTree<T>

leftTree,BinaryTree<T>

rightTree);

void

Change(BTNode<T>

*r);

private:

void

Destroy(BTNode<T>

*&r);

void

PreOrder(BTNode<T>

*r);

void

InOrder(BTNode<T>

*r);

void

PostOrder(BTNode<T>

*r);

int

Height(const

BTNode<T>

*r)const;

int

NodeCount(const

BTNode<T>

*r)const;

};

template<class

T>

BinaryTree<T>::BinaryTree()

{

root=NULL;

}

template<class

T>

BinaryTree<T>::~BinaryTree()

{

}

template<class

T>

void

BinaryTree<T>::Pre_Order()

{

PreOrder(root);

}

template<class

T>

void

BinaryTree<T>::In_Order()

{

InOrder(root);

}

template<class

T>

void

BinaryTree<T>::Post_Order()

{

PostOrder(root);

}

template<class

T>

int

BinaryTree<T>::TreeHeight()const

{

return

Height(root);

}

template<class

T>

int

BinaryTree<T>::TreeNodeCount()const

{

return

NodeCount(root);

}

template<class

T>

void

BinaryTree<T>::DestroyTree()

{

Destroy(root);

}

template<class

T>

void

BinaryTree<T>::PreOrder(BTNode<T>

*r)

{

if(r!=NULL)

{

cout<<r->data<<'

';

PreOrder(r->lChild);

PreOrder(r->rChild);

}

}

template<class

T>

void

BinaryTree<T>::InOrder(BTNode<T>

*r)

{

if(r!=NULL)

{

InOrder(r->lChild);

cout<<r->data<<'

';

InOrder(r->rChild);

}

}

template<class

T>

void

BinaryTree<T>::PostOrder(BTNode<T>

*r)

{

if(r!=NULL)

{

PostOrder(r->lChild);

PostOrder(r->rChild);

cout<<r->data<<'

';

}

}

template<class

T>

int

BinaryTree<T>::NodeCount(const

BTNode<T>

*r)const

{

if(r==NULL)

return

0;

else

return

1+NodeCount(r->lChild)+NodeCount(r->rChild);

}

template<class

T>

int

BinaryTree<T>::Height(const

BTNode<T>

*r)const

{

if(r==NULL)

return

0;

else

{

int

lh,rh;

lh=Height(r->lChild);

rh=Height(r->rChild);

return

1+(lh>rh?lh:rh);

}

}

template<class

T>

void

BinaryTree<T>::Destroy(BTNode<T>

*&r)

{

if(r!=NULL)

{

Destroy(r->lChild);

Destroy(r->rChild);

delete

r;

r=NULL;

}

}

template<class

T>

void

BinaryTree<T>::Change(BTNode<T>

*r)//將二叉樹bt所有結(jié)點(diǎn)的左右子樹交換

{

BTNode<T>

*p;

if(r){

p=r->lChild;

r->lChild=r->rChild;

r->rChild=p;

//左右子女交換

Change(r->lChild);

//交換左子樹上所有結(jié)點(diǎn)的左右子樹

Change(r->rChild);

//交換右子樹上所有結(jié)點(diǎn)的左右子樹

}

}

template<class

T>

void

BinaryTree<T>::MakeTree(T

pData,BinaryTree<T>

leftTree,BinaryTree<T>

rightTree)

{

root

=

new

BTNode<T>();

root->data

=

pData;

root->lChild

=

leftTree.root;

root->rChild

=

rightTree.root;

}

(3)MinHeap.h最小堆實(shí)現(xiàn)[cpp]

\o"viewplain"viewplain

\o"copy"copy#include

<iostream>

using

namespace

std;

template<class

T>

class

MinHeap

{

private:

T

*heap;

//元素?cái)?shù)組，0號(hào)位置也儲(chǔ)存元素

int

CurrentSize;

//目前元素個(gè)數(shù)

int

MaxSize;

//可容納的最多元素個(gè)數(shù)

void

FilterDown(const

int

start,const

int

end);

//自上往下調(diào)整，使關(guān)鍵字小的節(jié)點(diǎn)在上

void

FilterUp(int

start);

//自下往上調(diào)整

public:

MinHeap(int

n=1000);

~MinHeap();

bool

Insert(const

T

&x);

//插入元素

T

RemoveMin();

//刪除最小元素

T

GetMin();

//取最小元素

bool

IsEmpty()

const;

bool

IsFull()

const;

void

Clear();

};

template<class

T>

MinHeap<T>::MinHeap(int

n)

{

MaxSize=n;

heap=new

T[MaxSize];

CurrentSize=0;

}

template<class

T>

MinHeap<T>::~MinHeap()

{

delete

[]heap;

}

template<class

T>

void

MinHeap<T>::FilterUp(int

start)

//自下往上調(diào)整

{

int

j=start,i=(j-1)/2;

//i指向j的雙親節(jié)點(diǎn)

T

temp=heap[j];

while(j>0)

{

if(heap[i]<=temp)

break;

else

{

heap[j]=heap[i];

j=i;

i=(i-1)/2;

}

}

heap[j]=temp;

}

template<class

T>

void

MinHeap<T>::FilterDown(const

int

start,const

int

end)

//自上往下調(diào)整，使關(guān)鍵字小的節(jié)點(diǎn)在上

{

int

i=start,j=2*i+1;

T

temp=heap[i];

while(j<=end)

{

if(

(j<end)

&&

(heap[j]>heap[j+1])

)

j++;

if(temp<=heap[j])

break;

else

{

heap[i]=heap[j];

i=j;

j=2*j+1;

}

}

heap[i]=temp;

}

template<class

T>

bool

MinHeap<T>::Insert(const

T

&x)

{

if(CurrentSize==MaxSize)

return

false;

heap[CurrentSize]=x;

FilterUp(CurrentSize);

CurrentSize++;

return

true;

}

template<class

T>

T

MinHeap<T>::RemoveMin(

)

{

T

x=heap[0];

heap[0]=heap[CurrentSize-1];

CurrentSize--;

FilterDown(0,CurrentSize-1);

//調(diào)整新的根節(jié)點(diǎn)

ret