树结构入门教程-赫夫曼编码
前面我们学习了赫夫曼树的创建的过程,关于创建的详细过程可以看看上节的原理分析和代码实现,这节我们在它的基础上来学习赫夫曼的实践------------->编码过程,首先我们先来介绍下什么是赫夫曼编码.
赫夫曼编码介绍
赫夫曼编码也称(Huffman Code)哈夫曼编码,是一种常见的编码方式.
赫夫曼编码广泛的用于数据文件压缩,一般其压缩率达到20% -90%之间
赫夫曼编码是可变成编码的其中一种,由赫夫曼本人于1952年提出的一种编码方式,被称之为最佳编码.
接下来我们通过具体的案例来实现编码的过程:
假设我有一串字符串如: String string = "i like like like java do you like a java",我可以手动统计统计这个字符串是有40个字符(其中包括空格),我们可以分别统计每一个字符的个数如下:
- d=1; y=1; u=1; j=2; v=2; o=2; l=4; k=4; e=4; i=5; a=5; =9;
上述就是每一个字符的出现的个数,其中空格为9个,接下来我们利用上述的这些首先来构建一棵赫夫曼树,其中我们以每个字符的个数作为权值,具体的步骤这里就不重复了,上节我们我们已经说了,我们直接来看最终构建成的赫夫曼树如下图:
赫夫曼树.png
这其中我们规定赫夫曼树向左的路径为0,向右的路径规定为1,也就是如上图所示,我们可以通过规定的路径为每一个字符进行编码操作如下所示:
-
o:1000
-
u: 10010
-
d: 100110
-
y: 100111
-
j: 101
-
a: 110
-
k: 1110
-
e: 1111
-
j : 0000
-
v : 0001
-
l : 001
-
: 01
这里我们获取到了每一个字符的编码,我们可以按照上述编码规则那么我们的字符串String string = "i like like like java do you like a java"对应的编码应该为如下所示:
1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
最后将上述编码进行字节的转换,进行传输即可,这就是整个赫夫曼编码的过程,接着我们利用代码的方式来实现
代码实现
- 首先我们需要创建节点Node,其中包括如下属性 字节类型的data,其主要是用来存放字符对应的字节数据如a----------->97等,还有就是int类型的权值,其主要的目的是用来统计我们字符的次数,具体代码如下:
//创建node,这里是带数据和权值
class Node implements Comparable<Node>{
Byte data; //用来存放数据本身(字符),比如:字符'a' -->97 ' '--->32
int weight; //权值,也就是我们字符出现的次数
Node left;
Node right;
//前序遍历的方法
public void preOrder(){
System.out.println(this);
if (this.left !=null){
this.left.preOrder();
}
if (this.right !=null){
this.right.preOrder();
}
}
public Node(Byte data, int weight) {
this.data = data;
this.weight = weight;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
", weight=" + weight +
'}';
}
@Override
public int compareTo(Node o) {
return this.weight -o.weight;
}
- 接着我们需要将原字符串转成它所对应的字节数组,代码如下:
String string = "i like like like java do you like a java";
byte[] bytes = string.getBytes();
- 在接着我们需要编写方法,完成赫夫曼树的节点Node的存储过程,存储规则[data=97,weight=5].....为了方便处理我们这里采用List来帮助我们完成,具体代码实现如下:
public static List<Node> getNodes(byte[] bytes){
//1.创建list来
ArrayList<Node> nodes = new ArrayList<>();
//创建map,主要是用来统计byte出现的次数
HashMap<Byte, Object> map = new HashMap<>();
for (byte b:bytes){
Integer count = (Integer) map.get(b);
if (count ==null){
map.put(b,1);
}else {
map.put(b,count+1);
}
}
//遍历map,将键值对转成node节点对象
for (Map.Entry<Byte,Object> entry:map.entrySet()){
nodes.add(new Node(entry.getKey(), (Integer) entry.getValue()));
}
return nodes;
}
来看测试代码,如下:
/**
* 赫夫曼编码
*
*/
public class HuffmanCode {
public static void main(String[] args) {
String string = "i like like like java do you like a java";
byte[] bytes = string.getBytes();
System.out.println(bytes.length);
List<Node> nodes = getNodes(bytes);
System.out.println(nodes);
测试结果如下图所示:
节点测试图.png
太长了,这里就截了一部分,我们接着看拿到了List中存储的节点,我们可以利用它完成赫夫曼树的创建,代码如下:
//创建赫夫曼树
public static Node createHuffmanTree(List<Node> nodes){
//循环处理
while (nodes.size() >1){
//1.首先我们来排序(从小到大)
Collections.sort(nodes);
//2.取出第一棵最小的二叉树节点
Node leftNode = nodes.get(0);
//3.取出第二棵较小的二叉树节点
Node rightNode = nodes.get(1);
//4.创建一棵新的二叉树,这课新的二叉树是没有根节点的也就是我们的data为null,只有权值
Node parent = new Node(null, leftNode.weight + rightNode.weight);
//4.1.设置parent的左右节点
parent.left = leftNode;
parent.right = rightNode;
//4.2.将处理过的二叉树节点从nodes中删除,便于后面二叉树节点的操作
nodes.remove(leftNode);
nodes.remove(rightNode);
//4.3.将parent加入到nodes中作为下一次操作
nodes.add(parent);
}
//nodes中最后剩余的节点是我们要的赫夫曼的根节点
return nodes.get(0);
}
来看测试结果,如下图所示:
赫夫曼树的创建.png
可以对比我们之前分析的那个图来看我们创建的这颗赫夫曼树,到这里我们的工作完成了一半了,接下来我们首先需要做这个事情
- 我们要将这棵赫夫曼树转成对应的赫夫曼编码,这里为了方便我们操作我们使用map用来保存我们生成的编码,用StringBuilder来进行拼接操作,具体实现代码如下:
//1.我们将赫夫曼编码存放在map中
static Map<Byte,String> huffmanCodes = new HashMap<Byte,String>();
//2.在生成赫夫曼编码表时,我们需要去拼接路径,也就是用来记录某一个叶子节点的路径.这里选择StringBuilder来操作
static StringBuilder sb = new StringBuilder();
这里我们准备好我们所需要的的容器,接着进行核心代码的编写:
/**
* 目的 :将传入的node节点的所有叶子节点的赫夫曼编码得到,并存放到huffmanCodes
* @param node 传入的节点
* @param code 表示节点的路径 0表示左子节点 1:表示右子节点
* @param sb 用来拼接我们叶子节点的路径
*/
private static void getHuffmanCodes(Node node,String code,StringBuilder sb){
//初始化新的StringBuilder
StringBuilder builder = new StringBuilder(sb);
//拼接当前这个coed
builder.append(code);
//处理节点
if (node !=null){ //如果node== null 我们不做处理
//判断当前节点是叶子节点还是飞叶子节点
if (node.data ==null){ //表示非叶子节点
//递归处理
//说明:如果是向左的话,递归处理
getHuffmanCodes(node.left,"0",builder);
//如果是向右的话,递归处理
getHuffmanCodes(node.right,"1",builder);
}else { //表示叶子节点
//表示我们已经到了某叶子节点的最后,记录它的路径
huffmanCodes.put(node.data,builder.toString());
}
}
}
我们来看测试代码:
//测试赫夫曼树是否生成对应的赫夫曼编码
Map<Byte, String> huffmanCodes = getHuffmanCodes(root);
System.out.println("赫夫曼编码表:"+ huffmanCodes);
测试结果如下:
赫夫曼编码表.png
我们将赫夫曼树转成对应的赫夫曼编码之后,到这里我们的工作快接近尾声了,还有最后一步就是我们将上述生成的编码压缩成字节数组,代码如下:
/**
*
* @param bytes 原始字符串所对应的byte数组
* @param huffmanCodes 生成赫夫曼编码的map
* @return
*/
private static byte[] zip(byte[] bytes,Map<Byte,String> huffmanCodes){
//首先我们利用huffmanCodes将bytes转成赫夫曼编码对应的字符串
StringBuilder sb = new StringBuilder();
//遍历bytes
for (byte b :bytes){
sb.append(huffmanCodes.get(b));
}
System.out.println(sb);
// 1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
//将上述字符串转成byte数组
//首先我们需要统计返回byte[] huffmanCodeBytes的长度
int length;
if (sb.length() %8 ==0){
length = sb.length() /8;
}else {
length = sb.length() /8 +1;
}
//创建存储压缩后的byte数组
byte[] huffmanCodeBytes = new byte[length];
//创建一个记录遍历的sb的第几个byte
int index = 0;
//创建一个临时存储我们遍历到的byte
String strByte;
for (int i = 0; i <sb.length() ; i+=8) { //每8为对应一个byte,因此步长为8
if (i +8 >sb.length()){ //不够8位
strByte = sb.substring(i);
}else {
strByte = sb.substring(i,i+8);
}
//2.将strByte转成一个byte并且放入到huffmanCodeBytes中
huffmanCodeBytes[index] = (byte)Integer.parseInt(strByte,2);
index ++;
}
return huffmanCodeBytes;
}
上述过程涉及到了一些二进制的高位补码和转码的知识,感兴趣的可以自己去看看这块东西,我们来看下测试结果,直接在main方法里调用该方法即可:
字节压缩.png
那么到这里我们所有的工作就完成了,当然我们在实际的生产中也是通过字节来处理我们的数据的,那么关于赫夫曼编码的学习就到这里了,下节我们学习解码的操作,想看代码的去我git地址:
