哈夫曼编码及压缩率计算的C语言实现

太过爱你忘了你带给我的痛 2023-10-14 13:31 38阅读 0赞

### 哈夫曼编码及压缩率计算的C语言实现 ###

> 代码是最高级的浪漫

### 一，简介： ###

哈夫曼编码是一项神奇的黑科技，能够将数据高效地压缩和解压，为数据存储和传输带来了革命性的进步。在本技术博客中，我们将深入研究哈夫曼编码的工作原理和实现细节，并通过C语言代码演示其强大的数据压缩能力。探索哈夫曼编码的神奇世界，让你的数据更轻盈，节省存储空间，尽情享受黑科技的魅力。

### 二，实现逻辑： ###

从最小堆的使用到哈夫曼树的构建，我们将用通俗易懂的方式解释每个步骤，为读者提供一个完整的C语言实现示例。技术细节将一览无余，让你轻松掌握哈夫曼编码的奥秘。

### 三，函数介绍： ###

*  createNode: 构建哈夫曼树节点，存储字符和频率。
 *  createMinHeap: 创建一个空的最小堆，为哈夫曼树的构建奠定基础。
 *  swapNodes: 交换两个节点的位置，保持最小堆性质。
 *  minHeapify: 最小堆的向下调整，维持堆的稳定性。
 *  isSizeOne: 判断最小堆是否只有一个节点，确保算法正常运行。
 *  extractMin:从最小堆中提取频率最小的节点，关键步骤不容错过。
 *  insertMinHeap: 将节点插入到最小堆中，并维持堆性质，打造高效编码树。
 *  buildHuffmanTree: 构建哈夫曼树，通过字符频率构建编码树。
 *  printHuffmanCodes:
 *  打印哈夫曼编码，将构建的编码树输出为二进制编码，惊叹黑科技的魅力。
 *  calculateWPL:计算哈夫曼编码的平均码长（WPL），解密哈夫曼树的妙用。
 *  calculateTotalBits: 计算原始数据的总比特数，哈夫曼编码背后的数字王国。

### 四，哈夫曼树编码： ###

哈夫曼树编码采用前缀编码方式，将高频字符用短编码表示，低频字符用长编码表示，实现数据压缩。我们将解释哈夫曼编码的工作原理，为读者呈现编码树的构建过程，让你领略黑科技的魔力。

### 五，压缩率与WPL的实现和应用： ###

> 压缩率：介绍压缩率的概念，展示哈夫曼编码的高效压缩能力，让数据轻松瘦身。

> WPL（Weighted Path  
> Length）：解释WPL的计算方法，演示如何通过WPL评估哈夫曼编码的平均码长，更深入地理解黑科技的奥秘。

### 七，应用与前景： ###

探讨哈夫曼编码在现实生活中的应用，如图像、音频、视频文件的压缩，以及无损压缩领域的前景展望。让黑科技点亮未来的技术之路。

> 通过本文，你将领略哈夫曼编码的神奇魅力，掌握黑科技背后的技术精髓，让你的数据存储和传输更加高效和便捷。欢迎加入黑科技的世界，一起探索技术的无限可能。

### 八，代码介绍 ###

创建节点以及最小堆结构体

// 定义节点结构体
    struct Node {
        
        char data;
        unsigned freq;
        struct Node* left;
        struct Node* right;
    };
    
    // 定义最小堆的结构体
    struct MinHeap {
        
        unsigned size;
        unsigned capacity;
        struct Node** array;
    };

##### 1. createNode #####

作用：创建一个哈夫曼树节点。

Copy code
    // 定义节点结构体
    struct Node {
        
        char data;
        unsigned freq;
        struct Node* left;
        struct Node* right;
    };

##### 2. createMinHeap #####

作用：创建一个空的最小堆。

// 最小堆的结构体
    struct MinHeap {
        
        unsigned size;
        unsigned capacity;
        struct Node** array;
    };
    
    // 创建一个空的最小堆
    struct MinHeap* createMinHeap(unsigned capacity) {
        
        struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
        minHeap->size = 0;
        minHeap->capacity = capacity;
        minHeap->array = (struct Node**)malloc(capacity * sizeof(struct Node*));
        return minHeap;
    }

##### 3. swapNodes #####

作用：交换两个节点的位置。

// 交换两个节点
    void swapNodes(struct Node** a, struct Node** b) {
        
        struct Node* t = *a;
        *a = *b;
        *b = t;
    }

##### 4. minHeapify #####

作用：最小堆的向下调整，保持堆性质。

// 最小堆的向下调整
    void minHeapify(struct MinHeap* minHeap, int idx) {
        
        int smallest = idx;
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;
    
        if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq)
            smallest = left;
    
        if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]->freq)
            smallest = right;
    
        if (smallest != idx) {
        
            swapNodes(&minHeap->array[idx], &minHeap->array[smallest]);
            minHeapify(minHeap, smallest);
        }
    }

##### 5. isSizeOne #####

作用：判断最小堆是否只有一个节点。

// 判断最小堆是否只有一个节点
    int isSizeOne(struct MinHeap* minHeap) {
        
        return (minHeap->size == 1);
    }

##### 6. extractMin #####

作用：从最小堆中提取频率最小的节点。

// 从最小堆中提取最小值
    struct Node* extractMin(struct MinHeap* minHeap) {
        
        struct Node* temp = minHeap->array[0];
        minHeap->array[0] = minHeap->array[minHeap->size - 1];
        --minHeap->size;
        minHeapify(minHeap, 0);
        return temp;
    }

##### 7. insertMinHeap #####

作用：将节点插入到最小堆中，并保持堆性质。

// 插入节点到最小堆
    void insertMinHeap(struct MinHeap* minHeap, struct Node* node) {
        
        ++minHeap->size;
        int i = minHeap->size - 1;
        while (i && node->freq < minHeap->array[(i - 1) / 2]->freq) {
        
            minHeap->array[i] = minHeap->array[(i - 1) / 2];
            i = (i - 1) / 2;
        }
        minHeap->array[i] = node;
    }

##### 8. buildHuffmanTree #####

作用：构建哈夫曼树。

// 构建哈夫曼树
    struct Node* buildHuffmanTree(char data[], int freq[], int size) {
        
        struct Node *left, *right, *top;
    
        // 创建最小堆并插入所有节点
        struct MinHeap* minHeap = createMinHeap(size);
        for (int i = 0; i < size; ++i)
            insertMinHeap(minHeap, createNode(data[i], freq[i]));
    
        // 构建哈夫曼树
        while (!isSizeOne(minHeap)) {
        
            left = extractMin(minHeap);
            right = extractMin(minHeap);
    
            top = createNode('$', left->freq + right->freq);
            top->left = left;
            top->right = right;
    
            insertMinHeap(minHeap, top);
        }
    
        // 堆中的最后节点是根节点
        return extractMin(minHeap);
    }

##### 9. printHuffmanCodes #####

作用：打印哈夫曼编码。

// 打印哈夫曼编码
    void printHuffmanCodes(struct Node* root, int arr[], int top) {
        
        if (root->left) {
        
            arr[top] = 0;
            printHuffmanCodes(root->left, arr, top + 1);
        }
    
        if (root->right) {
        
            arr[top] = 1;
            printHuffmanCodes(root->right, arr, top + 1);
        }
    
        if (root->left == NULL && root->right == NULL) {
        
            printf("%c: ", root->data);
            for (int i = 0; i < top; ++i)
                printf("%d", arr[i]);
            printf("\n");
        }
    }

##### 10. calculateWPL #####

作用：计算哈夫曼编码的平均码长（WPL）。

// 计算哈夫曼编码的平均码长（WPL）
    int calculateWPL(struct Node* root, int depth) {
        
        if (root == NULL)
            return 0;
    
        if (root->left == NULL && root->right == NULL)
            return root->freq * depth;
    
        return calculateWPL(root->left, depth + 1) + calculateWPL(root->right, depth + 1);
    }

##### 11. calculateTotalBits #####

作用：计算原始数据的总比特数。

// 计算原始数据的总比特数
    int calculateTotalBits(int freq[], int size) {
        
        int totalBits = 0;
        for (int i = 0; i < size; ++i)
            totalBits += freq[i];
        return totalBits;
    }

> 以上函数实现了哈夫曼编码的构建和计算，同时也计算了哈夫曼编码的平均码长（WPL）以及压缩率。哈夫曼编码是一种经典的数据压缩算法，在实际应用中广泛用于无损压缩，如文本、图像和音频等领域。通过合理地构建哈夫曼树和生成哈夫曼编码，我们可以实现对数据的高效压缩，并在保持数据完整性的同时减少存储和传输成本。

#### 整体项目源码：(复制到任意C语言的编译内即可实现) ####

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    // 哈夫曼树节点结构
    struct Node {
        
        char data;
        unsigned freq;
        struct Node* left;
        struct Node* right;
    };
    
    // 创建一个哈夫曼树节点
    struct Node* createNode(char data, unsigned freq) {
        
        struct Node* node = (struct Node*)malloc(sizeof(struct Node));
        node->data = data;
        node->freq = freq;
        node->left = node->right = NULL;
        return node;
    }
    
    // 哈夫曼树的最小堆结构
    struct MinHeap {
        
        unsigned size;
        unsigned capacity;
        struct Node** array;
    };
    
    // 创建一个空的最小堆
    struct MinHeap* createMinHeap(unsigned capacity) {
        
        struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
        minHeap->size = 0;
        minHeap->capacity = capacity;
        minHeap->array = (struct Node**)malloc(capacity * sizeof(struct Node*));
        return minHeap;
    }
    
    // 交换两个节点
    void swapNodes(struct Node** a, struct Node** b) {
        
        struct Node* t = *a;
        *a = *b;
        *b = t;
    }
    
    // 最小堆的向下调整
    void minHeapify(struct MinHeap* minHeap, int idx) {
        
        int smallest = idx;
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;
    
        if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq)
            smallest = left;
    
        if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]->freq)
            smallest = right;
    
        if (smallest != idx) {
        
            swapNodes(&minHeap->array[idx], &minHeap->array[smallest]);
            minHeapify(minHeap, smallest);
        }
    }
    
    // 判断最小堆是否只有一个节点
    int isSizeOne(struct MinHeap* minHeap) {
        
        return (minHeap->size == 1);
    }
    
    // 从最小堆中提取最小值
    struct Node* extractMin(struct MinHeap* minHeap) {
        
        struct Node* temp = minHeap->array[0];
        minHeap->array[0] = minHeap->array[minHeap->size - 1];
        --minHeap->size;
        minHeapify(minHeap, 0);
        return temp;
    }
    
    // 插入节点到最小堆
    void insertMinHeap(struct MinHeap* minHeap, struct Node* node) {
        
        ++minHeap->size;
        int i = minHeap->size - 1;
        while (i && node->freq < minHeap->array[(i - 1) / 2]->freq) {
        
            minHeap->array[i] = minHeap->array[(i - 1) / 2];
            i = (i - 1) / 2;
        }
        minHeap->array[i] = node;
    }
    
    // 构建哈夫曼树
    struct Node* buildHuffmanTree(char data[], int freq[], int size) {
        
        struct Node *left, *right, *top;
    
        // 创建最小堆并插入所有节点
        struct MinHeap* minHeap = createMinHeap(size);
        for (int i = 0; i < size; ++i)
            insertMinHeap(minHeap, createNode(data[i], freq[i]));
    
        // 构建哈夫曼树
        while (!isSizeOne(minHeap)) {
        
            left = extractMin(minHeap);
            right = extractMin(minHeap);
    
            top = createNode('$', left->freq + right->freq);
            top->left = left;
            top->right = right;
    
            insertMinHeap(minHeap, top);
        }
    
        // 堆中的最后节点是根节点
        return extractMin(minHeap);
    }
    
    // 打印哈夫曼编码
    void printHuffmanCodes(struct Node* root, int arr[], int top) {
        
        if (root->left) {
        
            arr[top] = 0;
            printHuffmanCodes(root->left, arr, top + 1);
        }
    
        if (root->right) {
        
            arr[top] = 1;
            printHuffmanCodes(root->right, arr, top + 1);
        }
    
        if (root->left == NULL && root->right == NULL) {
        
            printf("%c: ", root->data);
            for (int i = 0; i < top; ++i)
                printf("%d", arr[i]);
            printf("\n");
        }
    }
    
    // 计算哈夫曼编码的平均码长（WPL）
    int calculateWPL(struct Node* root, int depth) {
        
        if (root == NULL)
            return 0;
    
        if (root->left == NULL && root->right == NULL)
            return root->freq * depth;
    
        return calculateWPL(root->left, depth + 1) + calculateWPL(root->right, depth + 1);
    }
    
    // 计算原始数据的总比特数
    int calculateTotalBits(int freq[], int size) {
        
        int totalBits = 0;
        for (int i = 0; i < size; ++i)
            totalBits += freq[i];
        return totalBits;
    }
    
    int main() {
        
        char data[] = {
        'a', 'b', 'c', 'd', 'e', 'f'};
        int freq[] = {
        5, 9, 12, 13, 16, 45};
        int size = sizeof(data) / sizeof(data[0]);
    
        struct Node* root = buildHuffmanTree(data, freq, size);
    
        printf("哈夫曼编码为:\n");
        int arr[100], top = 0;
        printHuffmanCodes(root, arr, top);
    
        int wpl = calculateWPL(root, 0);
        printf("平均码长 (WPL): %d\n", wpl);
    
        int totalBits = calculateTotalBits(freq, size);
        printf("原始数据总比特数: %d\n", totalBits);
    
        float compressionRatio = (float)totalBits / wpl;
        printf("压缩率: %.2f\n", compressionRatio);
    
        return 0;
    }

> 如果觉得有帮助就是点赞评论一下吧