huffmanalgorithm.cs

PDF文件格式解析库源代码

using System;
using System.Collections.Generic;
using System.Text;

namespace QiHe.CodeLib.Compress
{
    public class HuffmanAlgorithm
    {
        public static int[] ComputeOptimalCodeLengths(int[] symbolWeights)
        {
            BinaryTree tree = BuildTreeFromSymbolWeights(symbolWeights);
            int[] codeLengths = new int[symbolWeights.Length];
            foreach (Pair<int, int> pair in tree.GetSymbolCodeLengths())
            {
                codeLengths[pair.Left] = pair.Right;
            }
            return codeLengths;
        }

        /// <summary>
        /// Build Binary Huffman Tree From Symbol Weights(frequencies/probabilities)
        /// </summary>
        /// <param name="symbolWeights"></param>
        /// <returns></returns>
        static BinaryTree BuildTreeFromSymbolWeights(int[] symbolWeights)
        {
            Dictionary<BinaryTreeNode, int> nodes = new Dictionary<BinaryTreeNode, int>();
            for (int symbol = 0; symbol < symbolWeights.Length; symbol++)
            {
                if (symbolWeights[symbol] > 0)
                {
                    nodes.Add(new BinaryTreeLeafNode(symbol), symbolWeights[symbol]);
                }
            }

            if (nodes.Count == 1)
            {
                BinaryTreeInternalNode root = new BinaryTreeInternalNode();
                root.ChildNodes[1] = new List<BinaryTreeNode>(nodes.Keys)[0];
                BinaryTree tree = new BinaryTree(root);
                return tree;
            }
            else
            {
                List<BinaryTreeNode> sortedNodes = SortTreeNodes(nodes);

                Queue<BinaryTreeLeafNode> leafNodes = new Queue<BinaryTreeLeafNode>(nodes.Count);
                Queue<BinaryTreeInternalNode> interNodes = new Queue<BinaryTreeInternalNode>(nodes.Count - 1);

                foreach (BinaryTreeLeafNode leafNode in sortedNodes)
                {
                    leafNodes.Enqueue(leafNode);
                }

                while (leafNodes.Count + interNodes.Count > 1)
                {
                    BinaryTreeNode node1 = GetMinimunWeightNode(leafNodes, interNodes, nodes);
                    BinaryTreeNode node2 = GetMinimunWeightNode(leafNodes, interNodes, nodes);
                    BinaryTreeInternalNode interNode = CreateInternalNode(nodes, node1, node2);
                    interNodes.Enqueue(interNode);
                }

                BinaryTreeInternalNode root = interNodes.Dequeue();
                BinaryTree tree = new BinaryTree(root);
                return tree;
            }
        }

        private static BinaryTreeNode GetMinimunWeightNode(Queue<BinaryTreeLeafNode> leafNodes, Queue<BinaryTreeInternalNode> interNodes, Dictionary<BinaryTreeNode, int> nodes)
        {
            if (interNodes.Count == 0)
            {
                return leafNodes.Dequeue();
            }
            if (leafNodes.Count == 0)
            {
                return interNodes.Dequeue();
            }
            BinaryTreeNode node1 = leafNodes.Peek();
            BinaryTreeNode node2 = interNodes.Peek();
            if (nodes[node1] <= nodes[node2])
            {
                return leafNodes.Dequeue();
            }
            else
            {
                return interNodes.Dequeue();
            }
        }

        private static List<BinaryTreeNode> SortTreeNodes(Dictionary<BinaryTreeNode, int> nodes)
        {
            List<BinaryTreeNode> sortedNodes = new List<BinaryTreeNode>(nodes.Keys);
            sortedNodes.Sort(delegate(BinaryTreeNode node1, BinaryTreeNode node2)
            {
                return nodes[node1] - nodes[node2];
            });
            return sortedNodes;
        }

        private static BinaryTreeInternalNode CreateInternalNode(Dictionary<BinaryTreeNode, int> nodes, BinaryTreeNode node1, BinaryTreeNode node2)
        {
            BinaryTreeInternalNode interNode = new BinaryTreeInternalNode();
            interNode.ChildNodes[0] = node1;
            interNode.ChildNodes[1] = node2;
            int weight = nodes[node1] + nodes[node2];
            nodes.Remove(node1);
            nodes.Remove(node2);
            nodes.Add(interNode, weight);
            return interNode;
        }
    }
}