hufftree.java

哈夫曼压缩 哈弗曼算法是基本的压缩和解密算法

/*******************************************************************************
 * 
 * class HuffTree used for Huffman coding builds a Huffman coding tree based on
 * a table of byte frequencies Uses internal class HuffNode for tree nodes
 * HuffNode implements Comparable for priority queue use
 * 
 ******************************************************************************/


package huffmancoding;



import java.io.*;
import java.util.PriorityQueue;
import java.util.Map;
import java.util.HashMap;

public class HuffTree extends Object
{

	private final int BYTE_RANGE = Byte.MAX_VALUE + Math.abs(Byte.MIN_VALUE) + 1;

	private HuffNode root;

	private static class HuffNode implements Comparable
	{

		int weight;
		byte theByte;
		HuffNode left;
		HuffNode right;

		HuffNode(byte newByte, int newWeight)
		{

			weight = newWeight;
			theByte = newByte;
			left = null;
			right = null;
		}

		HuffNode(HuffNode newLeft, HuffNode newRight)
		{

			weight = newLeft.weight + newRight.weight;
			theByte = 0;
			left = newLeft;
			right = newRight;
		}

		// for use with priority queue
		public int compareTo(Object node) throws ClassCastException
		{

			if (! (node instanceof HuffNode))
				throw new ClassCastException("A HuffNode object expected");

			int newWeight = ((HuffNode) node).weight;
			int newByte = ((HuffNode) node).theByte;
			HuffNode newLeft = ((HuffNode) node).left;

			if (weight == newWeight)
			{
				if (theByte == 0 && right == null)
					return 1;
				if (newByte == 0 && newLeft == null)
					return -1;
				return (theByte > newByte) ? 1 : -1;
			}
			return (weight > newWeight) ? 1 : -1;
		}

	}

	public HuffTree()
	{

		root = null;
	}

	// creates a new tree from a frequencies table
	public HuffTree(int[] weights)
	{

		PriorityQueue<HuffNode> nodeQueue = new PriorityQueue<HuffNode>(weights.length);

		for (int byteIterator = 0; byteIterator < weights.length; byteIterator++)
		{
			if (weights[byteIterator] > 0)
				nodeQueue.add(new HuffNode((byte) (byteIterator + Byte.MIN_VALUE), weights[byteIterator]));
		}

		while(nodeQueue.size() > 1)
		{

			System.out.println(nodeQueue.size());
			HuffNode childLeft = nodeQueue.poll();
			HuffNode childRight = nodeQueue.poll();

			HuffNode newNode = new HuffNode(childLeft, childRight);
			nodeQueue.add(newNode);
			System.out.println(newNode.weight);
			System.out.println(childLeft.theByte + "    " + childRight.theByte);
		}

		root = nodeQueue.poll();
	}

	// gets the byte represented by the next valid code in a Bitstream
	public byte getByte(Bitstream stream)
	{

		HuffNode current = root;

		while(current.left != null || current.right != null)
		{
			if (stream.readBit())
				current = current.right;
			else
				current = current.left;
		}

		return current.theByte;
	}

	// creates a byte->code map from the tree
	public HashMap<Byte, String> getMap()
	{

		HashMap<Byte, String> map = new HashMap<Byte, String>(BYTE_RANGE);

		return getMap(map, root, new String(""));
	}

	// private helper function for recursive getMap()
	private HashMap<Byte, String> getMap(HashMap<Byte, String> map, HuffNode head, String code)
	{

		if (head.left == null && head.right == null)
		{
			map.put(new Byte(head.theByte), code);
		}
		else
		{
			getMap(map, head.left, code + "0");
			getMap(map, head.right, code + "1");
		}
		return map;
	}

}