哈夫曼树，哈夫曼编码
哈夫曼树
1.历史
首先是为了实现高效编码，在空间和整体效率方面寻求最优解。然后利用数据结构中的树型结构进一步发现构建这样的二叉树能够实现最优编码方案。
2.概念
设有n个权值对应的n个叶子节点，在构建一棵二叉树时，则称该树为带权路径长度最小的二叉树。这种特性使其成为最优二叉树，在数据结构领域具有最高的效率水平
1. 1. 二叉树
2. 2. 带权的节点为叶子节点
3. 3. 树的带权路径长度最小相关概念：
1. 路径：一个节点到另一个节点之间的分支构成这两个节点之间的路径
2. 路径的长度：路径上的分支数目之和
3. 树的路径长度：根节点到每个节点的路径长度之和
4. 在树结构中，每个节点所具有的加权路径长度定义为其自根节点至该节点经过的所有边上的权重之和
5. 树的带权路径长度：根节点到每个叶子节点的带权路径长度的和 （wpl）
6. 权值：出现的概率（根据实际情况统计而来的）
3. 实现
构建 ： 使权值越大的节点，路径长度越小（越靠近根节点）
步骤：
1. 从森林中选择两棵具有最小根部权重的树木，并将其设作左子和右子的基础；随后构造一个新的二叉tree结构；最后重新计算该binary tree 根结点的新权重，并将其设定为此两children结点权重之总和。
2. 在森林中删除这两棵树，并把新构建的树加入森林
3. 重复上诉两部，直到只有一棵树
4. 注意点：
相同的带权节点可以构成多颗哈夫曼树
通常情况下，在构建哈夫曼树的过程中，建议将新构建的树放置在所有具有相同概率的数据之后进行合并操作。这种做法有助于减少平均码长差异，并使编码得到的结果会更加接近于等长编码方案。值得注意的是，无论采用何种构建策略，最终生成的所有哈夫曼树都会具有相同的编码效率（即相同的wpl值）。
4. 应用
哈夫曼编码
1. 在数据通信过程中，在每个字符出现时会被转换为二进制编码的形式表示，并采用0、1码的不同排列组合来标识不同的字符；同时，在制定编码规范时需要遵循一定的基本规定
发送和解读的一致性和唯一性
编码长度尽可能短
实现
1. 等长编码 ：解读简单，但是不短
2. 不等长编码：可以做到尽可能的短，但是不一定满足唯一性
3. 前缀编码：基于非等长的编码体系中所采用的一种数据压缩方法，在这种体系下设计出一组码本（即各个码字），其特点是没有任何一个码字是另一个码字的最前面部分
1. 字符的使用频率作为叶子节点的权值构建一颗哈夫曼树
2. 以根节点作为起点，在二叉树中左分支标记为0、右分支标记为1。每个叶子节点的编码即为其从根节点到该叶子路径上的各分支依次排列的结果。
1. 静态哈夫曼编码
以下：为了优化性能需求，在处理大规模的数据时需要对源数据进行反复扫描整个数据集：通过计算源数据的频率分布，并利用构建好的哈夫曼树对源数据进行最优编码。
2. 动态哈夫曼编码
基于动态更新的哈夫曼树结构，在对后续添加的一个字符进行编码时，则是由对前t个字符构建的过程推导出的结果（涉及对哈夫曼树结构进行相应的调整）。
无丢失的数据压缩方法中，在"可逆"的情形下（即"可逆性"），经过编码处理后的数据可以通过解码操作恢复出原始的信息；而在"不可逆"的情形下（即"不可逆性"），编码过程中的某些信息会被丢失或无法恢复）
1. 背景：Unicode编码 每个字用2个字节表示，ascii编码 1个字节（byte）， 1byte = 8bit
2. 思路：具体而言，在哈夫曼编码的实际应用中，压缩文件的过程主要涉及对文件中各字符频率进行统计。接着为每个字符设计相应的编码方案。最后将这些字符按照其对应的哈夫曼编码格式进行逐字节存储。
用二进制描述代替每个字符
高频字符采用较短的编码长度,而罕见字符则采用较长的编码长度.这样一来平均码长会降低(因为高频字符占据更多权重),这种设计确保了总体编码效率最大化)
-
信息熵（Shannon entropy）：去除冗余后的平均不确定性 ，数据压缩能达到的最大效率是基于其自身的 -》 从而使得相同或相似的信息占用更少的空间
步骤：
统计要压缩的文件中的字符
对统计的字符进行排序
根据字符以及统计得到的每个字符出现的次数构建哈夫曼树
通过构建的哈夫曼树得到每个字符的哈夫曼编码
将文件的哈夫曼编码写入压缩文件
设置配置文件存储源（字符及其频率/编码对应关系），供解压使用
解压缩
1. 步骤
读取配置文件，重新构造哈夫曼树
读取压缩问题 （用编码对应的字符逐个代替）
- 判定
1. 通过构造哈夫曼树，使得总的判定次数最少
校验
1. 哈夫曼编码能够通过提取文件的关键属性来实现信息的有效编码。通过分析这些编码特征，我们可以对文件的一致性进行全面评估。
代码实现
package com.test.business; import com.google.common.collect.Lists; import com.google.common.collect.Maps; import lombok.Builder; import lombok.Data; import java.util.Comparator; import java.util.List; import java.util.Map; import java.util.stream.Collectors; public class HuffmanTreeTest { ``@Data ``@Builder ``static class HuffmanNode{ ``int weight ; ``int parent; ``HuffmanNode left; ``HuffmanNode right; ``String code; ``String character; ``boolean selected; ``} ``//统计字符串的字符和权重 ``public static List<HuffmanNode> getCharacterAndWeight(String content){ ``content = content.trim(); ``Map<String,Integer> characterIntegerMap = Maps.newHashMap(); ``for (``int i=``0``; i<content.length(); i++) { ``String c = String.valueOf(content.charAt(i)); ``if (characterIntegerMap.containsKey(c)) { ``characterIntegerMap.put(c, characterIntegerMap.get(c)+``1``); ``}``else { ``characterIntegerMap.put(c,``1``); ``} ``} ``List<HuffmanNode> huffmanNodes = Lists.newArrayList(); ``characterIntegerMap.forEach((key,value)->{ ``HuffmanNode node = HuffmanNode.builder().weight(value).character(key).build(); ``huffmanNodes.add(node); ``}); ``return huffmanNodes.stream() ``.sorted(Comparator.comparing(HuffmanNode::getWeight)) ``.collect(Collectors.toList()); ``} ``public static HuffmanNode createTree(List<HuffmanNode> huffmanNodes){ ``// 从节点列表中选取两个最新的节点构成一颗新树 ``HuffmanNode min1 = getUsefulMin(huffmanNodes,``0``); ``HuffmanNode min2 = getUsefulMin(huffmanNodes,``1``); ``if (min1 != ``null && min2 == ``null``) ``return min1; ``HuffmanNode newNode = HuffmanNode.builder() ``.left(min1) ``.right(min2) ``.code(``""``) ``.weight(min1.getWeight()+min2.getWeight()) ``.build(); ``// 将新树加入节点列表 ``huffmanNodes.add(newNode); ``huffmanNodes = huffmanNodes.stream() ``.sorted(Comparator.comparing(HuffmanNode::getWeight)) ``.collect(Collectors.toList()); ``return createTree(huffmanNodes); ``} ``public static HuffmanNode getUsefulMin(List<HuffmanNode> huffmanNodes, ``int n) { ``for (``int i = n; i<huffmanNodes.size(); i++) { ``if (! huffmanNodes.get(i).isSelected()) { ``huffmanNodes.get(i).setSelected(``true``); ``return huffmanNodes.get(i); ``} ``} ``return null``; ``} ``// 获得哈夫曼编码 ``public static Map<String,String> getCode(HuffmanNode huffmanNode,Map<String,String> codeMap){ ``if (huffmanNode != ``null``) { ``if (huffmanNode.getLeft()!=``null``) { ``huffmanNode.getLeft().setCode(huffmanNode.getCode()+``"0"``); ``getCode(huffmanNode.getLeft(),codeMap); ``} ``if (huffmanNode.getRight()!=``null``) { ``huffmanNode.getRight().setCode(huffmanNode.getCode()+``"1"``); ``getCode(huffmanNode.getRight(),codeMap); ``} ``if (huffmanNode.getCharacter() != ``null``){ ``codeMap.put(huffmanNode.getCharacter(),huffmanNode.getCode()); ``} ``} ``return codeMap; ``} ``// 编码 ``public static String encode (Map<String ,String> codeMap,String content) { ``String code = ``""``; ``for (``int i=``0 ;i<content.length(); i++) { ``code += codeMap.get(String.valueOf(content.charAt(i))) + ``" "``; ``} ``return code; ``} ``public static void main(String arg[]) { ``String content = ``"hellowwordo"``; ``List<HuffmanNode> huffmanNodes = getCharacterAndWeight(content); ``HuffmanNode huffmanTree = createTree(huffmanNodes); ``Map<String,String> codeMap = Maps.newHashMap(); ``codeMap = getCode(huffmanTree,codeMap); ``System.out.println(codeMap); ``System.out.println(encode(codeMap,content)); ``} } |
|---|