Technologies for heuristic huffman code generation

Patent metadata

Field	Value
Publication number	US-9973207-B2
Application number	US-201715639602-A
Country	US
Kind code	B2
Filing date	Jun 30, 2017
Priority date	Jul 22, 2016
Publication date	May 15, 2018
Grant date	May 15, 2018

Abstract

Technologies for heuristic Huffman code generation include a computing device that generates a weighted list of symbols for a data block. The computing device determines a threshold weight and identifies one or more lightweight symbols in the list that have a weight less than or equal to the threshold weight. The threshold weight may be the average weight of all symbols with non-zero weight in the list. The computing device generates a balanced sub-tree of nodes for the lightweight symbols, with each lightweight symbol associated with a leaf node. The computing device adds the remaining symbols and the root of the balanced sub-tree to a heap and generates a Huffman code tree by processing the heap. The threshold weight may be adjusted to tune performance and compression ratio. Other embodiments are described and claimed.

First claim

The invention claimed is:

1. A computing device comprising:
a heuristic processor to (i) determine a threshold weight for a list of symbols, wherein each symbol is associated with a weight, (ii) identify one or more lightweight symbols of the list of symbols, wherein the weight of each lightweight symbol has a predetermined relationship to the threshold weight, and (iii) generate a balanced sub-tree of nodes for the lightweight symbols, wherein each of the lightweight symbols is associated with a leaf node of the balanced sub-tree; and
a tree processor to generate a Huffman code tree for any remaining symbols of the list of symbols other than the lightweight symbols and a root node of the balanced sub-tree.

2. The computing device of claim 1 , wherein the predetermined relationship comprises less than or equal to.

3. The computing device of claim 1 , further comprising a Huffman encoder to:
compute a Huffman code length for each symbol of the list of symbols based on a depth of a corresponding node in the Huffman code tree; and
encode a data block with the Huffman code lengths, wherein the data block comprises a block of symbols.

4. The computing device of claim 1 , further comprising a hardware compression engine to generate the list of symbols, wherein to identify the one or more lightweight symbols comprises to identify the one or more lightweight symbols in response to generation of the list of symbols.

5. The computing device of claim 1 , wherein to determine the threshold weight for the list of symbols comprises to determine an average weight for each symbol of the list of symbols.

6. The computing device of claim 5 , wherein to determine the threshold weight for the list of symbols further comprises to scale the average weight by a predetermined scale factor.

7. The computing device of claim 1 , wherein to identify the one or more lightweight symbols of the list of symbols comprises to identify all symbols of the list of symbols as the lightweight symbols.

8. The computing device of claim 1 , wherein to generate the Huffman code tree for the remaining symbols of the list of symbols and the root node of the balanced sub-tree comprises to:
add the remaining symbols and the root node to a heap data structure; and
while the heap data structure includes more than one node, to:
pop a first node and a second node from the heap data structure, wherein the first node and the second node each have a weight, and wherein the weights of the first node and the second node are the smallest weights in the heap data structure;
create a third node, wherein the third node is a parent node of the first node and the second node, and wherein a weight of the third node is a sum of the weight of first node and the weight of the second node; and
insert the third node in the heap data structure.

9. The computing device of claim 8 , wherein to generate the Huffman code tree further comprises to add the first node and the second node to a sorted list of nodes in response to a pop of the first node and the second node.

10. The computing device of claim 1 , wherein to generate the Huffman code tree for the remaining symbols of the list of symbols and the root node of the balanced sub-tree comprises to:
add the remaining symbols and the root node of the balanced sub-tree to a heap data structure; and
while the heap data structure includes more than one node, to:
pop a first node from the heap data structure, wherein the first node has a weight, and wherein the weight of the first node is the smallest weight in the heap data structure;
create a second node, wherein the second node is a parent node of the first node and a third node, wherein the third node is at a top of the heap data structure, and wherein a weight of the second node is a sum of the weight of first node and the weight of the third node; and
replace the third node in the heap data structure with the second node.

11. One or more computer-readable storage media comprising a plurality of instructions that in response to being executed cause a computing device to:
determine a threshold weight for a list of symbols, wherein each symbol is associated with a weight;
identify one or more lightweight symbols of the list of symbols, wherein the weight of each lightweight symbol has a predetermined relationship to the threshold weight;
generate a balanced sub-tree of nodes for the lightweight symbols, wherein each of the lightweight symbols is associated with a leaf node of the balanced sub-tree; and
generate a Huffman code tree for any remaining symbols of the list of symbols other than the lightweight symbols and a root node of the balanced sub-tree.

12. The one or more computer-readable storage media of claim 11 , wherein the predetermined relationship comprises less than or equal to.

13. The one or more computer-readable storage media of claim 11 , wherein to determine the threshold weight for the list of symbols comprises to determine an average weight for each symbol of the list of symbols.

14. The one or more computer-readable storage media of claim 13 , wherein to determine the threshold weight for the list of symbols further comprises to scale the average weight by a predetermined scale factor.

15. The one or more computer-readable storage media of claim 11 , wherein to identify the one or more lightweight symbols of the list of symbols comprises to identify all symbols of the list of symbols as the lightweight symbols.

16. The one or more computer-readable storage media of claim 11 , wherein to generate the Huffman code tree for the remaining symbols of the list of symbols and the root node of the balanced sub-tree comprises to:
add the remaining symbols and the root node to a heap data structure; and
while the heap data structure includes more than one node:
pop a first node and a second node from the heap data structure, wherein the first node and the second node each have a weight, and wherein the weights of the first node and the second node are the smallest weights in the heap data structure;
create a third node, wherein the third node is a parent node of the first node and the second node, and wherein a weight of the third node is a sum of the weight of first node and the weight of the second node; and
insert the third node in the heap data structure.

17. The one or more computer-readable storage media of claim 16 , wherein to generate the Huffman code tree further comprises to add the first node and the second node to a sorted list of nodes in response to popping the first node and the second node.

18. The one or more computer-readable storage media of claim 11 , wherein to generate the Huffman code tree for the remaining symbols of the list of symbols and the root node of the balanced sub-tree comprises to:
add the remaining symbols and the root node of the balanced sub-tree to a heap data structure; and
while the heap data structure includes more than one node:
pop a first node from the heap data structure, wherein the first node has a weight, and wherein the weight of the first node is the smallest weight in the heap data structure;
create a second node, wherein the second node is a parent node of the first node and a third node, wherein the third node is at a top of the heap data structure, and wherein a weight of the second node is a sum of the weight of first node and the weight of the third node; and
replace the third node in the heap data structure with the second node.

19. A computing device comprising a heuristic processor to:
determine a thr

Assignees

• Intel Corp

Inventors

• Gopal Vinodh
• Guilford James D

Classifications

• G06F15/161 Primary

  Computing infrastructure, e.g. computer clusters, blade chassis or hardware partitioning (casings, cabinets, racks or drawers for data centers H05K5/00) · CPC title

• H04Q2213/13523

  bandwidth management, e.g. capacity management · CPC title

• H05K7/1485

  Servers; Data center rooms, e.g. 19-inch computer racks · CPC title

• G06F2212/1041

  Resource optimization · CPC title

• H04Q2011/0079

  Operation or maintenance aspects · CPC title