哈夫曼编码/哈夫曼树

哈夫曼编码/哈夫曼树

哈夫曼编码（英语：Huffman Coding），又译为霍夫曼编码、赫夫曼编码，是一种用于无损数据压缩的熵编码（权编码）算法。由美国计算机科学家大卫·霍夫曼于1952年发明。

霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1L1+W2L2+W3L3+…+WnLn），N个权值Wi（i=1,2,…n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,…n）。可以证明霍夫曼树的WPL是最小的。

这里可以是权重，也可以是在编码中出现的次数

例如

现在有一个字符串为'AABBBCDE'

编码方式大概有几种

1. 简单编码

A:0
B:1
C:10
D:11
E:100
依照上述变换方法
'AABBBCDE'->'001111011100'
当然，缺点或者硬伤也显而易见，得到的字符串解码结果不唯一

2. 等长编码

第二种方法就是在第一种方法的基础上让每一个码具有相同的位数，这样就保证了解码得到的结果是唯一的

A:000
B:001
C:010
D:011
E:100
这时，最简单的方式就出现了，但是仍然有缺点，也就是得到的结果并不一定是最短的

3. 哈夫曼编码

最后这一种就是哈夫曼编码，使用二叉树的数据结构，在保证解码结果唯一的前提下得到最短的结果

数据结构定义

// 以下是本文档使用的结构体
typedef struct ListNode // 结点结构，哈夫曼树与频度链表共用
{
    char c;                    // 结点的字符
    int frequency;             // 字符的频度
    char *code;                // 字符的编码(对哈夫曼树结点有效)
    struct ListNode *parent;   // 结点的双亲结点(对哈夫曼树结点有效)
    struct ListNode *left;     // 结点的左子树(对哈夫曼树结点有效)
    struct ListNode *right;    // 结点的右子树(对哈夫曼树结点有效)
    struct ListNode *next;     // 结点的后继结点(对频度链表结点有效)
} ListNode, HuffmanTree;

以下代码实现均采用C语言

FIRST 建立频度链表来统计字符的频度

通过频度也就是权重来建立哈夫曼树，频度链表的建立可以使用链表来实现

int main()
{
    // 这里一定要给字符串分配空间
    char str[1000];
    ListNode *head = (ListNode *)malloc(sizeof(ListNode));
    head->next = NULL;
    ListNode *p = head;
    
    // 循环读取每一行输入
    while (fgets(str, 1000, stdin) != NULL)
    {
        char *s = str;
        while (*s != '\0')
        {
            int flag = 0;
            p = head;
            while (p->next != NULL)
            {
                if (p->next->c == *s)
                {
                    p->next->frequency++;
                    flag = 1;
                    break;
                }
                p = p->next;
            }
            if (flag == 0)
            {
                ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
                newNode->c = *s;
                newNode->frequency = 1;
                newNode->code = NULL;
                newNode->parent = NULL;
                newNode->left = NULL;
                newNode->right = NULL;
                newNode->next = NULL;
                p->next = newNode;
            }
            s++;
        }
    }
    
    // 为每个节点添加序号以记录输入顺序
    int inputOrder = 0;
    p = head->next;
    while (p != NULL) {
        p->parent = (struct ListNode *)(long)inputOrder++; // 借用parent指针临时存储顺序
        p = p->next;
    }
    
    // 按照从大到小的顺序排序频度链表，相同频度按输入顺序
    // 使用插入排序，它是稳定的排序算法
    ListNode *sorted = NULL;
    p = head->next;
    head->next = NULL;
    
    while (p != NULL) {
        ListNode *next = p->next;
        
        if (sorted == NULL || sorted->frequency < p->frequency) {
            // 插入到链表头部
            p->next = sorted;
            sorted = p;
        } else {
            // 找到合适的位置插入
            ListNode *current = sorted;
            while (current->next != NULL && 
                  (current->next->frequency > p->frequency || 
                  (current->next->frequency == p->frequency && 
                   (long)current->next->parent < (long)p->parent))) {
                current = current->next;
            }
            p->next = current->next;
            current->next = p;
        }
        
        p = next;
    }
    head->next = sorted;
    
    // 遍历输出
    p = head->next;
    while (p != NULL)
    {
        if (p->c == '\n')
        {
            printf("'\\n' %d\n", p->frequency);
        }
        else
        {
            printf("'%c' %d\n", p->c, p->frequency);
        }
        p = p->next;
    }
    
    // 释放内存
    p = head->next;
    while (p != NULL)
    {
        ListNode *temp = p;
        p = p->next;
        free(temp);
    }
    free(head);
    return 0;
}

注意：一般都使用头插法实现链表，原因如下： 头插法的时间复杂度为O(1)，而尾插法的时间复杂度为O(n)

SECOND 建立哈夫曼树并生成哈夫曼编码

由于代码较长，这里只展示关键部分。完整实现包括：

1. 频度统计（同上）
2. 构建哈夫曼树
3. 生成哈夫曼编码
4. 输出编码表

关键函数：

// 函数声明
void generateHuffmanCode(HuffmanTree *root);
void freeHuffmanTree(HuffmanTree *root);
void collectLeafNodes(HuffmanTree *root, ListNode **list);

生成哈夫曼编码

// 生成哈夫曼编码
void generateHuffmanCode(HuffmanTree *root)
{
    if (root == NULL)
        return;

    // 初始化根节点的编码
    if (root->parent == NULL)
    {
        root->code = (char *)malloc(sizeof(char));
        root->code[0] = '\0';
    }

    // 递归生成左右子树的编码
    if (root->left != NULL)
    {
        int codeLen = strlen(root->code);
        root->left->code = (char *)malloc((codeLen + 2) * sizeof(char));
        strcpy(root->left->code, root->code);
        root->left->code[codeLen] = '0';
        root->left->code[codeLen + 1] = '\0';
        generateHuffmanCode(root->left);
    }

    if (root->right != NULL)
    {
        int codeLen = strlen(root->code);
        root->right->code = (char *)malloc((codeLen + 2) * sizeof(char));
        strcpy(root->right->code, root->code);
        root->right->code[codeLen] = '1';
        root->right->code[codeLen + 1] = '\0';
        generateHuffmanCode(root->right);
    }
}

THIRD 解码

// 解码哈夫曼编码
void decodeHuffmanCode(HuffmanTree *root, char *encodedStr)
{
    if (root == NULL || encodedStr == NULL)
        return;

    // 特殊情况：如果只有一个节点
    if (root->left == NULL && root->right == NULL)
    {
        for (int i = 0; i < strlen(encodedStr); i++)
        {
            printf("%c", root->c);
        }
        return;
    }

    HuffmanTree *current = root;
    char *p = encodedStr;

    while (*p != '\0')
    {
        if (*p == '0')
        {
            current = current->left;
        }
        else if (*p == '1')
        {
            current = current->right;
        }

        // 如果到达叶子节点，输出字符并重新从根节点开始
        if (current->left == NULL && current->right == NULL)
        {
            printf("%c", current->c);
            current = root;
        }

        p++;
    }
}