[發(fā)明專利]一種快速解析碼長的哈夫曼解碼方法

有效

• 申請?zhí)枺?/td>: 200810219457.6
• 申請日: 2008-11-27
• 公開（公告）號: CN101741392A
• 公開（公告）日: 2010-06-16
• 發(fā)明（設計）人: 裴少芳;馮云慶;張婷;胡勝發(fā)
• 申請（專利權）人: 安凱(廣州)軟件技術有限公司
• 主分類號: H03M7/42
• 分類號: H03M7/42
• 代理公司: 廣州知友專利商標代理有限公司 44104
• 代理人: 宣國華

技術領域

本發(fā)明涉及一種解碼方法，尤其涉及一種快速解析碼長的哈夫曼解碼方法。

背景技術

哈夫曼算法是一種根據(jù)待壓縮數(shù)據(jù)中各元素出現(xiàn)的概率進行編碼和解碼的 算法，能無損的壓縮數(shù)據(jù)所占用的空間。圖1是一個哈夫曼碼字生成樹的例子， 以其碼字為葉子，碼字所屬層數(shù)為級別數(shù)。

解析哈夫曼碼時，先確定要解析的碼流的首個碼字長度，將其取出，用哈夫 曼編碼提供的符號表就可以找到這個碼字所對應的數(shù)據(jù)元素。除去碼流里的首個 碼字，將剩余的碼流按上述方法逐一解析，即可完成哈夫曼的解碼過程。由于哈 夫曼編碼是變長編碼，在整個解碼過程中，必須解決的一個問題是確定哈夫曼碼 字的長度，以下描述了哈夫曼解碼中碼字長度確定的常見解決方案。

A、逐位比較解析法：將哈夫曼碼字所有級別的首個碼字按級別為索引建立 一張碼長檢索表。解碼時，取出碼流里的第一個比特，如果這個碼流數(shù)值不小于 碼長為1的碼長檢索表所對應的碼字，將前面取出的比特數(shù)左移一位，并加上下 一個取出的比特數(shù)，將這個合成的碼流數(shù)值與上一個碼長加1所對應的碼長檢索 表中的哈夫曼碼字比較；如果這個新的碼流數(shù)值還是不小于新的哈夫曼碼字，繼 續(xù)按上述方法比較，直到碼流數(shù)值小于碼長檢索表中的哈夫曼碼字。那么，這個 哈夫曼碼字所對應的碼長減1就是碼流里首個哈夫曼碼字的長度。

B、級別比較解析法：由于哈夫曼碼字生成樹并不一定每一級都有葉子，對 于那些葉子不存在的級別還去比較就沒有意義。級別比較解析法正是基于這一 點，在逐位比較解析法的基礎上，用一個葉子檢索表來指示最近下一級存在哈夫 曼碼字的級別(等同碼字長度)，并將同一級上最小碼字作為前綴位，其余位補 0，擴充到最大碼長長度，用這個擴充碼建成一張定長碼字檢索表。在哈夫曼碼 長解析時，取出碼流中待解碼的最大碼長長度的碼流數(shù)值與定長碼字檢索表里的 首個碼字比較，如果這個碼流數(shù)值不小于定長碼字檢索表里的碼字，按照葉子檢 索表檢索當前級別的下一級葉子碼字級別，然后用這個下一級別值來檢索定長碼 字檢索表里的碼字，以碼流數(shù)值比較檢索到的定長碼字，直到碼流數(shù)值小于定長 碼字檢索表里的碼字，此時葉子檢索表里當前級別數(shù)和碼流里首個碼字長度相 同。

在音頻、視頻領域，基于哈夫曼數(shù)據(jù)壓縮的編碼、解碼算法應用非常廣泛。 在哈夫曼算法中，碼字以變長二進制前綴碼表示，為了解析一個哈夫曼碼字，必 須先解析哈夫曼碼字的字長，傳統(tǒng)的碼長解析算法在總的解碼算法中耗時比例較 大，減少碼長解析的時間對于提高哈夫曼解碼的速度有很重要的意義。

發(fā)明內(nèi)容

本發(fā)明目的在于提供一種可以快速解析碼長的哈夫曼解碼方法。

本發(fā)明的目的可以通過以下技術實現(xiàn)：一種快速解析碼長的哈夫曼解碼方 法，步驟包括：

1)基于碼流中所包含的所有哈夫曼碼字生成樹的葉子碼字，建立一張完備 碼長碼表；

2)對于當前待解析的哈夫曼碼流，按照其待解析碼字所屬的哈夫曼碼字生 成樹，在定長碼字完備碼長碼表中檢索到與這個哈夫曼碼字生成樹相對 應的碼表部分；

3)以最大碼字長度截取當前待解析的哈夫曼碼流，并將這個截取出的碼流 數(shù)值作為索引，在當前碼流哈夫曼碼字生成樹對應的碼長碼表部分檢索， 檢索到的當前碼長碼表值即為當前待解析碼流中首個碼字碼長；

4)提取首個碼字，在當前哈夫曼碼字生成樹所對應的符號表中即可解析到 當前碼字所對應的數(shù)據(jù)；從碼流中除去已解析的部分，將剩余碼流返回 第二步；直至全部碼流解析完畢后退出。

上述的構造哈夫曼碼字生成樹對應的完備碼長碼表的過程：

按照對應的哈夫曼碼字生成樹，構建最大碼長長度的各個比特位為全0到全 1的索引，并將所有索引值(即碼長碼表值)初始化為0；以哈夫曼生成樹的所 有葉子碼子為前綴，將剩余碼字位以全0到全1填充到最大碼長長度，將所有同 哈夫曼碼字前綴的擴充碼的碼長碼表值以對應哈夫曼前綴碼的長度賦值。

上述的完備碼長碼表的每項索引以哈夫曼碼字為前綴、其余位按全0到全1填 充擴展到最大碼長長度，索引對應的值為相應的哈夫曼前綴碼碼長。