©2020-2024 ioDraw All rights reserved,
Privacy Policy
在远程通讯中，要将待传字符转换成二进制的字符串。
假设要传输的字符为：ABACCDA；若编码为：A——00；B——01；C——10；D——11。那么要传输的字符的编码为：00010010101100。
若将编码设计为长度不等的二进制编码，即让待传字符串中出现次数较多的字符采用尽可能短的编码，则转换的二进制字符串便可能减少。
假设要传送的字符为：ABACCDA；若编码为：A——0；B——00；C——1；D——01。则字符串的编码为：000011010。但是这种编码会出现重码的情况。
关键：要设计长度不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀。
哈夫曼编码：
1、统计字符集中每个字符在电文中出现的平均概率（概率越大，要求编码越短）。
2、利用哈夫曼树的特点：权越大的叶子结点离根越近；将每个字符的概率值作为权值，构造哈夫曼树。则概率越大的结点，路径越短。
3、在哈夫曼树的每个分支上标上0或1，结点的左分支标0，结点的右分支标1，把从根到每个叶子结点的路径上的标号连接起来，作为该叶子结点代表的字符的编码。
例：要传输的字符集：，字符出现的概率：。
如果电文是：
那么它的编码是：11010111011101000011111000011000；
反之，若编码是1101000，那么它的译码是：CAT。
两个问题：
1、为什么哈夫曼编码能保证是前缀编码？
因为没有一片树叶是另一片树叶的祖先，所以每个叶子结点的编码就不可能是其它叶子结点编码的前缀。
2、为什么哈夫曼编码能够保证字符编码总长最短？
因为哈夫曼树的带权路径长度最短，故字符编码的总长最短。
性质1：哈夫曼编码是前缀码。
性质2：哈夫曼编码是最优前缀码。
例子：假设组成电文的字符集D以及其概率分布W为：
设计哈夫曼编码：
哈夫曼编码的算法实现：
找到结点的哈夫曼编码要从叶子结点找父结点直到找到根结点。