Assigning codes to and repairing Huffman trees
A method for assigning codes to Huffman trees and repairing invalid Huffman trees is disclosed using a calculated delta and moving nodes within the Huffman tree by adjusting their encode register entries.
1. A method for facilitating repair of an invalid Huffman tree using an encode register, the method comprising:
determining a delta; and
moving a leaf node in accordance with the delta.
2. The method of claim 1 wherein determining a delta comprises:
calculating a valid codeword space value of 2 N where N=the number of allowed levels of the tree;
calculating
a
codeword
space
count
=
∑
k
=
0
N
-
1
codewords
k
*
2
k
wherein k refers to a specific level of the tree and where codewords k is the number of leaf nodes at the level of the tree equal to the current value of k; and
calculating a difference between the valid codeword space 2 N and the codeword space count to create a delta equal to codeword space count−2 N .
3. The method of claim 1 wherein determining a delta comprises:
calculating a valid codeword space value of 2 N where N=the number of allowed levels of the tree;
calculating
a
codeword
space
count
=
∑
k
=
0
N
-
1
codewords
k
*
2
k
;
wherein k refers to a specific level of the tree and where codewords k is the number of leaf nodes at the level of the tree equal to the current value of k; and
subtracting the codeword space count from 2 N .
4. The method of claim 1 wherein moving a leaf node in accordance with the delta comprises:
moving a leaf node down the tree from a current level in response to positive deltas and up the tree in response to negative deltas to a destination level in the tree;
reassigning a leaf node among the levels of the tree and updating the codeword space count to permit the leaf's move when the destination level is unsuitable to accept the leaf; and
repeating until the delta is zero.
5. A system for facilitating repair of an invalid Huffman tree, the system comprising:
a validity determination module configured to determine if a Huffman tree exceeds a permitted tree depth;
an encode register module; and
a manipulation module configured to adjust an entry in the encode register entries until a valid state of the tree is attained.
6. A method for assigning a number of bits used to represent leaf nodes at each level of a Huffman tree, the method comprising:
utilizing an encode register; and
assigning leaf nodes bits based on encode register entries.
7. The method of claim 6 further comprising:
initializing an encode register index, k, to a maximum tree level minus one and reading the encode register;
decrementing the encode register index and reading the next encode register entry when the value is zero and continuing until a non-zero value is found; and
popping a leaf node from a storage stack and encoding it with the number of bits used at this level wherein the number of bits is calculated by subtracting the encode register index from the maximum number of levels in the tree.
8. The method of claim 6 further comprising:
initializing an encode register index, k, to a maximum tree level minus one;
reading the encoding register;
decrementing the encode register index and reading the next encode register entry when the value is zero and continuing until a non-zero value is found;
popping a leaf node from the storage stack and prepending the number of bits used to encode the leaf at this level wherein the number of bits is calculated by subtracting the encode register index from the maximum number of levels in the tree; and
pushing the leaf node into an insertion sorter and continuing until the encode register index decrements to zero wherein the insertion sorter sorts the leaf nodes by the number of bits used to encode the leaf node.
9. Method of claim 6 further comprising:
sorting leaves lexically with equal length code words prior to assignment of codewords.
10. The method of claim 9 further comprising:
sorting leaf nodes with the same number of encode bits lexically.
11. A system for assigning the number of bits used to represent leaf nodes at each level of a Huffman tree comprising:
an encode register module; and
a bit assignment module assigning bits based on entries in the encode register.