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

有效

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

技術(shù)領(lǐng)域

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

背景技術(shù)

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

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

1、級(jí)別比較解析法。基于哈夫曼碼字生成樹建立一個(gè)葉子檢索表來指示最 近下一級(jí)存在哈夫曼碼字的級(jí)別(等同碼字長度)，并將同一級(jí)上最小碼字作為 前綴位，其余位補(bǔ)0，擴(kuò)充到最大碼長長度。以哈夫曼前綴碼所在級(jí)別為索引， 以這個(gè)擴(kuò)充碼為索引值，建一張各級(jí)最小哈夫曼碼字為前綴的定長碼字檢索表。 在哈夫曼碼碼長解析時(shí)，按葉子檢索表0級(jí)檢索下一級(jí)別，并以這個(gè)下一級(jí)別檢 索定長碼字檢索表里的碼字，取出最大碼長長度的碼流數(shù)值與之比較，如果這個(gè) 碼流數(shù)值不小于定長碼字檢索表里的碼字，葉子檢索表的當(dāng)前級(jí)別用下一級(jí)別替 換，并用這個(gè)新的當(dāng)前級(jí)別檢索下一級(jí)存在葉子的級(jí)別，然后用這個(gè)新的下一級(jí) 級(jí)別檢索定長碼字檢索表里的碼字，用碼流數(shù)值與之比較，直到碼流數(shù)值小于定 長碼字檢索表里的碼字，此時(shí)葉子檢索表里當(dāng)前級(jí)別和碼流里存在的碼字長度相 同。

2、完備碼表解析法。基于碼流中所包含的所有哈夫曼碼字生成樹的葉子碼 字，建立一張完備碼長碼表。這個(gè)完備碼長碼表的每項(xiàng)索引以哈夫曼碼字為前綴、 按一定規(guī)則擴(kuò)展到最大碼長長度，其索引值為相應(yīng)的哈夫曼前綴碼碼長。對(duì)于當(dāng) 前待解析的哈夫曼碼流，按照其待解析碼字所屬的哈夫曼碼字生成樹，在定長碼 字完備碼長碼表中檢索到與這個(gè)哈夫曼碼字生成樹相對(duì)應(yīng)的碼表部分。以最大碼 字長度截取當(dāng)前待解析的哈夫曼碼流，并將這個(gè)截取出的碼流數(shù)值作為索引，在 當(dāng)前碼流哈夫曼碼字生成樹對(duì)應(yīng)的碼長碼表部分檢索，檢索到的當(dāng)前碼長碼表值 即為當(dāng)前待解析碼流中首個(gè)碼字碼長。

得到碼長后提取首個(gè)碼字，在當(dāng)前哈夫曼碼字生成樹所對(duì)應(yīng)的符號(hào)表中即可 解析到當(dāng)前碼字所對(duì)應(yīng)的數(shù)據(jù)。從碼流中除去已解析的部分，在剩余碼流中繼續(xù) 逐個(gè)操作，即可完成所有哈夫曼碼的解析。

現(xiàn)有普遍使用的哈夫曼解碼算法雖然利用了編碼表體現(xiàn)的碼字出現(xiàn)的概率， 并基于哈夫曼碼生成樹各級(jí)葉子的存在性對(duì)檢索算法進(jìn)行了優(yōu)化，但對(duì)于絕大部 分碼字，碼長均需要多次才能確定，在總的解碼算法中耗時(shí)比例較大；基于完備 碼表解析碼長雖然提高了碼長解析速度，但是對(duì)于嵌入式系統(tǒng)的硬件存儲(chǔ)要求而 言，其空間復(fù)雜度增加太大，難以滿足要求。

在音頻、視頻領(lǐng)域，基于哈夫曼數(shù)據(jù)壓縮的編碼、解碼算法在嵌入式系統(tǒng)中 應(yīng)用非常廣泛。在哈夫曼算法中，碼字以變長二進(jìn)制前綴碼表示，為了解析一個(gè) 哈夫曼碼字，必須先解析哈夫曼碼字的字長，傳統(tǒng)的碼長解析算法不是速度過慢 就是碼表數(shù)據(jù)量過大，如何在不增加碼表數(shù)據(jù)量的同時(shí)減少碼長解析的時(shí)間，這 對(duì)于哈夫曼解碼有很重要的意義。

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

本發(fā)明目的在于提供一種基于非完備碼表解析碼長的哈夫曼解碼方法，該方 法可以大大減少碼表占用的儲(chǔ)存空間和加快解碼速度。

本發(fā)明的目的可以通過以下方案實(shí)現(xiàn)：一種基于非完備碼表的哈夫曼解碼方 法，步驟包括：

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

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

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

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