無(wú)需父級(jí)指針的遞歸Huffman編碼方法

一、引言

在高度信息化的社會(huì)中，大量數(shù)據(jù)的傳輸和存儲(chǔ)已成為人們?nèi)粘Ｉ詈凸ぷ髦胁豢苫蛉钡囊徊糠帧Ｈ欢瑪?shù)據(jù)傳輸?shù)乃俣韧艿接?jì)算機(jī)硬件性能、網(wǎng)絡(luò)帶寬等因素的限制。單純依靠提升硬件條件來(lái)提高傳輸效率顯然是不夠的。

在這種情況下，數(shù)據(jù)壓縮技術(shù)應(yīng)運(yùn)而生。數(shù)據(jù)壓縮是指在不丟失有用信息的前提下，減少數(shù)據(jù)量的過(guò)程。通過(guò)適當(dāng)?shù)臄?shù)據(jù)壓縮，可以顯著減少對(duì)存儲(chǔ)空間的需求，同時(shí)提高數(shù)據(jù)傳輸和處理的效率。因此，數(shù)據(jù)壓縮技術(shù)在解決數(shù)據(jù)存儲(chǔ)和傳輸問(wèn)題方面發(fā)揮著重要的作用。

哈夫曼編碼是一種經(jīng)典的無(wú)損數(shù)據(jù)壓縮算法。它首先對(duì)數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分析，根據(jù)不同數(shù)據(jù)元素出現(xiàn)的頻率分配不等長(zhǎng)的編碼。出現(xiàn)頻率高的數(shù)據(jù)被分配較短的編碼，而出現(xiàn)頻率低的數(shù)據(jù)被分配較長(zhǎng)的編碼。這樣可以使平均編碼長(zhǎng)度降低，從而提高數(shù)據(jù)傳輸?shù)男省?/p>

然而，在傳統(tǒng)的哈夫曼編碼方法中，哈夫曼樹的每個(gè)節(jié)點(diǎn)不僅需要左右孩子指針，還需要父級(jí)指針。這種方法不僅與正向思維相反，而且指針域會(huì)占用較大的空間。實(shí)際上，哈夫曼樹中有效的數(shù)據(jù)存儲(chǔ)只有符號(hào)和它對(duì)應(yīng)的頻率，指針的存在是為了輔助編碼順利進(jìn)行。因此，哈夫曼樹使用的輔助指針越少，空間效率越高。

為了解決上述問(wèn)題，本文提出了一種新的哈夫曼編碼方法。該方法無(wú)需父級(jí)節(jié)點(diǎn)指針，采用正向思維的編碼方式。它只需將哈夫曼樹遞歸遍歷一遍，即可獲得所有葉子節(jié)點(diǎn)的編碼。這不僅減少了哈夫曼樹節(jié)點(diǎn)的指針域，還保證了算法的時(shí)間效率依然最優(yōu)。

本文提出的改進(jìn)哈夫曼編碼算法，在保持壓縮率不變的同時(shí)，提高了空間利用率，有望為數(shù)據(jù)壓縮和通信領(lǐng)域帶來(lái)新的解決方案。

二、哈夫曼樹的構(gòu)建過(guò)程設(shè)計(jì)

（一）樹節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

在實(shí)現(xiàn)哈夫曼編碼算法時(shí)，合理設(shè)計(jì)樹節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)是關(guān)鍵。本文采用嵌套的結(jié)構(gòu)體來(lái)表示哈夫曼樹的節(jié)點(diǎn)。

樹節(jié)點(diǎn)結(jié)構(gòu)體包括左子節(jié)點(diǎn)指針、右子節(jié)點(diǎn)指針和參數(shù)表結(jié)構(gòu)體。其中，參數(shù)表結(jié)構(gòu)體又包括待編碼符號(hào)、該符號(hào)的頻率，以及該符號(hào)的編碼和該編碼的長(zhǎng)度。

除了樹節(jié)點(diǎn)本身，算法還需要使用一些輔助數(shù)據(jù)結(jié)構(gòu)來(lái)支持編碼過(guò)程。

節(jié)點(diǎn)指針隊(duì)列：用于暫存待處理的樹節(jié)點(diǎn)，按照節(jié)點(diǎn)頻率從小到大進(jìn)行排序。

編碼臨時(shí)棧：在遞歸遍歷哈夫曼樹時(shí)，用于臨時(shí)存儲(chǔ)每個(gè)葉子節(jié)點(diǎn)的編碼。

該數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)為構(gòu)建哈夫曼樹提供了基礎(chǔ)條件。具體而言，樹節(jié)點(diǎn)結(jié)構(gòu)體中的左右子節(jié)點(diǎn)指針用于構(gòu)建哈夫曼樹的拓?fù)浣Y(jié)構(gòu)。參數(shù)表結(jié)構(gòu)體則記錄了每個(gè)葉子節(jié)點(diǎn)的符號(hào)、頻率、編碼及其長(zhǎng)度等信息，為后續(xù)的編碼過(guò)程提供依據(jù)。

輔助的節(jié)點(diǎn)指針隊(duì)列用于存儲(chǔ)待處理的樹節(jié)點(diǎn)，并按照頻率從小到大的順序?qū)ζ溥M(jìn)行排序。這樣可以確保每次合并的兩個(gè)節(jié)點(diǎn)頻率最小，從而構(gòu)建最優(yōu)的哈夫曼樹。

編碼臨時(shí)棧則在遞歸遍歷哈夫曼樹時(shí)發(fā)揮作用，用于存儲(chǔ)每個(gè)葉子節(jié)點(diǎn)的編碼信息。通過(guò)這種方式，可以高效地獲得所有符號(hào)的編碼，而無(wú)需像傳統(tǒng)方法那樣從葉子節(jié)點(diǎn)向上遍歷到根節(jié)點(diǎn)。

本文設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)不僅能夠支持哈夫曼樹的構(gòu)建，還能夠?yàn)楹罄m(xù)的編碼過(guò)程提供便利，從而提高算法的整體效率。

（二）哈夫曼樹的構(gòu)建設(shè)計(jì)

根據(jù)給定的字符及其對(duì)應(yīng)的頻率，準(zhǔn)備好所有的樹節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)包含字符、頻率，以及指向左右子節(jié)點(diǎn)的指針。將這些準(zhǔn)備好的樹節(jié)點(diǎn)按照頻率從小到大的順序排序，并存入一個(gè)輔助隊(duì)列中。開(kāi)始循環(huán)處理隊(duì)列中的節(jié)點(diǎn)，每次從隊(duì)列中取出頻率最小的兩個(gè)節(jié)點(diǎn)。根據(jù)這兩個(gè)節(jié)點(diǎn)的情況，采取不同的操作。如果兩個(gè)節(jié)點(diǎn)都是葉子節(jié)點(diǎn)（即都是字符），則創(chuàng)建一個(gè)新的內(nèi)部節(jié)點(diǎn)，將這兩個(gè)節(jié)點(diǎn)作為它的左右子節(jié)點(diǎn)，新節(jié)點(diǎn)的頻率為兩個(gè)子節(jié)點(diǎn)頻率之和。如果兩個(gè)節(jié)點(diǎn)都是內(nèi)部節(jié)點(diǎn)（即都是樹），則直接將它們組合成一個(gè)新的內(nèi)部節(jié)點(diǎn)。如果一個(gè)節(jié)點(diǎn)是葉子節(jié)點(diǎn)，另一個(gè)是內(nèi)部節(jié)點(diǎn)，則創(chuàng)建一個(gè)新的內(nèi)部節(jié)點(diǎn)，將葉子節(jié)點(diǎn)作為左子節(jié)點(diǎn)，內(nèi)部節(jié)點(diǎn)作為右子節(jié)點(diǎn)。新節(jié)點(diǎn)的頻率為兩個(gè)子節(jié)點(diǎn)的頻率之和。將新創(chuàng)建的內(nèi)部節(jié)點(diǎn)重新插人隊(duì)列，并按照頻率從小到大的順序進(jìn)行排序。重復(fù)以上過(guò)程，當(dāng)隊(duì)列中只剩一個(gè)節(jié)點(diǎn)時(shí)，說(shuō)明構(gòu)建完成，且這個(gè)節(jié)點(diǎn)就是哈夫曼樹的根節(jié)點(diǎn)。在整個(gè)構(gòu)建過(guò)程中，應(yīng)始終保持隊(duì)列中節(jié)點(diǎn)按照頻率從小到大排序。這樣可以確保每次取出的兩個(gè)節(jié)點(diǎn)頻率最小，從而構(gòu)建帶權(quán)路徑長(zhǎng)度最小的哈夫曼樹。這種貪心策略保證了哈夫曼樹的最優(yōu)性。通過(guò)不斷地合并頻率最小的兩個(gè)節(jié)點(diǎn)，直到隊(duì)列中只剩下一個(gè)根節(jié)點(diǎn)，就成功地構(gòu)建出了哈夫曼樹。這個(gè)樹具有最優(yōu)的編碼性能，為接下來(lái)的編碼提供了條件。

三、無(wú)需父級(jí)指針的編碼方法算法說(shuō)明

（一）算法概要

本算法在編碼函數(shù)外設(shè)置了一個(gè)布爾標(biāo)記，用來(lái)記錄當(dāng)前節(jié)點(diǎn)是從父級(jí)節(jié)點(diǎn)的左或右側(cè)遍歷得到。若從父級(jí)節(jié)點(diǎn)的左側(cè)遍歷得到，那么該標(biāo)記為True，反之為False。函數(shù)內(nèi)部除先序遍歷所需的語(yǔ)句之外含有一個(gè)判斷當(dāng)前節(jié)點(diǎn)是否為葉子節(jié)點(diǎn)的語(yǔ)句。如果符合判斷條件，則把臨時(shí)棧中的編碼數(shù)據(jù)賦值給該葉子節(jié)點(diǎn)對(duì)應(yīng)字符的編碼，此處臨時(shí)棧不必清空，只需隨著遞歸的回退出棧一次即可，因?yàn)槲吹玫骄幋a的符號(hào)也包括臨時(shí)棧里的數(shù)據(jù)。遍歷從樹的根節(jié)點(diǎn)開(kāi)始，因采用先序遍歷，所以第一輪一定訪問(wèn)根節(jié)點(diǎn)的左孩子，因此標(biāo)記默認(rèn)為True。在編碼過(guò)程中，該標(biāo)記決定了人棧的是1還是0，若標(biāo)記為True，0人棧，反之，1人棧。

（二）算法詳細(xì)過(guò)程

算法過(guò)程如圖1所示。

1.訪問(wèn)哈夫曼樹的根節(jié)點(diǎn)。此時(shí)標(biāo)記默認(rèn)為True，入棧0。但由于該標(biāo)記記錄的是當(dāng)前節(jié)點(diǎn)是從父級(jí)節(jié)點(diǎn)的左或右側(cè)遍歷得到。而根節(jié)點(diǎn)沒(méi)有父級(jí)節(jié)點(diǎn)，所以此時(shí)人棧的0為無(wú)效數(shù)據(jù)，并且在后續(xù)永不參與編碼。

2.判斷該節(jié)點(diǎn)是否為葉子節(jié)點(diǎn)。（1）若不是葉子節(jié)點(diǎn)，則接下來(lái)一定訪問(wèn)它的左子樹（哈夫曼樹的節(jié)點(diǎn)只有度為0或度為2，若某節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，則它一定有左子樹）繼續(xù)將0人棧，并進(jìn)人下一層遞歸，訪問(wèn)左子樹。（2）若是葉子節(jié)點(diǎn)，則根據(jù)棧中元素對(duì)葉子節(jié)點(diǎn)進(jìn)行編碼操作，出棧，并回到上一層函數(shù)。

3.當(dāng)函數(shù)從左子樹回歸到上一層節(jié)點(diǎn)時(shí)，說(shuō)明即將遍歷右子樹，此時(shí)標(biāo)記為賦值為False，人棧1。當(dāng)函數(shù)不是從左子樹回歸到上一層時(shí)，說(shuō)明該節(jié)點(diǎn)以下的所有節(jié)點(diǎn)均訪問(wèn)完成，此時(shí)出棧一次。上述過(guò)程執(zhí)行到遍歷完所有節(jié)點(diǎn)，此時(shí)所有葉子節(jié)點(diǎn)的編碼也已經(jīng)完成。

（三）算法總結(jié)

該算法的核心在于使用一個(gè)標(biāo)記記錄哈夫曼樹的遍歷路徑。在遍歷過(guò)程中，直接通過(guò)標(biāo)記位記錄路徑，無(wú)需額外的數(shù)據(jù)結(jié)構(gòu)。并且利用哈夫曼樹結(jié)構(gòu)的特點(diǎn)（無(wú)度為1的節(jié)點(diǎn)），從而使程序在不依賴父級(jí)指針的情況下也可以記錄該節(jié)點(diǎn)被訪問(wèn)的路徑，因而節(jié)省一個(gè)指針域。這降低了哈夫曼樹的存儲(chǔ)空間開(kāi)銷。

四、算法分析及對(duì)比

（一）算法效率分析

在哈夫曼樹構(gòu)建階段，需要對(duì) n 個(gè)葉子節(jié)點(diǎn)進(jìn)行 n-1 次合并操作。每次合并操作的時(shí)間復(fù)雜度為0（1），因此，構(gòu)建哈夫曼樹的時(shí)間復(fù)雜度為O（n），構(gòu)建過(guò)程中需要的輔助隊(duì)列空間等于待編碼符號(hào)的個(gè)數(shù)，即空間復(fù)雜度為0（n）。在編碼階段，若有 n 個(gè)需要編碼的數(shù)據(jù)，即哈夫曼樹的葉子節(jié)點(diǎn)數(shù)量為 ，則哈夫曼樹共有2n-1個(gè)節(jié)點(diǎn)。該算法在編碼過(guò)程中對(duì)所有節(jié)點(diǎn)僅訪問(wèn)一次，因此，時(shí)間復(fù)雜度為0（n）。在編碼過(guò)程中使用了一個(gè)臨時(shí)棧。棧的空間需求與哈夫曼樹的深度有關(guān)，即哈夫曼樹的深度層數(shù)就是臨時(shí)棧所需要的空間個(gè)數(shù)。因此空間復(fù)雜度為0（ ）。

（二）算法對(duì)比

如圖2所示，方法1為從葉子向上編碼，需要順序表輔助，方法2為從根向下編碼，無(wú)需額外輔助，方法3為從根向下編碼，需要隊(duì)列輔助。以上三種方法都需要三類指針，即左右孩子指針和父級(jí)指針。本文方法為從根向下編碼，需要棧輔助，只需要左右孩子指針。

在時(shí)間效率方面，本文提出的算法對(duì)哈夫曼樹的每個(gè)節(jié)點(diǎn)都僅訪問(wèn)一次即可完成編碼，時(shí)間效率不小于目前已知的最優(yōu)編碼算法。同時(shí)，相較于需要額外儲(chǔ)存父級(jí)指針的前三種方法，本文方法的空間復(fù)雜度得到了顯著改善。

五、結(jié)束語(yǔ)

哈夫曼編碼作為一種經(jīng)典的無(wú)損數(shù)據(jù)壓縮算法，在通信和信息處理領(lǐng)域發(fā)揮著不可或缺的作用。本文提出的改進(jìn)哈夫曼編碼算法，在保持優(yōu)秀的時(shí)間效率的同時(shí)，顯著降低了算法的空間復(fù)雜度。這對(duì)于資源受限的移動(dòng)設(shè)備和嵌入式系統(tǒng)尤為重要。

哈夫曼樹作為哈夫曼編碼的基礎(chǔ)，其存儲(chǔ)空間的優(yōu)化直接影響整個(gè)算法的內(nèi)存占用。本文的改進(jìn)方案，通過(guò)巧妙地利用棧作為輔助數(shù)據(jù)結(jié)構(gòu)，避免了對(duì)父級(jí)指針的依賴，從而減少了哈夫曼樹的存儲(chǔ)空間。

與現(xiàn)有的哈夫曼編碼算法相比，本文提出的方法在時(shí)間效率方面不低于已知的改進(jìn)算法，且對(duì)哈夫曼樹的每個(gè)節(jié)點(diǎn)僅需訪問(wèn)一次即可完成編碼，達(dá)到了最優(yōu)時(shí)間效率。這種高效的時(shí)間效率和優(yōu)化后的空間效率，使得本文的改進(jìn)算法在文本、圖像和音頻壓縮等廣泛應(yīng)用場(chǎng)景中，都能發(fā)揮出色的性能。

本文提出的改進(jìn)哈夫曼編碼算法，在保持壓縮率不變的前提下，大幅降低了算法的內(nèi)存占用，這對(duì)于資源受限的移動(dòng)終端和嵌入式系統(tǒng)來(lái)說(shuō)尤為重要。該算法簡(jiǎn)單高效，值得在實(shí)際中進(jìn)一步推廣和應(yīng)用。

作者單位：閆智斌 史蕊 楊一蘭 河南大學(xué)軟件學(xué)院

參考文獻(xiàn)

[1]華東計(jì)算技術(shù)研究所（中國(guó)電子科技集團(tuán)公司第三十二研究所）.基于Huffman編碼的LZW數(shù)據(jù)壓縮方法及系統(tǒng)：CN201910646589.5[P].2023-01-03.

[2]劉幫濤，羅敏.改進(jìn)的赫夫曼樹（Huffman Tree）和赫夫曼編碼（HuffmanCode）構(gòu)造算法[J]福建電腦

[3]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）[M].北京：清華大學(xué)出版社，1997.

[4]吳晨暉，王映輝.一種基于自頂向下的哈夫曼編碼方法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2009，19（10）：51-53+58