1、学习 Matlab软件的使用和编程;
2、进一步深入理解 Huffman编码算法的原理;
3、提高独立进行算法编程的能力。
1、用 Matlab实现 Huffman编码算法程序;
3、设计简单的输入界面(可以是简单的文字提示信息),程序运行时提示用户输入代
表信源符号概率的向量;要对用户输入的概率向量进行合法性检查。
(1) 把信源符号集中的所有符号按概率从大到小排队。
(2) 取概率最小的两个符号作为两片叶子合并(缩减)到一个 节点。
(3) 视此节点为新符号,其概率等于被合并(缩减)的两个概率之和,参与概率排队。
(4) 重复(2)(3)两步骤,直至全部符号都被合并(缩减)到根。
(5) 从根出发,对各分枝标记 0 和 1。从根到叶的路径就给出了各个码字的编码和码长。
2、程序设计的原理
(1)程序的输入:以一维数组的形式输入要进行 huffman编码的信源符号的概率,在运行该
程序前,显示文字提示信息,提示所要输入的概率矢量;然后对输入的概率矢量进行合法性
判断,原则为:如果概率矢量中存在小于0 的项,则输入不合法,提示重新输入;如果概率
矢量的求和大于 1,则输入也不合法,提示重新输入。
1>在输入的概率矩阵 p 正确的前提条件下,对 p 进行排序,并用矩阵 L 记录 p 排序之前
各元素的顺序,然后将排序后的概率数组 p 的前两项,即概率最小的两个数加和,得到新的
一组概率序列,重复以上过程,最后得到一个记录概率加和过程的矩阵 p 以及每次排序之前
概率顺序的矩阵 a。
2>新生成一个 n-1行 n 列,并且每个元素含有 n 个字符的空白矩阵,然后进行 huffman
编码:
将 c 矩阵的第 n-1行的第一和第二个元素分别令为0 和 1(表示在编码时,根节点之下
的概率较小的元素后补 0,概率较大的元素后补 1,后面的编码都遵守这个原则)
然后对 n-i-1的第一、二个元素进行编码,首先在矩阵 a 中第 n-i行找到值为 1 所在的
位置,然后在 c 矩阵中第 n-i行中找到对应位置的编码(该编码即为第n-i-1行第一、
二个元素的根节点),则矩阵 c 的第 n-i行的第一、二个元素的 n-1的字符为以上求得
的编码值,根据之前的规则,第一个元素最后补 0,第二个元素最后补 1,则完成该行
的第一二个元素的编码,
最后将该行的其他元素按照“矩阵 c 中第 n-i 行第 j+1 列的值等于对应于 a 矩阵中第
n-i+1行中值为 j+1的前面一个元素的位置在 c 矩阵中的编码值”的原则进行赋值,重
复以上过程即可完成 huffman编码。
3>计算信源熵和平均码长,其比值即为编码密码效率。