一種基於非完備碼錶解析碼長的哈夫曼解碼方法
2023-06-14 04:10:56
專利名稱：一種基於非完備碼錶解析碼長的哈夫曼解碼方法
技術領域：
本發明涉及一種哈夫曼解碼方法，尤其涉及一種基於非完備碼錶快速解析碼長的
哈夫曼解碼方法。
背景技術：
哈夫曼算法是一種根據待壓縮數據中各元素出現的概率進行編碼和解碼的算法， 能無損的壓縮數據所佔用的空間。圖1是一個哈夫曼碼字生成樹的例子，以其碼字為葉子， 碼字所屬層數為級別數。 解析哈夫曼碼時，先確定要解析的碼流的首個碼字長度，將其取出，用哈夫曼編碼 提供的符號表就可以找到這個碼字所對應的數據元素。除去碼流裡的首個碼字，將剩餘的 碼流按上述方法逐一解析，即可完成哈夫曼的解碼過程。由於哈夫曼編碼是變長編碼，在整 個解碼過程中，必須解決的一個問題是確定哈夫曼碼字的長度，以下描述了哈夫曼解碼中 碼字長度解析的常見解決方案 1、級別比較解析法。基於哈夫曼碼字生成樹建立一個葉子檢索表來指示最近下一 級存在哈夫曼碼字的級別(等同碼字長度)，並將同一級上最小碼字作為前綴位，其餘位補 O，擴充到最大碼長長度。以哈夫曼前綴碼所在級別為索引，以這個擴充碼為索引值，建一 張各級最小哈夫曼碼字為前綴的定長碼字檢索表。在哈夫曼碼碼長解析時，按葉子檢索表 O級檢索下一級別，並以這個下一級別檢索定長碼字檢索表裡的碼字，取出最大碼長長度的 碼流數值與之比較，如果這個碼流數值不小於定長碼字檢索表裡的碼字，葉子檢索表的當 前級別用下一級別替換，並用這個新的當前級別檢索下一級存在葉子的級別，然後用這個 新的下一級級別檢索定長碼字檢索表裡的碼字，用碼流數值與之比較，直到碼流數值小於 定長碼字檢索表裡的碼字，此時葉子檢索表裡當前級別和碼流裡存在的碼字長度相同。
2、完備碼錶解析法。基於碼流中所包含的所有哈夫曼碼字生成樹的葉子碼字，建 立一張完備碼長碼錶。這個完備碼長碼錶的每項索引以哈夫曼碼字為前綴、按一定規則擴 展到最大碼長長度，其索引值為相應的哈夫曼前綴碼碼長。對於當前待解析的哈夫曼碼流， 按照其待解析碼字所屬的哈夫曼碼字生成樹，在定長碼字完備碼長碼錶中檢索到與這個哈 夫曼碼字生成樹相對應的碼錶部分。以最大碼字長度截取當前待解析的哈夫曼碼流，並將 這個截取出的碼流數值作為索引，在當前碼流哈夫曼碼字生成樹對應的碼長碼錶部分檢 索，檢索到的當前碼長碼錶值即為當前待解析碼流中首個碼字碼長。 得到碼長後提取首個碼字，在當前哈夫曼碼字生成樹所對應的符號表中即可解析 到當前碼字所對應的數據。從碼流中除去已解析的部分，在剩餘碼流中繼續逐個操作，即可 完成所有哈夫曼碼的解析。 現有普遍使用的哈夫曼解碼算法雖然利用了編碼表體現的碼字出現的概率，並基 於哈夫曼碼生成樹各級葉子的存在性對檢索算法進行了優化，但對於絕大部分碼字，碼長 均需要多次才能確定，在總的解碼算法中耗時比例較大；基於完備碼錶解析碼長雖然提高 了碼長解析速度，但是對於嵌入式系統的硬體存儲要求而言，其空間複雜度增加太大，難以滿足要求。 在音頻、視頻領域，基於哈夫曼數據壓縮的編碼、解碼算法在嵌入式系統中應用非 常廣泛。在哈夫曼算法中，碼字以變長二進位前綴碼表示，為了解析一個哈夫曼碼字，必須 先解析哈夫曼碼字的字長，傳統的碼長解析算法不是速度過慢就是碼錶數據量過大，如何 在不增加碼錶數據量的同時減少碼長解析的時間，這對於哈夫曼解碼有很重要的意義。
發明內容
本發明目的在於提供一種基於非完備碼錶解析碼長的哈夫曼解碼方法，該方法可 以大大減少碼錶佔用的儲存空間和加快解碼速度。 本發明的目的可以通過以下方案實現一種基於非完備碼錶的哈夫曼解碼方法， 步驟包括 1、按級別比較解析法，構建所有用於級別比較解析的碼錶，包括葉子檢索表和各 級哈夫曼最小碼字為前綴的定長碼字檢索表； 2、確定非完備碼錶臨界碼長L :從最小碼長和最大碼長之間選擇一個值L，作為構 建非完備碼錶的臨界碼長； 3、基於碼流中所包含的所有哈夫曼碼字生成樹的不超過臨界碼長L比特的葉子 碼字，再構建一個以哈夫曼碼字為前綴的L比特非完備碼錶； 4、按照當前碼流中待解析部分所屬的哈夫曼碼字生成樹，讀取最大碼長長度的碼 流數值，以這個碼流數值為索引，按照當前待解析碼流所屬的哈夫曼碼字生成樹，在對應的 以各級哈夫曼最小碼字為前綴的定長碼字檢索表裡檢索級別(碼長)為(L+l)的碼字；
5、比較碼流數值與剛檢索到的(L+l)級的定長碼字，若碼流數值小於剛檢索到的 碼字，以碼流數值的前L比特為新的索引，在對應的非完備碼長碼錶部分檢索，檢索到的值 即為當前碼流待解析部分首個碼字碼長；反之，以舊的碼流數值作為比較對象，按照級別比 較解析法，解析其對應的L級之後的首個碼字長度； 6、根據已解析的碼長，在當前碼流中提取其碼字，基於碼字對應的符號表，查取其 對應符號值，即可完成碼流中首個碼字的解析； 7、從當前碼流中剔除已經解析的碼字，將剩餘碼流重複步驟4、5、6，即可完成所有 哈夫曼碼的解碼。 所述的非完備碼長碼錶以碼流包含的每個哈夫曼碼字生成樹為單位，按相同的方 式逐一構建；對於每棵哈夫曼碼字生成樹，以不超過L比特的哈夫曼碼字為前綴，其餘位由 全0到全1擴展到L比特長度，建立非完備碼長碼錶的索引；索引指向的值為哈夫曼前綴碼 碼長。 所述的每個哈夫曼碼字生成樹對應的碼長碼錶部分構建過程首先，按照對應的 哈夫曼碼字生成樹，構建L比特長度的各個比特位為全O到全1的索引，並將所有索引值 (即碼長碼錶值)初始化為0 ;以哈夫曼生成樹的所有不超過L比特葉子碼子為前綴，將剩 餘碼字位以全0到全1填充到L比特長度，將所有同哈夫曼碼字前綴的擴充碼的碼長碼錶 值以對應哈夫曼前綴碼的長度賦值。 本發明可以大大減少存儲空間和加快了檢測速度。例如當最大碼長為N( —般為
416)時，級別比較解析法的碼長解析時間複雜度為o(l>, x/ )—其中Pi為碼長為i的碼
字的統計概率，每個描述符對應的碼長碼錶空間複雜度為N ;完備碼錶碼長解析時間複雜 度為O(l)，對應每個描敘符的完備碼長碼錶空間複雜度為(2~N);對比於這兩種技術，非完
備碼錶碼長解析法的時間複雜度為0(1+^P, XZ')，接近於完備碼錶馬場時間解析複雜度，
其對應的每個描述符的空間複雜度為(2'8+N)，按普通碼長16計算，其空間複雜度只有完 備碼錶解析法的i ，極大地節省了存取空間。
圖1是現有技術中的哈夫曼碼字生成樹； 圖2是本發明的單個哈夫曼碼字生成樹對應的非完備碼長碼錶生成流程示意圖；
圖3是本發明的碼長解析流程示意圖。
具體實施例方式
先構建一個基於級別比較解析法的用於檢索定長碼字的碼錶；按現有技術中的級 別比較解析法，構建所有用於級別比較解析的碼錶，包括葉子檢索表和各級哈夫曼最小碼 字為前綴的定長碼字檢索表； 再構建一個以哈夫曼碼字為前綴的L比特非完備碼錶基於碼流中所包含的所有 哈夫曼碼字生成樹的不超過L比特的葉子碼字，建立一張非完備碼長碼錶，L為構建非完備 碼錶的臨界碼長，從最小碼長和最大碼長之間選擇，對於最大碼長為16位的碼錶，推薦使 用8作為臨界碼長L。這個非完備碼長碼錶的每項索引以不超過L比特的哈夫曼碼字為前 綴、其餘由全0到全1擴展到L比特長度，其索引值為相應的哈夫曼前綴碼碼長。在這個非 完備碼長碼錶的構建過程中，以碼流包含的每個哈夫曼碼字生成樹為單位，按相同的方式 逐一構建。 每個哈夫曼碼字生成樹對應的碼長碼錶部分構建過程如下，首先，按照對應的哈 夫曼碼字生成樹，構建L比特長度的各個比特位為全O到全1的索引，並將所有索引值(即 碼長碼錶值)初始化為0 ;以哈夫曼生成樹的所有不超過L比特葉子碼子為前綴，將剩餘碼 字位以全0到全1填充到L比特長度，將所有同哈夫曼碼字前綴的擴充碼的碼長碼錶值以 對應哈夫曼前綴碼的長度賦值。 圖2是選用8比特非完備碼長碼錶構建過程中單個哈夫曼碼字生成樹對應部分的
處理，其中當前級別、當前葉子數和當前碼字在當前級別中的位序均從o起始。具體步驟如
下 1、初始化將所有碼長設為0，並設置當前級別為1 ; 2、計算當前級別葉子總數；然後設置當前級別當前葉子位序位0 ; 3、以葉子位序對應碼字為前綴碼，補0到L位，計算其擴充碼字總數；然後設置當
前葉子當前碼字位序位O; 4、以擴充碼字加其位序位索引，索引值為當前級別值；
5、比較擴充碼字位序是否小於當前碼字總數，如果結果返回是，則擴充碼字位序
加1並返回步驟4 ;如果結果返回否，則進行下一步； 6、將前綴碼加1作為下一個前綴碼，比較當前葉子位序是否小於級別總葉子數，
如果結果返回是，則當前葉子位序加1並返回步驟3 ;如果結果返回否，則進行下一步； 7、檢測當前碼字級別是否不大於L，如果結果返回是，則返回步驟2 ;如果結果返 回否，則碼錶生成完畢並結束。 構建上述兩個碼錶後，然後解析碼長，按照當前碼流待解析部分所屬的哈夫曼碼 字生成樹，讀取其最大碼長長度的碼流數值，以這個碼流數值為索引，在對應的各級哈夫曼 碼最小碼字前綴定長碼字檢索表裡檢索級別(碼長)為L+1的碼字。 比較碼流數值與剛檢索到的碼字，若碼流數值小於剛檢索到的碼字，以碼流數值 的前L比特為新的索引，在與當前碼流待解析部分所屬的哈夫曼碼字生成樹對應的非完備 碼長碼錶部分檢索，檢索到的值即為當前碼流待解析部分首個碼字碼長；反之，以舊的碼流 數值作為比較對象，按照級別比較解析法，從對應的哈夫曼碼字生成樹的L級之後檢索當 前碼流中待解析的首個碼字長度。從當前碼流中提取剛解析到的碼長碼流，在當前碼字所 屬哈夫曼碼字生成樹對應的符號表中即可查出其對應的數據。 從當前碼流剔除已經解析的碼字，將剩餘碼流按上述方法解析，即可完成所有哈 夫曼碼的解碼。 具體解碼流程如圖3所示，首先提取當前比特流最大碼長比特A和定長碼字表中 級別為L+l的碼字B，並比較A、 B的大小。如果A小於B則取A的前L比特數作為索引在 對應的非完備碼錶部分檢索，碼長為索引值，並結束解碼。如果A不小於B，則在葉子檢索表 中檢索哈夫曼碼字數第L級之後存在碼字的下一級級別；在定長碼錶檢索當下一級別對應 的碼字C。如果A不小於C，則以下一級別代替當前級別，在葉子檢索表中檢索存在碼字的 下一級別，並返回重新檢索碼字C ;如果A小於C，則碼長為當前級別值，並結束解碼。
權利要求
一種基於非完備碼錶解析碼長的哈夫曼解碼方法，其特徵在於，步驟包括(a)、按級別比較解析法，構建所有用於級別比較解析的碼錶，包括葉子檢索表和各級哈夫曼最小碼字為前綴的定長碼字檢索表；(b)、確定非完備碼錶臨界碼長L從最小碼長和最大碼長之間選擇一個值L，作為構建非完備碼錶的臨界碼長；(c)、基於碼流中所包含的所有哈夫曼碼字生成樹的不超過臨界碼長L比特的葉子碼字，再構建一個以哈夫曼碼字為前綴的L比特非完備碼錶；(d)、按照當前碼流中待解析部分所屬的哈夫曼碼字生成樹，讀取最大碼長長度的碼流數值，以這個碼流數值為索引，按照當前待解析碼流所屬的哈夫曼碼字生成樹，在對應的以各級哈夫曼最小碼字為前綴的定長碼字檢索表裡檢索級別(碼長)為(L+1)的碼字；(e)、比較碼流數值與剛檢索到的(L+1)級的定長碼字，若碼流數值小於剛檢索到的碼字，以碼流數值的前L比特為新的索引，在對應的非完備碼長碼錶部分檢索，檢索到的值即為當前碼流待解析部分首個碼字碼長；反之，以舊的碼流數值作為比較對象，按照級別比較解析法，解析其對應的L級之後的首個碼字長度；(f)、根據已解析的碼長，在當前碼流中提取其碼字，基於碼字對應的符號表，查取其對應符號值，即可完成碼流中首個碼字的解析；(g)、從當前碼流中剔除已經解析的碼字，將剩餘碼流重複步驟d、e、f，即可完成所有哈夫曼碼的解碼。
2. 根據權利要求1所述的一種基於非完備碼錶解析碼長的哈夫曼解碼方法，其特徵在 於，所述的非完備碼長碼錶以碼流包含的每個哈夫曼碼字生成樹為單位，按相同的方式逐 一構建；對於每棵哈夫曼碼字生成樹，以不超過L比特的哈夫曼碼字為前綴，其餘位由全0 到全1擴展到L比特長度，建立非完備碼長碼錶的索引；索引指向的值為哈夫曼前綴碼碼 長。
3. 根據權利要求1所述的一種基於非完備碼錶解析碼長的哈夫曼解碼方法，其特徵在 於，所述的每個哈夫曼碼字生成樹對應的碼長碼錶部分構建過程首先，按照對應的哈夫曼 碼字生成樹，構建L比特長度的各個比特位為全O到全1的索引，並將所有索引值(即碼長 碼錶值)初始化為0 ;以哈夫曼生成樹的所有不超過L比特葉子碼子為前綴，將剩餘碼字位 以全0到全1填充到L比特長度，將所有同哈夫曼碼字前綴的擴充碼的碼長碼錶值以對應 哈夫曼前綴碼的長度賦值。
全文摘要
本發明公開了一種基於非完備碼錶解析碼長的哈夫曼解碼方法，步驟包括構建所有用於級別比較解析的碼錶；確定非完備碼錶臨界碼長L；再構建L比特非完備碼錶；讀取最大碼長長度的碼流數值，在對應的以各級哈夫曼最小碼字為前綴的定長碼字檢索表裡檢索級別為(L+1)的碼字；解析L級之後的首個碼字長度；查取其對應符號值，完成碼流中首個碼字的解析；從當前碼流中剔除已經解析的碼字，重複上述步驟完成所有哈夫曼碼的解碼。本發明可以大大減少存儲空間和加快了檢測速度；當最大碼長為16時，其空間複雜度只有完備碼錶解析法的，極大地節省了存取空間。
文檔編號H03M7/42GK101729076SQ20081021856
公開日2010年6月9日 申請日期2008年10月22日 優先權日2008年10月22日
發明者葉廣明, 胡勝發, 蘇丹, 裴少芳 申請人:安凱(廣州)軟體技術有限公司