一種基於部分霍夫曼樹的數據壓縮編碼方法
2023-07-17 02:33:41 1
一種基於部分霍夫曼樹的數據壓縮編碼方法
【專利摘要】本發明涉及一種基於部分霍夫曼樹的數據壓縮編碼方法，該方法首先通過較為粗略但計算十分簡便的方法為所有需編碼的字符預先分配一個編碼長度，從而構成一個分層的編碼表稱為預編碼表；然後以預編碼表為基礎對霍夫曼樹中一些特定部分進行構建；在構建部分霍夫曼樹的同時，動態的調整字符的編碼長度，實現對預編碼表的修改，直到其滿足了最優編碼表的條件為止。這樣不用構建一個完整的霍夫曼樹，就能獲得與經典霍夫曼算法同樣的編碼效果。採用本發明可以有效地消除經典霍夫曼算法中的冗餘計算，提高了編碼效率，用於對數據的編碼過程，提高實時性，同時降低對能源的消耗。
【專利說明】一種基於部分霍夫曼樹的數據壓縮編碼方法
【技術領域】
[0001] 本發明涉及數據壓縮領域，更具體地涉及一種基於部分霍夫曼樹的數據壓縮編碼 方法，以通過構建部分霍夫曼樹實現快速數據壓縮編碼的方法。
【背景技術】
[0002] 隨著計算機和網絡技術的蓬勃發展，整個網絡的數據量正呈指數型增長。雖然計 算機的處理速度、硬碟容量以及網絡帶寬也有了巨大的進步，但仍難以適應數據增長的速 度。如何將數據壓縮的更小，壓縮的更快一直以來都是人們積極研究的方向。
[0003] 熵編碼是數據壓縮的一種重要方式。簡單地說，熵編碼的內涵就是對一段數據中 出現概率高的字符用較短的碼字代替，相應的較少出現的字符則用相對長的碼字代替，這 樣就達到了對數據壓縮的目的，所以熵編碼可以看作是一個分配碼字的過程。在由q個字 符組成的字符集{叫，a 2，…，a,}中，字符ai(i=l，2,…，q)發生的概率為Pi，分配給它的編碼 長度為Q，最優編碼便是指平均編碼長度：
[0004]
【權利要求】
1. 一種基於部分霍夫曼樹的數據壓縮編碼方法，所述的編碼方法包括步驟： 1) 統計數據中各個字符的出現概率，得到字符集及與其相對應的概率集； 2) 對數據的字符集中的各個字符預先分配一個預編碼長度，構成分層的預編碼表；其 中，所述的預編碼表中每一層的字符擁有相同的編碼長度，較低層字符的概率小於較高層 字符的概率；該預編碼表中相鄰的兩層之間有一個固定的概率邊界，且相鄰兩個邊界值為 二倍關係； 3) 以預編碼表為基礎自底向上的逐層構建部分霍夫曼樹；在構建過程中，首先遞推的 計算各層的節點個數；如果一層中節點個數為偶數，則繼續計算上一層的節點個數；如果 一層中節點個數為奇數，需首先對該層節點個數偶數化，並動態調整字符的編碼長度，同時 更新編碼表；如果調整後的編碼表滿足最優編碼表的條件，則終止構建部分霍夫曼樹，否則 重複步驟3)繼續計算上一層的節點個數； 其中，所述最優編碼表的條件為
為編碼表中各個字 符的編碼長度； 4) 根據經過上述步驟3)修改後的預編碼表輸出最優編碼表，對數據進行壓縮編碼。
2. 根據權利要求1所述的數據壓縮編碼方法，其特徵在於，所述的預編碼表的層序即 該層字符的編碼長度。
3. 根據權利要求1或2所述的數據壓縮編碼方法，其特徵在於，所述的預編碼表的建立 方法包括步驟： 21) 確定分層邊界，規定第n層與第n-1層概率邊界值為：Un=2-n+°_5,第n層與第n+1層 概率邊界值為：Un+1=2f°_5 ; 22) 在字符集{叫，a2, ? ? ?，aq}中，若字符屮的概率Pi滿足Un < Pi彡Un+1，則將屮填入 預編碼表的第n層。
4. 根據權利要求1所述的數據壓縮編碼方法，其特徵在於，所述的步驟3)中計算部分 霍夫曼樹中各層的節點個數的公式為： Sn=Cn+Sn+1/2 (n=l，2，...，M); 其中，Sn為部分霍夫曼樹中第n層的節點個數，Cn為預編碼表第n層的字符個數，M為 最大層序。
5. 根據權利要求1所述的數據壓縮編碼方法，其特徵在於，所述的步驟3)中部分霍夫 曼樹第n層節點個數Sn為奇數時，對於該層節點個數進行偶數化具體包括以下步驟： 31) 找到第n層概率最大的節點C_與第n-1層概率最小的節點Cmin以及以它們為根 節點的樹T_和Tmin; 32) 以這兩棵樹作為左右子樹，構成一棵新樹； 33) 節點Cmax與節點Cmin的概率之和如果大於第n-1層的上界值，子樹Tmax中的所有節 點提升一層，否則就將子樹Tmin中的節點下降一層； 34) 找到被調整的子樹T_或者Tmin中所含的葉子節點，更新預編碼表中與其對應的字 符層序。
6. 根據權利要求5所述的數據壓縮編碼方法，其特徵在於，所述的步驟31)中尋找C_、 Tmax與Cmin、Tmin的具體步驟包括： 311) 設定一個層序的中間變量p，初始值為p=M ; 312) 將第p層概率最大的21?個節點按概率大小順序排列，依次作為左右子節點構建 2pti個新節點，新節點的概率等於其左右子節點概率的和；將這些新節點的概率逐個與編 碼錶中第P-1層字符的概率進行比較，得到這兩部分中概率最大的前21?個節點； 313) 類似於步驟312)將第p層概率最小的前2p_n+1個節點按概率大小順序排列，依次 作為左右子節點構建2^個新節點，新節點的概率等於其左右子節點概率的和；將這些新 節點的概率逐個與編碼表中第P-1層字符的概率進行比較，得到這兩部分中概率最小的前 2p_n個節點； 314) 如果p大於n，將p減1，重複執行步驟312)與步驟313);如果p等於n+1則輸出 第n層概率最大節點Cmax，並追溯該節點的構成，找出Tmax，將p減1，並執行步驟313);如果 P等於n則結束循環，輸出Cmin並追溯該節點的構成，找出Tmin ;。
7.根據權利要求1所述的數據壓縮編碼方法，其特徵在於，所述的步驟4)中對最優編 碼錶的輸出採用範式霍夫曼編碼規範。
【文檔編號】H03M7/40GK104283568SQ201310294301
【公開日】2015年1月14日 申請日期:2013年7月12日 優先權日:2013年7月12日
【發明者】臺玉朋, 王海斌, 汪俊 申請人:中國科學院聲學研究所