Back to results
US 7,609,182 B2Granted
Generating dynamic huffman codes
AssigneeComtech AHA Corporation
InventorsPatrick A. Owsley, Brian Banister, Jason Franklin
Life of this patent
Estimating the term…
Abstract
Huffman trees may be rapidly and effectively created by sorting a plurality of nodes by weight in an insertion sorter stack, popping the two lowest weighted nodes from the insertion sorter stack, forming a branch node from the popped entries, and placing the branch node into the insertion sorter.
Claims6
A method facilitating Huffman tree building, the method comprising:
- creating leaf nodes, the creating comprising:
- using weights of a plurality of symbols occurring in a data block;
- designating each symbol with non-zero weight as a leaf node of a Huffman tree;
- inserting two or more leaf nodes into an insertion sorter for sorting;
- sorting contents of the insertion sorter;
- building a first branch node, the building comprising:
- popping the two lowest weighted entries found in the contents of the insertion sorter from the insertion sorter to form the first branch node;
- inserting the first branch node into the insertion sorter for sorting;
- sorting contents of the insertion sorter;
- and
- building a second branch node, the building comprising:
- popping the two lowest weighted entries found in the contents of the insertion sorter from the insertion sorter to form the second branch node.
9 more elements
A method of facilitating management of a Huffman tree depth using an encode register, the method comprising:
- building an encode register during formation of a Huffman tree wherein the building further comprises:
- calculating a number of available nodes for a current level of the Huffman tree, wherein calculating the number of available nodes comprises:
- defaulting to two when at the first non-root level in the Huffman tree;
- multiplying a number of branches on an immediately adjacent prior Huffman tree level by two when the current level is not the first non-root level;
- popping a node from a branch/leaf stack and designating an entry in the encode register as a branch or leaf;
- storing a total number of leaf nodes for the current level of the Huffman tree in the encode register;
- and
- relocating a node within the Huffman tree in accordance with the encode register.
5 more elements
Dependencies are inferred from the claim text.