那些做测评的网站好,seo搜狗排名,中国最新消息军事方面的,wordpress php apache目录
一、哈夫曼树的基本概念
二、哈夫曼树的构造算法
2.1 - 哈夫曼树的构造过程
2.2 - 哈夫曼树的存储表示
2.3 - 算法实现
三、哈夫曼编码
3.1 - 哈夫曼编码的主要思想
3.2 - 哈夫曼编码的性质
3.3 - 算法实现 一、哈夫曼树的基本概念
哈夫曼树的定义#xff0c;涉…目录
一、哈夫曼树的基本概念
二、哈夫曼树的构造算法
2.1 - 哈夫曼树的构造过程
2.2 - 哈夫曼树的存储表示
2.3 - 算法实现
三、哈夫曼编码
3.1 - 哈夫曼编码的主要思想
3.2 - 哈夫曼编码的性质
3.3 - 算法实现 一、哈夫曼树的基本概念
哈夫曼树的定义涉及路径、路径长度、权等概念下面先给出这些概念的定义然后再介绍哈夫曼树。 路径从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。 路径长度路径上的分支数目称作路径长度。 树的路径长度从树根到每一结点的路径长度之和。 权赋予某个实体的一个量对实体的某个或某些属性的数值化描述。在数据结构中实体有结点元素和边关系两大类所以对应有结点权和边权。结点权和边权具体代表什么意义由具体情况决定。如果在一棵树中的结点上带有权值则对应就有带权树等概念。 结点的带权路径长度从树根到该结点的路径长度与该结点上权值的乘积。 树的带权路径长度树中所有叶子结点的带权路径长度之和通常记作 。
在含有 n 个叶子结点的二叉树中每个叶子结点的权值为 则其中 WPL 最小的二叉树称作最优二叉树或哈夫曼Huffman树。
例如下图所示的 3 棵二叉树中都含有 4 个叶子结点 a、b、c、d分别带权 7、5、2、4。 其中 (c) 树的带权路径长度最小可以验证它恰为哈夫曼树。
哈夫曼树中具有不同权值的叶子结点的分布有什么特点呢从上面的例子中可以直观地发现在哈夫曼树中权值越大的结点离根结点越近。根据这个特点哈夫曼最早给出了一个构造哈夫曼树的方法称哈夫曼算法。 二、哈夫曼树的构造算法
2.1 - 哈夫曼树的构造过程 根据给定的 n 个权值 构造 n 棵只有根结点的二叉树这 n 棵二叉树构成一个森林 FForest。 在森林 F 中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 在森林 F 中删除这两棵树同时将新得到的二叉树加入 F 中。 重复 2 和 3直到 F 中只含一棵树为止这棵树便是哈夫曼树。
在构造哈夫曼树时首先选择权值小的结点这样保证权值大的结点离根结点较近这样一来在计算树的带权路径长度时自然会得到最小带权路径长度这种生成算法是一种典型的贪心法。
例如下图所示为上图 (c) 所示的哈夫曼树的构造过程。其中根结点上标注的数字是所赋的权。 注意哈夫曼树并不唯一但 WPL 必然相同且最优。 2.2 - 哈夫曼树的存储表示
typedef struct HTNode
{int weight; // 结点的权值int parent; // 结点的双亲的下标int left; // 结点的左孩子的下标int right; // 结点的右孩子的下标
}HTNode;
typedef struct HTree
{HTNode* data;int size;
}HTree;
哈夫曼树中的各结点存储在 data 指向的一个大小为 2n - 1 的动态分配的数组中。 解释 1n 个叶子结点进行 n - 1 次合并生成 n - 1 个度为 2 的新结点所以总结点数 N 为 2n - 1。 解释 2因为哈夫曼树中没有度为 1 的结点所以一棵有 n 个叶子结点的哈夫曼树总共有 2n - 1 结点即 N N0 N1 N2 2N0 - 1 2n - 1。 将叶子结点集中存储在 data[0] ~ data[n - 1] 中将非叶子结点存储在 data[n] ~ data[2n - 2] 中。 2.3 - 算法实现
构造哈夫曼树算法的实现可以分为两大部分 初始化首先动态申请 2n - 1 个单元然后循环 2n - 1 次将所有单元中结点的双亲、左孩子、右孩子的下标都初始化为 -1如果是前 n 个单元还要初始化这 n 个单元中叶子结点的权值。 创建树循环 n - 1 次通过 n - 1 次的选择、删除与合并来创建哈夫曼树。
HuffmanTree.c
#include HuffmanTree.h
#include stdlib.h
// 在 HT-data[0] ~ HT-data[end] 中选择两个双亲的下标为 -1 且权值最小的结点
// 并通过输出型参数 pMinIndex1 和 pMinIndex2 返回它们在 HT-data 中的下标
void Select(HTree* HT, int end, int* pMinIndex1, int* pMinIndex2)
{int min1 INT_MAX;for (int i 0; i end; i){if (HT-data[i].parent -1 HT-data[i].weight min1){min1 HT-data[i].weight;*pMinIndex1 i;}}int min2 INT_MAX;for (int i 0; i end; i){if (i ! *pMinIndex1 HT-data[i].parent -1 HT-data[i].weight min2){min2 HT-data[i].weight;*pMinIndex2 i;}}
}
HTree* CreateHuffmanTree(int* weight, int n)
{// 初始化HTree* HT (HTree*)malloc(sizeof(HTree));HT-data (HTNode*)malloc(sizeof(HTNode) * (2 * n - 1));HT-size 2 * n - 1;for (int i 0; i 2 * n - 1; i){if (i n)HT-data[i].weight weight[i];
HT-data[i].parent -1;HT-data[i].left -1;HT-data[i].right -1;}// 创建树for (int i n; i 2 * n - 1; i){int minIndex1, minIndex2;// 选择Select(HT, i - 1, minIndex1, minIndex2); // 删除HT-data[minIndex1].parent i;HT-data[minIndex2].parent i;// 合并HT-data[i].left minIndex1;HT-data[i].right minIndex2;HT-data[i].weight HT-data[minIndex1].weight HT-data[minIndex2].weight;}return HT;
}
Test.c
#include HuffmanTree.h // 包含了哈夫曼树的存储表示以及函数声明
#include stdio.h
#include stdlib.h
void PreOrder(HTree* HT, int rootIndex)
{if (rootIndex -1)return;
printf(%d , HT-data[rootIndex].weight);PreOrder(HT, HT-data[rootIndex].left);PreOrder(HT, HT-data[rootIndex].right);
}
void DestroyHuffmanTree(HTree* HT)
{free(HT-data);HT-data NULL;HT-size 0;
}
int main()
{int weight[8] { 5, 29, 7, 8, 14, 23, 3, 11 };HTree* HT CreateHuffmanTree(weight, 8);PreOrder(HT, HT-size - 1);// 100 42 19 8 3 5 11 23 58 29 29 14 15 7 8printf(\n);DestroyHuffmanTree(HT);return 0;
} 三、哈夫曼编码
3.1 - 哈夫曼编码的主要思想
在数据通信、数据压缩问题中需要将数据文件转换成二进制字符 0、1 组成的二进制串称之为编码。
假设待压缩的数据为 abcdabcdaaaaabbbdd数据包含 18 个字符其中只有 a(7 个)、b(5 个)、c(2 个)、d(4 个) 四种字符如果采用等长编码每个字符编码取两位即可编码总长度为 36 位。下表所示为一种等长编码方案。
字符编码a00b01c10d11
但这并非最优的编码方案因为每个字符出现的频率不同如果在编码时考虑字符出现的频率使频率高的字符采用尽可能短的编码频率低的字符采用稍长的编码来构造一种不等长编码则会获得更好的空间效率这也是文件压缩技术的核心思想。下表所示为一种不等长编码方案采用这种编码方案编码总长度为 35 位。
字符编码a0b10c110d111
但是对于不等长编码如果设计得不合理便会给解码带来困难。例如对于下表所示的另一种不等长编码方案。
字符编码a0b01c010d111
采用该编码方案后上述数据编码后为 00101111100101111100000010101111111。但是这样的编码数据无法翻译例如传过去的字符串中前 4 个字符的子串 0010 就可有不同的译法或是 aba或是 ac。因此若要设计长度不等的编码必须满足一个条件任何一个字符的编码都不是另一个字符的编码的前缀最左子串。
那么如何设计有效的用于数据压缩的二进制编码呢我们可以利用哈夫曼树来设计。第二个表格所示的编码是以字符 a、b、c、d 在数据串 abcdabcdaaaaabbbdd 中出现的次数 7、5、2、4 为权值构造下图所示的哈夫曼树约定左分支标记为 0右分支标记为 1则根结点到每个叶子结点路径上的 0、1 序列即为相应字符的编码。 a、b、c、d 的哈夫曼编码分别为 0、10、110 和 111。 3.2 - 哈夫曼编码的性质 性质一哈夫曼编码是前缀编码。 前缀编码如果在一个编码方案中任一个编码都不是其他任何编码的前缀最左子串则称编码是前缀编码。 证明哈夫曼编码是从根结点到叶子结点路径上的编码序列由树的特点可知若路径 A 是另一条路径 B 的左部分则 B 经过了 A则 A 的终点一定不是叶子结点。而哈夫曼编码对应路径的终点一定为叶子结点因此任一哈夫曼编码都不会与任意其他哈夫曼编码的前缀部分完全重叠因此哈夫曼编码是前缀编码。 性质二哈夫曼编码是最优前缀编码。 对于包含 n 个字符的数据文件分别以它们出现次数为权值构造哈夫曼树则利用该树对应的哈夫曼编码对文件进行编码能使文件压缩后对应的二进制文件的长度最短。、 证明由哈夫曼树的构造算法可知出现次数较多的字符对应的编码较短这便直观地说明了该定理是成立的。 3.3 - 算法实现
在构造哈夫曼树之后求哈夫曼编码的主要思想是依次以叶子结点出发向上回溯至根结点位置。回溯时走左分支则生成代码 0走右分支则生成代码 1。
由于每个哈夫曼编码是变长编码因此使用一个字符指针数组来存放每个字符编码串的首地址。
#include HuffmanTree.h
#include stdlib.h
#include string.hchar** CreateHuffmanCode(HTree* HT)
{int n (HT-size 1) / 2;char** HC (char**)malloc(sizeof(char*) * n);char* tmp (char*)malloc(sizeof(char) * n); // 字符编码的长度一定小于 ntmp[n - 1] \0;// 逐个求 n 个字符的哈夫曼编码for (int i 0; i n; i){int pos n - 2;int cur i;int parent HT-data[i].parent;while (parent ! -1){if (HT-data[parent].left cur)tmp[pos--] 0;elsetmp[pos--] 1;// 向上回溯cur parent;parent HT-data[parent].parent;}HC[i] (char*)malloc(sizeof(char) * (n - 1 - pos));strcpy(HC[i], tmp[pos 1]);}free(tmp);tmp NULL;return HC;
}
