赫夫曼树的python实现 赫夫曼树的构造过程

文章目录

• 赫夫曼树

• 1. 赫夫曼树介绍：
• 2. 赫夫曼树的创建过程：
• 3. 赫夫曼树的性质：
• 4. 赫夫曼编码：
• 5. 赫夫曼树与赫夫曼编码的c语言代码实现：

赫夫曼树

1. 赫夫曼树介绍：

赫夫曼树是一种带权重的树，它的结点中有一项数据是权重信息，根据结点中的权重生成一棵二叉树，结点的权生越大，离根结点就越近。

2. 赫夫曼树的创建过程：

1、获取值和权重信息、。

2、根据值和权重信息生成若干棵度为0的树，存储到小根堆中形成森林。

3、从小根堆获取到两棵权重最轻的树，把这两棵树的权重相加生成一个新的只有权重的空白树，它的左子树指向权重较小的树，右子树指向权较大的树，然后再把新的树添加到小根堆。

4、重复步骤3，直到小根堆中只有一棵树，它就是创建出的赫夫曼树的根结点。

3. 赫夫曼树的性质：

1、赫夫曼树只有前序遍历才有意义。

2、赫夫曼树的非叶子结点都是只有权重信息，而没有值的空白结点，反之，所有叶子结点都是既有权重又有值的结点。

3、结点的权重越大，结点的高度编号就是越小，离根结点就越近，前遍历访问的速度就越快，反之结点的权重越小，结点的高度编号就越大，离根结点就是越远，前序遍历访问的速度就越慢。

4. 赫夫曼编码：

从赫夫曼树的根结点出发进行前序遍历，遍历过程中把往左子树遍历记作0，把往右子树遍历记作1，到达叶子结点时，走过的路径所形成的01信息被称为赫夫曼编码，使用这种编码就访问到赫夫曼树根结点出发访问到叶子结点中的数据。

这种编码的特点就是权重越大的数据，生成的编码就越短，权重越小的数据，生成的编码就越长。

这种编码可以用于提高数据传输效率，还有文件的压缩和解压。

5. 赫夫曼树与赫夫曼编码的c语言代码实现：

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#include <unistd.h>
#include <math.h>
#include "heap.h"

typedef struct CharCode
{
	uint32_t code; // 赫夫曼编码
	uint8_t cnt;   // 编码位数
} CharCode;

// 赫夫曼编码数组
CharCode code_arr[128];

// 赫夫曼树结点
typedef struct TreeNode
{
	uint8_t data;	 // 数据
	uint32_t weight; // 权重
	struct TreeNode *left;
	struct TreeNode *right;
} TreeNode;

// 用于比较结点权重的回调函数，给小堆根使用的
int node_cmp(const void *p1, const void *p2)
{
	if (((TreeNode *)p1)->weight > ((TreeNode *)p2)->weight)
		return 1;
	if (((TreeNode *)p1)->weight < ((TreeNode *)p2)->weight)
		return -1;
	return 0;
}

TreeNode *create_node(char data, size_t weight)
{
	TreeNode *node = malloc(sizeof(TreeNode));
	node->data = data;
	node->weight = weight;
	node->left = NULL;
	node->right = NULL;
	return node;
}

void _create_code(TreeNode *root, uint8_t path, uint32_t code, uint8_t cnt)
{
	if (NULL == root)
		return;

	code = (code << 1) + path;

	// 到达叶子结点时，记录赫夫曼编码
	if (0 != root->data)
	{
		code_arr[root->data].code = code;
		code_arr[root->data].cnt = cnt;
		return;
	}

	_create_code(root->left, 0, code, cnt + 1);
	_create_code(root->right, 1, code, cnt + 1);
}

// 生成赫夫曼编码
void create_code(TreeNode *root)
{
	_create_code(root->left, 0, 0, 1);
	_create_code(root->right, 1, 0, 1);
}

// 生成赫夫曼树
TreeNode *init_tree(char *val_arr, size_t *weight_arr, size_t len)
{
	// 创建存储森林的小根堆
	Heap *heap = create_heap(len, node_cmp);
	for (int i = 0; i < len; i++)
	{
		push_heap(heap, create_node(val_arr[i], weight_arr[i]));
	}

	// 直到堆中只有一个结点，这就是赫夫曼树的根结点
	while (1 < size_heap(heap))
	{
		// 从堆中获取一个权重最小的树,当作左子树
		TreeNode *left = top_heap(heap);
		pop_heap(heap);

		// 从堆中获取一个权重最小的树，当作右子树
		TreeNode *right = top_heap(heap);
		pop_heap(heap);

		// 左右子树的权重相加生成一个新的空白结点
		TreeNode *root = create_node(0, left->weight + right->weight);
		root->left = left;
		root->right = right;

		// 新的结点加入小根堆
		push_heap(heap, root);
	}

	TreeNode *root = top_heap(heap);
	destroy_heap(heap);

	return root;
}

// 压缩文件
int compress_file(const char *oldfile, const char *newfile)
{
	FILE *rfp = fopen(oldfile, "r");
	if (NULL == rfp)
	{
		printf("%s文件打开失败！\n", oldfile);
		return -1;
	}

	FILE *wfp = fopen(newfile, "w");
	if (NULL == wfp)
	{
		printf("压缩文件失败！\n");
		return -1;
	}

	fseek(rfp, 0, SEEK_END);
	fprintf(wfp, "%ld\n", ftell(rfp));
	rewind(rfp);

	uint8_t buf[4096], cnt = 0;
	uint32_t data = 0, offset = 0xffffffff;

	int ret;
	while (ret = fread(buf, 1, sizeof(buf), rfp))
	{
		for (int i = 0; i < ret; i++)
		{
			if (32 > cnt + code_arr[buf[i]].cnt)
			{
				data = (data << code_arr[buf[i]].cnt) + code_arr[buf[i]].code;
				cnt += code_arr[buf[i]].cnt;
			}
			else
			{
				// 32-cnt 计算出data中还余多少位
				data = (data << (32 - cnt)) + (code_arr[buf[i]].code >> (code_arr[buf[i]].cnt - (32 - cnt)));
				fwrite(&data, 1, sizeof(data), wfp);

				data = (~(offset << (code_arr[buf[i]].cnt - (32 - cnt)))) & code_arr[buf[i]].code;
				cnt = code_arr[buf[i]].cnt - (32 - cnt);
			}
		}
	}

	data = data << (32 - cnt);
	fwrite(&data, 1, sizeof(data), wfp);

	fclose(rfp);
	fclose(wfp);
	return 0;
}

int dp_file(TreeNode *root, const char *filename, const char *oldfile)
{
	FILE *rfp = fopen(filename, "r");
	if (NULL == rfp)
	{
		printf("解压失败！\n");
		return -1;
	}

	long filesize;
	fscanf(rfp, "%ld\n", &filesize);

	FILE *wfp = fopen(oldfile, "w");
	if (NULL == wfp)
	{
		printf("解压失败！\n");
		return -1;
	}

	unsigned int data;
	TreeNode *node = root;
	while (fread(&data, 1, sizeof(data), rfp))
	{
		for (int i = 0; i < 32; i++)
		{
			if ((data << i) & 0x80000000)
				node = node->right;
			else
				node = node->left;
			if (0 != node->data)
			{
				fwrite(&node->data, 1, 1, wfp);
				node = root;
			}
		}
	}
	fclose(rfp);
	fclose(wfp);

	return truncate(oldfile, filesize);
}

int main(int argc, const char *argv[])
{
	char val_arr[] = {9, 10, 12, 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};

	size_t weight_arr[] = {16468, 29797, 15, 173045, 243, 916, 8025, 11, 24, 571, 1177, 8000, 8016, 16626, 517, 7384, 1855, 8775, 13269, 5276, 4848, 3603, 2032, 2593, 886, 3292, 805, 1219, 1360, 563, 4162, 943, 1248, 1032, 104, 241, 8184, 2145, 6653, 4971, 12331, 3990, 4196, 4170, 9197, 92, 856, 8929, 5168, 8000, 8562, 7509, 116, 11576, 10356, 12187, 4616, 1346, 2660, 3251, 1510, 859, 213, 808, 195, 16, 48314, 739, 35359, 8675, 21905, 27939, 79328, 25790, 8803, 17961, 48009, 361, 2336, 22424, 11352, 47506, 34893, 13171, 470, 40014, 35301, 57634, 16370, 4914, 6093, 4605, 6933, 2144, 440, 577, 435, 11};

	// 数据+权重构建出森林存储到小根堆里面
	TreeNode *root = init_tree(val_arr, weight_arr, sizeof(val_arr));
	create_code(root);
	printf("%d\n", compress_file("/usr/include/elf.h", "test.dat"));
	printf("%d\n", dp_file(root, "test.dat", "test.h"));
	return 0;
}