[發(fā)明專利]一種基于非完備碼表解析碼長的哈夫曼解碼方法

有效

• 申請?zhí)枺?/td>: 200810218565.1
• 申請日: 2008-10-22
• 公開（公告）號: CN101729076A
• 公開（公告）日: 2010-06-09
• 發(fā)明（設(shè)計）人: 裴少芳;蘇丹;葉廣明;胡勝發(fā)
• 申請（專利權(quán)）人: 安凱(廣州)軟件技術(shù)有限公司
• 主分類號: H03M7/42
• 分類號: H03M7/42
• 代理公司: 廣州知友專利商標代理有限公司 44104
• 代理人: 宣國華

1.一種基于非完備碼表解析碼長的哈夫曼解碼方法，其特征在于，步驟包 括：

(a)、按級別比較解析法，構(gòu)建所有用于級別比較解析的碼表，包括葉子檢 索表和各級哈夫曼最小碼字為前綴的定長碼字檢索表；

(b)、確定非完備碼表臨界碼長L：從最小碼長和最大碼長之間選擇一個值L， 作為構(gòu)建非完備碼表的臨界碼長；

(c)、基于碼流中所包含的所有哈夫曼碼字生成樹的不超過臨界碼長L比特 的葉子碼字，再構(gòu)建一個以哈夫曼碼字為前綴的L比特非完備碼表；

(d)、按照當前碼流中待解析部分所屬的哈夫曼碼字生成樹，讀取最大碼長 長度的碼流數(shù)值，以這個碼流數(shù)值為索引，按照當前待解析碼流所屬的哈夫曼碼 字生成樹，在對應的以各級哈夫曼最小碼字為前綴的定長碼字檢索表里檢索級別 為L+1的碼字；

(e)、比較碼流數(shù)值與剛檢索到的L+1級的定長碼字，若碼流數(shù)值小于剛檢 索到的碼字，以碼流數(shù)值的前L比特為新的索引，在對應的非完備碼長碼表部分 檢索，檢索到的值即為當前碼流待解析部分首個碼字碼長；若碼流數(shù)值不小于剛 檢索到的碼字，以所述葉子檢索表的碼流數(shù)值作為比較對象，按照級別比較解析 法，解析剛檢索到的碼字對應的L級之后的首個碼字長度；

(f)、根據(jù)已解析的碼長，在當前碼流中提取其碼字，基于碼字對應的符號 表，查取其對應符號值，即可完成碼流中首個碼字的解析；

(g)、從當前碼流中剔除已經(jīng)解析的碼字，將剩余碼流重復步驟d、e、f， 即可完成所有哈夫曼碼的解碼。

2.根據(jù)權(quán)利要求1所述的一種基于非完備碼表解析碼長的哈夫曼解碼方法， 其特征在于，所述的非完備碼長碼表以碼流包含的每個哈夫曼碼字生成樹為單 位，按相同的方式逐一構(gòu)建；對于每棵哈夫曼碼字生成樹，以不超過L比特的哈 夫曼碼字為前綴，其余位由全0到全1擴展到L比特長度，建立非完備碼長碼表 的索引；索引指向的值為哈夫曼前綴碼碼長。

3.根據(jù)權(quán)利要求1所述的一種基于非完備碼表解析碼長的哈夫曼解碼方法， 其特征在于，所述的每個哈夫曼碼字生成樹對應的碼長碼表部分構(gòu)建過程：首先， 按照對應的哈夫曼碼字生成樹，構(gòu)建L比特長度的各個比特位為全0到全1的索 引，并將所有索引值初始化為0；以哈夫曼生成樹的所有不超過L比特葉子碼子 為前綴，將剩余碼字位以全0到全1填充到L比特長度，將所有同哈夫曼碼字前 綴的擴充碼的碼長碼表值以對應哈夫曼前綴碼的長度賦值。