deflatehuffmancoding.cs

PDF文件格式解析库源代码

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

namespace QiHe.CodeLib.Compress
{
    public static class DeflateHuffmanCoding
    {
        /// <summary>
        /// Compute Huffman codes from symbols' code lengths.
        /// 
        /// The Huffman codes used for each alphabet in the “deflate” format have two additional rules:
        /// · All codes of a given bit length have lexicographically consecutive values,
        ///    in the same order as the symbols they represent;
        /// · Shorter codes lexicographically precede longer codes.
        /// Given this rule, we can define the Huffman code for an alphabet just by giving the bit lengths of the codes
        /// for each symbol of the alphabet in order; this is sufficient to determine the actual codes.
        /// </summary>
        /// <param name="codeLengths"></param>
        /// <returns></returns>
        public static int[] AssignCodes(int[] codeLengths)
        {
            //Count the number of codes for each code length
            int maxlen = Algorithm.Maximum(codeLengths);
            //if (maxlen > 15)
            //{
            //    throw new Exception("Deflate Huffman code length can not exceeds 15.");
            //}

            int[] lengthCount = new int[maxlen + 1];

            for (int symbol = 0; symbol < codeLengths.Length; symbol++)
            {
                int numofbits = codeLengths[symbol];
                if (numofbits > 0)
                {
                    lengthCount[numofbits]++;
                }
            }

            //Find the numerical value of the smallest code for each code length
            int[] nextCode = new int[maxlen + 1];
            int code = 0;
            lengthCount[0] = 0;
            for (int len = 1; len <= maxlen; len++)
            {
                code = (code + lengthCount[len - 1]) << 1;
                nextCode[len] = code;
            }

            //Assign numerical values to all codes, 
            //using consecutive values for all codes of the same length
            int[] codes = new int[codeLengths.Length];
            for (int n = 0; n < codes.Length; n++)
            {
                int len = codeLengths[n];
                if (len != 0)
                {
                    codes[n] = nextCode[len];
                    nextCode[len]++;
                }
            }
            return codes;
        }
    }
}