一、实验目的 1．掌握 MATLAB 软件的使用，以及其设计流程； 2．掌握哈夫曼编码的实现方法； 3．用 MATLAB 语言设计哈夫曼编码的实现方法。 4．提高独立进行算法编程的能力。 二、实验仪器或设备 装 MATLAB 软件的微机一台 三、总体设计 1、 二进制 Huffman 编码的基本原理及算法 1).将信源消息符号按其出现的概率大小依次排列为
河南师范大学计算机与信息技术学院
%这里从 c(n)分出两枝，对开始合并的两节点成码 %恢复原顺序 index = [index , i1 , i2] ; c(index) = c ; 五、结果分析与总结 通过本次实验，我对 huffman 编码的具体实现原理有了更加深刻的理解，在 实验的过程中也遇到了一பைடு நூலகம்问题，通过查找资料和相关书籍得到了解决，在完成 该实验的过程中，还是学到了比较多的知识，包括使对一些 matlab 语句的掌握 的更加熟练，完成一个算法必须要有一个整体的把握等。在以后的学习过程中， 我会继续努力，争取在这方面做的更好。
河南师范大学计算机与信息技术学院
置，然后在 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 编码。 四、实验步骤（包括主要步骤、代码分析等） （一）主要步骤 1．打开 MATLAB 集成调试软件 2．单击“File”－“New” ，新建一个.M 文件，命名为“c” 。 3．保存后运行。 4．在 MATLAB 的主窗口输入 p=[0.20 0.19 0.18 0.17 0.15 0.10 0.01]按 Enter 后，输入 c=Huffman(p)再按 Enter，即可出现实验结果。 5．观察到实验结果为 ‘10’ ‘11’ ‘000’ ‘001’ ‘010’ ‘0110’ ‘0111’ 6．分析实验结果 （二）主要代码分析 function c = huffman(p) n = size(p , 2) ; if n == 1 %此时已合并到一棵树上了，直接返回 c = cell(1,1) ; c{1} = '' ; return end %找最小的 [p1 , i1] = min(p) ; index = [(1:i1-1) , (i1+1:n)] ; %这里的 index 是一个 trick %他跟踪了现在的 p 的每个分量，在原来的 p 里面的下标 %在最后，将依据这个下标来成码 p = p(index) ; n = n - 1 ; %找第二小的 [p2 , i2] = min(p) ; index2 = [(1:i2-1) , (i2+1:n)] ; %index2 是在上一个 p 中的下标 p = p(index2); i2 = index(i2) ;%i2 变为在原 p 中次小值的下标 index = index(index2) ;%继续跟踪现在的 p 在原 p 中的下标 p(n) = p1 + p2 ;%生成一个新节点，即合并的两个最小节点的和 c = huffman(p) ;%对新的 p 的序列做 huffman 编码 c{n+1} = strcat(c{n} , '0') ;%p(n)是开始合并的节点 c{n} = strcat(c{n} , '1') ;
p1 p2 ... pn
2).取两个概率最小的字母分别配以 0 和 1 两个码元，并将这两个 概率相加作为一个新字母的概率，与未分配的二进制符号的字母重新排 队。 3).对重排后的两个概率最小符号重复步骤 2 的过程。 4).不断继续上述过程，直到最后两个符号配以 0 和 1 为止。 5).从最后一级开始，向前返回得到各个信源符号所对应的码元序 列，即相应的码子。 2、程序设计的原理 1)程序的输入： 以一维数组的形式输入要进行 huffman 编码的信源符号的概率，在 运行该程序前，显示文字提示信息，提示所要输入的概率矢量；然后对 输入的概率矢量进行合法性判断，原则为：如果概率矢量中存在小于 0 的项，则输入不合法，提示重新输入；如果概率矢量的求和大于 1，则 输入也不合法，提示重新输入。 2）huffman 编码具体实现原理： 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 所在的位
教师签名： 年 月 日
河南师范大学计算机与信息技术学院