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

有效

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

1.一種保存范式哈夫曼樹的方法，其特征在于，該方法包括：

對范式哈夫曼樹的節點進行標記，用M標記節點有子樹，用N標記節點無子樹；

由上至下對范式哈夫曼樹每層節點的標記依次進行記錄，具體地：對于該層節點，采用從左至右的順序，從第一個節點開始記錄，只記錄到第一個不為N的節點；

將記錄的節點標記作為最終記錄結果，保存最終記錄結果。

2.如權利要求1所述的方法，其特征在于，該方法還包括對范式哈夫曼樹的解碼，具體地：

從上至下對各層依次進行解碼：

統計當前層的上一層中標記為M的節點數，將統計出的節點數乘以2，將得到的乘積值作為當前層的節點數P；若當前層為第一層時，P為1；

從最終記錄結果中依次讀取標記，直至遇到標記為M或讀取的標記數目達到P個時停止，為讀取的標記填充后續標記M，直到標記總數達到P位，將填充后的標記作為當前層的標記結果。

3.如權利要求1所述的方法，其特征在于，對范式哈夫曼樹每層節點的標記依次進行記錄時，不對最后一層的節點進行記錄；該方法還包括：

對范式哈夫曼樹中的葉節點數目進行統計，得到葉節點總數，將葉節點總數添加到最終記錄結果中。

4.如權利要求1所述的方法，其特征在于，對范式哈夫曼樹每層節點的標記依次進行記錄時，每層的最后一個節點不記錄；該方法還包括：

對范式哈夫曼樹中的葉節點數目進行統計，得到葉節點總數，將葉節點總數添加到最終記錄結果中。

5.如權利要求4所述的方法，其特征在于，對范式哈夫曼樹每層節點的標記依次進行記錄時，不對最后一層的節點進行記錄。

6.如權利要求5所述的方法，其特征在于，該方法還包括對范式哈夫曼樹的解碼，具體地：

將第一層節點的標記設置為M；

從上至下對后續各層依次進行解碼：

統計當前層的上一層中標記為M的節點數，將統計出的節點數乘以2，將得到的乘積值作為當前層的節點數P；

從最終記錄結果中讀取葉節點總數，統計出當前層之前所有層標記為N的葉節點數，計算出剩余葉節點數Q；

判斷P是否等于Q，如果是，則當前層為最后一層，P個節點全部為葉節點，標記為N；否則，從最終記錄結果中依次讀取標記，直至遇到標記為M或讀取的標記數目達到P-1個時停止，為讀取的標記填充后續標記M，直到標記數達到P位，將填充后的標記作為當前層的標記結果。

7.一種保存范式哈夫曼樹的裝置，其特征在于，該裝置包括節點標記記錄模塊和保存模塊；

所述節點標記記錄模塊，對范式哈夫曼樹的節點進行標記，用M標記節點有子樹，用N標記節點無子樹；由上至下對范式哈夫曼樹每層節點的標記依次進行記錄，具體地：對于該層節點，采用從左至右的順序，從第一個節點開始記錄，只記錄到第一個不為N的節點；將記錄的節點標記發送給所述保存模塊；

所述保存模塊，將記錄的節點標記作為最終記錄結果，保存最終記錄結果。

8.如權利要求7所述的裝置，其特征在于，該裝置還包括第一解碼模塊，對范式哈夫曼樹的解碼，具體地：從上至下對各層依次進行解碼：

統計當前層的上一層中標記為M的節點數，將統計出的節點數乘以2，將得到的乘積值作為當前層的節點數P；若當前層為第一層時，P為1；從最終記錄結果中依次讀取標記，直至遇到標記為M或讀取的標記數目達到P個時停止，為讀取的標記填充后續標記M，直到標記總數達到P位，將填充后的標記作為當前層的標記結果。

9.一種保存范式哈夫曼樹的方法，其特征在于，該方法包括：

對范式哈夫曼樹的節點進行標記，用M標記節點有子樹，用N標記節點無子樹；

由上至下對范式哈夫曼樹每層節點的標記依次進行記錄，具體地：對于該層節點，采用從右至左的順序，從第一個節點開始記錄，只記錄到第一個不為M的節點；

將記錄的節點標記作為最終記錄結果，保存最終記錄結果。