公开(公告)号：US09698819B1

公开(公告)日：2017-07-04

申请号：US15390304

申请日：2016-12-23

Applicant: AMAZON TECHNOLOGIES, INC.

Inventor： Michael Baranchik ,  Ron Diamant ,  Muhannad Ghanem ,  Ori Weber

IPC: H03M7/40 ,  H03M7/30 ,  H03M7/42

CPC classification number: H03M7/40 ,  H03M7/30 ,  H03M7/405 ,  H03M7/42 ,  H03M7/6076

Abstract: A method for generating Huffman codewords to encode a dataset includes selecting a Huffman tree type from a plurality of different Huffman tree types. Each of the Huffman tree types specifies a different range of codeword length in a Huffman tree. A Huffman tree of the selected type is produced by: determining a number of nodes available to be allocated as leaves in each level of the Huffman tree accounting for allocation of leaves in each level of the Huffman tree; allocating nodes to be leaves such that the number of nodes allocated in a given level of the Huffman tree is constrained to be no more than the number of nodes available to be allocated in the given level; and assigning the leaves to symbols of the dataset based an assignment strategy selected from a plurality of assignment strategies to produce symbol codeword information.