[發(fā)明專利]一種基于Huffman表的數(shù)據(jù)處理方法

有效

• 申請?zhí)枺?/td>: 201310630387.4
• 申請日: 2013-12-02
• 公開（公告）號: CN104679775B
• 公開（公告）日: 2019-04-23
• 發(fā)明（設(shè)計(jì)）人: 楊正傳
• 申請（專利權(quán)）人: 上海聯(lián)影醫(yī)療科技有限公司
• 主分類號: G06F16/51
• 分類號: G06F16/51;H03M7/40
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發(fā)明提供一種基于Huffman表的數(shù)據(jù)處理方法，包括：基于Huffman表構(gòu)建二叉樹數(shù)組，并基于所述二叉樹數(shù)組進(jìn)行解碼。所述二叉樹數(shù)組為二維數(shù)組，第一維是二叉樹的層數(shù)，第二維是每層的節(jié)點(diǎn)數(shù)。述基于所述二叉樹數(shù)組進(jìn)行解碼包括：讀取圖片數(shù)據(jù)，獲取節(jié)點(diǎn)查詢碼，并根據(jù)所述二維數(shù)組的層數(shù)和節(jié)點(diǎn)查詢碼，對應(yīng)定位至所述二維數(shù)組中的對應(yīng)節(jié)點(diǎn)：若對應(yīng)位置數(shù)據(jù)有效，則為葉節(jié)點(diǎn)，則當(dāng)前查詢結(jié)束；若否，則繼續(xù)讀取圖片數(shù)據(jù)。本方法采用數(shù)組方式，避免容易出錯(cuò)的指針及樹的操作，且編碼相對更加簡單，調(diào)試時(shí)更是比二叉樹方式更加直觀簡單。

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

本發(fā)明涉及一種數(shù)據(jù)處理方法，尤其涉及一種基于Huffman表的數(shù)據(jù)處理方法。

背景技術(shù)

傳統(tǒng)的圖像編碼技術(shù)也稱為第一代編碼技術(shù)，主要有預(yù)測編碼、變換編碼、信息嫡編碼與矢量量化。預(yù)測編碼和變換編碼是當(dāng)前圖像編碼器最常用的技術(shù)，預(yù)測和變換的主要目的是降低圖像原始空間域表示中存在的強(qiáng)相關(guān)性，使得預(yù)測或變換后的數(shù)據(jù)矩陣變成弱相關(guān)性矩陣，這樣可以用標(biāo)量量化和嫡編碼進(jìn)行有效的壓縮。信息嫡編碼是一種無失真編碼，常用的有哈夫曼編碼(Huffman Coding)、游程長度編碼(Run Length Coding)和算術(shù)編碼(Arithmetic Coding)三種。

傳統(tǒng)的Huffman編碼算法需要對原始數(shù)據(jù)進(jìn)行兩遍掃描：第一遍掃描要精確地統(tǒng)計(jì)出原始數(shù)據(jù)中每個(gè)值出現(xiàn)的頻率，利用得到的頻率創(chuàng)建Huffman樹，并將樹的有關(guān)信息保存起來，便于解壓時(shí)使用；第二遍掃描根據(jù)前面得到的Huffman樹對原始數(shù)據(jù)進(jìn)行編碼，并將編碼信息存儲起來。

在JPEG文件中，每個(gè)Huffman樹的表示形式如圖1所示：開始的16個(gè)字節(jié)是每個(gè)級別的數(shù)據(jù)的個(gè)數(shù)，本文稱為數(shù)目區(qū)。緊接著的是對應(yīng)的數(shù)據(jù)，本文成為數(shù)據(jù)區(qū)，一個(gè)數(shù)據(jù)一個(gè)字節(jié)，字節(jié)數(shù)是開始16個(gè)字節(jié)的字節(jié)之和。數(shù)據(jù)區(qū)按照數(shù)目區(qū)的順序依次排列，直到結(jié)束。在解碼的時(shí)候首先依次讀取數(shù)目區(qū)的一個(gè)字節(jié)，得到對應(yīng)的區(qū)段的數(shù)據(jù)數(shù)目，然后再依次將數(shù)據(jù)區(qū)中對應(yīng)的數(shù)據(jù)添加到對應(yīng)深度二叉樹中，插入優(yōu)先為左側(cè)分支。再編碼的時(shí)候是解碼的逆向過程。

JPEG的圖片數(shù)據(jù)是bit流的形式，每組可處理的數(shù)據(jù)由兩部分組成，一個(gè)是Huffman查詢碼，一個(gè)是數(shù)據(jù)值，所有這些都按照字節(jié)流緊密排列。每部分的bit數(shù)目不定。

基于所述Huffman樹的構(gòu)建包括首先構(gòu)建一個(gè)二叉樹節(jié)點(diǎn)，具體如下：

其中，各成員變量的意義如下：L_child：該節(jié)點(diǎn)的左側(cè)分支；R_child：該節(jié)點(diǎn)的右側(cè)分支；ch：該節(jié)點(diǎn)的數(shù)據(jù)；IsLeaf：該節(jié)點(diǎn)是否是葉節(jié)點(diǎn)；若無左右分支，用來標(biāo)志是不是數(shù)據(jù)節(jié)點(diǎn)，即存放數(shù)據(jù)的，如果不是葉節(jié)點(diǎn)則為中繼節(jié)點(diǎn)，即無有效數(shù)據(jù)，只是向下一層查找的支持節(jié)點(diǎn)。

采用上述方法構(gòu)建出來的Huffman樹的示例如圖2所示。其中，對應(yīng)的其對應(yīng)的JPEG數(shù)據(jù)如下表一所示。

表一

下面是解碼的步驟：

1、首先讀取數(shù)目區(qū)第一個(gè)字節(jié)，數(shù)值為0，表明第一層無數(shù)據(jù)。

2、讀取數(shù)目區(qū)的第二個(gè)字節(jié)，數(shù)值為1，表明第二層有一個(gè)數(shù)據(jù)，則為Root Node構(gòu)建一個(gè)左子節(jié)點(diǎn)，該節(jié)點(diǎn)是第一層的，所以還需為該節(jié)點(diǎn)再構(gòu)建一個(gè)左子節(jié)點(diǎn)，并填入數(shù)據(jù)區(qū)第一個(gè)字節(jié)的數(shù)值，設(shè)置該節(jié)點(diǎn)狀態(tài)為葉節(jié)點(diǎn)。

3、讀取數(shù)目區(qū)的第三個(gè)字節(jié)，數(shù)值為2，則接著讀取數(shù)據(jù)區(qū)的兩個(gè)字節(jié)，數(shù)值依次為6和7。依舊從根節(jié)點(diǎn)開始，采用前序遍歷，創(chuàng)建第三層的第一個(gè)節(jié)點(diǎn)，并設(shè)置其數(shù)值為6，狀態(tài)為葉節(jié)點(diǎn)；接著再按照前序遍歷的規(guī)則，增加第三層的第二個(gè)節(jié)點(diǎn)，設(shè)置數(shù)值為7，狀態(tài)為葉節(jié)點(diǎn)。注意遍歷的時(shí)候碰到葉節(jié)點(diǎn)則遞歸返回其他的樹。

4、讀取數(shù)目區(qū)的第四個(gè)字節(jié)，數(shù)值為0，表明第四層無數(shù)據(jù)。