huffman树编码压缩解压 压缩码表

Question

// 压缩函数
int compress(char ifname, char *ofname)
{
unsigned int i, j;
unsigned int char_kinds; // 字符种类
unsigned char char_temp; // 暂存8bits字符
unsigned long file_len = 0;
FILE *infile, *outfile;
TmpNode node_temp;
unsigned int node_num;
HufTree huf_tree;
char code_buf[256] = "\0"; // 待存编码缓冲区
unsigned int code_len;
/
** 动态分配256个结点，暂存字符频度，
** 统计并拷贝到树结点后立即释放
*/
TmpNode *tmp_nodes =(TmpNode *)malloc(256*sizeof(TmpNode));

// 初始化暂存结点
for(i = 0; i < 256; ++i)
{
    tmp_nodes[i].weight = 0;
    tmp_nodes[i].uch = (unsigned char)i;        // 数组的256个下标与256种字符对应
}

// 遍历文件，获取字符频度
infile = fopen(ifname, "rb");
// 判断输入文件是否存在
if (infile == NULL)
    return -1;
fread((char *)&char_temp, sizeof(unsigned char), 1, infile);        // 读入一个字符
while(!feof(infile))
{
    ++tmp_nodes[char_temp].weight;      // 统计下标对应字符的权重，利用数组的随机访问快速统计字符频度
    ++file_len;
    fread((char *)&char_temp, sizeof(unsigned char), 1, infile);        // 读入一个字符
}
fclose(infile);

// 排序，将频度为零的放最后，剔除
for(i = 0; i < 256-1; ++i)           
    for(j = i+1; j < 256; ++j)
        if(tmp_nodes[i].weight < tmp_nodes[j].weight)
        {
            node_temp = tmp_nodes[i];
            tmp_nodes[i] = tmp_nodes[j];
            tmp_nodes[j] = node_temp;
        }

// 统计实际的字符种类（出现次数不为0）
for(i = 0; i < 256; ++i)
    if(tmp_nodes[i].weight == 0) 
        break;
char_kinds = i;

if (char_kinds == 1)
{
    outfile = fopen(ofname, "wb");                  // 打开压缩后将生成的文件
    fwrite((char *)&char_kinds, sizeof(unsigned int), 1, outfile);      // 写入字符种类
    fwrite((char *)&tmp_nodes[0].uch, sizeof(unsigned char), 1, outfile);       // 写入唯一的字符
    fwrite((char *)&tmp_nodes[0].weight, sizeof(unsigned long), 1, outfile);        // 写入字符频度，也就是文件长度
    free(tmp_nodes);
    fclose(outfile);
}
else
{
    node_num = 2 * char_kinds - 1;      // 根据字符种类数，计算建立哈夫曼树所需结点数 
    huf_tree = (HufNode *)malloc(node_num*sizeof(HufNode));     // 动态建立哈夫曼树所需结点     

    // 初始化前char_kinds个结点
    for(i = 0; i < char_kinds; ++i) 
    { 
        // 将暂存结点的字符和频度拷贝到树结点
        huf_tree[i].uch = tmp_nodes[i].uch; 
        huf_tree[i].weight = tmp_nodes[i].weight;
        huf_tree[i].parent = 0; 
    }   
    free(tmp_nodes); // 释放字符频度统计的暂存区

    // 初始化后node_num-char_kins个结点
    for(; i < node_num; ++i) 
        huf_tree[i].parent = 0; 

    CreateTree(huf_tree, char_kinds, node_num);     // 创建哈夫曼树

    HufCode(huf_tree, char_kinds);      // 生成哈夫曼编码

    // 写入字符和相应权重，供解压时重建哈夫曼树
    outfile = fopen(ofname, "wb");                  // 打开压缩后将生成的文件
    fwrite((char *)&char_kinds, sizeof(unsigned int), 1, outfile);      // 写入字符种类
    for(i = 0; i < char_kinds; ++i)
    {
        fwrite((char *)&huf_tree[i].uch, sizeof(unsigned char), 1, outfile);            // 写入字符（已排序，读出后顺序不变）
        fwrite((char *)&huf_tree[i].weight, sizeof(unsigned long), 1, outfile);     // 写入字符对应权重
    }

    // 紧接着字符和权重信息后面写入文件长度和字符编码
    fwrite((char *)&file_len, sizeof(unsigned long), 1, outfile);       // 写入文件长度
    infile = fopen(ifname, "rb");       // 以二进制形式打开待压缩的文件
    fread((char *)&char_temp, sizeof(unsigned char), 1, infile);     // 每次读取8bits
    while(!feof(infile))
    {
        // 匹配字符对应编码
        for(i = 0; i < char_kinds; ++i)
            if(char_temp == huf_tree[i].uch)
                strcat(code_buf, huf_tree[i].code);

        // 以8位（一个字节长度）为处理单元
        while(strlen(code_buf) >= 8)
        {
            char_temp = '\0';       // 清空字符暂存空间，改为暂存字符对应编码
            for(i = 0; i < 8; ++i)
            {
                char_temp <<= 1;        // 左移一位，为下一个bit腾出位置
                if(code_buf[i] == '1')
                    char_temp |= 1;     // 当编码为"1"，通过或操作符将其添加到字节的最低位
            }
            fwrite((char *)&char_temp, sizeof(unsigned char), 1, outfile);      // 将字节对应编码存入文件
            strcpy(code_buf, code_buf+8);       // 编码缓存去除已处理的前八位
        }
        fread((char *)&char_temp, sizeof(unsigned char), 1, infile);     // 每次读取8bits
    }
    // 处理最后不足8bits编码
    code_len = strlen(code_buf);
    if(code_len > 0)
    {
        char_temp = '\0';       
        for(i = 0; i < code_len; ++i)
        {
            char_temp <<= 1;        
            if(code_buf[i] == '1')
                char_temp |= 1;
        }
        char_temp <<= 8-code_len;       // 将编码字段从尾部移到字节的高位
        fwrite((char *)&char_temp, sizeof(unsigned char), 1, outfile);       // 存入最后一个字节
    }

    // 关闭文件
    fclose(infile);
    fclose(outfile);

    // 释放内存
    for(i = 0; i < char_kinds; ++i)
        free(huf_tree[i].code);
    free(huf_tree);
}

}//compress
代码如上
不懂的就是压缩后码表的部分
希望各位懂得帮帮忙
huffman树以及码表如下图，求解释码表下半部分引出部分。

Answer 1

图片如下，楼主网络不好，图片传送老是失败