packagemergealgorithm.cs

PDF文件格式解析库源代码

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

namespace QiHe.CodeLib.Compress
{
    /// <summary>
    /// A Fast algorithm for optimal length-limited Huffman codes
    /// </summary>
    /// <remarks>
    /// Reference:
    /// L. L. Larmore and D. S. Hirschberg, 
    /// "A Fast algorithm for optimal length-limited Huffman codes,"
    /// Journal of the ACM 37 (1990) pp. 464-473 
    /// </remarks>
    public class PackageMergeAlgorithm
    {
        class Package
        {
            public int Weight;
            public int Height;
            public int Symbol;
            public Package LeftChild;
            public Package RightChild;

            public Package(int symbol, int weight)
            {
                this.Height = 0;
                this.Weight = weight;
                this.Symbol = symbol;
            }

            public Package(Package subPackage1, Package subPackage2)
            {
                this.Symbol = -1;
                this.LeftChild = subPackage1;
                this.RightChild = subPackage2;
                this.Weight = subPackage1.Weight + subPackage2.Weight;
                this.Height = Math.Max(subPackage1.Height, subPackage2.Height) + 1;
            }
        }

        /// <summary>
        /// Calculate code lengths for symbols
        /// </summary>
        /// <param name="weights">symbols weights</param>
        /// <param name="maxLength">code length limit</param>
        /// <returns>code lengths</returns>
        public static int[] Solve(int[] weights, int maxLength)
        {
            List<Package> items = new List<Package>();
            for (int symbol = 0; symbol < weights.Length; symbol++)
            {
                int weight = weights[symbol];
                if (weight > 0)
                {
                    Package package = new Package(symbol, weight);
                    items.Add(package);
                }
            }

            if (items.Count == 1)
            {
                int[] codeLengths = new int[weights.Length];
                codeLengths[items[0].Symbol] = 1;
                return codeLengths;
            }

            if (items.Count > 1 << maxLength)
            {
                throw new Exception("Too many symbols to be coded within " + maxLength + " bits.");
            }
            SortSymbols(items);

            List<Package> packages = items;

            int totalWidth = packages.Count - 1;
            List<int> powers = DiadicExpansion(totalWidth);
            int minpower = powers[powers.Count - 1];
            int level = -maxLength;

            List<Package> solution = new List<Package>();
            while (true)
            {
                if (level > minpower)
                {
                    throw new Exception("No solution in PackageMergeAlgorithm.");
                }
                else if (level == minpower)
                {
                    //the width of packages[0] is 2^(-level)
                    solution.Add(packages[0]);
                    packages.RemoveAt(0);

                    //the minwidth of totalWeight is 2^(-minpower)
                    powers.RemoveAt(powers.Count - 1);

                    if (powers.Count == 0)
                    {
                        //assert(packages.Count == 0);
                        break;
                    }
                    else
                    {
                        minpower = powers[powers.Count - 1];
                    }
                }
                level++;
                int count = level < 0 ? items.Count : 0;
                packages = PACKAGE(packages, count);
                if (level < 0)
                {
                    MERGE(packages, items);
                }
            }

            return ConvertToCodeLengths(weights.Length, solution);
        }

        private static int[] ConvertToCodeLengths(int count, List<Package> solution)
        {
            int[] codeLengths = new int[count];
            foreach (Package package in solution)
            {
                CountSymbols(package, codeLengths);
            }
            return codeLengths;
        }

        static List<Package> PACKAGE(List<Package> items, int count)
        {
            int num = items.Count / 2;
            List<Package> packages = new List<Package>(num + count);
            for (int i = 0; i < num; i++)
            {
                Package package = new Package(items[2 * i], items[2 * i + 1]);
                packages.Add(package);
            }
            return packages;
        }

        private static void MERGE(List<Package> packages, List<Package> items)
        {
            packages.AddRange(items);
            SortPackage(packages);
        }

        private static void SortPackage(List<Package> packages)
        {
            packages.Sort(delegate(Package item1, Package item2)
            {
                if (item1.Weight == item2.Weight)
                {
                    return item1.Height - item2.Height;
                }
                else
                {
                    return item1.Weight - item2.Weight;
                }
            });
        }

        private static void SortSymbols(List<Package> items)
        {
            items.Sort(delegate(Package item1, Package item2)
            {
                if (item1.Weight == item2.Weight)
                {
                    return item1.Symbol - item2.Symbol;
                }
                else
                {
                    return item1.Weight - item2.Weight;
                }
            });
        }

        static void CountSymbols(Package package, int[] codeLengths)
        {
            if (package.Symbol == -1)
            {
                CountSymbols(package.LeftChild, codeLengths);
                CountSymbols(package.RightChild, codeLengths);
            }
            else
            {
                codeLengths[package.Symbol]++;
            }
        }

        /// <summary>
        /// representation of x as powers of 2.
        /// </summary>
        /// <param name="x">non-negative number</param>
        /// <returns></returns>
        static List<int> DiadicExpansion(int x)
        {
            List<int> powers = new List<int>();

            while (x > 0)
            {
                int log = (int)Math.Log(x, 2);
                int pow = (int)Math.Pow(2, log);
                if (pow * 2 == x)
                {
                    log += 1;
                    pow *= 2;
                }
                x = x - pow;
                powers.Add(log);
            }

            return powers;
        }
    }
}