adaptivehuffmancompression.cs

自适应huffman编码工具

					_eos = true;
					return -1;
				}

				// Move along the tree appropriately
				if (bit == 0) node = node.LeftChild;
				else if (bit == 1) node = node.RightChild;
				else throw new ApplicationException("Invalid bit in the stream.");
			}

			// We're at the leaf... if we are at an EOS node, we're done.  Set and return EOS.
			if (node.Type == AdaptiveHuffmanTreeNodeType.EndOfStream) 
			{
				_eos = true;
				return -1;
			}

			// We're at a leaf, so get the byte value for the node.  If the node is an 
			// NYT node, read the next byte as that is the byte to return.  Otherwise, 
			// return the byte represented by this node.  Make sure to update the tree 
			// before doing so.
			int readValue = (node.Type == AdaptiveHuffmanTreeNodeType.NYT) ?
				_bitStream.ReadByte() : node.Value;
			if (readValue < 0) 
			{
				// Something went wrong... set and return EOS.
				_eos = true;
				return readValue;
			}

			// Update the tree with the value
			_tree.UpdateTree((byte)readValue);

			return readValue;
		}
        
		/// <summary>Read and decompress an array of bytes from the input stream.</summary>
		/// <param name='buffer'>The destination buffer for the read bytes.</param>
		/// <param name='offset'>The position in the buffer at which to begin storing the read bytes.</param>
		/// <param name='count'>The number of bytes to read.</param>
		/// <returns>The number of bytes actually read.</returns>
		public override int Read(byte [] buffer, int offset, int count)
		{
			// Read each byte.  If it is valid, store it to the buffer.
			// Otherwise return how many bytes we've already read.  If we read
			// all required bytes, return the requested number.
			for(int i=offset; i<offset+count; i++) 
			{
				int readByte = ReadByte();
				if (readByte >= 0) buffer[i] = (byte)readByte;
				else return i-offset;
			}

			// Return the number of read bytes
			return count;
		}
		#endregion

		#region Other Stream Operations
		/// <summary>Flushes the stream underlying the BitStream.</summary>
		public override void Flush() 
		{ 
			// Just flush the base stream as we don't store any of the bytes
			// in this stream; flushing the base stream is sufficient.
			_bitStream.Flush();
		}
        
		/// <summary>Flushes the underlying stream and closes it.</summary>
		public override void Close() 
		{
			// Only do work if we're still open
			if (_open)
			{
				// If we're writing, add an end of stream marker to denote that we're done.
				if (_direction == StreamDirection.Write) 
				{
					int [] bits = _tree.GetBitEncoding(_tree.GetEOSNode());
					_bitStream.Write(bits, 0, bits.Length);
				}

				// Close the stream and reset the buffers for idealogical reasons.
				// We always want to close the bit stream here; the CloseBaseStream
				// applies to the bit stream's base.
				_bitStream.Close();
				_bitStream = null;
				_open = false;
				_eos = true;
			}
		}
		#endregion

		#region IDisposable and Finalization
		/// <summary>Clean up after the Huffman stream.</summary>
		void IDisposable.Dispose()
		{
			// Close the stream and suppress finalization
			Close();
			GC.SuppressFinalize(this);
		}

		/// <summary>Clean up after the Huffman stream.</summary>
		~AdaptiveHuffmanStream()
		{
			Close();
		}
		#endregion
        
		#region Not Supported Stream Operations
		/// <summary>Not Supported.</summary>
		public override long Length { get { throw new NotSupportedException("Can't seek on a compression stream."); } }
        
		/// <summary>Not Supported.</summary>
		public override void SetLength(long value) 
		{ 
			throw new NotSupportedException("Can't set the length of a compression stream."); 
		}
        
		/// <summary>Not Supported.</summary>
		public override long Seek(long offset, System.IO.SeekOrigin origin)
		{
			throw new NotSupportedException("Can't seek on a compression stream.");
		}
        
		/// <summary>Not Supported.</summary>
		public override void EndWrite(System.IAsyncResult asyncResult)
		{
			throw new NotSupportedException("Can't asynchronously access a compression stream.");
		}
        
		/// <summary>Not Supported.</summary>
		public override System.IAsyncResult BeginWrite(System.Byte[] buffer, int offset, int count, System.AsyncCallback callback, object state)
		{
			throw new NotSupportedException("Can't asynchronously access a compression stream.");
		}
        
		/// <summary>Not Supported.</summary>
		public override int EndRead(System.IAsyncResult asyncResult)
		{
			throw new NotSupportedException("Can't asynchronously access a compression stream.");
		}
        
		/// <summary>Not Supported.</summary>
		public override System.IAsyncResult BeginRead(System.Byte[] buffer, int offset, int count, System.AsyncCallback callback, object state)
		{
			throw new NotSupportedException("Can't asynchronously access a compression stream.");
		}
		#endregion
	}

	/// <summary>Represents a tree for use with adaptive Huffman coding.</summary>
	internal class AdaptiveHuffmanTree
	{
		#region Constants
		/// <summary>The maximum number of leaf nodes we can have (the size of the alphabet we can represent).</summary>
		private const int _alphabetSize = 258; // 256 byte values + EOS + NYT
		/// <summary>The maximum number of possible nodes in the tree.</summary>
		private const int _maxNodes = _alphabetSize * 2;
		/// <summary>The hashtable key for the NYT node.</summary>
		private const string _nytKey = "NYT";
		/// <summary>The hashtable key for the End Of Stream node.</summary>
		private const string _eosKey = "EOS";
		#endregion

		#region Member Variables
		/// <summary>The root node of the adaptive Huffman tree.</summary>
		private AdaptiveHuffmanTreeNode _root;
		/// <summary>A lookup table of all the leaf nodes in the tree for quick access.</summary>
		private Hashtable _nodeTable;
		#endregion

		#region Construction
		/// <summary>Initialize the adaptive Huffman tree.</summary>
		public AdaptiveHuffmanTree()
		{
			// Create the root internal node, the NYT node, and the EOS node.
			_root = new AdaptiveHuffmanTreeNode(AdaptiveHuffmanTreeNodeType.Internal, 0, 1, _maxNodes);
			_root.LeftChild = new AdaptiveHuffmanTreeNode(AdaptiveHuffmanTreeNodeType.NYT, 0, 0, _maxNodes - 2);
			_root.RightChild = new AdaptiveHuffmanTreeNode(AdaptiveHuffmanTreeNodeType.EndOfStream, 0, 1, _maxNodes - 1);

			// Link new nodes back to their parents (the root)
			_root.LeftChild.Parent = _root;
			_root.RightChild.Parent = _root;

			// Initialize the node lookup table
			_nodeTable = new Hashtable(_alphabetSize * 2, .5f);

			// Add the NYT and EOS nodes to the lookup table
			_nodeTable[_nytKey] = _root.LeftChild;
			_nodeTable[_eosKey] = _root.RightChild;
		}
		#endregion

		#region Public Functions
		/// <summary>Updates the tree to reflect a new byte value.</summary>
		/// <param name="value">The byte value with which to update the tree.</param>
		public void UpdateTree(byte value)
		{
			// Find the node that represents the byte value.  
			// If it doesn't exist, add it.
			AdaptiveHuffmanTreeNode current = GetValueNode(value);
			if (current == null) current = AddValueNode(value, 0); // we'll increment the value to 1 later

			// Now work our way up the tree.
			do
			{
				// Get the node in the tree with the highest number and with the same count
				// as the current node.  If that node is different from the current node
				// and is not an ancestor, swap 'em.
				AdaptiveHuffmanTreeNode highest = HighestWithSameCountFGK(current);
				if (current != highest && 
					current.Parent != highest) SwapNodes(current, highest);

				// Increment the count on this node and move up to the parent
				current.Count++;
				current = current.Parent;

			} while(current != null);
		}

		/// <summary>Returns an array of 0's and 1's, the encoding for a node.</summary>
		/// <param name="node">The node for which we want the bit encoding.</param>
		/// <returns>The encoding for a character in the tree.</returns>
		public int [] GetBitEncoding(AdaptiveHuffmanTreeNode node)
		{
			// Create a list to store the bits
			ArrayList list = new ArrayList();

			// Get the bits that make the path up the tree.
			while(node.Parent != null)
			{
				// Get the parent node and determine whether we were a 0 or a 1.
				// Move up the tree.
				list.Add(node.Parent.LeftChild == node ? 0 : 1);
				node = node.Parent;
			}

			// Return the bit array (we need to reverse it first as we inserted them 
			// in the incorrect order).
			list.Reverse();
			return (int[])list.ToArray(typeof(int));
		}

		/// <summary>Gets the node in the tree that represents the given byte.</summary>
		/// <param name="value">The value node for which to search.</param>
		/// <returns>The node if found; null, otherwise.</returns>
		public AdaptiveHuffmanTreeNode GetValueNode(byte value)
		{
			// Lookup the node in the table and return it if found, otherwise null.
			return (AdaptiveHuffmanTreeNode)_nodeTable[value];
		}

		/// <summary>Gets the NYT node in the tree.</summary>
		/// <returns>The NYT node in the tree.</returns>
		public AdaptiveHuffmanTreeNode GetNYTNode()
		{
			// Return the NYT node
			return (AdaptiveHuffmanTreeNode)_nodeTable[_nytKey];
		}

		/// <summary>Gets the End Of Stream node in the tree.</summary>
		/// <returns>The EOS node in the tree.</returns>
		public AdaptiveHuffmanTreeNode GetEOSNode()
		{
			// Return the EOS node
			return (AdaptiveHuffmanTreeNode)_nodeTable[_eosKey];
		}
		#endregion

		#region Tree Manipulation
		/// <summary>Swap two nodes in the tree by fixing references and node numbers.</summary>
		/// <param name="node1">The first node to swap.</param>
		/// <param name="node2">The second node to swap.</param>
		private void SwapNodes(AdaptiveHuffmanTreeNode node1, AdaptiveHuffmanTreeNode node2)
		{
			// Make sure we're not dealing with the root node
			if (node1.Parent == null || node2.Parent == null) throw new ApplicationException("Can't swap root nodes.");
		
			// Swap their node numbers
			int num = node1.Number;
			node1.Number = node2.Number;
			node2.Number = num;

			// We don't need to swap any children, but we do need to swap their parents'
			// references to them.  Note that we have to be careful if both nodes happen
			// to be siblings.
			AdaptiveHuffmanTreeNode oldLeft1 = node1.Parent.LeftChild, oldLeft2 = node2.Parent.LeftChild;
			if (oldLeft1 == node1) node1.Parent.LeftChild = node2;
			else node1.Parent.RightChild = node2;
			if (oldLeft2 == node2) node2.Parent.LeftChild = node1;
			else node2.Parent.RightChild = node1;

			// We also need to swap the references to the parents
			AdaptiveHuffmanTreeNode parent = node1.Parent;