adaptivehuffmancompression.cs

自适应huffman编码工具

			node1.Parent = node2.Parent;
			node2.Parent = parent;
		}

		/// <summary>Adds a new node to the tree to represent a new byte value.</summary>
		/// <param name="value">The value to add to the tree.</param>
		/// <param name="initialCount">The initial frequency count to store in the node.</param>
		/// <returns>The new value node.</returns>
		private AdaptiveHuffmanTreeNode AddValueNode(byte value, int initialCount)
		{
			// Get the old NYT node
			AdaptiveHuffmanTreeNode oldNYT = GetNYTNode();
	
			// Modify it to be an internal node
			oldNYT.Type = AdaptiveHuffmanTreeNodeType.Internal;
			
			// Create the new NYT node; make sure to link it up correctly to the parent.
			// This node has a number two less than the original.
			oldNYT.LeftChild = 
				new AdaptiveHuffmanTreeNode(AdaptiveHuffmanTreeNodeType.NYT, 0, 0, oldNYT.Number - 2);
			oldNYT.LeftChild.Parent = oldNYT;

			// Create the new byte value node; make sure to link it up correctly to the parent.
			// This node has a number one less than the original.
			oldNYT.RightChild = 
				new AdaptiveHuffmanTreeNode(AdaptiveHuffmanTreeNodeType.Value, value, initialCount, oldNYT.Number - 1);
			oldNYT.RightChild.Parent = oldNYT;

			// Fix up the node table to include both new nodes and the old NYT node
			// as a normal internal node.
			_nodeTable[_nytKey] = oldNYT.LeftChild;
			_nodeTable[value] = oldNYT.RightChild;

			// Return the new value node.
			return oldNYT.RightChild;
		}

		/// <summary>Find the highest-numbered node with the given count. (FGK algorithm)</summary>
		/// <param name="current">The starting node.</param>
		/// <returns>The current node if no higher nodes were found; the higher node, otherwise.</returns>
		/// <remarks>
		/// Use this HighestWithSameCount function to use the FGK algorithm for adaptive
		/// huffman compression method.  The FGK algorithm is often much faster than Vitter's
		/// variation and often produces results just as good; however, in some cases
		/// Vitter's method can produce better compression.
		/// </remarks>
		private AdaptiveHuffmanTreeNode HighestWithSameCountFGK(AdaptiveHuffmanTreeNode current)
		{
			// We'll start by saying that we're the highest
			AdaptiveHuffmanTreeNode highest = current;

			// Now we'll check our sibling to see if he's bigger.  He's the highest
			// if he's to our right and has the same count.
			if (current.Parent != null) 
			{
				// Does our right sibling have the same count?  If yes, he's the highest thus far.
				AdaptiveHuffmanTreeNode parent = current.Parent;
				if (parent.LeftChild == current &&
					parent.RightChild.Count == current.Count) highest = parent.RightChild;
				
				// Now we'll check our parent's siblings.  If his sibling has a higher
				// count, then he's the highest.
				if (parent.Parent != null) 
				{
					AdaptiveHuffmanTreeNode grandparent = parent.Parent;

					// If our parent is the right child, then check the left child's count.
					// If our parent is the left child, then check the right child's count. etc.
					// If one of these siblings has the same count as us, woo hoo!  Movin' on up.
					if (grandparent.LeftChild == parent &&
						grandparent.RightChild.Count == current.Count) highest = grandparent.RightChild;
					else if (grandparent.RightChild == parent &&
						grandparent.LeftChild.Count == current.Count) highest = grandparent.LeftChild;
				}
			}

			// Return the highest one we found
			return highest;
		}

		/// <summary>Find the highest-numbered node with the given count. (Vitter algorithm)</summary>
		/// <param name="current">The node whose count we want to find in the tree.</param>
		/// <returns>The node if found; null if no nodes have the given count.</returns>
		/// <remarks>
		/// Use this HighestWithSameCount function to use Vitter's variation of the adaptive
		/// huffman compression method.  Vitter's variation can produce better compression
		/// than the FGK algorithm, however it is much slower as it can require a full
		/// tree walk on every update to the tree.
		/// </remarks>
		private AdaptiveHuffmanTreeNode HighestWithSameCountVitter(AdaptiveHuffmanTreeNode current)
		{
			// Get the count
			long count = current.Count;

			// Create a queue to hold the nodes and add the root node as the starting node
			Queue levelQueue = new Queue();
			levelQueue.Enqueue(_root);

			// While there are more nodes to look at...
			while(levelQueue.Count > 0) 
			{
				// Get the next node from the queue.  If it is the correct count, return it,
				// as we're processing the nodes in order from highest to lowest number.
				AdaptiveHuffmanTreeNode node = (AdaptiveHuffmanTreeNode)levelQueue.Dequeue();
				if (node.Count == count) return node;

				// Add the right and then the left child; we add the right first as it has
				// a higher number.  And since a node must have two children if it has at least
				// one, we can just check to see if it has one child.
				if (node.RightChild != null) 
				{
					levelQueue.Enqueue(node.RightChild);
					levelQueue.Enqueue(node.LeftChild);
				}
			}

			// Uh oh... couldn't find a node with the given count.
			// Something went wrong as we should have at least found current, assuming
			// it was in the tree, which it should have been.
			return null;
		}
		#endregion

		#region Properties
		/// <summary>Gets the root node of the Huffman tree.</summary>
		public AdaptiveHuffmanTreeNode RootNode { get { return _root; } }
		#endregion

		#region Debugging Functions
		/// <summary>Renders the tree in human readable form for debugging purposes.</summary>
		/// <returns>A string rendering of the tree.</returns>
		internal string Render()
		{
			string text = "";
			if (_root != null) 
			{
				text += "Depth: " + Depth(_root) + Environment.NewLine;
				text += Render(_root, 0);
			}
			return text;
		}

		/// <summary>Renders a node of the tree in human readable form for debugging purposes.</summary>
		/// <param name="node">The node to render.</param>
		/// <param name="level">The indentation level for this node.</param>
		/// <returns>A string rendering of the tree.</returns>
		private string Render(AdaptiveHuffmanTreeNode node, int level)
		{
			System.Text.StringBuilder sb = new System.Text.StringBuilder();

			// Print information about the node
			sb.Append(PrintTabs(level) + "Type: " + node.Type + Environment.NewLine);
			sb.Append(PrintTabs(level) + "Number: " + node.Number + Environment.NewLine);
			sb.Append(PrintTabs(level) + "Count: " + node.Count + Environment.NewLine);
			sb.Append(PrintTabs(level) + "Value: " + node.Value + 
				"(" + (Char.IsControl((char)node.Value) ? '-' : (char)node.Value) + ")" + Environment.NewLine);
			
			// Print the left child
			if (node.LeftChild != null)
			{
				sb.Append(PrintTabs(level+1) + "---- Left ----" + Environment.NewLine);
				sb.Append(Render(node.LeftChild, level+1));
			}

			// Print the right child
			if (node.RightChild != null) 
			{
				sb.Append(PrintTabs(level+1) + "---- Right ----" + Environment.NewLine);
				sb.Append(Render(node.RightChild, level+1));
			}

			// Return the rendering
			return sb.ToString();
		}

		/// <summary>Creates an indentation string for use in rendering.</summary>
		/// <param name="level">How many levels to indent.</param>
		/// <returns>String full of tabs for indentation to a certain level.</returns>
		private string PrintTabs(int level)
		{
			string tabs = "";
			for(int i=0; i<level; i++) tabs += "\t\t";
			return tabs;
		}

		/// <summary>Gets the depth of the tree starting at a particular node.</summary>
		/// <param name="node">The node for which we're computing the depth.</param>
		/// <returns>The depth starting at the given node.</returns>
		private int Depth(AdaptiveHuffmanTreeNode node)
		{
			// Get the left size and the right size.  Add ourselves to the max of the two.
			if (node == null) return 0;
			int leftDepth = Depth(node.LeftChild);
			int rightDepth = Depth(node.RightChild);
			return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
		}

		/// <summary>List all of the values in the tree and their associated weights.</summary>
		/// <returns>A string description of all the values in the tree and their associated weights.</returns>
		private string ListValueNodeCounts()
		{
			// Create a StringBuilder to hold the text
			System.Text.StringBuilder sb = new System.Text.StringBuilder();

			// Get all possible byte values that could be in the tree
			for(int b=0; b<256; b++) 
			{
				// Get the node if it exists
				AdaptiveHuffmanTreeNode node = GetValueNode((byte)b);
				if (node != null) 
				{
					// Print out information on the node
					sb.Append(
						"[" + (Char.IsControl((char)node.Value) ? '-' : (char)node.Value) + "]: "
						+ node.Count + Environment.NewLine);
				}
			}

			// Return the information
			return sb.ToString();
		}
		#endregion
	}

	/// <summary>Represents a node in the adaptive Huffman tree.</summary>
	internal class AdaptiveHuffmanTreeNode
	{
		#region Member Variables
		/// <summary>The node number of the node.</summary>
		private int _number;
		/// <summary>The frequency count of the byte value in the node.</summary>
		private long _count;
		/// <summary>The byte value stored in the node.</summary>
		private byte _value;
		/// <summary>The node type of the node.</summary>
		private AdaptiveHuffmanTreeNodeType _type;
		/// <summary>The left child of the node.</summary>
		private AdaptiveHuffmanTreeNode _leftChild;
		/// <summary>The right child of the node.</summary>
		private AdaptiveHuffmanTreeNode _rightChild;
		/// <summary>The parent of the node.</summary>
		private AdaptiveHuffmanTreeNode _parent;
		#endregion

		#region Construction
		/// <summary>Initialize the node.</summary>
		/// <param name="type">The node type of the node.</param>
		/// <param name="value">The byte value to store in the node.</param>
		/// <param name="count">The frequency count of the byte value in the node.</param>
		/// <param name="number">The node number of the node.</param>
		public AdaptiveHuffmanTreeNode(AdaptiveHuffmanTreeNodeType type, byte value, long count, int number)
		{
			// Store the data in the node
			_value = value;
			_number = number;
			_count = count;
			_type = type;
		}
		#endregion

		#region Properties
		/// <summary>Gets or sets the node number of this node.</summary>
		public int Number { get { return _number; } set { _number = value; } }
		/// <summary>Gets or sets the frequency count of this node.</summary>
		public long Count { get { return _count; } set { _count = value; } }
		/// <summary>Gets or sets the byte value of this node.</summary>
		public byte Value { get { return _value; } set { _value = value; } }
		/// <summary>Gets or sets the node type of this node.</summary>
		public AdaptiveHuffmanTreeNodeType Type { get { return _type; } set { _type = value; } }
		/// <summary>Gets or sets the left child of this node.</summary>
		public AdaptiveHuffmanTreeNode LeftChild { get { return _leftChild; } set { _leftChild = value; } }
		/// <summary>Gets or sets the right child of this node.</summary>
		public AdaptiveHuffmanTreeNode RightChild { get { return _rightChild; } set { _rightChild = value; } }
		/// <summary>Gets or sets the parent of this node.</summary>
		public AdaptiveHuffmanTreeNode Parent { get { return _parent; } set { _parent = value; } }
		#endregion
	}
	
	/// <summary>Types of adaptive Huffman tree nodes.</summary>
	internal enum AdaptiveHuffmanTreeNodeType 
	{ 
		/// <summary>Node that represents an Not Yet Transmitted special node marker.</summary>
		NYT,
		/// <summary>Node that represents an End Of Stream special node marker.</summary>
		EndOfStream,
		/// <summary>Node that represents a byte value in the tree.</summary>
		Value,
		/// <summary>Node that represents an internal node, just part of the tree.</summary>
		Internal 
	};
}