huffencoder.java

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

/************************

class HuffEncoder
encodes a Bitstream using Huffman coding
encoded bitstream format is:
first int - total codes in file
array of <byte><int> - frequency table for each type of byte in file
<byte><int> - sentinel value
<bits> - the encoded form of the original stream

 ************************/


package huffmancoding;



import java.io.*;
import java.util.Arrays;
import java.util.HashMap;

public class HuffEncoder
{

	private final int BYTE_LENGTH = 8;
	private final int DWORD_LENGTH = 32;
	private final int BYTE_RANGE = Byte.MAX_VALUE + Math.abs(Byte.MIN_VALUE) + 1;
	private final byte SENTINEL_BYTE = 65;
	private final int SENTINEL_FREQ = 0;

	private Bitstream encodedStream;

	public HuffEncoder(Bitstream inputStream)
	{

		inputStream.reset();

		// count byte frequencies in the stream
		int[] frequencies = getFreqs(inputStream);
		System.out.println("Encoder: got freqs");

		// build an encoder tree from the freqs
		HuffTree encoderTree = new HuffTree(frequencies);
		System.out.println("Encoder: got tree");

		// map bytes to their codes
		HashMap<Byte, String> codeMap = encoderTree.getMap();
		System.out.println("Encoder: got map");
		System.out.println("Codes: " + codeMap.toString());

		// encoded the stream
		encodedStream = encodeStream(inputStream, frequencies, codeMap);
		System.out.println("Encoder: got encoded stream");
	}

	public Bitstream getEncodedStream()
	{
		return encodedStream;
	}

	// counts the frequencies of bytes in the stream
	private int[] getFreqs(Bitstream stream)
	{

		int[] freqs = new int[BYTE_RANGE];
		Arrays.fill(freqs, 0);

		while(!stream.eof())
		{
			freqs[stream.readByte() - Byte.MIN_VALUE]++;
		}

		return freqs;
	}

	// encodes the stream and returns it in encoded form
	private Bitstream encodeStream(Bitstream inStream, int[] freqs, HashMap<Byte, String> codes)
	{

		Bitstream encodedStream = new Bitstream();

		// write the total number of encoded bytes
		encodedStream.writeDWord(inStream.size() / BYTE_LENGTH);

		// write the frequency table
		for (int byteIterator = 0; byteIterator < BYTE_RANGE; byteIterator++)
		{
			if (freqs[byteIterator] > 0)
			{
				encodedStream.writeByte((byte) (byteIterator + Byte.MIN_VALUE));
				encodedStream.writeDWord(freqs[byteIterator]);
			}
		}
		encodedStream.writeByte(SENTINEL_BYTE);
		encodedStream.writeDWord(SENTINEL_FREQ);

		// write the codes
		inStream.reset();
		while(!inStream.eof())
		{
			encodedStream.append(codes.get(new Byte(inStream.readByte())));
		}

		encodedStream.reset();
		return encodedStream;
	}

}