concept

Huffman Coding, also known as Huffman Coding, is a Coding mode. Huffman Coding is a type of variable word length Coding (VLC). The method constructs the code word with the shortest average length of the different prefix completely according to the probability of character occurrence, which is sometimes called the optimal encoding and generally called.

Huffman thought

Take students’ grades

Table describes

The code description

if(sum < 60) result = "fail";else if(sum < 70) result = "pass";else if(sum < 80) result = "average";else if(sum < 90) result = "good";elseResult = "excellent";Copy the code

Binary tree description

In order to improve efficiency to generate more practical binary tree structure

Usually we use WPL (the tree’s weighted path length) to calculate quality. The weighted value is the proportion of students x the tree’s path to a given node

  • Before optimization: 1 * 5 + 2 * 15 + 3 * 40 + 4 * 30 + 4 * 10 = 315
  • Optimization: 5 * 3 + 15 * 3 + 40 * 2 + 30 * 2 + 10 * 2 = 220

And then optimize it

  • After optimization again: 40 * 1 + 30 * 1 + 15 * 2 + 10 * 3 + 5 * 4 = 205

The build process

  1. The sorting

  1. Build a tree

  1. The path of the left child is represented by 0, and the path of the right child is represented by 1

  1. Return new code

Code implementation

#include "string.h"
#include "stdio.h"
#include "stdlib.h"const int MaxValue = 10000; Const int MaxBit = 4; Const int MaxN = 10; Typedef struct HaffNode{int weight; int flag; int parent; int leftChild; int rightChild; }HaffNode; Typepedef struct Code {int bit[MaxBit]; // array int start; // Start index int weight; // Weight of character}Code; // Build Huffman tree according to the weight value; / /,4,5,7 {2} / / n = 4; void Haffman(int weight[],int n,HaffNode *haffTree){ int j,m1,m2,x1,x2; //1. Huffman tree initializes //n leaves. 2n-1for(int i = 0; i < 2*n-1; i++){if(i<n)
            haffTree[i].weight = weight[i];
        elsehaffTree[i].weight = 0; haffTree[i].parent = 0; haffTree[i].flag = 0; haffTree[i].leftChild = -1; haffTree[i].rightChild = -1; } //2. Construct n-1 non-leaf nodes of haffTreefor(int i = 0; i< n - 1; i++){ m1 = m2 = MaxValue; x1 = x2 = 0; / / 2,4,5,7for(j = 0; j< n + i; J++)// loop to find the two smallest values of ownership weight -- Morgan {if (haffTree[j].weight < m1 && haffTree[j].flag == 0)
            {
                m2 = m1;
                x2 = x1;
                m1 = haffTree[j].weight;
                x1 = j;
            } else if(haffTree[j].weight<m2 && haffTree[j].flag == 0) { m2 = haffTree[j].weight; x2 = j; HaffTree [x1]. Parent = n + I; haffTree[x1]. haffTree[x2].parent = n + i; HaffTree [x1]. Flag = 1; haffTree[x1]. haffTree[x2].flag = 1; HaffTree [n + I].weight = haffTree[x1].weight + haffTree[x2].weight; HaffTree [n + I]. LeftChild = x1; haffTree[n + i].rightChild = x2; Void HaffmanCode(HaffNode haffTree[], int n, {HaffNode haffTree[], int n, {HaffNode haffTree[], int n, {HaffNode haffTree[], int n, {HaffNode haffTree[], int n, {HaffNode haffTree[], int n, Code haffCode[]) { //1. Create a nodecd
    Code *cd= (Code * )malloc(sizeof(Code)); int child, parent; //2. Find the Huffman code of n leaf nodesfor(int i = 0; i<n; I++) {// count from 0cd->start = 0; // Get the character encoding the corresponding weightcd->weight = haffTree[i].weight; // when leaf I is child, child = I; // Find the parent of child; parent = haffTree[child].parent; // From the leaf to the rootwhile(parent ! = 0) {if (haffTree[parent].leftChild == child)
                cd->bit[cd->start] = 0; // The left child node encodes 0else
                cd->bit[cd->start] = 1; // Right child node encoding 1 // encoding incrementcd->start++; // The parent node becomes the child node. Parent = haffTree[child]. Parent; } int temp = 0;for (int j = cd->start - 1; j >= 0; j--){
            temp = cd->start-j-1;
            haffCode[i].bit[temp] = cd->bit[j]; } / /cd// Save the starting bit and weight of haffCode; haffCode[i].start =cd->start; HaffCode [I].weight =cd->weight;
    }
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, Huffman code! \n"); int i, j, n = 4, m = 0; // int weight[] = {2,4,5,7}; HaffNode *myHaffTree = malloc(sizeof(HaffNode)*2*n-1); Code *myHaffCode = malloc(sizeof(Code)*n); // If n > MaxN, it is out of bounds. Unable to handle.if (n>MaxN)
    {
        printf("Defined n out of bounds, modify MaxN!");
        exit(0); } //1. Build Haffman(weight, n, myHaffTree); HaffmanCode(myHaffTree, n, myHaffCode); / / 3.for (i = 0; i<n; i++)
    {
        printf("Weight = %d\n",myHaffCode[i].weight);
        for (j = 0; j<myHaffCode[i].start; j++)
            printf("%d",myHaffCode[i].bit[j]);
        m = m + myHaffCode[i].weight*myHaffCode[i].start;
         printf("\n");
    }
    printf("Huffman's WPS is:%d\n",m);

    return 0;
}

Copy the code

Running results: