Huffman编码是一种无损压缩编码方案。
思想:根据源字符出现的(估算)概率对字符编码,概率高的字符使用较短的编码,
概率低的字符使用较长的编码,从而使得编码后的字符串长度期望最小。
Huffman是一种贪心算法:每次总选择两个最小概率字符结点合并。
称字符出现的次数为频数,则概率等于频数处于字符串总长;因此,频率可以用频数替代。
例如一个文本,统计出A,B,C,D,E,出现次数为15,7,6,6,5
根据上面定义,每次贪心选择最小的两个,如图:
每次选好后合并,变成一颗二叉树。
最优Huffman编码为
A:0 B:100 C:101 D:110 E:111
问题1 为什么这种情况压缩最小?
次数越多,离根越近,编码越短,所以最优。
问题2 Huffman是否唯一?
不是,从两点来看。1,若左子树边为1,右子树那边为0,则编码相反,但效果一样
2.若次数相同,出现并列现象,随便选一个都行。
问题3 像100100111000111110101这样经过Huffman编码压缩后能还原?
Huffman编码是前缀吗,不需要分割符,任何一个字符的编码都不是另一个字符的前缀。