java的huffman实现 博客分类： Java数据结构

需求分析

从一个文件中读取数据，统计文件的每个字节出现的频数，根据不同的这些频数构建赫夫曼树并实现编码译码分别保存到新的文件中。编码文件为原文件+“.ext”,译码文件为编码文件+“.txt”。

养成良好习惯：每个小功能的实现都需要及时进行测试，第一个功能没写好就不要往下写，不然到时候出了错都没办法找原因。

流程分析

先从文件中初始化数据，用map来保存名值对。Byte对应出现次数。

根据map创建树的节点。

根据节点创建赫夫曼树。

根据赫夫曼树进行编码。

根据编码和源文件内容对其进行编码并保存到文件中。

从已编码的文件中读取数据进行译码并保存到文件中。

最终产生的文件和原文件是一模一样的即算成功。

搭建框架

1、需要创建节点类。

节点类需要以下属性：
int intWeight;// 频数

Byte byteData;// 字节内容

Tree parent;// 父节点

Tree lchild;

Tree rchild;

Int intFlag = -1;// 保存该节点编码，初始化为-1，树根为-1，左子树为0，右子树为1（便于编码）

 

 

构建好了需求，开始写好类

 

public class Tree{
	int weight; // 重复出现次数
	Byte data; // 字节内容-128~127
	Tree parent;
	Tree lchild;
	Tree rchild;
	int flag = -1;// 初始化该点编码为-1，到时候如果被变成左孩子，赋值为0.右孩子赋值为1

	public Tree(Byte data, int weight) {
		this.data = data;
		this.weight = weight;
	}

	public String toString() {
		return data + "\t 权值：" + weight;
	}
}

2、从文件中读取数据，构建HashMap<Byte, Integer> map

 

 

 

首先，我们需要选择合适的输入流，在这里，我们可以用FileInputStream和BufferedInputStream。从文件中读取字节，并统计每个字节的次数并put进map中，如果在map中已经存在，则取出map中该名对应的值，并对其加1.首先需要判断空文件的处理。具体操作如下：

 

int t = bis.read();// 字节
			if (t == -1) {// 空文件的处理
				new FileOutputStream(new File(str + ".ext")).close();
				return null;
			}

while (t != -1) {
				byte b = (byte) t;
				if (map.containsKey(b)) {
					int v = (int) map.get(b);
					v++;
					map.put(b, v);
				} else {
					map.put(b, 1);
				}
				t = bis.read();
			}

return map;

 

 

3、根据map创建节点

在这里，我们为了方便之后建树的时候要找到权值最小的两个节点，所以我们直接用一个排序队列来保存节点。当然，这个排序队列需要我们自己写好排序规则。

先遍历map取出数据，创建Tree对象。再将其加到queueNode里面去。

4、根据节点创建树

由于队列中的Tree都是根据权值进行了排序的，每次取出队列中最前面两个，链接好节点与节点之间的关系。并初始化该节点对应的编码。

Tree tree1 = queueNode.poll();

                            Tree tree2 = queueNode.poll();

                            Tree tree3 = new Tree(null, tree1.weight + tree2.weight);

                            tree3.lchild = tree1;

                            tree3.rchild = tree2;

 

                            tree1.flag = 0;// 标记左边的元素为0，编码时候为0

                            tree2.flag = 1;// 标记右边为1

 

                            tree1.parent = tree3;

                            tree2.parent = tree3;

                            queueNode.add(tree3);

 

5、根据树进行编码

左边为0，右边为1，如果只有一个点，则编码为0。并将每个字节对应的编码信息存到HashMap<Byte, String> mapCode中。

 

如果只有一个节点，直接mapCode.put(root.data, "0");

 

否则，用递归来进行编码。代码如下：

 

public void enCoding(Tree parent, Tree child, String str,
			HashMap<Byte, String> mapCode) {
		// 递归找到叶子节点，字符串加上其flag值（构建树的时候初始化为0和1了）
		if (child != null) {
			if (child.flag != -1) {// 不是根节点
				str += child.flag;
			}
			enCoding(child, child.lchild, str, mapCode);
			enCoding(child, child.rchild, str, mapCode);
		} else {
			// 将字节与编码的对应关系存入mapCode中
			mapCode.put(parent.data, str);
		}
	}

 

 

6、根据编码对原文件进行编码并保存

在这里，我们需要保存编码表到文件，到时候译码可不一定还能找到原文件对其先编码。

所以我们选择ObjectOutputStream。先将mapCode写到文件，之后再写编码后的数据。

代码为：

oos.writeObject(mapCode);

oos.flush();

 

接下来如何编码呢？

先从文件中一个一个字节的读出来，然后再去编码表进行搜索。将搜索到的记录保存到临时存储这些编码的String中间。如果String长度超过了8，就可以将其变成一个字节保存出去了。一边读，一边编码，一边保存。（在这里，和线程中提到的生产消费模型很相似。）到最后，就会发现一个问题，如果我的编码最后没满8位岂不是最后就编不了了？所以，我们最后要进行一次判断，如果我的string长度最后大于0小于8，那么我就在后面补0直到长度为8，并在最后将补0的数目写到文件结尾。

 

经过这些步骤，就保存好了。

 

String st = "";
// 保存文件中每个字节的编码
int t = bis.read();// 字节
while (t != -1) {
	byte b = (byte) t;
	st += mapCode.get(b);
	while (st.length() > 8) {
将string转为byte保存出去
st = st.substring(8);
	}
t = bis.read();
}
int len = st.length();
int count = 0;
if (len > 0) {
	count = 8 - len;// 得到补0个数
将最后这个字节保存到文件中
}
bos.write(count);

 

 

7、从编码文件中读取文件对其译码

如何实现译码呢？最简单的就是和保存编码文件一样，从文件中先读取一段byte，将其转为字符串，然后在编码表中找对应的byte。匹配成功就将其写到文件中。

所以在写译码的方法时，我们需要用到编码文件中的编码表，需要用到需要翻译的字符串，还要用一个数组来保存译出来的byte。

我们可以每读一个字节就将其转为8位的string（01串），如果string长度超过256（最坏的情况编码长度最大不超过256），我们就对其进行译码，译码得到的字节临时存在一个数组中。然后译码一次完成之后，保存数组中的字节，并清空数组，清除字符串中翻译出来了的字符。继续读数据，如果再超过256，再译码，就这样不断循环。最后翻译完毕。

框架如下：
<!--[if !supportLineBreakNewLine]-->
<!--[endif]-->

 

public String deCoding(HashMap<Byte, String> mapCode, String string,
			ArrayList<Byte> data) {
String str = "";
	HashMap<String, Byte> map = new HashMap<String, Byte>();
//先得到编码与字节的名值对
	Set<Byte> keys = mapCode.keySet();
	for (Byte bt : keys) {
		map.put(mapCode.get(bt), bt);
	}
for (int i = 0; i < string.length(); i++) {
		str += string.charAt(i) - 48;
		// System.out.println(str);
		if (map.containsKey(str)) {
得到对应字节保存到数组
字符串剪掉这一段
i = -1重新开始寻找
｝
｝
return string;
｝

 

 

8、到这里基本功能都已经实现了，现在需要一个文件选择器，选择文件对其编码译码。

 

用一个窗口，在上面增加文件选择器。选择文件进行操作。

 

测试

 

经过多次测试，两者都对同一个不同大小文件测试，都是建树版效率更高，尤其是编码平均长了的时候。

 

对于同一个1899125字节的文件，用编码表压缩297454字节，用建树版压缩298324字节，大了1kb左右

 

对于一个144,262,144 字节的压缩文件再次压缩，编码表版增肥4755字节，建树版增肥14634字节，多占用近10kb

 

 

 

 

总结

在译码的时候，不仅可以根据编码表进行译码，也可以根据树进行译码（这个也实现了）。

经过测试，建树译码效率高很多，但是存储的是排序的队列，所以占用空间大一点。

程序中没超过8为就写数据，没超过256就开始译码有效解决了打文件的问题。但是如果有一个文件，某个字节出现的次数已经超过了int的表示范围，就会有问题了。

 

在窗口中，加入文本框，输入一串文字，在进行编码的时候，有效的利用这串文字进行编码就可以作为一个加密软件了。毕竟赫夫曼的压缩效果一般都不明显。

 

 

 String与byte互相转换参考：http://479001499.iteye.com/admin/blogs/2094257