HuffmanTree的淺析和在C#中的算法實(shí)現(xiàn)

    無論是在我們的開發(fā)項(xiàng)目中，還是在我們的日常生活中，都會(huì)較多的涉及到文件壓縮。談到文件壓縮，可能會(huì)有人想問文件壓縮到底是怎么實(shí)現(xiàn)的，實(shí)現(xiàn)的原理是什么，對(duì)于開發(fā)人員來說，怎么實(shí)現(xiàn)這樣一個(gè)壓縮的功能。

     接下來，我們就來了解一下文件壓縮的相關(guān)知識(shí)。文件壓縮是如何實(shí)現(xiàn)的？這個(gè)我們就得了解一下數(shù)據(jù)結(jié)構(gòu)，因?yàn)槲募趬嚎s的過程中會(huì)轉(zhuǎn)化為數(shù)據(jù)流，那么如何將數(shù)據(jù)流進(jìn)行對(duì)應(yīng)的壓縮，這個(gè)問題就得靠算法來實(shí)現(xiàn)。那么文件壓縮的算法是什么呢？那就是HuffmanTree。

     提到HuffmanTree，我們就需要順道講講數(shù)據(jù)結(jié)構(gòu)和算法。在計(jì)算機(jī)中，數(shù)據(jù)結(jié)構(gòu)和算法可以說是程序的靈魂。

        數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。按照視點(diǎn)的不同，我們將數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。

     邏輯結(jié)構(gòu)：是指數(shù)據(jù)對(duì)象中數(shù)據(jù)元素之間的相互關(guān)系。邏輯結(jié)構(gòu)包含：集合結(jié)構(gòu)（集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一個(gè)集合外，他們之間沒有其他關(guān)系）；線性結(jié)構(gòu)（線性結(jié)構(gòu)中的數(shù)據(jù)元素之間是一對(duì)一的關(guān)系）；樹形結(jié)構(gòu)（樹形結(jié)構(gòu)的數(shù)據(jù)元素之間存在一種一對(duì)多的層次關(guān)系）；圖形結(jié)構(gòu)（圖形結(jié)構(gòu)的數(shù)據(jù)元素是多對(duì)多的關(guān)系）。

        物理結(jié)構(gòu)：是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)形式。物理結(jié)構(gòu)包含：順序存儲(chǔ)結(jié)構(gòu)（是把數(shù)據(jù)元素存放在地址連續(xù)的存儲(chǔ)單元里，其數(shù)據(jù)間的邏輯關(guān)系和物理關(guān)系是一致的）；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（是指把數(shù)據(jù)元素存放在任意的存儲(chǔ)單元里，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的）

     上面介紹了一下數(shù)據(jù)結(jié)構(gòu)的分類，當(dāng)然，說到HuffmanTree，那就需要提一下“樹形結(jié)構(gòu)”。

        樹：是N（N大于或等于0）個(gè)節(jié)點(diǎn)的有限集合。

     現(xiàn)在介紹一下樹的三種表示法：

         雙親表示法（在每個(gè)節(jié)點(diǎn)中，附設(shè)一個(gè)指示器指示雙親節(jié)點(diǎn)到鏈表中的位置）；

         孩子表示法（每個(gè)節(jié)點(diǎn)有多個(gè)指針域，其中每個(gè)指針指向一個(gè)棵樹的根節(jié)點(diǎn)，我們把這種方法叫做鏈表表示法）；

         孩子兄弟表示法（任意一棵樹，它的第一個(gè)孩子如果存在就是唯一的，它的友兄弟如果存在也是唯一的，因此，我們?cè)O(shè)置兩個(gè)指針，分別指向該節(jié)點(diǎn)的第一個(gè)孩子和此節(jié)點(diǎn)的又兄弟）。

     上面提到樹，現(xiàn)在介紹一下二叉樹。

         二叉樹：是N（N大于或等于0）個(gè)節(jié)點(diǎn)的有限集合，該集合或者為空，或者有一個(gè)根節(jié)點(diǎn)和兩棵互不相交的、分別稱為根節(jié)點(diǎn)的左子樹和右子樹的二叉樹組成。

     接下來介紹一下幾種特殊的二叉樹：

        斜樹：所有的節(jié)點(diǎn)都只有在左子樹的二叉樹叫做左斜樹。所有節(jié)點(diǎn)都是只有右子樹叫做右斜樹。

        滿二叉樹：在一棵二叉樹中，如果所有分支節(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹成為滿二叉樹。

        完全二叉樹：對(duì)一棵具有N個(gè)節(jié)點(diǎn)的二叉樹按層序編號(hào)，如果編號(hào)為I（1大于或等于I小于或等于N）的節(jié)點(diǎn)與同樣深度的滿二叉樹中編號(hào)為I的節(jié)點(diǎn)在二叉樹中位置完全相同，則這棵二叉樹成為完全二叉樹。

   前面我首先介紹了數(shù)據(jù)結(jié)構(gòu)的定義和分類，接著介紹了樹，二叉樹。最后讓我們一起來具體的了解一下HuffmanTree。

      從樹中的一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)之間的分支構(gòu)成兩個(gè)節(jié)點(diǎn)之間的路徑，路徑上的分支數(shù)目稱做路徑長(zhǎng)度。樹的路徑長(zhǎng)度就是從樹根到每一個(gè)節(jié)點(diǎn)的路徑長(zhǎng)度之和。節(jié)點(diǎn)的帶權(quán)的路徑長(zhǎng)度為從該節(jié)點(diǎn)到跟之間的路徑長(zhǎng)度與節(jié)點(diǎn)上權(quán)的乘積。樹的帶權(quán)路徑長(zhǎng)度為樹中所有葉子節(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。

      HuffmanTree：帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹稱做赫夫曼樹。（又稱做：最優(yōu)二叉樹）

      赫夫曼編碼：規(guī)定赫夫曼樹的左分支代表0，又分支代表1，則從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)所經(jīng)過的路徑分支組成的0和1的序列便為該節(jié)點(diǎn)對(duì)應(yīng)字符的編碼。

     以上介紹了 HuffmanTree的相關(guān)概念知識(shí)，現(xiàn)在就需要將這個(gè)數(shù)據(jù)結(jié)構(gòu)采用代碼實(shí)現(xiàn)，接下來提供一段采用C#代碼實(shí)現(xiàn)的 HuffmanTree。

      1.位流的基類：

/// <summary>
    /// 位流的基類。
    /// </summary>
    /// <remarks>
    /// 一個(gè)字節(jié)流轉(zhuǎn)換到一個(gè)位流的規(guī)則實(shí)現(xiàn)之間。
    /// </remarks>
    public abstract class BitStream
    {
        /// <summary>
        /// 在數(shù)據(jù)流上快速的獲取最大位數(shù)
        /// </summary>
        public abstract int MaxReadAhead { get; set; }

        /// <summary>
        /// 從流中讀取位。
        /// </summary>
        /// <param name="count">讀取的比特?cái)?shù)。</param>
        /// <returns>位為UInt32。</returns>
        public abstract uint Read(int count);

        /// <summary>
        /// 在流上查詢數(shù)據(jù)
        /// </summary>
        /// <param name="count">查詢的位數(shù)。</param>
        /// <returns>位為UInt32。</returns>
        /// <remarks>此方法不消耗位（即移動(dòng)文件指針）。</remarks>
        public abstract uint Peek(int count);

        /// <summary>
        /// 從流中消耗比特，而不返回它們。
        /// </summary>
        /// <param name="count">消耗的比特?cái)?shù)。</param>
        public abstract void Consume(int count);
    }

2.哈夫曼樹的實(shí)現(xiàn)：

/// <summary>
    ///哈夫曼樹的實(shí)現(xiàn)。
    /// </summary>
    /// <remarks>
    /// 創(chuàng)建一個(gè)查找表，將采取任何位序列（最大樹深度的長(zhǎng)度），指示輸出符號(hào)。在WIM文件，在實(shí)踐中，沒有一塊超過32768字節(jié)
    ///長(zhǎng)度，所以我們經(jīng)常會(huì)產(chǎn)生一個(gè)更大的查找表比它的數(shù)據(jù)編碼。這使得異?？焖俜?hào)查找O（1），但效率較低整體。
    /// </remarks>
    public sealed class HuffmanTree
    {
        // 每個(gè)符號(hào)的最大位
        private readonly int _numBits;

        // 最大符號(hào)
        private readonly int _numSymbols;

        private readonly uint[] _buffer;

        public HuffmanTree(uint[] lengths)
        {
            Lengths = lengths;
            _numSymbols = lengths.Length;

            uint maxLength = 0;
            for (var i = 0; i < Lengths.Length; ++i)
            {
                if (Lengths[i] > maxLength)
                {
                    maxLength = Lengths[i];
                }
            }

            _numBits = (int)maxLength;
            _buffer = new uint[1 << _numBits];

            Build();
        }

        public uint[] Lengths { get; set; }

        public uint NextSymbol(BitStream bitStream)
        {
            var symbol = _buffer[bitStream.Peek(_numBits)];

            // 我們可能在讀，復(fù)位比特流的位置
            bitStream.Consume((int)Lengths[symbol]);

            return symbol;
        }

        private void Build()
        {
            var position = 0;

            //對(duì)于每一位長(zhǎng)度…
            for (var i = 1; i <= _numBits; ++i)
            {
                // 檢查每個(gè)符號(hào)
                for (uint symbol = 0; symbol < _numSymbols; ++symbol)
                {
                    if (Lengths[symbol] != i) continue;
                    var numToFill = 1 << (_numBits - i);
                    for (var n = 0; n < numToFill; ++n)
                    {
                        _buffer[position + n] = symbol;
                    }

                    position += numToFill;
                }
            }

            for (var i = position; i < _buffer.Length; ++i)
            {
                _buffer[i] = uint.MaxValue;
            }
        }
    }

  赫夫曼樹和赫夫曼編碼對(duì)于帶權(quán)路徑的二叉樹做了一些了解，用于初步理解壓縮原理。對(duì)于數(shù)據(jù)結(jié)構(gòu)的理解，需要我們花費(fèi)很多的時(shí)間，也需要我們?cè)谶@些數(shù)據(jù)結(jié)構(gòu)中做一個(gè)細(xì)致的分類。