C 实现 哈夫曼编码

哈夫曼编码是一种用于数据压缩的无损熵编码,根据压缩数据符号出现频率大小进行编码, 出现频率越高,编码后占bit 越少的变长编码。(其他详细介绍见参考)

刚好这两天看到,大学时信息论学完后基本忘记,顺便复习以下,并尝试C代码实现。

如何编码

假设, 准备压缩的数据源, 评估得到各个符号出现的频率如下, 则其编码过程如下图

这里写图片描述

详细参考 huffman编码

程序流程

编码 :

  1. 遍历准备压缩的输入内容,累计各个符号出现频率
static void cal_char_freq_table(char *array, uint32 len)
{   
    memset(freq_table, 0, sizeof(freq_table));
    while (len--) {
        ++freq_table[*array++];
    }
}
  1. 遍历频率数组, 根据符号输入频率为每个出现的符号新建节点, 并插入队列,队列中根据频率从小到大排序(方便下一步构建二叉树)
static int8 build_char_freq_list(struct hfm_node *list)
{
    uint32 i = 0;
    for (; i < 256; ++i) {
        if (freq_table[i] > 0) {
            struct hfm_node *new = new_hfm_node((char)i, freq_table[i]);
            if (new != NULL) {
                list_insert(list, new);
            } else {
                printf("New ffm_node failue!!\n");
                return -1;
            }
        }
    }
    return 0;
}
  1. 循环取出队列最小两项合并,新建节点, 保存合并后频率值,被合并两项则为新节点左右子节点, 然后将新节点插回队列。 队列中只剩下一项时, 二叉树建立完成, 该项为二插树根节点。
static struct hfm_node *build_char_freq_tree(struct hfm_node *list)
{
    struct hfm_node *new = NULL;
    struct hfm_node *left, *right;

    while (1) {
        // 取权中最小的两个节点合并
        left = list_pop(list);
        if (left == NULL) {
            return NULL;
        }

        right = list_pop(list);
        if (right == NULL) {
            // root
            return left;
        }
        new = new_hfm_node(0, left->freq + right->freq);
        new->left = left;
        new->right = right;
        list_insert(list, new);
    }
}
  1. 遍历二叉树,得到符号对应的编码 (一个byte标记编码编码序列, 左0, 右1, 一个值记录几位), 遇到叶节点,取出值设置对应的code;
static uint8 hfm_code = 0;
static uint8 hfm_deep = 0;
static void _build_hfm_code_table(struct hfm_node *root)
{
    ++hfm_deep;

    if (root->left == NULL && root->right == NULL) {
        hfm_code_table[root->val].code = hfm_code;
        hfm_code_table[root->val].len = hfm_deep - 1;
    } else {
        hfm_code = (hfm_code << 1);

        if (root->left != NULL) {
            _build_hfm_code_table(root->left);
        }
        if (root->right != NULL) {
            hfm_code |= 1;
            _build_hfm_code_table(root->right);
        }
        hfm_code = (hfm_code >> 1);
    }

    --hfm_deep;
}

static void build_hfm_code_table(struct hfm_node *root)
{
    hfm_code = 0;
    hfm_deep = 0;
    memset(hfm_code_table, 0, sizeof(hfm_code_table));

    if (root != NULL) _build_hfm_code_table(root);
}

完整代码

得到对应的编码映射, 便可以对应编码了 解码时, 也需要二叉树, 依据编码值, 寻得叶节点,得到对应的符号。


参考

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

C/C++中peek函数的原理及应用

C++中的peek函数   该调用形式为cin.peek() 其返回值是一个char型的字符,其返回值是指针指向的当前字符,但它只是观测,指针仍停留在当前位置,...

31250
来自专栏Java帮帮-微信公众号-技术文章全总结

Java面试系列2

六、&和&&的区别? &是位运算符,表示按位与运算,&&是逻辑运算符,表示逻辑与(and) 七、swtich是否能作用在byte上,是否能作用在long上,是否...

30360
来自专栏Java帮帮-微信公众号-技术文章全总结

【大牛经验】探讨Java的异常与错误处理

探讨Java的异常与错误处理 ENTER TITLE ? Java中的异常处理机制已经比较成熟,我们的Java程序到处充满了异常的可能,如果对这些异常不做预先的...

38660
来自专栏专注 Java 基础分享

深入理解Struts2----类型转换

     之前的一系列文章主要介绍了有关Struts2的一些基本用法和部分的简单原理,但是始终没有介绍有关拦截器的相关内容,从本篇开始我们将从另一个角度去深入理...

23690
来自专栏java达人

多线程设计模式解读5—Immutable Object(不可变对象)模式

前面讲了Producer-Consumer模式,它有许多变种,我们以后会讲。我们将接着了解另外一种分支的设计模式,前面所讲的所有的模式,都是要用到锁的,而锁是会...

9030
来自专栏java学习

面试题63(链表,哈希表)

关于链表,哈希表 1·以下关于链式存储结构的叙述中哪一个是正确的? A.链式存储结构不是顺序存取结构 B.逻辑上相邻的节点物理上必须邻接 C.可以通过计算直接确...

31660
来自专栏Dawnzhang的开发者手册

数据结构与算法学习笔记之 提高读取性能的链表(上)

链表(Linked list)比数组稍微复杂一点,在我们生活中用到最常见的应该是缓存,它是一种提高数据读取性能的技术,常见的如cpu缓存,浏览器缓存,数据库缓...

12630
来自专栏皮皮之路

【JDK1.8】Java 8源码阅读汇总

16840
来自专栏增长技术

ConcurrentModificationException

12630
来自专栏从流域到海域

《笨办法学Python》 第3课手记

《笨办法学python》第3课手记 本节课介绍运算符,如果你有C语言的基础的话很简单,运算符跟C语言都一样,优先级也一样。出现小数会四舍五入。但逻辑判断时,C语...

20580

扫码关注云+社区

领取腾讯云代金券