huffman编译码..doc

实验二 Huffman编译码 一 设计思想 Huffman编码是可变字长编码(VLC)的一种。 Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就称Huffman编码。Huffman编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的Huffman编码。 二 实现流程 图 1 编码基本流程 输入字符串“abcdeabcde”，得到概率向量为[0.2 0.2 0.2 0.2 0.2]，每次根据概率排序的顺序即为 2 3 4 5 2 3 4 1 0 2 1 3 0 0 2 1 0 0 0 依据概率排序矩阵编码 在得到最后两个概率时进行编码，统一用大概率或统一用大概率都可以，根据每一次的编码顺序，如图 01 110 111 10 110 111 10 0 10 11 0 0 1 Huffman解码 Huffman编码的特殊性，我们在进行解码时只需要查找，每发现，解码一处，最终即可获得原来的字符串。 Huffman编码的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的，就是说出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，极大的节约了信道资源 实验结果如下 概率[0.1 0.2 0.3 0.4] 概率[0.2 0.2 0.2 0.2 0.2] 概率[0.1 0.2 0.1 0.2 0.4] 其中ll表示各概率编码长度，h表示最终概率编码，t为编码效率。从上述几组数据中可以看出，效率越低，码长越长，效率越高，码长越短。这样可以使得编码总长度最短，对信道的占用也越低，极大地提高了信息传输的效率，而各编码间的任意组合也不会变成其他编码，可以看出Huffman编码是一种十分优秀的编码。 由于编程水平有限，对字符串以及随机化的处理未能掌握，故输入采取的直接输入概率，而具体的实现方法我在思考题中给出了做法。 四 思考题解答 如何对文本进行概率统计？ 答：用循环语句输入，当前输入数i，n=0，输入时新开一个数组一个位置数组，加入一个新字符，数组长度加1并将此数组[输入字符]=i，是之前输入字符，，出现的量，a[i]第i个字符出现多少次，总量累看每字符所占比例其概率。 由于Huffman编码的唯一性，任何一位码串错位都会对之后的解码造成很大影响，甚至可能导致错码之后的解码全部出错或是不能继续解码，然而，中信道存在噪声，过程中肯定会出错，我们可以在码中加入纠错码，使其在解码时实现功能。6 输入 统计概率 根据概率排序 进行Huffman编码 生成码表并计算编码效率 输出