java实现哈夫曼编码和解码

前段时间的数据结构课上，学习了哈夫曼编码的相关知识，后来我又自己完成了解码的过程。所以在这里分享一下开发文档，帮助有需要的同学，如有问题欢迎再评论区讨论。

（一）需求

对字母进行哈夫曼数加密，然后再逆解密，可以实现通过获得的加密数字获取隐藏的字母。

（二）需求分析

该实验共分为两部分，先是对每一个字母进行哈夫曼加密，这可以使用哈夫曼树实现，但这部分的难点是如何读取相应字母的编码数据。为了实现这一需求，使用二维数组实现，将每一行的数据与每一个字母对应，输出相应字母编码就是输出相应行数的数据。第二部分是解码，这一部分相较第一部分要困难很多。还是得建立在前一部分构建好的数组基础上，将获得的加密数据与每一行数组数据比较获得相应字母，当然这一部分很复杂，详情见第三部分的设计。

（三）设计

第一部分是将每一个字母加密，这里大体上按照书本上的思路。首先是获得每一个字母的词频，（注意：每一个字母的权值不能相差较大，不然的话很容易在后续中数组出现有字母的编码是另一个字母的前部分，导致无法正确的解码。）我是使用python获取的两篇文章的词频。然后就与书本上结构类似的建立哈夫曼树，储存权值，并且从叶子向根的读取数据并且储存到二维数组中。

比较麻烦的是第二部分的解密，在这一部分最大的难点就是无法判断加密后的数据之间的分割，也就是无法判断每一个字母的读取到哪里停止。好在由于哈夫曼树的特性每一个字母都不会成为另一个字母编码的前序列，这里可以使我们通过数组比较。我会在下面进行详细介绍：

第一步：为了更好的控制加密的数据与数组比较，我使用链队储存加密数据，主要是利用它先进先出的特性。

第二步：使用大量的循环语句进行数组与加密数据比较，我设置了一个初始为0的变量flag，通过for循环将每一行都与数组比较，当加密数据与数组数据不符时，flag+1，直到这一行比较终止。然后使用if语句判断每一行的最终flag是否为0，如果为0，就记录下对应的行数（存入一个数组list里）。

第三步：当比较出一个字母之后，需要继续后面加密数据的比对，这里我使用变量len记录下每一次比较的个数，并将链队前len个结点删除，继续后续的比较。

第四步：由于数组每一行的数据个数都不相同，很容易出现数组数据先比较完，或者加密数据先比较完的情况。数组数据比较完被for循环条件条件限制，不会报错。但当链队较短的时候，加密数据比较完了，链队读取null，会报错。所以在循环中要比较变量len与链队长度，当两者相等时，就需要break脱离循环。

第五步：我在每一个循环层面都设置了链队长度的检查，一旦length为0，就终止所有循环。（不然会报错）

第六步：脱离循环之后，遍历存储对应行数的数组list，并且输出相应行数对应的字母。

其实这么多步骤可以封装成一个函数，但由于我技术不熟，封装中反复报错，索性就直接使用。

代码：

package work;

public interface IQueue {
	public void clear();
	public boolean isEmpty();
	public int length();
	public Object peek();
	public void offer(Object x) throws Exception;
	public Object poll();
}

package work;

public class HuffmanNode {
	public int weight;
	public int flag;
	public HuffmanNode parent,lchild,rchild;
	public HuffmanNode() {
		this(0);
	}
	public HuffmanNode(int weight) {
		this.weight = weight;
		flag=0;
		parent = lchild = rchild = null;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   
	}
}

package work;

public interface IStack {
	public void clear();
	public boolean isEmpty();
	public int length();
	public Object peek();
	public void push(Object x) throws Exception;
	public Object pop();
}

package work;

public class Node {
	public Object data;
	public Node next;
	public Node() {
		this(null,null);
	}
	public Node(Object data) {
		this(data,null);
	}
	public Node(Object data,Node next) {
		this.data = data;
		this.next = next;
	}
}

package work;

public class LinkQueue implements IQueue{
	public Node front;
	public Node rear;
	public LinkQueue() {
		front = rear = null;
	}
	public void clear() {
		front = rear = null;
	}
	public boolean isEmpty() {
		return front==rear;
	}
	public int length() {
		Node p = front;
		int length = 0;
		while (p!=null) {
			p=p.next;
			++length;
		}return length;
	} 
	public Object peek() {
		if(front != null) 
			return front.data;
		else
			return null;
	}
	public void offer(Object x) {
		Node p = new Node(x);
		if(front != null) {
			rear.next=p;
			rear = p;
		}
		else
			front = rear = p;
	}
	public Object poll() {
		if(front != null) {
			Node p = front;
			front = front.next;
			if(p==rear)
				rear = null;
			return p.data;
		}
		else
			return null;
	}
}

package work;
import java.util.Scanner;
import java.util.Arrays;
public class HuffmanTree {
	public int[][] huffmanCoding(int[] W,String[] y){
		int n = W.length;//字符个数
		int m = 2*n-1;//结点个数
		HuffmanNode[] HN = new HuffmanNode[m];
		int i;
		for(i =0;i