哈夫曼编码码长怎么算？
假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}。
哈夫曼编码 根据上面可得编码表： a:1001 b:01 c:10111 d:1010 e:11 f:10110 g:00 h:1000
用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为：4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 2.61/3=0.87=87%其平均码长是等长码的87%，所以平均压缩率为13%。
因为定长编码已经用相同的位数这个条件保证了任一个字符的编码都不会成为其它编码的前缀,所以这种情况只会出现在变长编码当中，要想避免这种情况，
就必须用一个条件来制约定长编码，这个条件就是要想成为压缩编码，变长编码就必须是前缀编码，所谓的前缀编码就是任何一个字符的编码都不能是另一个字符编码的前缀。
扩展资料：
实际应用中，除采用定时清洗以消除误差扩散和采用缓冲存储以解决速率匹配以外，主要问题是解决小符号集合的统计匹配，
例如黑（1）、白（0）传真信源的统计匹配，采用0和1不同长度游程组成扩大的符号集合信源。游程，指相同码元的长度（如二进码中连续的一串0或一串1的长度或个数）。按照CCITT标准，需要统计2×1728种游程（长度），
这样，实现时的存储量太大。事实上长游程的概率很小，故CCITT还规定：若l表示游程长度，则l=64q+r。其中q称主码，r为基码。编码时，不小于64的游程长度由主码和基码组成。而当l为64的整数倍时，只用主码的代码，已不存在基码的代码。
参考资料来源：百度百科-哈夫曼编码
介绍一个不用构造哈夫曼树的方法来计算哈夫曼编码的长度的算法，本算法的时间复杂度为O(nlogn)，空间复杂度为O(N)。下面是具体代码。
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
using namespace std;
#define BUFF_SIZE 4096
#define HASH_SIZE 256
char buff[BUFF_SIZE]; //缓冲区
int hash[HASH_SIZE]; //统计每个字符出现的次数
int heap[(HASH_SIZE<<1)+2];
int pos[HASH_SIZE+1][3];//内部节点 , 0和1记录子结点位置,3节录当前的深度
int tlen[HASH_SIZE+1]; //记录每个叶子结点的深度
int fd; //文件描述符
int sym_num ; //文件中出现的符号数量
int SUM(0); //文件中字符总数
//初始化程序
void init(const char * pathname)
{
memset(buff , 0 , sizeof(buff));
memset(hash , 0 , sizeof(hash));
memset(heap , 0 , sizeof(heap));
memset(pos , 0 , sizeof(pos));
memset(tlen , 0 , sizeof(tlen));
//打开文件
fd = open(pathname , O_RDONLY);
if(fd < 0){
printf("init: %s dont exit!\n" , pathname);
exit(1);
}
}
//统计文件中每个符号出现的次数
void count_symbol()
{
lseek(fd , 0 , SEEK_SET);
while(read(fd , buff , BUFF_SIZE)){
SUM += strlen(buff);
for(int i=strlen(buff) - 1;i>=0;i--)
hash[(unsigned int)(buff[i] & 0xFF)]++;
}
//记录出现的符号数量;
for(int i = HASH_SIZE - 1; i >= 0; i--)
if(hash[i])sym_num++;
}
//建立一个最小堆
void build_min_heap()
{
for(int i=sym_num;i>0;i--){
int p = i >> 1 , j = i;
while(p >= 1){
if(heap[heap[p]] > heap[heap[j]])
std::swap(heap[j] , heap[p]);
j = p; p >>= 1;
}
}
}
//每次取出最小数之后重新调整堆,
//h 指推中元素的个数
void heap_adjust(int h)
{
int t = 1 , p , q , l;
while(t<h){
p = t<<1; q = p + 1; l = t;
if(p <= h && heap[heap[p]] < heap[heap[t]])l = p;
if(q <= h && heap[heap[q]] < heap[heap[l]])l = q;
if(l == t)break;
std::swap(heap[l] , heap[t]);
t = l;
}
}
//计算每个字符编码的长度
void huff_length()
{
int i , j , p , h , m1 , m2;
for(i=1 , p=0;i<=sym_num;i++){
while(!hash[p]) p++;
heap[sym_num + i] = hash[p];
heap[i] = sym_num + i;
p++;
}
h = sym_num;
//对1到n建立最小堆
build_min_heap();
while(h>1){
//取出最小数
m1 = heap[heap[1]];
pos[h][0] = heap[1];
heap[1] = heap[h];
h--;
heap_adjust(h);
//取出次小数
m2 = heap[heap[1]];
pos[h+1][1] = heap[1];
//最后数和次小数之和放在堆的最后一个位置
heap[h+1] = m1 + m2;
//重新指向最新合并的结点
heap[1] = h+1;
heap_adjust(h);
}
//统计编码长度 , 线性时间统计
int ts = sym_num << 1;
for(int i=2;i<=sym_num;i++){
if(pos[i][0] <= sym_num) pos[pos[i][0]][2] = pos[i][2] + 1;
else tlen[pos[i][0] - sym_num] = pos[i][2] + 1;
if(pos[i][1] <= sym_num) pos[pos[i][1]][2] = pos[i][2] + 1;
else tlen[pos[i][1] - sym_num] = pos[i][2] + 1;
}
}
int main()
{
init("data.dat");
count_symbol();
huff_length();
unsigned int sum = 0;
for(int i=1;i<=sym_num;i++)
sum += tlen[i] * heap[sym_num + i];
cout<<SUM <<"\t\t"<<sum<<"\t\t"<<sum*1.0/SUM<<endl;
return 0;
}
假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}.
哈夫曼编码 根据上面可得编码表： a:1001 b:01 c:10111 d:1010 e:11 f:10110 g:00 h:1000
用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为： 4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 2.61/3=0.87=87%其平均码长是等长码的87%，所以平均压缩率为13%。
参考资料
哈夫曼编码码长怎么算？.新浪博客[引用时间2018-1-5]
