adaptivehuffmancompression.cs

自适应huffman编码工具

// Stephen Toub
// [e-mail]
//
// AdaptiveHuffmanCoding.cs
// Classes for performing Adaptive Huffman Coding (both FGK and modified Vitter algorithm).
//		- AdaptiveHuffmanProvider: Static methods used to compress and decompress
//		- AdaptiveHuffmanStream: Stream-based compression and decompression
//
// NOTE:
// Requires BitStream stream class, located in BitStream.cs.
//
// v1.0.0
// July 17th, 2002

#region Namespaces
using System;
using System.IO;
using System.Collections;
using Toub.IO;
#endregion

namespace Toub.Compression
{
	/// <summary>Provides Adaptive Huffman compression and decompression.</summary>
	public class AdaptiveHuffmanProvider
	{
		#region Constants
		/// <summary>Size of the memory buffer to use when reading and writing data.</summary>
		private const int _bufferSize = 2048;
		#endregion

		#region Construction
		/// <summary>Prevent external instantiation.</summary>
		private AdaptiveHuffmanProvider() {}
		#endregion

		#region Public Functions
		#region Compression
		/// <summary>Compress a stream of input data to an output stream.</summary>
		/// <param name="from">The stream containing the data to be compressed.</param>
		/// <param name="to">The stream to which the compressed data should be written.</param>
		/// <remarks>
		/// Reading and writing begins at the current position in both streams.
		/// Reading and writing ends at the end of each stream.
		/// </remarks>
		public static void Compress(Stream from, Stream to)
		{
			// Create a new Huffman stream around the outpt stream and
			// write the bytes to it, reading them portions at a time
			// from the input stream.
			using (AdaptiveHuffmanStream huffman = 
					   new AdaptiveHuffmanStream(to, StreamDirection.Write)) 
			{
				int read;
				byte [] buffer = new byte[_bufferSize];
				while((read = from.Read(buffer, 0, _bufferSize)) > 0) 
				{
					// Write the buffer (what was actually read) to the output stream
					huffman.Write(buffer, 0, read);
				}
			}
		}

		/// <summary>Compress a stream of data to an output stream.</summary>
		/// <param name="s">The input stream to be compressed.</param>
		/// <returns>A stream of compressed data.</returns>
		/// <remarks>
		/// Compression begins at the current position in the input stream.
		/// The resulting stream's position is at the end of the current data.
		/// </remarks>
		public static MemoryStream Compress(Stream s)
		{
			// Create a new memory stream to hold the compressed data
			MemoryStream ms = new MemoryStream();

			// Compress from s to ms
			Compress(s, ms);

			// Return the compressed stream after resetting its position to the beginning
			return ms;
		}

		/// <summary>Compress an array of bytes using adaptive Huffman compression.</summary>
		/// <param name="bytes">The bytes to be compressed.</param>
		/// <returns>The compressed bytes.</returns>
		public static byte [] Compress(byte [] bytes)
		{
			// Create a new memory stream to hold the input uncompressed bytes
			// and one to hold the output compressed bytes
			MemoryStream from = new MemoryStream(bytes);
			MemoryStream to = new MemoryStream();

			// Compress from input to output
			Compress(from, to);

			// Get the compressed bytes and return them
			return to.ToArray();
		}
		#endregion

		#region Decompression
		/// <summary>Decompress a stream of input data to an output stream.</summary>
		/// <param name="from">The stream containing the data to be decompressed.</param>
		/// <param name="to">The stream to which the decompressed data should be written.</param>
		/// <remarks>
		/// Reading and writing begins at the current position in both streams.
		/// Reading and writing ends at the end of each stream.
		/// </remarks>
		public static void Decompress(Stream from, Stream to)
		{
			// Create a new Huffman stream around the compressed stream and
			// read the bytes from it portions at a time from the given stream,
			// writing the decompressed data to the output decompressed stream.
			using (AdaptiveHuffmanStream huffman = 
					   new AdaptiveHuffmanStream(from, StreamDirection.Read)) 
			{
				int read;
				byte [] buffer = new byte[_bufferSize];
				while((read = huffman.Read(buffer, 0, _bufferSize)) > 0) 
				{
					// Write the buffer (what was actually read) to the output stream
					to.Write(buffer, 0, read);
				}
			}
		}

		/// <summary>Decompress a stream of data to an output stream.</summary>
		/// <param name="s">The input stream to be decompressed.</param>
		/// <returns>A stream of decompressed data.</returns>
		/// <remarks>
		/// Decompression begins at the current position in the input stream.
		/// The resulting stream's position is at the end of the current data.
		/// </remarks>
		public static MemoryStream Decompress(Stream compressedStream)
		{
			// Create a new memory stream to hold the decompressed data
			MemoryStream ms = new MemoryStream();

			// Decompress the stream to the memory stream
			Decompress(compressedStream, ms);

			// Return the decompressed stream
			return ms;
		}

		/// <summary>Decompress an array of bytes using adaptive Huffman compression.</summary>
		/// <param name="compressedBytes">The bytes to be decompressed.</param>
		/// <returns>The decompressed bytes.</returns>
		public static byte [] Decompress(byte [] compressedBytes)
		{
			// Create a new memory stream to hold the input compressed bytes
			// and one to hold the output uncompressed bytes
			MemoryStream ms = new MemoryStream(compressedBytes);
			MemoryStream output = new MemoryStream();

			// Create a new Huffman stream around the memory stream and
			// read the bytes from it.
			Decompress(ms, output);

			// Get the compressed bytes and return them
			return output.ToArray();
		}
		#endregion
		#endregion
	}

	/// <summary>Stream that uses adaptive Huffman coding to compress and decompress a stream of bytes.</summary>
	public class AdaptiveHuffmanStream : Stream, IDisposable
	{
		#region Member Variables
		/// <summary>The direction in which this stream is processing bits.</summary>
		private StreamDirection _direction;
		/// <summary>The underlying stream for the bit stream (i.e. a FileStream).</summary>
		private BitStream _bitStream;
		/// <summary>Huffman tree to use for compression and decompression.</summary>
		private AdaptiveHuffmanTree _tree;
		/// <summary>Whether the stream is open.  Used primarily when closing the stream.</summary>
		private bool _open;
		/// <summary>Whether we're at the end of the readable Huffman stream.</summary>
		private bool _eos;
		#endregion

		#region Construction
		/// <summary>Initialize the BitStream.</summary>
		/// <param name="baseStream">The underlying stream for the bit stream.</param>
		/// <param name="direction">The direction of the stream.</param>
		public AdaptiveHuffmanStream(Stream baseStream, StreamDirection direction)
		{
			// Store the direction and create a new bitstream.  We want to make sure that
			// the base stream is not closed when we are (even though the bitstream will be).
			_direction = direction;
			_bitStream = new BitStream(baseStream, direction);
			_bitStream.CloseBaseStream = false;

			// Make sure we can process the underlying stream in the requested direction
			if (direction == StreamDirection.Read && !baseStream.CanRead) 
			{
				throw new ArgumentException("Can't read from the underlying stream.");
			} 
			else if (direction == StreamDirection.Write && !baseStream.CanWrite) 
			{
				throw new ArgumentException("Can't write to the underlying stream.");
			}

			// Setup stream
			_open = true;
			_eos = false;

			// Setup Huffman tree
			_tree = new AdaptiveHuffmanTree();
		}
		#endregion

		#region Properties
		/// <summary>Gets whether we can read bits from this stream.</summary>
		public override bool CanRead { get { return _open && _direction == StreamDirection.Read; } }
        
		/// <summary>Gets whether we can seek on this stream.  Always returns false.</summary>
		public override bool CanSeek { get { return false; } }
        
		/// <summary>Gets whether we can write bits to this stream.</summary>
		public override bool CanWrite { get { return _open && _direction == StreamDirection.Write; } }

		/// <summary>Gets the number of compressd bits processed by the stream (either read or written).</summary>
		public override long Position
		{
			get { return _bitStream.Position; }
			set { throw new NotSupportedException("Can't seek on a compression stream."); }
		}

		/// <summary>Gets whether we're at the end of the Huffman stream.</summary>
		public bool EndOfStream { get { return _eos; } }

		/// <summary>Gets or sets whether to close the base stream when this stream is closed.</summary>
		public bool CloseBaseStream 
		{
			get { return _bitStream.CloseBaseStream; } 
			set { _bitStream.CloseBaseStream = value; } 
		}
		#endregion
        
		#region Writing
		/// <summary>Compresses a byte and writes it to the output stream.</summary>
		/// <param name='value'>The byte to be written.</param>
		public override void WriteByte(byte value)
		{
			// Get the node for the value (or NYT if the value doesn't exist)
			AdaptiveHuffmanTreeNode node = _tree.GetValueNode(value);
			if (node == null) node = _tree.GetNYTNode();

			// Get the encoding for the node and write out all of the bits
			int [] bits = _tree.GetBitEncoding(node);
			_bitStream.Write(bits, 0, bits.Length);

			// If we have an NYT node, then we also need to write out the byte value
			// of the character as it is the first time we're seeing it.
			if (node.Type == AdaptiveHuffmanTreeNodeType.NYT) _bitStream.WriteByte(value);

			// Update the tree to reflect the value
			_tree.UpdateTree(value);
		}
        
		/// <summary>Compresses and writes a buffer's worth of bytes to the output stream.</summary>
		/// <param name='buffer'>The bytes to be written.</param>
		/// <param name='offset'>The position in the array of bytes at which to begin writing.</param>
		/// <param name='count'>The number of bytes to write.</param>
		public override void Write(byte [] buffer, int offset, int count)
		{
			// Write each byte to the output stream.
			for(int i=offset; i<offset+count; i++) WriteByte(buffer[i]);
		}
		#endregion
        
		#region Reading
		/// <summary>Read and decompress a byte from the input stream.</summary>
		/// <returns>The byte read from the input stream; -1 if at the end of the Huffman stream.</returns>
		public override int ReadByte()
		{
			// If we're at the end of the stream, return EOS (-1).
			if (_eos) return -1;

			// Get the root node of the tree
			AdaptiveHuffmanTreeNode node = _tree.RootNode;
			if (node == null) throw new ApplicationException("The tree cannot be empty.");

			// Follow the tree till we reach a leaf
			while(node.LeftChild != null) 
			{
				// Get a bit from the stream
				int bit = _bitStream.ReadBit();
				if (bit < 0)
				{
					// For some reason we hit the end of the stream, so we're done.