哈夫曼树的应用
已知一个文件中仅有10个不同的字符，各字符出现的个数分别为100,150,180,200,260,300,350,390,400,500。试对这些符号重新编码，以压缩文件的规模，并求出其压缩后的规模以及压缩比（压缩前后的规模比）。 本帖最后由 isdkz 于 2023-4-26 22:16 编辑哈夫曼编码是一种基于哈夫曼树的数据压缩方法，通过给出现频率高的字符分配较短的编码，出现频率低的字符分配较长的编码，从而达到压缩数据的目的。这里我们已知文件中10个不同字符出现的个数，可以按照以下步骤构建哈夫曼树和进行哈夫曼编码。
1. 将这10个字符按照出现的次数作为权值构建10个叶子节点；
2. 从叶子节点中选取权值最小的两个节点组成一个新的节点，它们的权值之和作为新节点的权值；
3. 将这两个节点从叶子节点列表中删除，将新节点加入到列表中；
4. 重复步骤2-3，直到只剩下一个节点为止，这个节点就是哈夫曼树的根节点。
构建好哈夫曼树后，我们可以从根节点开始分配编码：向左子树分配0，向右子树分配1。这样，每个字符的哈夫曼编码就是从根节点到叶子节点的路径。
现在我们来计算压缩前的文件规模和压缩后的文件规模。假设原文件中的字符使用定长的8位二进制编码，那么压缩前的文件规模可以通过这个公式计算：
压缩前规模 = ∑(字符个数 * 字符编码长度)
假设压缩后的文件规模为：
压缩后规模 = ∑(字符个数 * 字符哈夫曼编码长度)
首先，我们需要得到每个字符的哈夫曼编码长度。这里只给出了字符的出现次数，我们无法直接得到具体的哈夫曼编码。但根据哈夫曼编码的特点，我们可以大致估计每个字符的哈夫曼编码长度：
字符1: 5位
字符2: 4位
字符3: 4位
字符4: 4位
字符5: 3位
字符6: 3位
字符7: 3位
字符8: 2位
字符9: 2位
字符10: 1位
然后，我们可以计算压缩前的文件规模：
压缩前规模 = (100+150+180+200+260+300+350+390+400+500) * 8 = 2730 * 8 = 21840 位
压缩后的文件规模：
压缩后规模 = 100 * 5 + 150 * 4 + 180 * 4 + 200 * 4 + 260 * 3 + 300 * 3 + 350 * 3 + 390 * 2 + 400 * 2 + 500 * 1 = 500 + 600 + 720 + 800 + 780 + 900 + 1050 + 780 + 800 + 500 = 6630 位
现在我们已经得到了压缩前后的文件规模，接下来我们计算压缩比：
压缩比 = (压缩前规模 - 压缩后规模) / 压缩前规模
压缩比 = (21840 - 6630) / 21840 ≈ 0.696
所以，通过哈夫曼编码，压缩后的文件规模大约为6630位，压缩比约为69.6%。这意味着经过哈夫曼编码，文件大小减小了约69.6%。 由于仅有10个不同的字符，我们可以使用3位二进制数字（000到101）来对其进行重新编码。这样可以表示2^3=8个可能的组合，正好可以覆盖10个字符。
以下是一种可能的重新编码方式：
字符 原始编码 重新编码
A 00000001 000
B 00000010 001
C 00000011 010
D 00000100 011
E 00000101 100
F 00000110 101
G 00000111 110
H 00001000 111000
I 00001001 111001
J 00001010 111010
其中最后三个字符的编码都使用了7位二进制数字，以确保所有字符都能得到唯一的编码。这样，每个字符的重新编码长度为3至7位之间。
对于原始数据中的每个字符，则替换为其对应的重新编码，并计算新文件的长度。这里假设将重新编码后的二进制数拼接成一个连续的字符串。
例如，如果原始数据为：ABCDAAAAACCCCGGGGIIIIIJIBBBBEFGHIJCFGEFGHGHHHDDDDDDDGGCCCIAAAAJJJJ
则替换后的编码为：0010111001111000000000100101011110110111101010101011110111111101100111011110101111001010101000111110111111011111101111101111001110101001100100010111011110
新文件的长度为1003 + 1503 + 1803 + 2003 + 2603 + 3003 + 3503 + 3903 + 4007 + 5007 = 9130位（1141.25字节）。
如果使用原始编码，则文件大小为10100 + 10150 + 10180 + 10200 + 10260 + 10300 + 10350 + 10 * 390 + 10400 + 10*500 = 3700字节。
因此，压缩比 (compression ratio) 约为 3700/1141.25 ≈ 3.24，即将原始数据压缩为大约三分之一的大小。
页:
[1]