信
息
论
与
编
码
课
程
设
计
学院：计算机学院
专业：信息与计算科学 0802
学号：0808060204
姓名：贾永侠
目录
1
1 课题描述 …………………………………………………3
2 霍夫曼编码及香农编码的相关介绍
2.1 霍夫曼编码介绍………………………………………3
2.2 香农编码介绍………………………………………….3
3 霍夫曼编码及香农编码
3.1 霍夫曼编码算法 ……………………………………..3
3.2 霍夫曼编码特点 ……………………………………..4
3.3 香农编码算法………………………………………....4
3.4 香农编码特点………………………………………….5
4 费诺编码的 C 程序实现
4.1 霍夫曼程序设计…………………………………… …5
4.2 霍夫曼运行结果 …………………………………….11
4.3 香农程序设计…………………………………………11
4.4 香农运行结果…………………………………………15
总 结 …………………………………………………………..15
参考文献 ………………………………………………………15
1 .课题描述
信源编码主要可分为无失真信源编码和限失真信源编码。无失真信源编码
主要适用于离散信源或数字信号，如文本、表格及工程图纸等信源，它们要求
进行无失真地数据压缩，要求完全能够无失真地可逆恢复。凡是能载荷一定的
2
信息量，且码字的平均长度最短，可分离的变长码的码字集合称为最佳变长码，
为此必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，是
的平均码字长度最短，能得到最佳的编码方法主要有：香农，费诺，霍夫曼编
码等，实现至少两种无失真信源编码（香农码，哈夫曼码、费诺码）及其编码
效率。
2 霍夫曼编码及香农编码的相关介绍
2.1 霍夫曼编码介绍
霍夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编
码(VLC)的一种。huffman 于 1952 年提出一种编码方法，该方法完全依据字符
出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就
叫作 Huffman 编码。以霍夫曼树即最优二叉树，带权路径长度最小的二叉树，
经常应用于数据压缩。 在计算机信息处理中，“哈夫曼编码”是一种一致性编
码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张
特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表
的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出
现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这
便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目
的）。这种方法是由 David.A.Huffman 发展起来的。 例如，在英文中，e 的
出现概率很高，而 z 的出现概率则最低。当利用哈夫曼编码对一篇英文进行
压缩时，e 极有可能用一个位(bit)来表示，而 z 则可能花去 25 个位（不是
26）。用普通的表示方法时，每个英文字母均占用一个字节（ byte），即 8
个位。二者相比，e 使用了一般编码的 1/8 的长度，z 则使用了 3 倍多。倘若
我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提
高无损压缩的比例。
2.2 香农编码介绍
香农第一定律指出了平均码长与信源之间的关系，同时也指出了可以通过
编码使得平均码长达到极限值，这是一个很重要的极限定理。香农第一定理指
出选择每一个码字的长度 ki 满足下式： +1 对于任意的 i
就可以得到这种码。每一个信源符号的自信息量和码长，这种编码方法 称为香
农编码。
3 霍夫曼编码及香农编码
3.1 霍夫曼编码算法
二元霍夫曼码编码:
(1) 将 q 个信源符号按概率分布 P(s
i
)的大小，以递减次序排列起来，设
p
1
≥p
2
≥p
3
≥…≥p
q
(2) 用 0 和 1 码符号分别代表概率最小的两个信源符号，并将这两个概
率最小的信源符号合并成一个符号，从而得到只包含 q-1 个符号的
信源，称为 S 信源的缩减信源 S
1
。
(3) 把缩减信源 S 的符号仍按概率大小以递减次序排列，再将其最后二
个概率最小的符号合并成一个符号，并分别用 0 和 1 码符号表示，
3
这样又形成了 q-2 个符号的缩减信源 S
2
。
(4) 依此继续下去，直至信源最后只剩两个符号为止。将这两个最后的
信源符号分别用 0 和 1 码符号表示然后从最后一级缩减信源开始，
向前返回，就得出各信源符号所对应的码符号序列，即得对应的码
字。
r 元 human 编码：
（1）验证所给 n 个是否满足 n=(r-1)Q+r，若不满足该式，可以人为地增
加一些概率为零的符号在最后，以使最后一步有 r 个信源符号；
（2）将 n 个信源 U的各个符号 u 按概率分布 p(u )以递减次序排列起来。
（3）取 r 个概率最小的符号分别配以 0 到 r-1 的码元，并将这 r 个概率相
加作为一个新符号的概率，重新以概率递减的次序排队。
（4）对重新排后的两个最小的概率重复步骤（3）。
（5）依次继续下去，直至信源最后 r 个符号分配到 0 到 r-1 为止。
（6）从最后一级开始，从前返回得到各个信源符号所对应的码元序列。
3.2 霍夫曼编码特点
霍夫曼编码使用概率匹配的方法进行信源编码，它有两个明显的特点：一是
霍夫曼码的编码方法保证了概率大的符号对应短码，概率小的符号对应于长码，
充分利用了短码，二是缩减了信源的最后两个码字总是最后一位不同，从而保
证了霍夫曼码是即时码。
3.3 香农编码算法
（1）将信源消息符号按其出现的概率大小依次排列为
….
(2)确定满足下列不等式的整数码长 为
-lb（ ） <-lb( )+1
(3)为了编成一唯一可译码，计算第 i 个消息的累加概率
（4）将累加概率 变换成二进制数。
（5）取 二进制小数点后 位即为该消息符号的二进制码字。
3.4 香农编码特点
1.将概率序列排序，为方便，还是记作 p，在编程时调整一下就行。
2.算累加概率 pa(i) = sum(p(j)) , j = 0..i-1，视 p(0) = 0
3.算码长 k(i) = ceil(log2(p(i)))
4.将 pa(i)换成二进制表示，取小数前 k(i)位为 c(i)
香农编码的效率一般并不是最高的！
4 费诺编码的 C 程序实现
4
4.1 霍夫曼程序设计
#include <conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MAXLEN 100
typedef struct Huffmantree {
char ch; /*键值*/
int weight,mark,hu;/*weight 为权值,mark 为标志域*/
struct Huffmantree *parent,*lchild,*rchild,*next;
}Hftree,*linktree;
int sum=0;
float k=0.0;
double r, H=0.0;;
linktree tidycharacter(char character[])
{
int i=0;
for(i=0;character[i]!='\0'&&character[i]!='\n';i++) { /*遍历直到字符串结束为止*/
sum++;}
linktree tree,ptr,beforeptr,node; /* 链 式 ,tree 为 头结 点 ,beforeptr 为 ptr 的 前一 结
点,node 为新申请的结点*/
tree=(linktree)malloc(sizeof(Hftree));/*创建单链表的头结点*/
if(!tree)return NULL;
tree->next=NULL; /* 头结点为空,且后续结点为空*/
for(i=0;character[i]!='\0'&&character[i]!='\n';i++) { /*遍历直到字符串结束为止*/
ptr=tree;
beforeptr=tree;
node=(linktree)malloc(sizeof(Hftree)); /*新申请结点 node*/
if(!node)return NULL;
node->next=NULL;
node->parent=NULL;
node->lchild=NULL;
node->rchild=NULL; /*置空*/
node->mark=0;
node->ch=character[i];
node->weight=1;
node->hu=0;
if(tree->next==NULL)
tree->next=node; /*头结点的下一结点为空,连接 node*/
else {
ptr=tree->next;
while(ptr&&ptr->ch!=node->ch) {/*将指针移至链表尾*/
5
- 1
- 2
前往页