compress.java

Huffman Algorithm: 基础的压缩方式

package huffman_tree;

import java.util.PriorityQueue;
import java.util.Vector;

public class Compress {
	public static void compress(String filename) {
		Vector<HuffmanNode> letterNode = ReadIn.readIn(filename);
		PriorityQueue<HuffmanNode> priQ = new PriorityQueue<HuffmanNode>();
		priQ.addAll(letterNode);
		Vector<HuffmanNode> allNode = new Vector<HuffmanNode>();
		// System.out.println(HuffmanNode.nodeNum);
		while (priQ.size() != 1) {
			HuffmanNode least1 = priQ.poll();
			HuffmanNode least2 = priQ.poll();
			HuffmanNode merge = new HuffmanNode('\0', least1.getFreq()
					+ least2.getFreq(), least1.getIndex(), least2.getIndex());
			least1.setParent(merge.getIndex());
			least2.setParent(merge.getIndex());
			allNode.add(least1);
			allNode.add(least2);
			priQ.add(merge);
		}
		HuffmanNode root = priQ.poll();
		allNode.add(root);
		// System.out.println("root:"+root.getIndex());
		HuffmanNode[] letNod = new HuffmanNode[letterNode.size()];
		for (int i = 0; i < letterNode.size(); i++) {
			letNod[letterNode.elementAt(i).getIndex()] = letterNode
					.elementAt(i);
		}
		// System.out.println("\n"+HuffmanNode.nodeNum+"\n"+allNode.size());
		HuffmanNode[] allNod = new HuffmanNode[allNode.size()];
		for (int i = 0; i < allNode.size(); i++) {
			allNod[allNode.elementAt(i).getIndex()] = allNode.elementAt(i);
		}
		for (int i = 0; i < letNod.length; i++) {
			StringBuilder bitString = new StringBuilder();
			HuffmanNode current = allNod[i];
			while (!current.equals(root)) {
				if (allNod[current.getParent()].getLeft() == current.getIndex()) {
					bitString.append("0");
				} else if (allNod[current.getParent()].getRight() == current
						.getIndex()) {
					bitString.append("1");
				}
				current = allNod[current.getParent()];
			}
			allNod[i].setBitArray(bitString.reverse().toString());
			letNod[i].setBitArray(bitString.reverse().toString());
			System.out.println(letNod[i].getLetter() + ": "
					+ letNod[i].getBitArray());
		}
		int compressedSize = 0;
		for (int i = 0; i < letNod.length; i++) {
			compressedSize += letNod[i].getBitArray().length()
					* letNod[i].getFreq();
		}
		System.out.println("FILE LENGTH(before the compression): "
				+ ReadIn.fileSize + "\nFILE LENGTH(before the compression): "
				+ compressedSize / 8 + "\nThe compression ratio: "
				+ ((double) ReadIn.fileSize * 8) / compressedSize);

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Compress.compress("Test.txt");
		// System.out.println(HuffmanNode.nodeNum);
	}
}