Method for storing node information of huffman tree and corresponding decoding method

Abstract

A method for storing node information of a Huffman tree. The method creates an index of each node in the Huffman tree using a breadth first search (BFS) algorithm. The method further reads each node of the Huffman tree beginning from a root node according to a sequence of the index of each node, and stores node information of each node into an array of the Huffman tree.

1 . A method for decoding data using an array of a Huffman tree, node information of each node in the Huffman tree being stored in the array of the Huffman tree, each node comprising a return value, the method comprising:
 (a) obtaining a bit stream to be decoded;   (b) reading a root node of the Huffman tree;   (c) determining whether the node is a leaf node;   (d) reading a bit from the bit stream sequentially to determine a next node in the Huffman tree when the node is not the leaf node, and returning to step (c) to determine whether the next node is a leaf node;   (e) searching a decimal number of the node from the array of the Huffman tree according to an index of the node when the node is a leaf node, and obtaining the return value of the node from the decimal number of the node;   (f) determining whether reading of the bit stream has been finished;   (g) returning to step (b) when reading of the bit stream has not been finished; or   (h) outputting the return value of each node to generate a decoded bit stream when reading of the bit stream has been finished.   
     
     
         2 . The method according to  claim 1 , wherein the node information of each node is stored with a first part and a second part into the array of the Huffman tree. 
     
     
         3 . The method according to  claim 2 , wherein the node information of each node are stored into the array of the Huffman tree by:
 dividing the node information of each node in the Huffman tree into a first part and a second part;   merging a binary number of a first value of the first part and a binary number of a second value of the second part of each node to acquire a merged binary number, the first value and the second value being decimal numbers;   storing a decimal number of the merged binary number into the array of the Huffman tree.   
     
     
         4 . The method according to  claim 3 , wherein a storage length of the first part of each node is 7 bits, and the storage length of the second part of each node is 1 bit. 
     
     
         5 . The method according to  claim 3 , wherein the first value of the first part and the second value of the second part of the node are determined by:
 determining whether the node is an internal node or a leaf node of the Huffman tree;   determining that a first value of the first part of the node is equal to a difference value between an index of a left child node of the node and an index of the node when the node is the internal node, and a second value of the second part of the node is “1;” or   determining that the first value of the first part of the node is equal to the return value of the node when the node is the leaf node, and the second value of the second part of the node is “0.”   
     
     
         6 . The method according to  claim 5 , wherein the step of determining whether the node is a leaf node comprises:
 determining that the node is the internal node when the second value of second part of the node is “1”; and   determining that the node is the leaf node when the second value of second part of the node is “0”.   
     
     
         7 . The method according to  claim 5 , wherein the next node in the Huffman tree in step (d) is determined by the following formulas:
 the index of the next node=(the index of a current node+the first value of the first part of the current node), upon the condition that the bit read from the bit stream is “0”; and   the index of the next node=(the index of the current node+the first value of the first part of the current node+1), upon the condition that the bit read from the bit stream is “1”.   
     
     
         8 . The method according to  claim 7 , wherein the return value of the node is equal to the first value of the first part of the node. 
     
     
         9 . The method according to  claim 8 , wherein the first value of the first part of the node is determined by the following steps:
 converting the decimal number of the node to the binary number, and performing a right arithmetic shift operation on the binary number by 1 bit to obtain a right-shifted binary number; and   converting the right-shifted binary number to the decimal number to obtain the first value of the first part of the node.