Back to results
US 2009/0140895 A1Published application
Generating Dynamic Huffman Codes
AssigneeComtech AHA Corporation
InventorsPatrick A. Owsley, Brian Banister, Jason Franklin
Life of this patent
Estimating the term…
Abstract
A method for generating Huffman trees using an insertion sorter and encode register is disclosed.
Claims7
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
A method for creating a Huffman tree, the method comprising:
- 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.
2 more elements
Dependencies are inferred from the claim text.