Huffman编码与译码 代码

1 完成对输入的序列进行各个码元的概率统计 完成对字符串中的各字符的统计 并列出其概率分布矩阵 返回 pro 矩阵 s 待编码序列 S 所含的码元序列 function pro getpro s pro a length s S unique s b length S c zeros 1 b 用以存放个序列中各个码元的个数 进行概率计算 for i 1 b for j 1 a if S i s j c i c i 1 else continue end end end pro c a disp S disp pro 完成对已知编码序列的译码 以及在改变码表中的某一位值得情况下 再一次译码 计 算其误码率 Codenumber 已编码序列 huffmantable 码表 Code2 各码元的码长 pro2 各码元的概 率分布矩阵 s 原始序列 decodenumber 译码序列 function decodenumber huffmandecode Codenumber huffmantable Code2 pro2 bit mm unique bit 码元序列 mm mm pro2 2 lx ly size huffmantable LL size Codenumber 2 decodenumber ZF Codenumber ones 1 max Code2 for j 1 length bit for i 1 lx k Code2 i while ZF 1 k huffmantable i 1 k decodenumber decodenumber mm i ZF ZF k 1 end end end end disp 译码序列如下 disp decodenumber disp 原始序列如下 disp bit end 对于译码部分所用到的部分主要是编码时生成的码表以及 huffmantree 在进行编 码的时候 通过筛选后的源字符串的字符序列的下标 与码表中的每行相对应的原则 遍历 编码序列 在遍历的时候 通过码表中各行的码长 控制遍历的长度 与每行中的码表进行 比较 输出相对应的字符 即完成了译码 3 编码 完成构成完整的基本树 形成 huffmantree 并对其遍历 得到码表 通过码表 对序列进行编码 并求其平均码长 信息熵 编码效率 HuffmanTree 哈夫曼树 pro 码元概率分布矩阵 S 待编码序列 function Codenumber huffmantable Code2 huffmanencode HuffmanTree pro bit p pro a1 unique bit a2 bit len1 length a1 码元序列的长度 len2 length a2 所要编码序列的长度 a3 zeros 1 len2 生成与编码序列长度一样的零矩阵 用以存放编码 对应的下标 Code 存放其遍历一个码元所对应的编码 Code2 记录各个码元的码长 Lastnumber 1 Sumnumber 0 累积计算编码总长度 huffmantable ones len1 len1 建立 len1 len1 的单位负矩阵 用以存放其码表 遍历二叉树 生成码表 huffmantable for i 1 len1 循环完成 len1 个符号的编码 k pro 2 i key 1 m find HuffmanTree 6 1 len1 k while HuffmanTree 5 m 1 判断是否遍历到根结点 Code key HuffmanTree 4 m key key 1 m HuffmanTree 3 m 指向父节点 end lc length Code huffmantable i 1 lc fliplr Code 将 Code 矩阵中的编码左右翻转 完成倒序 排列 Code2 Code2 lc 将各个码元的编码长度赋予 矩阵 Code2 end 显示码表 即只输出矩阵 huffmantable 中非 1 的部分 disp 码表如下 Code4 for i 1 len1 显示其码表 disp a1 pro 2 i flag 1 while huffmantable i flag 1 Code4 flag huffmantable i flag flag flag 1 end Code4 disp 码长 Code2 i end 通过以上生成的码表 然后遍历源字符串与 unique 之后的字符串 找出其下标并对应输 出码表中对应的编码序列 这样源字符串的编码就完成了 以下是编码部分的主要代码 通过码元与待编码的序列一一比较 输出 huffmantable 中对应的编码 Codenumber for i 1 len2 for j 1 len1 if a1 j a2 i v find HuffmanTree 6 j flag 1 while huffmantable v flag 1 Code1 flag huffmantable v flag flag flag 1 Sumnumber Sumnumber 1 end Codenumber Sumnumber flag 2 Sumnumber Code1 1 flag 1 end end end disp 编码如下 disp Codenumber 计算其平均码长 PJ Code pro 1 Code2 计算其信息熵 HX 0 for i 1 len1 HX HX pro 1 i log2 pro 1 i end 计算其编码效率 N HX PJ Code disp 平均码长 PJ Code disp 信息熵 HX disp 编码效率 N end function huffmanmain disp 请输入待编码序列 s input s 调用概率统计函数 输出各码元的概率分布矩阵 pro getpro s 调用生成 huffmantree 函数 输出基本树 及完整 huffmantree HuffmanTree pro2 huffmantree pro 调用编码函数 输出码表 编码序列 平均码长 信息熵 编码效率 Codenumber huffmantable Code2 huffmanencode HuffmanTree pro2 s 调用译码函数 输 出译码序列以及误码率 decodenumber huffmandecode Codenumber huffmantable Code2 pro2 s 改变编码序列中的前两个值 即是 0 的变为 1 是 1 的变为 0 然后再 进行重新译码输出 Codenumber1 yiweicodenumber Codenumber 调用译码函数 对错位后的编码序列进行 译码 decodenumber huffmandecode Codenumber1 huffmantable Code2 pro2 s 2 通过构建二叉树 遍历 huffman 树 从而得到其对应的码表 pro1 各码元概率分布矩阵 pro2 各码元按倒序排列后的顺序以及对应之前的位置 function HuffmanTree pro2 huffmantree pro1 构建基础二叉树 LL length pro1 p1 p2 sort pro1 descend pro2 zeros 2 LL pro2 1 p1 pro2 2 p2 n0 size pro2 2 n1 ceil log2 n0 二叉树的深度 n LL tree ones 6 2 n 1 构造二叉树 声明一个 tree 6 x 结构的树型结点 一个结点包括 有 6 个变量存储单元 建立其 6 2 n 1 的单位 1 矩阵 用以存储二叉树中各个结点 父节点 以及各个结点的编号 tree 1 1 2 n 1 用以编号并存储二叉树中的结点 tree 5 n 1 end 0 用以存放其根结点 标记为 1 时作为结束标志 tree 2 1 n pro2 1 用以存放概率分布 tree 6 1 n pro2 2 用以存放每个概率对应的符号的下标 tree 6 n 1 end 0 disp 基本树形式 显示构建其的基本树形式 disp tree tree 1 x 记录该结点的编号 tree 2 x 记录该结点的概率值 tree 3 x 记录该结点的父结点编号 tree 4 x 记录该结点是左结点还是右结点 其中左结点为 0 右结点为 1 tree 5 x 记录该结点是否为根结点标志 该结点为根结点记为 1 否则决为 0 tree 6 x 记录该结点的字符 x 为 pro 中源字符经过筛选后的 下标数 其余值赋为零 对概率分布矩阵进行运算 每次进行最小两个值相加 其和赋予其中一个 另外一个置 1 重复操作 将其每一次输出的结果存于 s1 矩阵中 至最后两个概率和为 1 结束 s1 ones n 1 2 n 1 s1 1 sort tree 2 for i 2 n s1 i s1 i 1 1 s1 i 1 2 1 s1 i 1 3 2 n 1 s1 i sort s1 i end 对基础二叉树进行操作 完整构造 m1 0 m2 0 s2 tree 2 将 tree 2 中的概率分布赋予 s2 矩阵中 在不改 变 tree 2 中概率分布 方便对其操作 for i n 1 2 n 1 min1 find s2 s1 i n 1 从 tree 2 中找对应于 s1 矩阵中每一行的 最小的两个概率值的下标 为避免 tree 2 中出现两个相同的最小值 将进行如下判断并操作 if length min1 1 m1 min1 min2 find tree 2 s1 i n 2 m2 min2 1 else m1 min1 1 1 m2 min1 1 2 end tree 2 i tree 2 m1 tree 2 m2 s2 i tree 2 m1 tree 2 m2 s2 m1 1 s2 m2 1 tree 5 i 1 tree 3 m1 i tree 3 m2 i tree 4 m1 1 tree 4 m2 0 tree 5 m1 0 tree 5 m2 0 end HuffmanTree tree disp 哈夫曼树如下 d