[發明專利]保存范式哈夫曼樹的方法及裝置

有效

• 申請號: 201510836102.1
• 申請日: 2015-11-26
• 公開（公告）號: CN105490683B
• 公開（公告）日: 2019-01-08
• 發明（設計）人: 王志強;郭軍
• 申請（專利權）人: 東方網力科技股份有限公司
• 主分類號: H03M7/40
• 分類號: H03M7/40;H03M7/42
• 代理公司: 北京德琦知識產權代理有限公司 11018
• 代理人: 周華霞;王麗琴

本發明公開了保存范式哈夫曼樹的方法及裝置，其中，該方法包括：對范式哈夫曼樹的節點進行標記，用M標記節點有子樹，用N標記節點無子樹；由上至下對范式哈夫曼樹每層節點的標記依次進行記錄，具體地：采用從左至右的順序，從第一個節點開始記錄，只記錄到第一個不為N的節點；將記錄的節點標記作為最終記錄結果，保存最終記錄結果。本發明方案能夠實現采用盡量少的數據來保存范式哈夫曼樹，提高存儲效率。

技術領域

本發明涉及編碼存儲技術，尤其涉及保存范式哈夫曼樹的方法及裝置。

背景技術

在進行數據壓縮時常用到范式哈夫曼樹，如：GZIB、ZLIB、PNG、JPEG、MPEG。實際壓縮中，除了保存壓縮編碼，還需要保存范式哈夫曼樹及原始數據總量等，這樣才能夠解壓縮。本發明方案針對的是如何保存范式哈夫曼樹。

首先介紹范式哈夫曼編碼的原理，范式哈夫曼編碼過程大概分為4步：

1)對壓縮單元進行計數或概率統計，并按照從大到小進行排序，假定對字節數據統計結果如下述表1所示：

符號	A	B	C	D	E
計數	15	7	6	6	5
概率	0.38461538	0.17948718	0.15384615	0.15384615	0.12820513

表1對壓縮單元進行計數或概率統計后的排序

其中，符號用于對壓縮單元進行標識，計數表示相應壓縮單元的個數，概率表示相應壓縮單元占總壓縮單元的比例。

2)按照統計結果創建范式哈夫曼樹，具體地：總是找到兩個出現概率或次數最少的合并二叉樹，直到合并到一個根節點為止。假定按照上述結果分a，b，..e共5步(e為結果)，創建流程如圖1所示。