Huffman树以及Huffman编码

Share

Huffman树是一种存储结构，由于国内有的资料翻译为哈夫曼或者是霍夫曼，这里为了简单（当然不是懒了）就是用英语Huffman代替。

解决Huffman树问题是典型的贪心算法问题。

贪心算法

贪心算法又叫贪婪算法，是指在对问题求解释，总是做出当前看来是最好的选择。

当一个问题具有以下性质时可以用贪心算法求解：每一步的局部最优解，同时也是整个问题的最优解。

如果一个问题可以用贪心算法解决，那么贪心算法是解决这个问题最好的方法。贪心算法一般比其他算法更有效。但是贪心算法不能总是被应用。

贪心算法有时也用来得到一个近似优化问题。例如，旅行商问题是一个NP问题。贪心的选择是选择最近的并且从当前城市每一步。

Huffman Code

关于什么是Huffman树以及Huffman编码我在以前写的这篇博客中介绍了

http://www.saberismywife.com/2016/10/17/树与二叉树（六）/

Huffman编码是一种无损数据压缩算法。在计算机数据处理中，Huffman编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用Huffman编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个比特。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。

构建Huffman编码主要包括两个部分：

  • 根据输入的字符串构建Huffman树
  • 遍历Huffman树并给每个字符分配编码

Huffman Tree又叫最优二叉树，指的是对于一组具有确定权值的叶子结点的具有最小路径长度的二叉树。

下面简单介绍一下基础名词

1
2
3
4
5
6
1.路径(Path)：从树中的一个结点到另一个结点之间的分支构成两个结点间的路径
2.路径长度(Path Length)：路径上的分支数
3.树的路径长度(Path Length of Tree)：从树的根结点到每个结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。
4.结点的权(Weight of Node)：在一些应用中，赋予树中结点的一个有实际意义的树。
5.结点的带权路径长度(Weight Path Length of Node)：从该结点到树的根结点的路径长度与该结点的权的乘积。
6.树的带权路径长度(Weight Path Length of Tree)：树中所有叶子结点的带权路径长度之和

构建Huffman树的步骤

即假设有n个字符，则构造出得哈夫曼树有n个叶子结点。n个字符的权值(频率)分别设为w1,w2,…,wn,则Huffman树的构造规则为:

  • 将w1,w2,…,wn看成是有n棵树的森林(每棵树仅有一个结点)；
  • 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
  • 从森林中删除选取的两棵树，并将新树加入森林；
  • 重复2、3步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树

具体实现

第一段代码是比较详细的，告诉大家具体的实现过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
#include <stdio.h>
#include <stdlib.h>

#define MAX_TREE_HT 100

// 一个Huffman树节点
struct MinHeapNode {
    
    char data;  // 输入的字符数组中的一个字符
    unsigned freq;  // 字符出现的次数
    struct MinHeapNode *left, *right;
    
};

// 最小堆: 作为优先队列使用
struct MinHeap {
    
    unsigned size;    // 最小堆元素的个数
    unsigned capacity;   //最大容量
    struct MinHeapNode **array;
    
};

//初始化一个最小堆节点
struct MinHeapNode* newNode(char data, unsigned freq) {
    
    struct MinHeapNode* temp =(struct MinHeapNode*) malloc(sizeof(struct MinHeapNode));
    temp->left = temp->right = NULL;
    temp->data = data;
    temp->freq = freq;
    return temp;
    
}

// 创建一个容量为capacity 的最小堆
struct MinHeap* createMinHeap(unsigned capacity) {
    
    struct MinHeap* minHeap =(struct MinHeap*) malloc(sizeof(struct MinHeap));
    minHeap->size = 0;  // current size is 0
    minHeap->capacity = capacity;
    minHeap->array =(struct MinHeapNode**)malloc(minHeap->capacity * sizeof(struct MinHeapNode*));
    return minHeap;
    
}



//  swap 两个堆节点
void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) {
    
    struct MinHeapNode* 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) {
        swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);
        minHeapify(minHeap, smallest);
    }
    
}

//检测堆的大小是否为1
int isSizeOne(struct MinHeap* minHeap) {
    
    return (minHeap->size == 1);
    
}

//取得堆中最小的节点
struct MinHeapNode* extractMin(struct MinHeap* minHeap) {
    
    struct MinHeapNode* 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 MinHeapNode* minHeapNode) {
    
    ++minHeap->size;
    int i = minHeap->size - 1;
    while (i && minHeapNode->freq < minHeap->array[(i - 1)/2]->freq) {
        minHeap->array[i] = minHeap->array[(i - 1)/2];
        i = (i - 1)/2;
    }
    minHeap->array[i] = minHeapNode;
    
}

//构建一个最小堆
void buildMinHeap(struct MinHeap* minHeap) {
    
    int n = minHeap->size - 1;
    int i;
    for (i = (n - 1) / 2; i >= 0; --i)
        minHeapify(minHeap, i);
    
}

void printArr(int arr[], int n) {
    
    int i;
    for (i = 0; i < n; ++i)
        printf("%d", arr[i]);
    printf("\n");
    
}

// 检测是否是叶子节点
int isLeaf(struct MinHeapNode* root) {
   
    return !(root->left) && !(root->right) ;
   
}

// 创建一个容量为 size的最小堆，并插入 data[] 中的元素到最小堆
struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) {
    
    struct MinHeap* minHeap = createMinHeap(size);
    for (int i = 0; i < size; ++i)
        minHeap->array[i] = newNode(data[i], freq[i]);
    minHeap->size = size;
    buildMinHeap(minHeap);
    return minHeap;
    
}

// 构建Huffman树
struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) {
   
    struct MinHeapNode *left, *right, *top;

    // 第 1步 : 创建最小堆.
    struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size);
    //知道最小堆只有一个元素
    while (!isSizeOne(minHeap)) {
        
        // 第二步: 取到最小的两个元素
        left = extractMin(minHeap);
        right = extractMin(minHeap);
        // Step 3: 根据两个最小的节点，来创建一个新的内部节点
        // '$' 只是对内部节点的一个特殊标记，没有使用
        top = newNode('$', left->freq + right->freq);
        top->left = left;
        top->right = right;
        insertMinHeap(minHeap, top);
    }
    // 第4步: 最后剩下的一个节点即为跟节点
    return extractMin(minHeap);
    
}

// 打印Huffman编码
void printCodes(struct MinHeapNode* root, int arr[], int top) {
    
    if (root->left) {
        arr[top] = 0;
        printCodes(root->left, arr, top + 1);
    }
    if (root->right) {
        arr[top] = 1;
        printCodes(root->right, arr, top + 1);
    }
    // 如果是叶子节点就打印
    if (isLeaf(root)) {
        printf("%c: ", root->data);
        printArr(arr, top);
    }
}

// 构建Huffman树，并遍历打印该Huffman树
void HuffmanCodes(char data[], int freq[], int size) {
    
    //  构建Huffman树
    struct MinHeapNode* root = buildHuffmanTree(data, freq, size);
    // 打印构建好的Huffman树
    int arr[MAX_TREE_HT], top = 0;
    printCodes(root, arr, top);
}


int main() {
    
    char arr[MAX_TREE_HT]; 
    int freq[MAX_TREE_HT]; 
    while (i < MAX_TREE_HT && scanf("%c", &arr[i])) {
        i++;
    }
    while (j < MAX_TREE_HT && scanf("%d", &freq[j])) {
        j++;
    }
    if (i != j) {
        printf("输入不正确\n");
        return 0;
    }
    int size = sizeof(arr)/sizeof(arr[0]);
    HuffmanCodes(arr, freq, size);
    return 0;
    
}

第二段就是比较简单的并且含有解码函数的过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <stdio.h>
#include<stdlib.h>

#define MAXBIT      100
#define MAXVALUE  10000
#define MAXLEAF     30
#define MAXNODE    MAXLEAF*2 -1

typedef struct {

    int bit[MAXBIT];
    int start;
    
} HCodeType;        //编码结构体 
typedef struct {

    int weight;
    int parent;
    int lchild;
    int rchild;
    int value;
    
} HNodeType;        //结点结构体

//构造一颗Huffman树
void HuffmanTree (HNodeType HuffNode[MAXNODE],  int n) {
    // i、j： 循环变量，m1、m2：构造Huffman树不同过程中两个最小权值结点的权值，
     x1、x2：构造Huffman树不同过程中两个最小权值结点在数组中的序号。
    int i, j, m1, m2, x1, x2;
    //初始化存放哈夫曼树数组 HuffNode[] 中的结点
    for (i=0; i<2*n-1; i++) {
        HuffNode[i].weight = 0;//权值
        HuffNode[i].parent =-1;
        HuffNode[i].lchild =-1;
        HuffNode[i].rchild =-1;
        HuffNode[i].value=i; //实际值，可根据情况替换为字母
    }
    
    //输入 n 个叶子结点的权值
    for (i=0; i<n; i++) {
        printf ("Please input weight of leaf node %d: \n", i);
        scanf ("%d", &HuffNode[i].weight);
    }
    
    //循环构造 Huffman 树
    for (i=0; i<n-1; i++) {
        m1=m2=MAXVALUE;     //m1、m2中存放两个无父结点且结点权值最小的两个结点
        x1=x2=0;
        //找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树
        for (j=0; j<n+i; j++) {
            if (HuffNode[j].weight < m1 && HuffNode[j].parent==-1) {
                m2=m1;
                x2=x1;
                m1=HuffNode[j].weight;
                x1=j;
            }
            else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1) {
                m2=HuffNode[j].weight;
                x2=j;
            }
        }
        //设置找到的两个子结点 x1、x2 的父结点信息
        HuffNode[x1].parent  = n+i;
        HuffNode[x2].parent  = n+i;
        HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight;
        HuffNode[n+i].lchild = x1;
        HuffNode[n+i].rchild = x2;
        
        printf ("x1.weight and x2.weight in round %d: %d, %d\n", i+1, HuffNode[x1].weight, HuffNode[x2].weight);  /* 用于测试 */
        printf ("\n");
    }
}

//解码
void decodeing(char string[],HNodeType Buf[],int Num) {

    int i,tmp=0,code[1024];
    int m=2*Num-1;
    char *nump;
    char num[1024];
    for(i=0;i<strlen(string);i++) {
        if(string[i]=='0')
            num[i]=0;
        else
            num[i]=1;
    }
    i=0;
    nump=&num[0];
    
    while(nump<(&num[strlen(string)])) {
        tmp=m-1;
        while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1)) {
            if(*nump==0) {
                tmp=Buf[tmp].lchild ;
            }
            else
                tmp=Buf[tmp].rchild;
            nump++;
        }
        printf("%d",Buf[tmp].value);
    }
}

int main(void) {

    HNodeType HuffNode[MAXNODE];            //定义一个结点结构体数组
    HCodeType HuffCode[MAXLEAF],  cd;       //定义一个编码结构体数组， 同时定义一个临时变量来存放求解编码时的信息
    int i, j, c, p, n;
    char pp[100];
    printf ("Please input n:\n");
    scanf ("%d", &n);
    HuffmanTree (HuffNode, n);
    
    for (i=0; i < n; i++) {
        cd.start = n-1;
        c = i;
        p = HuffNode[c].parent;
        while (p != -1) {   //父结点存在
            if (HuffNode[p].lchild == c)
                cd.bit[cd.start] = 0;
            else
                cd.bit[cd.start] = 1;
            cd.start--;        //求编码的低一位
            c=p;
            p=HuffNode[c].parent;    //设置下一循环条件
        }
        
        //保存求出的每个叶结点的Huffman编码和编码的起始位
        for (j=cd.start+1; j<n; j++) {
            HuffCode[i].bit[j] = cd.bit[j];
        }
        HuffCode[i].start = cd.start;
    }
    
    //输出已保存好的所有存在编码的Huffman编码
    for (i=0; i<n; i++) {
        printf ("%d 's Huffman code is: ", i);
        for (j=HuffCode[i].start+1; j < n; j++) {
            printf ("%d", HuffCode[i].bit[j]);
        }
        printf(" start:%d",HuffCode[i].start);
        printf ("\n");
    }
    printf("Decoding?Please Enter code:\n");
    scanf("%s",&pp);
    decodeing(pp,HuffNode,n);
    return 0;
}