第1题：

2.利用程序huff_enc和huff_dec进行以下操作.

（a）对Sena、Sensin和Omaha图像进行编码

文件名	压缩前大小	压缩后大小	压缩比
Sena	64kb	57kb	0.89
Sensin	64kb	61kb	0.95
Omaha	64kb	58kb	0.91

 

 

 

 

 

4.一个信源从符号集A={a1,a2,a3,a4,a5}中选择字母，概率为p(a1)=0.15,p(a2)=0.04,p(a3)=0.26,p(a4)=0.05,p(a5)=0.50.

(a)计算这个信源的熵.

解：H(A) = -0.15*log₂0.15-0.04*log₂0.04-0.26*log₂0.26-0.05*log₂0.05-0.50*log₂0.50

               =0.15* 2.737+0.04*4.644+0.26*1.943+0.05*4.322+0.5*1

               =0.411+0.186+0.505+0.216+0.5

               =1.818（bits/symbol）  

  

(b)求这个信源的赫夫曼码.

解： a1:001

       a2:0000

       a3:01

       a4:0001

       a5:1

(c)求(b)中代码的平均长度及其冗余度.

解：平均长度：L=0.15*3+0.04*4+0.26*2+0.05*4+0.5*1

                   =0.45+0.16+0.52+0.2+0.5

                   =1.83（bits/symbol）

       冗余度：L-H(A)=1.83-1.818=0.012（bits/symbol）

 

第2题：

思考：为什么压缩领域中的编码方法总和二叉树联系在一起呢？

       答：我们之前学过前缀编码，为了使用不固定的码长表示单个字符，编码必须符合“前缀编码”的要求，即较短的编码决不能是较长编码的前缀，没有码字是其他码字的前缀。要构造符合这一要求的二进制编码体系，二叉树是最理想的选择，可将码字放在叶子节点上。

第3题：

选做：试将"Shannon-Fano"编程实现.

C++编程：

#include"iostream"

#include "queue"

#include "map"

#include "string"

#include "iterator"

#include "vector"

#include "algorithm"

#include "math.h"

using namespace std;

#define NChar 8

#define Nsymbols 1<<NChar

#define INF 1<<31-1

typedef vector<bool> SF_Code;

map<char,SF_Code> SF_Dic;

int Sumvec[Nsymbols];

class HTree

{

public :

HTree* left;

HTree* right;

char ch;

int weight;

HTree(){left = right = NULL; weight=0;ch ='\0';}

HTree(HTree* l,HTree* r,int w,char c){left = l; right = r; weight=w; ch=c;}

~HTree(){delete left; delete right;}

bool Isleaf(){return !left && !right; }

};

bool comp(const HTree* t1, const HTree* t2)

{ return (*t1).weight>(*t2).weight; }

typedef vector<HTree*> TreeVector;

TreeVector TreeArr;

void Optimize_Tree(int a,int b,HTree& root)

{

if(a==b)

{

root = *TreeArr[a-1];

return;

}

else if(b-a==1)

{

root.left = TreeArr[a-1];

root.right=TreeArr[b-1];

return;

}

int x,minn=INF,curdiff;

for(int i=a;i<b;i++)

{

curdiff = Sumvec[i]*2-Sumvec[a-1]-Sumvec[b];

if(abs(curdiff)<minn){

x=i;

minn = abs(curdiff);

}

else break;

}

HTree*lc = new HTree; HTree *rc = new HTree;

root.left = lc; root.right = rc;

Optimize_Tree(a,x,*lc);

Optimize_Tree(x+1,b,*rc);

}

HTree* BuildTree(int* freqency)

{

int i;

for(i=0;i<Nsymbols;i++)

{

if(freqency[i])

TreeArr.push_back(new HTree (NULL,NULL,freqency[i], (char)i));

}

sort(TreeArr.begin(), TreeArr.end(), comp);

memset(Sumvec,0,sizeof(Sumvec));

for(i=1;i<=TreeArr.size();i++)

Sumvec[i] = Sumvec[i-1]+TreeArr[i-1]->weight;

HTree* root = new HTree;

Optimize_Tree(1,TreeArr.size(),*root);

return root;

}

void Generate_Coding(HTree* root, SF_Code& curcode)

{

if(root->Isleaf())

{

SF_Dic[root->ch] = curcode;

return;

}

SF_Code lcode = curcode;

SF_Code rcode = curcode;

lcode.push_back(false);

rcode.push_back(true);

Generate_Coding(root->left,lcode);

Generate_Coding(root->right,rcode);

}

int main()

{

int freq[Nsymbols] = {0};

char *str = "bbbbbbbccccccaaaaaaaaaaaaaaaeeeeedddddd";

//statistic character frequency

while (*str!='\0') freq[*str++]++;

HTree* r = BuildTree(freq);

SF_Code nullcode;

Generate_Coding(r,nullcode);

for(map<char,SF_Code>::iterator it = SF_Dic.begin(); it != SF_Dic.end(); it++) {

cout<<(*it).first<<'\t';

std::copy(it->second.begin(),it->second.end(),std::ostream_iterator<bool>(cout));

cout<<endl;

}

}