文章插图
- 通信领域中信息的处理方式 3-赫夫曼编码
i like like like java do you like a java2、d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各个字符对应的个数
3、按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值构成赫夫曼树的步骤：
- 从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树
- 取出根节点权值最小的两颗二叉树
- 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
- 再将这颗新的二叉树，以根节点的权值大小 再次排序，不断重复 1-2-3-4 的步骤 ， 直到数列中，所有的数据都被处理，就得到一颗赫夫曼树
文章插图
4、根据赫夫曼树，给各个字符,规定编码 (前缀编码) ， 向左的路径为 0 向右的路径为 1，编码如下:
o: 1000 u: 10010 d: 100110 y: 100111 i: 101a : 110k: 1110 e: 1111j: 0000v: 0001l: 001 : 01(空格)5、按照上面的赫夫曼编码 ， 我们的
"i like like like java do you like a java" 字符串对应的编码为 (注意这里我们使用的无损压缩)1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110通过赫夫曼编码处理 长度为 133,且不会有多义性
6、长度为 ：
133说明:原来长度是359 , 压缩了 (359-133) / 359 = 62.9%此编码满足前缀编码, 即字符的编码都不能是其他字符编码的前缀 。不会造成匹配的多义性赫夫曼编码是无损处理方案（可以完全恢复）
注：这个赫夫曼树根据 排序方法不同，也可能不太一样，这样对应的 赫夫曼编码也不完全一样 ， 但是 wpl 是一样的，都是最小的, 最后生成的赫夫曼编码的长度是一样，比如: 如果我们让每次生成的新的二叉树总是排在权值相同的二叉树的最后一个，则生成的二叉树如下图，但是编码长度是不会变的，还是133
文章插图
3.3、创建赫夫曼树（数据压缩）将给出的一段文本 ， 比如
"i like like like java do you like a java"，根据前面的讲的赫夫曼编码原理，对其进行数据 压 缩 处 理，形 式 如"1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100 110111101111011100100001100001110"功能： 根据赫夫曼编码压缩数据的原理，需要创建
"i like like like java do you like a java" 对应的赫夫曼树思路:
(1) Node { data (存放数据)，weight (权值)， left和 right }(2) 得到
"i like like like java do you like a java"对应的 byte[] 数组(3)编写一个方法，将准备构建赫夫曼树的Node 节点放到 List, 形式 [Node[date=97 ,weight = 5], Node[]date=32,weight = 9]......],体现 d:1 y:1 u:1 j:2v:2o:2l:4k:4e:4 i:5a:5:9(4) 可以通过List 创建对应的赫夫曼树代码实现
import java.util.*;public class HuffmanCode {public static void main(String[] args) {String content = "i like like like java do you like a java";byte[] contentBytes = content.getBytes();System.out.println(contentBytes.length);//40List<Node> nodes = getNodes(contentBytes);System.out.println("nodes="+nodes);//测试创建的二叉树System.out.println("创建赫夫曼树：");Node huffmanTreeRoot = createHuffmanTree(nodes);System.out.println("前序遍历：");huffmanTreeRoot.preOrder();}//前序遍历的方法public static void preOrder(Node root){if (root != null){root.preOrder();}else {System.out.println("赫夫曼树为空");}}/**** @param bytes 接收字节数组* @return 返回的就是 List 形式[Node[date=97 ,weight = 5], Node[]date=32,weight = 9]......],*/private static List<Node> getNodes(byte[] bytes){//1.创建一个ArrayListArrayList<Node> nodes = new ArrayList<>();//遍历bytes,存储每一个byte出现的次数=》map[key,value]HashMap<Byte,Integer> counts = new HashMap<>();for (byte b: bytes) {Integer count = counts.get(b);if (count == null){//Map还没有这个数据counts.put(b,1);}else {counts.put(b,count+1);}}//把每个键值对转成一个Node对象,并加入到nodes集合//遍历mapfor (Map.Entry<Byte,Integer> entry : counts.entrySet()){nodes.add(new Node(entry.getKey(), entry.getValue()));}return nodes;}//通过list创建应的赫夫曼树private static Node createHuffmanTree(List<Node> nodes){while (nodes.size() > 1){//排序,从小到大Collections.sort(nodes);//取出第一棵最小的二叉树左节点Node leftNode = nodes.get(0);//取出第二棵最小的二叉树右节点Node rightNode = nodes.get(1);//创建一棵新的二叉树，它的根节点没有data，只有权值Node parent = new Node(null, leftNode.weight+ rightNode.weight);parent.left = leftNode;parent.right = rightNode;//将已经处理的两棵二叉树从nodes删除nodes.remove(leftNode);nodes.remove(rightNode);//将新的二叉树加入到nodesnodes.add(parent);}//nodes 最后的节点就是赫夫曼树的根节点return nodes.get(0);}}//创建Node,带数据和权值class Node implements Comparable<Node>{Byte data;//存放数据本身a===>97 ascii码int weight;//权值，表示字符出现的次数Node left;Node right;public Node(Byte data, int weight) {this.data = https://www.huyubaike.com/biancheng/data;this.weight = weight;}@Overridepublic int compareTo(Node o) {//从小到大排序return this.weight-o.weight;}public String toString() {return"Node [data = "https://www.huyubaike.com/biancheng/+ data +" weight=" + weight + "]";}//前序遍历public void preOrder() {System.out.println(this);if(this.left != null) {this.left.preOrder();}if(this.right != null) {this.right.preOrder();}}}
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 1 python-数据描述与分析
- 创造与魔法最新每日礼包兑换码是多少
- 企业运维 | MySQL关系型数据库在Docker与Kubernetes容器环境中快速搭建部署主从实践
- 驱动通信：通过PIPE管道与内核层通信
- 光与夜之恋双十一礼包怎么购买
- MES系统与ERP系统信息集成有哪些原则？
- 企业MES系统与ERP信息集成要素有哪些？
- 光与夜之恋钜惠嘉年华怎么买划算
- 补充部分---ScheduledThreadPoolExecutor类分析 线程池底层原理详解与源码分析
- 驱动开发：通过ReadFile与内核层通信
