哈弗曼树

哈弗曼树(最优二叉树)

带权路径长度最小(WPL)的树(权值越大的节点离根节点越近)

WPL(带权路径长度)

WPL(带权路径长度):树中所有叶子节点的带权路径长度之和

WPL计算举例(X的系数就是从这个节点到根节点的有几个节点)

流程分析

步骤:

1. 排序
2. 挑选最小的两个 生成新的节点
3. 两个步骤不停的交替执行(排序之后就选最小的两个生成新的然后把新的节点放到以前的序列排序)

手写流程:

哈弗曼树代码实现(List范型)

步骤分析

//先使用数组中所有元素创建若干个二叉树(只有一个节点)
//排序
//取出来权值最小的两个二叉树
//创建一颗新的二叉树
//将取出来权值最小的两个二叉树移除    
//放入原来的二叉树集合中

Node类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Node implements Comparable<Node>{  //要使用排序要实现Comparable类
    int value;
    Node left;
    Node right;

    public Node(int value){
        this.value=value;
    }

    @Override
    public int compareTo(Node o) {
        return -(this.value-o.value);  //自己设置输出node节点的值
    }

    @Override
    public String toString() {
        return "Node{" + "value=" + value + '}';
    }

}

Test类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Test {
    public static void main(String[] args) {
        int[] arr=new int[]{3,7,8,29,5,11,23,14};
        System.out.println("原来的数组: "+Arrays.toString(arr));  //输出原来的数组
        Node node=createHuffmanTree(arr);  //调用方法
    }

    public static Node createHuffmanTree(int[] arr){
    //先使用数组中所有元素创建若干个二叉树(只有一个节点)
        List<Node> nodes=new ArrayList<>();
            for(int value:arr){
                nodes.add(new Node(value));
            }
        //循环处理
        while(nodes.size()>1){
          //排序
             Collections.sort(nodes);
            System.out.println("每一次剩下的数: "+nodes);
          //取出来权值最小的两个二叉树
            Node left=nodes.get(nodes.size()-1);
            Node right=nodes.get(nodes.size()-2);
          //创建一颗新的二叉树
            Node parent=new Node(left.value+right.value);
          //将取出来权值最小的两个二叉树移除
            nodes.remove(left);
            nodes.remove(right);
          //将新的放入原来的二叉树集合中
            nodes.add(parent);
        }
        System.out.println(nodes);
        return null;
    }

}

总结

1. 使用list<Node>范型去存储数组元素
2. 使用for循环add方法添加数组元素为节点
3. 使用Collections类的sort方法对范型对象排序
4. 获取范型对象的最后两个二叉树
5. 创建新的二叉树(值为第四步两个二叉树的值)
6. 通过remove方法移除
7. 通过add添加第五步新创建的二叉树
8. 可以直接输出nodes(最后只剩下结果的那个二叉树)

执行过程分析:

哈弗曼编码原理分析

通讯领域信息处理的三种方式

1. 定长编码(将对应的数字用ASCII码替换)
2. 不定长编码(将字母的出现频率计算出来 然后给固定的数字代表)
    容易出现分不清到底是代替哪个字母 
3. 哈夫曼编码(将字母出现频率计算出来 然后排序 选出最小两个生成新的 排序)
    然后左边的路权值给0 / 右边的给1

三种方式举例

定长编码

将对应的字母的翻译成ASCII码 – ASCII码翻译对应二进制

不定长编码

将对应单词的出现频率排序 – 出现最多的给0(依次给二进制)

哈夫曼编码

将对应单词的出现频率排序 – 出现最多的给0(依次给二进制) – 编写哈弗曼树(左路径给0/右路径给1) – 不同路径找到不同单词的值

哈弗曼编码代码实现

步骤分析

1. 统计字符数并且排序
2. 创建哈夫曼树
3. 创建哈夫曼树编码表
4. 编码

Node类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Node implements Comparable<Node>{
    Byte data;  //n:11 c:1 这种形式
    int weight;  //权值
    Node left;
    Node right;
    public Node(Byte data,int weight){
        this.data=data;
        this.weight=weight;
    }

    //实现接口方法 (获取值)
    @Override
    public int compareTo(Node o) {
        return o.weight-this.weight;
    }

    //输出node信息
    @Override
    public String toString() {
        return "Node{" + "data=" + data + ", weight=" + weight + ", left=" + left + ", right=" + right + '}';
    }

}

TestHuffmantreeCoDE类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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
127
128
129
130
131
132
133
134
135
136
137
138
public class TestHuffmantreeCoDE {

    public static void main(String[] args) {
     //输入一个叫msg的字符串  让他使用哈夫曼编码
        String msg="can you can a can as a can canner can a can.";
            byte[] bytes=msg.getBytes();
        //进行哈夫曼编码压缩
         byte[] b=huffmanZip(bytes);
            System.out.println("压缩前"+bytes.length);
            System.out.println("压缩后"+b.length);
    }

    //进行哈夫曼编码(主)
    private static byte[] huffmanZip(byte[] bytes) {
        //1. 先统计每一个byte出现的个数  放入一个集合
            List<Node> nodes=getNodes(bytes);  //调用方法
        //2. 创建哈弗曼树
            Node tree=createHuffmanTree(nodes);  //创建一个叫tree的哈弗曼树
        //3. 创建哈夫曼编码表
            Map<Byte,String> huffCodes=getCodes(tree);
        //4. 编码(将每个byte替换成map里面的string)
            byte[] b=zip(bytes,huffCodes);

        return b;
    }

    //4. 将每个byte替换成Map集合里面的string即可
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffCodes) {
        StringBuilder sb=new StringBuilder();
        //把需要压缩的byte数组处理成一个二进制的字符串
        for(byte i:bytes){
            sb.append(huffCodes.get(i));  //获取到键
        }
        //定义长度
        int len;
        if(sb.length()%8==0){
            len=sb.length()/8;
        }else{
            len=sb.length()/8+1;  //%8之后的余数还可以凑成一个
        }

        //用于存储压缩后的byte
            byte[] by=new byte[len];
        //记录新byte的位置
            int index=0;

        for(int i=0;i<sb.length();i+=8){
            String strByte;
            if(i+8>sb.length()){
                strByte = sb.substring(i); // 不截取 只显示当前的
            }else{
                strByte = sb.substring(i, i + 8); // 截取8位为一个单元
            }
            byte byt=(byte)Integer.parseInt(strByte,2); //将2进制其转成10进制
          //将截取出来的8位的单元转成10进制最后存到之前创建的by数组
            by[index++]=byt;
        }

        return by;
    }

    //在第三步中用于存储路径
    static  StringBuilder sb=new StringBuilder();
    //在第三步中用于存储哈弗曼编码
    static Map<Byte,String> huffCodes=new HashMap<>();

    //3. 创建哈弗曼树编码表
    private static Map<Byte, String> getCodes(Node tree) {
        if(tree==null){
            return null;
        }
        getCodes(tree.left,"0",sb);   //左边赋0
        getCodes(tree.right,"1",sb);  //右边赋1
        return huffCodes;
    }

    //3.1 给左右节点递归传递下面的值
    private static void getCodes(Node node, String code, StringBuilder sb) {
      //新建stringbuilder的sb2对象
        StringBuilder sb2=new StringBuilder(sb);
      //新的stringbuilder对象添加进去 0 / 1
        sb2.append(code);
      //
        if(node.data==null){  //不是节点
            getCodes(node.left,"0",sb2);
            getCodes(node.right,"1",sb2);
        }
        else{  //直到最后一个叶子节点(底部)
            huffCodes.put(node.data,sb2.toString()); //将输出 n:00 a:01 c:02这种形式
        }
    }

    //2. 创建哈夫曼树
    private static Node createHuffmanTree(List<Node> nodes) {
        //
        while(nodes.size()>1){
            //排序
            Collections.sort(nodes);
            //取出两个权值最小的二叉树
                Node left=nodes.get(nodes.size()-1);
                Node right=nodes.get(nodes.size()-2);
            //创建新的二叉树
                Node parent=new Node(null,left.weight+right.weight);  //新创建的没有值 权值是下面两个相加
            //把之前的两棵二叉树设置为新创建的二叉树的子树
                parent.left=left;
                parent.right=right;
            //把之前的两棵二叉树从之前的删除
                nodes.remove(left);
                nodes.remove(right);
            //把新创建的二叉树放入集合中
                nodes.add(parent);
        }
        return nodes.get(0); //返回第0个(最大的那个)
    }

    //1. 把byte数组转化为node集合
    private static List<Node> getNodes(byte[] bytes) {
        List<Node> nodes=new ArrayList<>();
        //使用map数组存储每一个byte出现了多少次
            Map<Byte,Integer> counts=new HashMap<>();  //map对象叫counts   c:11 a:12 d:123 这种形式
        //s统计每一个byte出现次数
            for(byte i:bytes){
                Integer count = counts.get(i);  //统计对应每个byete出现的次数为count
                if(count==null){
                    counts.put(i,1);  //如果第一次出现  出现次数为1
                }
                else{
                    counts.put(i,count+1);  //不是第一次出现 直接出现次数+1
                }
            }
        //把每一个键值对转为一个node对象
            for(Map.Entry<Byte,Integer> i:counts.entrySet()){      //map集合遍历的一种方式
                nodes.add(new Node(i.getKey(),i.getValue()));
            }
         return null;
    }

}

哈夫曼编码解码

实现思路

1. 把byte数组转为一个二进制的字符串(使用异或补齐八位)
2. 将字符串按照指定的赫夫曼编码进行解码
    2.1 使用map将赫夫曼树编码的键值交换(现在是反向通过value查找)
    2.2 创建集合存储解码之后的数字
    2.3 处理字符串(按照0 01 11这种形式转换为 99 95这种数字)
    2.4 将存储解码的集合转为数组

解码的类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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
  //解码
   private static byte[] decode(Map<Byte, String> huffCodes2, byte[] bytes) {
       StringBuilder sb=new StringBuilder();
       //1. 把byte数组转为一个二进制的字符串
           for(int i=0;i<bytes.length;i++){
               byte b=bytes[i];
               boolean flag=(i==bytes.length-1);
               sb.append(byteToBitstr(!flag,b));  //不断地添加对应的二进制字符串
           }
       //2. 将字符串按照指定的赫夫曼编码进行解码
           //把赫夫曼编码的键值对进行交换(反向)
               Map<String,Byte> map=new HashMap<>();
               for(Map.Entry<Byte,String> entry:huffCodes.entrySet()){
                   map.put(entry.getValue(),entry.getKey());
               }
       //创建一个集合 用于存byte
           List<Byte> list=new ArrayList<>();

       //处理字符串(前缀编码不重复)
           for(int i=0;i<sb.length();){
               int count=1;
               boolean flag=true; //确定几位是一个判断的 (1 11 111这种)
            //截取一个byte
                 while(flag){
                   String key=sb.substring(i,i+count);  //用key去map找对应的
                   Byte b=map.get(key);
                   if(b==null){
                       count++;  //没截取到 就往下放一位找
                   }else{
                       flag=false; //截取到 就不让截取
                   }
               }
           }

        //把集合转为数组
           byte[] b=new byte[list.size()];   //[96,98,98,...]  转为数组{96,98,98,...}
           for(int i=0;i<b.length;i++){
               b[i]=list.get(i);
           }

       return b;
   }

//需要将所需要的8位截取出来
   public static String byteToBitstr(boolean flag,byte b) {
       int temp = b;
       if (flag) {
           temp |= 256; //异或
       }
       String str = Integer.toBinaryString(temp);
       if (flag) {
           return str.substring(str.length() - 8);  //取出来后八位
       }else{
           return str;  //只取出来自己的东西
       }
       
   }

哈夫曼编码压缩文件

实现原理

1. 创建一个输入流
2. 创建一个和输入流指向的文件大小一样的byte数组
3. 读取文件内容;
4. 读取结束后关闭输入流
5. 进行哈夫曼编码进行编码
6. 创建输出流
  6.1 将压缩后的byte数组写入文件
  6.2 将哈夫曼编码表写入文件
  6.3 关闭输出流

具体方法

main方法:

1
2
3
4
//进行哈夫曼压缩文件
      String src="1.bmp";  //压缩前的文件
      String dst="2.zip";  //压缩后的文件
          zipFile(src,dst);  //调用压缩方法

压缩的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static  void zipFile(String src,String dst)throws IOException {
     //1. 创建一个输入流
         InputStream is=new FileInputStream(src);  //使用输入流获取文件内容
     //2. 创建一个和输入流指向的文件大小一样的byte数组
         byte[] b=new byte[is.available()];
     //3. 读取文件内容
         is.read(b);
     //4. 读取结束后关闭
         is.close();
     //5. 进行哈夫曼编码进行编码
         byte[] bytezip=huffmanZip(b);  //调用方法
     //6. 创建输出流
         OutputStream os=new FileOutputStream(dst);
         ObjectOutputStream oos=new ObjectOutputStream(os);
       //6.1 将压缩后的byte数组写入文件
           oos.writeObject(bytezip);
       //6.2 将哈夫曼编码表写入文件
           oos.writeObject(huffCodes);
       //6.3 关闭流
           os.close();
           oos.close();

   }

哈夫曼编码解压文件

实现原理

1. 创建一个输入流
2. 读取byte数组     (解压给byte数组的)
3. 读取哈夫曼编码表  (解压给byte数组的)
4. 关闭流
5. 调用解码方法
6. 创建一个输出流
7. 写出数据
8. 关闭输出流

具体方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//解压
   public static void unZip(String src,String dst) throws IOException, ClassNotFoundException {
       //1. 创建一个输入流
           InputStream is=new FileInputStream("2.zip");  //使用输入流获取文件内容
           ObjectInputStream ois =new ObjectInputStream(is);
       //2. 读取byte数组
           byte[] b= (byte[]) ois.readObject();
       //3. 读取哈夫曼编码表
           Map<Byte,String> codes=(Map<Byte, String>) ois.readObject();
       //4. 关闭流
           ois.close();
           is.close();
       //5. 解码
           byte[] bytes = decode(codes, b);
       //6. 创建一个输出流
            OutputStream os=new FileOutputStream(dst);
       //7. 写出数据
            os.write(bytes);
       //8. 关闭输出流
            os.close();
   }

哈夫曼编码完整代码(Node不展示)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
public class TestHuffmanCode {

	public static void main(String[] args) {
//		String msg="can you can a can as a can canner can a can.";
//		byte[] bytes = msg.getBytes();
//		//进行赫夫曼编码压缩
//		byte[] b = huffmanZip(bytes);
//		//使用赫夫曼编码进行解码
//		byte[] newBytes = decode(huffCodes,b);
//		System.out.println(new String(newBytes));
		String src="1.bmp";
		String dst="2.zip";
//		try {
//			zipFile(src, dst);
//		} catch (IOException e) {
//			e.printStackTrace();
//		}
		try {
			unZip("2.zip", "3.bmp");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	/**
	 * 文件的解压
	 * @param src
	 * @param dst
	 * @throws Exception 
	 */
	public static void unZip(String src,String dst) throws Exception {
		//创建一个输入流
		InputStream is  = new FileInputStream("2.zip");
		ObjectInputStream ois = new ObjectInputStream(is);
		//读取byte数组
		byte[] b = (byte[]) ois.readObject();
		//读取赫夫曼编码表
		Map<Byte, String> codes = (Map<Byte, String>) ois.readObject();
		ois.close();
		is.close();
		//解码
		byte[] bytes = decode(codes, b);
		//创建一个输出流
		OutputStream os  = new FileOutputStream(dst);
		//写出数据
		os.write(bytes);
		os.close();
	}
	
	/**
	 * 压缩文件
	 * @param src
	 * @param dst
	 * @throws IOException
	 */
	public static void zipFile(String src,String dst) throws IOException {
		//创建一个输入流
		InputStream is = new FileInputStream(src);
		//创建一个和输入流指向的文件大小一样的byte数组
		byte[] b = new byte[is.available()];
		//读取文件内容
		is.read(b);
		is.close();
		//使用赫夫曼编码进行编码
		byte[] byteZip = huffmanZip(b);
		//输出流
		OutputStream os = new FileOutputStream(dst);
		ObjectOutputStream oos = new ObjectOutputStream(os);
		//把压缩后的byte数组写入文件
		oos.writeObject(byteZip);
		//把赫夫曼编码表写入文件
		oos.writeObject(huffCodes);
		oos.close();
		os.close();
	}
	
	/**
	 * 使用指定的赫夫曼编码表进行解码
	 * @param huffCodes2
	 * @param b
	 * @return
	 */
	private static byte[] decode(Map<Byte, String> huffCodes, byte[] bytes) {
		StringBuilder sb = new StringBuilder();
		//把byte数组转为一个二进制的字符串
		for(int i=0;i<bytes.length;i++) {
			byte b = bytes[i];
			//是否是最后一个。
			boolean flag = (i==bytes.length-1);
			sb.append(byteToBitStr(!flag,b));
		}
		//把字符串按照指定的赫夫曼编码进行解码
		//把赫夫曼编码的键值对进行调换
		Map<String, Byte> map = new HashMap<>();
		for(Map.Entry<Byte, String> entry:huffCodes.entrySet()) {
			map.put(entry.getValue(), entry.getKey());
		}
		//创建一个集合，用于存byte
		List<Byte> list = new ArrayList<>();
		//处理字符串
		for(int i=0;i<sb.length();) {
			int count=1;
			boolean flag = true;
			Byte b=null;
			//截取出一个byte
			while(flag) {
				String key = sb.substring(i, i+count);
				b = map.get(key);
				if(b==null) {
					count++;
				}else {
					flag=false;
				}
			}
			list.add(b);
			i+=count;
		}
		//把集合转为数组
		byte[] b = new byte[list.size()];
		for(int i=0;i<b.length;i++) {
			b[i]=list.get(i);
		}
		return b;
	}
	
	private static String byteToBitStr(boolean flag,byte b) {
		int temp=b;
		if(flag) {
			temp|=256;
		}
		String str = Integer.toBinaryString(temp);
		if(flag) {
			return str.substring(str.length()-8);
		}else {
			return str;
		}
	}

	/**
	 * 进行赫夫曼编码压缩的方法
	 * @param bytes
	 * @return
	 */
	private static byte[] huffmanZip(byte[] bytes) {
		//先统计每一个byte出现的次数，并放入一个集合中
		List<Node> nodes = getNodes(bytes);
		//创建一颗赫夫曼树
		Node tree = createHuffmanTree(nodes);
		//创建一个赫夫曼编码表
		Map<Byte, String> huffCodes = getCodes(tree);
		//编码
		byte[] b = zip(bytes,huffCodes);
		return b;
	}
	
	/**
	 * 进行赫夫曼编码
	 * @param bytes
	 * @param huffCodes2
	 * @return
	 */
	private static byte[] zip(byte[] bytes, Map<Byte, String> huffCodes) {
		StringBuilder sb = new StringBuilder();
		//把需要压缩的byte数组处理成一个二进制的字符串
		for(byte b:bytes) {
			sb.append(huffCodes.get(b));
		}
		//定义长度
		int len;
		if(sb.length()%8==0) {
			len=sb.length()/8;
		}else {
			len=sb.length()/8+1;
		}
		//用于存储压缩后的byte
		byte[] by = new byte[len];
		//记录新byte的位置
		int index = 0;
		for(int i=0;i<sb.length();i+=8) {
			String strByte;
			if(i+8>sb.length()) {
				strByte = sb.substring(i);
			}else {
				strByte = sb.substring(i, i+8);
			}
			byte byt = (byte)Integer.parseInt(strByte, 2);
			by[index]=byt;
			index++;
		}
		return by;
	}

	//用于临时存储路径
	static StringBuilder sb = new StringBuilder();
	//用于存储赫夫曼编码
	static Map<Byte, String> huffCodes = new HashMap<>();
	/**
	 * 根据赫夫曼树获取赫夫曼编码
	 * @param tree
	 * @return
	 */
	private static Map<Byte, String> getCodes(Node tree) {
		if(tree==null) {
			return null;
		}
		getCodes(tree.left,"0",sb);
		getCodes(tree.right,"1",sb);
		return huffCodes;
	}

	private static void getCodes(Node node, String code, StringBuilder sb) {
		StringBuilder sb2 = new StringBuilder(sb);
		sb2.append(code);
		if(node.data==null) {
			getCodes(node.left, "0", sb2);
			getCodes(node.right, "1", sb2);
		}else {
			huffCodes.put(node.data, sb2.toString());
		}
	}

	/**
	 * 创建赫夫曼树
	 * @param nodes
	 * @return
	 */
	private static Node createHuffmanTree(List<Node> nodes) {
		while(nodes.size()>1) {
			//排序
			Collections.sort(nodes);
			//取出两个权值最低的二叉树
			Node left = nodes.get(nodes.size()-1);
			Node right = nodes.get(nodes.size()-2);
			//创建一颗新的二叉树
			Node parent = new Node(null, left.weight+right.weight);
			//把之前取出来的两颗二叉树设置为新创建的二叉树的子树
			parent.left=left;
			parent.right=right;
			//把前面取出来的两颗二叉树删除
			nodes.remove(left);
			nodes.remove(right);
			//把新创建的二叉树放入集合中
			nodes.add(parent);
		}
		return nodes.get(0);
	}

	/**
	 * 把byte数组转为node集合
	 * @param bytes
	 * @return
	 */
	private static List<Node> getNodes(byte[] bytes) {
		List<Node> nodes = new ArrayList<>();
		//存储每一个byte出现了多少次。
		Map<Byte, Integer> counts = new HashMap<>();
		//统计每一个byte出现的次数
		for(byte b:bytes) {
			Integer count = counts.get(b);
			if(count==null) {
				counts.put(b, 1);
			}else {
				counts.put(b, count+1);
			}
		}
		//把每一个键值对转为一个node对象
		for(Map.Entry<Byte, Integer> entry:counts.entrySet()) {
			nodes.add(new Node(entry.getKey(), entry.getValue()));
		}
		return nodes;
	}

}

赏

×

纯属好玩

扫码支持
扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦

本文标题:哈弗曼树

文章作者:Larkkkkkkk

发布时间:2020年04月22日 - 20时06分

最后更新:2020年04月29日 - 22时12分

原始链接:https://larkkkkkkk.github.io/2020/04/22/%E5%93%88%E5%BC%97%E6%9B%BC%E6%A0%91/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 哈弗曼树(最优二叉树)
    1. 1.1. WPL(带权路径长度)
  2. 2. 流程分析
  3. 3. 哈弗曼树代码实现(List范型)
    1. 3.1. 步骤分析
    2. 3.2. Node类
    3. 3.3. Test类
    4. 3.4. 总结
  4. 4. 哈弗曼编码原理分析
    1. 4.1. 通讯领域信息处理的三种方式
    2. 4.2. 三种方式举例
      1. 4.2.1. 定长编码
      2. 4.2.2. 不定长编码
      3. 4.2.3. 哈夫曼编码
  5. 5. 哈弗曼编码代码实现
    1. 5.1. 步骤分析
    2. 5.2. Node类
    3. 5.3. TestHuffmantreeCoDE类
  6. 6. 哈夫曼编码解码
    1. 6.1. 实现思路
    2. 6.2. 解码的类
  7. 7. 哈夫曼编码压缩文件
    1. 7.1. 实现原理
    2. 7.2. 具体方法
  8. 8. 哈夫曼编码解压文件
    1. 8.1. 实现原理
    2. 8.2. 具体方法
  9. 9. 哈夫曼编码完整代码(Node不展示)
,