哈弗曼压缩

 

一、哈弗曼树，又称最优树，是一种带权路径长度最短的树。

路径长度：        两个节点之间的路径上的分支数目

数的带权路劲长度：树中所有叶子节点的带权路径长度之和（WPL值，其中WPL最小的就叫最优二叉树或者哈弗曼树）。

二、哈弗曼树的建立

哈弗曼树也算二叉树的一种，所以哈弗曼树的建立和二叉树类似，只是多了个参数--权值。

基本步骤：

一.读取文件,将读取的信息转化为ASCII码,建立数组以ASCII码为下标,记录字符出现的次数

二.生成节点,根据节点的权值排序(使用优先队列) 三.构建哈夫曼树,生成码表根据权值进行排序，根据权值排好序以后，去前两个节点也就是最小的节点，取出后删除节点，两个节点形成一个新的节点，权值小的为新节点的左子节点，权值大的为右子节点。（同时给节点赋值，左子节点为“0”，右子节点为“1”。这就是哈弗曼编码，我们在递归的时候让子节点不断加上父节点的哈弗曼编码就能得到该节点的哈弗曼编码。）我们再将新节点加入优先队列重复以上步骤

HuffmanNode node1 = nodeQueue.poll();

			HuffmanNode node2 = nodeQueue.poll();
			HuffmanNode parent_node = new HuffmanNode(0, node1.getCount()+ node2.getCount());
			parent_node.setLeftChild(node1);
			node1.setHuffmanCode("0");
			parent_node.setRightChild(node2);
			node2.setHuffmanCode("1");
			nodeQueue.add(parent_node);

 

三、得到哈弗曼编码

哈弗曼树构建好了以后我们开始遍历这棵树，得到他的哈弗曼编码，首先该节点的左右字数是否为空，是则得到其哈弗曼编码，反之则遍历，将子节点的编码加上父节点的编码

if (root.getLeftChild() == null && root.getRightChild() == null) {

			// 把叶子节点添加到节点数组里
			leafNode[counter] = root;
			counter++;
			
		} else {
			// 获取当前节点的哈夫曼编码值
			String str = root.getHuffmanCode();
			// 左节点的编码值加上当前节点的编码值
			str += root.getLeftChild().getHuffmanCode();
			// 把加后的编码值赋值给左节点
			root.getLeftChild().setHuffmanCode(str);
			// 递归左节点
			printHuffmanCode(root.getLeftChild());
			// 获取当前节点的编码值
			String str1 = root.getHuffmanCode();
			// 右节点的编码值加上当前节点的编码值
			str1 += root.getRightChild().getHuffmanCode();
			// 把加后的编码值赋值给右节点
			root.getRightChild().setHuffmanCode(str1);
			// 递归右节点
			printHuffmanCode(root.getRightChild());
		}
		

 

四、文件的写入

将所有的哈弗曼编码不够八位的补满八位，超过八位补成整数个八位，同时记录补零的个数

for (int i = 0; i < leafNode.length; i++) {

				allhfmCode[i] = leafNode[i].getHuffmanCode();
			}

			for (int i = 0; i < leafNode.length; i++) {
				int zeroCount = 0;
				String presentCode = leafNode[i].getHuffmanCode();
				while (presentCode.length() % 8 != 0) {
					zeroCount++;
					presentCode += "0";
				}
				int bytesize = presentCode.length() / 8;
				leafNode[i].setByteSize(bytesize);

				leafNode[i].setHuffmanCode(presentCode);

				leafNode[i].setZeroCount(zeroCount);

				allString += leafNode[i].getHuffmanCode();
			}

 

将头文件信息写完后，用一串字符进行标记，将头信息和文件体信息隔开解压文件时可以进行判断。文件写入时每八位写入，没有八位的补零满八,写入，同时写入补零个数

for (int i = 0; i < allString.length(); i++) {

				// 一个一个的读取给中转字符
				writes += allString.charAt(i);
				// 当读满八位时执行
				if (i % 8 == 7) {
					if (byteCount1 == byteCount2) {
						// 写入该字符占有几个位置
						byteCount2 = leafNode[nodeCount].getByteSize();
						bos.write(leafNode[nodeCount].getByteSize());
						// 写入字符
						bos.write(leafNode[nodeCount].getASCII());
						// 写入补了多少个0
						String str_zerocount = Integer.toString(leafNode[nodeCount]
								.getZeroCount());
						bos.write((int) str_zerocount.charAt(0));
						nodeCount++;
						byteCount1 = 0;
					}
					// 把这8位字符串转化成整形
					if (byteCount1 < byteCount2) {
						int x = ChangeString(writes);
						// 写入转换后的整型
						bos.write(x);
						// 中转字符串归零
						writes = "";
						byteCount1++;
					}
				}
			}
		
			for (int i = 0; i < 5; i++) {
				bos.write(97 + i);
			}
			// 定义计数器，记录的是内容的补零个数
			int zeroCount = 0;
			// 定义一个存储内容编码的字符串
			String content = "";
			// 定义一个中转字符串
			String tranString = "";
			// 遍历读取文件内容，并写入文件
			for (int i = 0; i < length; i++) {
				// 读取文件
				int x = bis.read();
				// 循环判断该字符所对应的编码
				for (int j = 0; j < allhfmCode.length; j++) {
					if (x == leafNode[j].getASCII()) {
						// 把编码赋值给字符串中存储
						content += allhfmCode[j];
					}
				}
				// 如果此时的字符串位数大于等于8
				if (content.length() >= 8) {
					// 循环获得前八位
					for (int j = 0; j < 8; j++) {
						tranString += content.charAt(j);
					}
					// 把这8位字符串转化成整形
					int a = ChangeString(tranString);
					// 写入转换后的整型
					bos.write(a);
					// 清空转换字符串
					tranString = "";
					// 循环获得除去前八位后剩下的字符
					for (int j = 8; j < content.length(); j++) {
						tranString += content.charAt(j);
					}
					// 把原先的字符串覆盖掉
					content = tranString;
					// 清空转换字符串
					tranString = "";
				}
			}
			// 如果没有满八位，则补上0
			while (content.length() % 8 != 0) {
				zeroCount++;
				content += "0";
			}
			// 把这8位字符串转化成整形
			if (content.equals("")) {
			} // 把这8位字符串转化成整形
			else {
				int b = ChangeString(content);
				// 写入转换后的整型
				bos.write(b);
			}
			// 写入补零计数器
			String so = Integer.toString(zeroCount);
			bos.write((int) so.charAt(0));

 

五、文件解压

解压可以算是压缩的逆过程

按照自己写入的规律读取文件形成新的文件