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.

BRIEF DESCRIPTIONS OF THE DRAWINGS

Tools and techniques related to generating dynamic Huffman codes and repairing Huffman code trees are described in connection with the following drawing figures. The same numbers are used throughout the disclosure and figures to reference like components and features. The first digit in a reference number indicates the drawing figure in which that reference number is introduced.

FIG. 1is a combined block and flow diagram illustrating examples of systems or operating environments in which the tools described herein may generate dynamic Huffman codes and related trees.

FIG. 2is a block diagram illustrating different possible implementations of an insertion sorter and a tree generator used to generate dynamic Huffman codes.

FIG. 3is a combined block and flow diagram illustrating operation of the insertion sorter in loading and sorting new symbols into a data structure to facilitate the processing further described below.

FIG. 4is a combined block and flow diagram illustrating different implementations of the insertion sorter and the tree generator component, as suitable for generating dynamic Huffman codes.

FIG. 5is a combined block and flow diagram illustrating process flows for generating code words for the input symbols.

FIG. 6is a flow diagram illustrating processes for generating dynamic Huffman codes.

FIG. 7is a flow diagram illustrating processes for building a branch and leaf stack and incrementing counters.

FIG. 8is a sequence diagram illustrating states through which the sorter and branch/leaf stack may progress as the branch nodes and branch/leaf stack are generated.

FIG. 9is a sequence diagram illustrating how the branch-leaf stack structure constructed inFIG. 8may be used to populate an encode register.

FIG. 10is a block diagram illustrating how the exemplary Huffman tree ofFIG. 8is constructed.

FIG. 11is a block diagram illustrating how the leaves of the exemplary Huffman tree constructed inFIG. 8may be assigned codes by an encode register.

FIG. 12is a sequence diagram illustrating different states through which the sorter and branch/leaf stack may progress as dynamic Huffman codes are generated compared toFIG. 8.

FIG. 13is a sequence diagram illustrating how the branch-leaf stack structure constructed inFIG. 12may be used to populate an encode register.

FIG. 14is a block diagram illustrating the exemplary Huffman tree constructed inFIG. 12.

FIG. 15is a block diagram illustrating how the exemplary Huffman tree constructed inFIG. 12may assign codes to leaves.

FIG. 16is a tree diagram illustrating a repair in which the illegal tree is transformed into the legal tree.

FIG. 17is a block diagram illustrating different possible implementations of an insertion sorter and a tree generator used to generate dynamic Huffman codes.

FIG. 18is a tree diagram illustrating an illegal tree scenario, with two illegal nodes.

FIG. 19is a tree diagram illustrates an illegal tree scenario with four illegal nodes.

FIG. 20is a tree diagram illustrates an illegal tree scenario with six illegal nodes.

FIG. 21is a sequence diagram illustrating how the contents of the encode register may be altered to implement the tree repairs.

FIG. 22is a block diagram illustrating how codeword bit lengths are assigned to leaf nodes, and sorted by bit length and lexical value

DETAILED DESCRIPTION

Overview

The following document describes systems, methods, user interfaces, and computer-readable storage media (collectively, “tools”) that are capable of performing and/or supporting many techniques and processes. The following discussion describes exemplary ways in which the tools generate dynamic Huffman codes and repair Huffman code trees. This discussion also describes other techniques and/or processes that may be performed by the tools.

FIG. 1illustrates examples of systems or operating environments100in which the tools described herein may generate dynamic Huffman codes. Block102represents storage of statistical or histogram data indicating how often given symbols occur within given blocks of data to be dynamically encoded. This data may include a plurality of blocks, denoted generally at104.FIG. 1shows examples of two blocks at104aand104n, but implementations of the operating environments may include any number of blocks.

Individual blocks104may include a plurality of un-encoded symbols, denoted generally at106.FIG. 1shows examples of two symbols at106aand106n, but implementations of the operating environments may include any number of symbols. In general, the blocks104represent collections of symbols106that are processed, encoded, and handled as logical units.

When blocks of these symbols are to be encoded, they may be statistically analyzed to determine how many times different symbols occur within the block. Put differently, for each symbol that occurs at least once in the block, the statistical analysis computes how frequently this symbol occurs in the block.FIG. 1represents the results of this statistical analysis generally at102.

The frequencies at which different symbols occur may be expressed as a weight parameter associated with the different symbols. The more frequently that a given symbol occurs in a block, the higher the weight assigned to the symbol. The less frequently that a given symbol occurs in a block, the lower the weight assigned to the symbol. In the examples described herein, the weights assigned to the symbols occurring within a give block may sum to 1.0. However, this description is non-limiting and provided only as an example. Any number of different weighting schemes may be suitable in different possible implementations. For example, while the examples provided herein pertain to weights expressed in floating point formats, implementations may use floating point, integer, or other convenient forms of arithmetic.

FIG. 1represents these weights generally at112.FIG. 1illustrates two examples of weights, denoted at112aand112n. After a statistical analysis of the blocks (not shown explicitly inFIG. 1), the symbols106that occur in the given block (e.g.,104a) are associated with a respective weight. In the example shown inFIG. 1, the symbol106ahas an assigned weight112a, and the symbol106nhas an assigned weight112n.

Once the weights112are assigned for the various symbols106in the blocks104, the blocks may be forwarded to an insertion sorter114. In general, the insertion sorter may operate to receive blocks of symbols, and insert the symbols into a suitable data structure, as described in detail below.FIG. 1shows an example in which the insertion sorter114produces a set of sorted symbols, denoted at116.

The systems100may include a tree generation unit118that receives blocks of sorted symbols116, and generates respective dynamic Huffman codes and related trees for these blocks of symbols.FIG. 1denotes examples of the output Huffman trees at120.

The Huffman codes generated using the techniques described here are described as “dynamic,” in the sense that different blocks are encoded using different coding schemes. Thus, the statistical data storage102may include respective histogram data for each different block104. Symbols appearing within different blocks may be assigned different weights in those different blocks, depending on how frequently these symbols occur in those different blocks. As detailed further below, these different weights assigned to the symbols may result in the same symbol being encoded differently in different blocks. Thus, a given symbol occurring in a first given block (e.g.,104a) may be encoded with a given bit string within that first block. However, if that given symbol occurs in a second given block (e.g.,104n), the bit string to which the symbol is encoded may be different.

FIG. 2illustrates different possible implementations, denoted generally at200, of an insertion sorter and tree generator used to generate dynamic Huffman codes. For convenience and conciseness of description, but not to limit possible implementations, some items described previously are carried forward intoFIG. 2and denoted by the same reference numbers.

As shown inFIG. 2, the insertion sorter and tree generator may be implemented in hardware and/or software. In hardware-based implementations, the insertion sorter and tree generator, as well as other elements described herein, may be implemented in circuit form. Hardware implementations of the insertion sorter and tree generator are denoted, respectively, at114aand118a. These hardware implementations may reside in or on substrates202. Examples of such substrates may include printed circuit boards, chip dies, or the like. As such, these hardware implementations may include one or more integrated circuits connected to printed circuit boards, may include modules that are resident on-board with microprocessor units, or in other environments.

In software-based implementations, the insertion sorter and tree generator may be implemented as one or more software modules that may reside in one or more instances of computer-readable storage media204.FIG. 2denotes software implementations of the insertion sorter and stack at114nand118n, respectively. These software modules may include sets of computer-executable instructions that may be loaded into one or more processors206and executed. When executed, these instructions may cause the processor, and any machine containing the processor, to perform any of the various functions described herein.

FIG. 2also provides non-limiting examples of systems within which the substrates202and/or computer-readable media204may reside. A server-based system208may include the substrates202and/or computer-readable media204. The server208may, for example, process media or other data to be encoded, as represented generally at102inFIG. 1. In other instances, the server208may enable development, testing, or simulation of the various tools and techniques described herein. As such, the server208may be accessible by one or more remote users (not shown inFIG. 2).

FIG. 2also illustrates a workstation system210in which the substrates202and/or computer-readable media204may reside. Like the server208, the workstation system210may process media or other data to be encoded, or may enable development, testing, or simulation of the various tools and techniques described herein.

FIG. 3illustrates an operation300of an insertion sorter in loading and sorting new symbols into a data structure to facilitate the processing further described below. For convenience and conciseness of description, but not to limit possible implementations, some items described previously are carried forward intoFIG. 3and denoted by the same reference numbers.

Examples of an insertion sorter are denoted at114. More specifically,FIG. 3provides examples of how the insertion sorter evolves as a new symbol114xis loaded into the sorter. As described previously, blocks104of symbols106to be encoded may arrive for processing at the insertion sorter114.FIG. 3generally represents a given symbol to be inserted at106x. This symbol106xmay be associated with a weight112x, which indicates how frequently the symbol occurs within the instant block104.

FIG. 3generally represents at114xan example (but non-limiting) state of the insertion sorter when the new symbol106xarrives. In this example state, the insertion sorter114xmay already contain entries for two symbols106aand106n, with associated weights112aand112n. When the new symbol106xarrives, the insertion sorter may push the new symbol106xinto the top-of-stack (TOS) position in the insertion sorter116. The insertion sorter may compare the weight112xof the new symbol106xwith the weights of any symbols already in the stack to determine where in the insertion sorter the new symbol should be placed. In some instances, the insertion sorter may be sorted in ascending order of weight, with the lowest-weighted symbols closer to the top of the insertion sorter. In other instances, the insertion sorter may be sorted in descending order of weight, with the highest-weighted symbols closer to the top of the insertion sorter.

Depending on how the insertion sorter is implemented, the sorter may place the new symbol106xinto the appropriate location within the sorter, based on how its weight112xcompares to the weights of any symbols already in the sorter (e.g., symbols106aand106n, with weights112aand112n). Assuming that the weight112xof the new symbol106xfalls between the weights112aand112nof the existing symbols, the new symbol106xmay be located in the sorter between the existing symbols106aand106n.FIG. 3represents, at114y, the state of the sorter after it has pushed-in the new symbol106xand sorted to accommodate the symbol in its appropriate position.

It is noted that the scenario shown at114xis non-limiting, and the insertion sorter may contain zero or more entries for previously-pushed symbols. For example, if the sorter is empty when the new symbol106xarrives, the insertion sorter may push the new symbol106xinto the top-of-stack position, and then await the arrival of the next symbol106. In this case, the sorting operation would be superfluous, since the stack contains only one entry.

When all symbols from the input block104have been pushed into the insertion sorter, the sorter may pass the sorted symbols116to the tree generator118. In turn, the tree generator may produce the output tree120. It is noted that the description herein uses the term “push” (and variations thereof) only for ease of description, but not to limit possible implementations. More specifically, the term “push” does not limit such implementations to stack-type structures. Instead, any suitable structure may be appropriate in different implementations.

FIG. 4illustrating different implementations400of an insertion sorter and a tree generator component suitable for generating dynamic Huffman codes. For convenience and conciseness of description, but not to limit possible implementations, some items described previously are carried forward intoFIG. 4and denoted by the same reference numbers.

An insertion sorter, such as the sorter114, may contain any number of symbols106that are sorted according to their respective weights112. For convenience of description only,FIG. 4carries forward the sorter114in its state as shown at114yinFIG. 3, with three symbols106a-nsorted according to their respective weights112a-n. The sorter, when fully loaded, may contain all of the symbols occurring in a given block of data (e.g.,102inFIG. 1).

A tree generator component, carried forward at118may extract the sorted symbols, denoted generally at116, to generate dynamic Huffman codes for the symbols. The tree generator component may include a hardware circuit implementation118athat may reside on the substrate (e.g.,202). The sorted symbols as input to such a circuit are denoted at116a. The tree generator component may also include a software implementation denoted at118nthat may reside on the computer-readable storage medium (e.g.,204). The sorted symbols as input to such software are denoted at116n. In either of the example implementations, a server (e.g.,208), a workstation (e.g.,210), or other systems may include the tree generator component118.

FIG. 4denotes generated dynamic Huffman codes and related trees generally at120. More specifically, dynamic Huffman codes generated by hardware implementations are denoted at120a, while dynamic Huffman codes generated by software implementations are denoted at120n.

FIG. 5illustrates process flows500for generating code words for the input symbols. More specifically, the process flows500elaborate further on illustrative processing that the tree generator component118may perform. For convenience and conciseness of description, but not to limit possible implementations, some items described previously are carried forward intoFIG. 5and denoted by the same reference numbers.

Block502represents sorting histogram data (e.g.,102) by weight/frequency. Block502may include using an insertion sorter (e.g.,114), as described above. In different implementations, the process flows500may sort heaviest weight/highest frequency symbols to the bottom of the sorter, or may sort heaviest weight/highest frequency symbols to the top of the sorter. The symbols loaded into the sorter will become the leaf nodes in the final tree, so this description refers to the symbols as leaf nodes.

Block504represents building the storage stack and branch/leaf list. The storage stack may be implemented as an inverted stack derived from the initial insertion sorter, with neither having branch nodes. The branch/leaf list may be implemented as a stack that contains the number of consecutive branches from the insertion sorter, followed by the number of consecutive leaf nodes from the insertion sorter as the tree is build bottom up. Block504may repeat until the branch/leaf list contains all the leaf nodes from the insertion sorter. Put differently, the branch/leaf list may contain the number of leafs and branches on each level of the tree.

In more detail, block504may include popping two items from the top of the insertion sorter, summing their weight to form a branch node, and pushing the branch onto the insertion sorter. If either of the items popped from the sorter are leaf nodes, block504may include pushing them onto the storage stack. Branch nodes are not pushed onto the storage stack; however, they are counted in the construction of the branch/leaf list.

Block504may include constructing the branch/leaf list as follows:a) when the first two leaf nodes are popped from the insertion sorter, set the leaf count register to two;b) continue to increment the leaf count register as leaf nodes are popped of the sorter, until a branch node is reached;c) when a branch node is reached, push the leaf count value onto the branch/leaf list stack, clear the leaf count register, and increment the branch count register;d) continue to increment the branch count register as branch nodes are popped from the sorter, until a leaf node is reached;e) when a leaf node is reached, push the branch count value onto the branch/leaf list stack, clear the branch count register, and increment the leaf count register; andf) return to sub-process b) above. Continue until insertion sorter is empty

Block506represents writing and/or filling an encode register, which may include a register for each level of the tree being constructed. When the block506completes, the encode register contains the number of leaf nodes on each level of the tree. Block506may include processing the branch/leaf list to determine how many leaf nodes are to occur on each level of the tree. The tree may be built in top-down fashion, starting with the highest index value down to the index zero at the bottom of the tree. Since the top of the tree has one branch node, no register is required. The next level down the tree has two nodes.

Block506may include:a) Determining the number of nodes for a current level of the tree. The number of nodes is twice the number of branch nodes on the level above the current level. Block506may include storing this value in a register that represents a number of nodes that are available on this current level.b) Popping the top entry off the branch/leaf list (assuming the branch-leaf list is not empty. This entry will indicate either a number of branch nodes or a number of leaf nodes.c) Assign the available nodes as leaves or branches, according to what was popped off the branch/leaf stack, and decrement the available nodes each time an entry is popped from the branch/leaf list. If the entry from the branch/leaf list is used up, pop the next entry off the branch/leaf list. Continue until all the available nodes for this level are assigned, popping entries from the branch/leaf list as appropriate. In an example implementation, block506may include only storing the leaf count in the encode register for this current level. Additionally, block506may include storing the branch count in a register that is used for calculating the number of available nodes on the next lower level of the tree.d) Return to sub-process a) to start the process of determining the number of leaf nodes for the next encode register, which represents the next level of the tree. Continue this process until the branch-leaf list is empty

Block508represents checking for a valid tree, based on the depth or levels of the tree. If the tree exceeds a maximum permitted level or depth, the process flows500may take No branch510to block512, which represents repairing the tree.FIG. 21below illustrate techniques for repairing trees, and the description of these drawings elaborates further on block512.

Returning to block508, if the tree is valid, the process flows500may take Yes branch514to block516, which represents reading leaf nodes from the storage stack. The process flows500may also reach block516after repairing an illegal tree in block512. In turn, block518represents assigning the number of bits that will be used to represent leaf nodes at the current tree level, and block520represents writing these numbers of bits to the insertion sorter. More specifically, blocks518-520may include:a) Initializing the encode register index, k, to the maximum tree levels minus 1 (codewidth−1), and reading the encoding register. If the value is zero, decrement the index and read the next encode register. Continue until a non-zero value is found. Note that in an example implementation, this process may start with the highest index because the top of the storage stack has the heaviest/most frequent leaf node. Other implementations could perform this process in reverse.b) Pop a leaf node from the storage stack, and prepend the number of bits used to encode the leaf node. Push the leaf node onto the insertion sorter, and continue until the count decrements to zero. The insertion sorter is not required for generic Huffman trees (i.e., trees that are not subject to additional constraints, understood in the context of GZIP). Some formats (e.g., GZIP) specify that items on the same tree level be sorted lexically.c) Decrement the index and read the next encode register. Continue until a non-zero entry is found. Calculate the number of bits with which to encode leaves for this level by subtracting the index from the maximum number of levels in the tree.d) Return to sub-process b) above, unless the stack is empty, at which point this process ends.

Block522represents assigning codewords to each element in the insertion sorter. More specifically, block522may include:a) initializing a current code word value to zero. Recall from the previous description that the number of bits for a given code word was previously stored in the insertion sorter;b) popping the top two leaf nodes from the sorter. In some example implementations, the sorter may be designed to pop two items at a time. However, in other example implementations, the sorter may be designed to pop one item at a time;c) pushing the second item back onto the sorter;d) assigning the code word value to the leaf popped from the sorter. The level bits that were popped with the leaf define the number of bits used for the code word value. Recall that the number of bits was previously prepended to the leaf node as it was pushed into the sorter;e) outputting the leaf, the level bits, and the codeword value;f) if the sorter is not empty, continuing with the following actions:g) incrementing the codeword value;h) popping the next two items from the sorter and pushing the second back onto the sorter;i) if the number of bits in the level field has increased, left shifting the codeword value;j) assigning the codeword value to the leaf;k) returning to sub-action e) above.

Using the foregoing actions, block522may output all elements (e.g., leaf nodes) that were encoded by the Huffman code. Block522may include outputting the elements with the codeword that represents them and with the number of bits used by the codeword.

FIG. 6illustrates processes600for generating branch nodes and pushing leaf nodes into a storage stack as they are popped from the insertion sorter. For convenience and conciseness of description, but not to limit possible implementations, some items described previously are carried forward intoFIG. 6and denoted by the same reference numbers. Additionally, while the processes600are described in connection with certain components and systems identified herein, it is noted that at least some of the processes may be performed with other components and systems without departing from the spirit and scope of the description herein. Finally, the order in whichFIG. 6presents various processing or decision blocks is chosen only for ease of description, but not to limit possible implementations.

The processes600shown inFIG. 6may be performed by, for example, a branch node generator component (e.g.,504inFIG. 5). More specifically, the branch node generator component may, for example, perform the processes600to build branch nodes in connection with generating the dynamic Huffman code.

Block606represents instantiating a branch node element for the two entries popped off of the sorter in block602. This branch node element may then be pushed into the insertion sorter as detailed further below.

Block608represents adding the weights of the two entries popped from the sorter in block602.

Block610represents assigning the added weights of the two popped entries as the weight of the branch node element that was instantiated in block602.

Block612represents pushing the branch node element into the sorter. In effect, the branch node element replaces the two popped entries in the sorter, as illustrated and discussed below inFIG. 6.

The sorter Block612can be implemented to sort with the highest weight nodes on the bottom or with the highest weight nodes on the top depending on whether nodes will be removed from the top or the bottom. The example Block618sorts with the highest weight nodes on the bottom, and nodes are removed from the top. A different implementation can sort with the highest weight on top, with nodes removed from the bottom.

In addition, if a branch is equal in weight to other nodes in the sorter, it may be placed above the nodes of equal weight,614. Or, in a different implementation, it may be placed below nodes of equal weight,616.

In different instances, the weight of the branch node element may or may not equal the weight of one or more other elements in the sorter. Whether the weight of the branch node element equals the weight of any existing entries in the sorter may impact how the stack is reordered or resorted, after the new branch node is pushed in.

In some implementations, reordering the sorter (block618) may include placing the branch node above these one or more existing leaf nodes of weight equal to the branch node, as represented by block614. Block614may also include placing the new branch node below any existing nodes having lower weights than the new branch node, and/or above any existing nodes having higher weights than the new branch node. In other implementations, reordering the sorter (block618) may include placing the branch node below these one or more existing leaf nodes having weight equal to the branch node, as represented by block616. Block616may also include placing the new branch node below any existing nodes having lower weights than the new branch node, and/or above any existing nodes having higher weights than the new branch node. It is noted that the terms “above” and “below” are used in this description for ease of description, but not to limit possible implementations.

Whether the branch node is placed below or above these existing entries of equal weight may have consequences on the dynamic Huffman codes that are generated. More specifically, different Huffman trees may result in different implementations of the process600, depending on which of blocks614and616are chosen.FIGS. 8-11provide examples of tree construction and code generation resulting from choosing block614, whileFIGS. 12-15provide examples of tree construction and code generation resulting from choosing block616.

If the weight of the branch node is not equal to any other existing entries in the sorter, then the process600may reorder the sorter by placing the branch node within the sorter based on the weight of the branch node, where this weight is not equal to any other entries in the sorter and may include placing the new branch node below any existing nodes having lower weights than the new node, and/or above any existing nodes having higher weights than the new node.

After performing618, the process600may proceed to decision block620, which represents evaluating whether the processes600are complete. For example, block620may include determining whether the weight of the branch node in the sorter indicates that the sorter has been fully processed. In the floating-point example described herein, the weights of the symbols in a given block are defined so that they sum to 1.0. In this example implementation, when the weight of the new branch node being pushed onto the sorter is 1.0, this indicates the end of the process600. However, this scenario is non-limiting, and the actual value of the weight tested for in block620may vary from 1.0. Other implementations may forego the overhead associated with floating point arithmetic, in favor of integer operations, with block620testing for a particular weight, expressed as an integer. In still other examples, block620may terminate the process600when the last entry is popped from the sorter, and the sorter thus becomes empty. Other techniques for determining when the sorter is empty may be equally appropriate.

Continuing with these example implementations, from block620, if the sorter is not yet fully processed, the process600may take No branch622to return to block602, to repeat the process600with the sorter in its updated state. However, if the process600is complete, and the sorter is now fully processed, the process600may take Yes branch624to block626, which represents designating the branch node currently being processed as the root node of the output tree being constructed (e.g.,120).

Block626represents an end state of the process600. Having completed processing the sorter for a given block of symbols, the process600may wait in block626for the arrival of a next block of symbols. When the next block of symbols arrives, the process600may process this next block, beginning at block602.

FIG. 7is a flow diagram illustrating processes700for building a branch and leaf stack and incrementing counters. For convenience and conciseness of description, but not to limit possible implementations, some items described previously are carried forward intoFIG. 7and denoted by the same reference numbers. For clarity, but not to limit possible implementations,FIG. 7shows the branch/leaf stack built one node at a time; however, it can be built one, two, or more nodes at a time as needed. Two nodes at a time is a good option as two nodes are popped from the sorter for building branch nodes. After popping the two lowest-weighted entries or the last entry from the sorter702, if the process is done the Yes706branch is taken from704. If the process is not done, the No710branch is taken from704. Following the No710branch, the entry is checked to determine if it is the first entry from the sorter712. If the Yes branch714is taken the leaf node count is incremented716.

If the No branch718is taken the entry is checked to determine if the previous entry was a leaf720. If Yes branch722is taken and if the current entry is a leaf724then the Yes branch726is taken and the leaf node count is incremented728. Returning to724, if the current entry is not a leaf, the No branch730is taken and the leaf node count is pushed onto branch/leaf stack732and the branch node count is incremented734.

Returning to720, if the previous entry was not a leaf, the No branch736is taken to block738, where it is determined if the current entry is a branch. If the current entry is a branch738, the Yes branch740is taken and the branch node count is incremented742. If the current entry is not a branch738, the No branch744is taken and a branch node count is pushed onto the branch/leaf stack746and the leaf node count is incremented748.

FIG. 8illustrates examples800of states through which a sorter (e.g.,114) and branch/leaf stack may progress as dynamic Huffman codes are generated. For convenience and conciseness of description, but not to limit possible implementations, some items described previously are carried forward intoFIG. 8and denoted by the same reference numbers. The progression of states shown inFIG. 8may indicate how the sorter and branch/leaf stack may evolve as dynamic Huffman codes are generated.FIG. 6shows an example of such a process at600; however, the process600is non-limiting.

In an initial or beginning state, shown at114a, the sorter is assumed to contain five symbols, or leaves, denoted respectively at106a,106b,106c,106d, and106n. In this example, a given block of symbols (e.g.,104inFIG. 1) is assumed to contain instances of five symbols (e.g.,106). Further, a statistical analysis of the symbols may indicate how frequently the symbols occur in the block. Additionally, the symbols are assigned weights according to their respective frequencies of occurrence. In the example shown inFIG. 8, the leaves106a,106b,106c,106d, and106nas associated with respective weights112a,112b,112c,112d, and112n. These weights112may take the respective values of 0.1, 0.1, 0.1, 0.2, and 0.5, as shown in block116aofFIG. 8.

The description herein provides this specific example of symbols and weights only for ease of understanding, but not to limit possible implementations. Instead, such implementations may include any number of symbols, and may include any suitable weighting scheme.

The sorter114is assumed to be sorted by weights in ascending order, such that the lowest-weighted symbols are at the top of the sorter. In the example shown at116a, the three lowest-weighted symbols are106a,106b, and106c, all of which have the weight 0.1. This indicates that the symbols106a,106b, and106coccur the least frequently of all the symbols represented in the sorter.

When two or more symbols are determined to have equal weights, these symbols may be arranged within the sorter arbitrarily or according to their lexical value, with these lexical values serving as a type of tie-breaker. In the sorter state116a, the symbols106aand106bare assumed to have the same weights, but the symbol106ahas lower lexical value than the symbols106b.

FIG. 8also illustrates a branch-leaf stack structure that is associated with the sorter114.FIG. 8provides five examples of the branch-leaf stack structure, several states of which are denoted at802a,802b,802c,802d, and802n. These states of the branch-leaf stack are associated with corresponding states of the sorter, as denoted at114a,114b,114c,114d, and114n. The branch/leaf stack is described as a stack structure, but may be implemented as registers or any other appropriate memory.

The two symbols106aand106bare popped from the sorter114a(e.g., block602inFIG. 6). The weights of these two symbols106aand106bare added (e.g., block608inFIG. 6), resulting a combined weight of 0.2. A branch node element for these two popped symbols106aand106bis instantiated (e.g., block606inFIG. 6), as denoted inFIG. 8at804a. The new branch node804ais assigned the combined weight of 0.2, as denoted at806a, and is pushed into the sorter. At this point, the sorter state114amay transition to a sorter state114b.

Turning to the branch-leaf stack, it may transition from an initial empty state (802a) to the state802b. As indicated by the label “(2L)” in block802b, the branch-leaf stack may include an entry indicating that two leaves (106aand106b) were popped from the sorter, as the latter passes from state114ato114b.

The sorter114bis sorted based on the weights of the entries in the sorter. In this case, the weight of branch node802ais 0.2, which equals the weight of existing symbol106d.FIG. 8assumes that such ties are resolved by placing the branch node in the stack above any equally-weighted leaf-node elements (e.g.,614inFIG. 6). Afterwards, the branch node804aappears second in the sorter state116b, between the symbols106cand106d.

From the sorter state114b, the top two elements106cand804aare popped, and a new branch node804bis instantiated for them. The popped elements106cand804ahave weights of 0.1 and 0.2, respectively. The new branch node804bis assigned the combined weights of the popped elements106cand804a, (i.e., 0.3, as denoted at806b). The new branch node804bis then pushed back into the sorter, transitioning the sorter state114bto a new sorter state114c, with the popped branch node804breplacing the symbols106cand804a.

Turning to the branch-leaf stack, it may transition from state802bto the state802c. As indicated by the label “(3L)” in block802c, the branch-leaf stack may include an entry indicating that a total of three leaves have been popped from the sorter, including the two leaves106aand106bfrom the sorter state114aand the leaf106cfrom the sorter state114b. As indicated by the label “(1L)” in block802c, the branch-leaf stack may also indicate that the branch node804awas popped from the sorter114b, with a corresponding representation of the popped branch node804abeing pushed into the branch-leaf stack802c.

In the sorter state114c, the entries are sorted according to weight, resulting in the branch node804b(weight 0.3) being located between the leaves106d(weight 0.2) and106n(weight 0.5). From the sorter state114c, the top-two entries106dand804bare popped, and a new branch node804cis instantiated for these two popped entries106dand804b. The two popped entries106dand804bhave weights of 0.2 and 0.3, respectively, so the new branch node804cis assigned a combined weight of 0.5, as denoted at806c. The new branch node804cis then pushed back into the sorter, transitioning the sorter state114cto a new sorter state114d, with the branch node804creplacing the popped entries106dand804b.

As shown at114d, the branch node804chas the same weight as the symbol106n(i.e., 0.5). As described above, the implementation inFIG. 8assumes that the new branch node is placed above the existing symbol (e.g., block614inFIG. 6), resulting in the sorter state114d.

Turning to the branch-leaf stack, it may transition from the state802cto the state802d. As indicated by the label “(1L)” in block802d, the branch-leaf stack may include an entry indicating that one leaf (106d) was popped from the sorter, as the latter passes from state114cto114d. As indicated by the label “(1B)” in block802d, the branch-leaf stack may also include an entry indicating that one branch node (804b) was popped from the sorter during this same sorter transition. When the branch node804bis popped, the branch-leaf stack stops counting leaves, pushes the leaf representation (1L) onto the stack, and then pushes on the branch representation (1B).

In the sorter state114d, only two entries remain. These two entries are popped from the sorter, and their weights are added resulting in a combined weight of 1.0. A new branch node804dis instantiated for the two popped entries, and the branch node804dis assigned the combined weight of 1.0, as indicated at706d. Additionally, under the weighting scheme used in these examples, a branch node weight of 1.0 indicates that the sorter has been completely processed (e.g., Yes branch624inFIG. 6). In this event, the new branch node804dis then pushed back into the sorter, transitioning the sorter state114dto a final sorter state114n, with the branch node804dreplacing the popped entries804cand106n. Additionally, the branch node804dis designated as the root node for the tree being constructed. In implementation, it is not necessary to push the root node804dback onto the sorter as there is nothing to sort, so the root node can be discarded.

Turning to the branch-leaf stack, it may transition from the state802dto the state802n. As indicated by the label “(2B)” in block802n, the branch-leaf stack may include an entry indicating that one branch (804c) was popped from the sorter, as the latter passes from state114dto114n. Because the branch-leaf stack was counting branches in the state802d, the branch-leaf stack adds this new branch to the previously-counted branch, resulting in the designation (2B) as shown in802n. As indicated by the label “(1L)” in block802n, the branch-leaf stack may also include an entry indicating that one leaf node (106n) was popped from the sorter after the branch node804cwas popped. When the leaf node106nis popped, the branch-leaf stack stops counting branches, pushes the branch representation (2B) onto the stack, and then pushes on the leaf representation (1L).

FIG. 9illustrates examples, denoted generally at900, of how the branch-leaf stack structure constructed inFIG. 9may be used to populate an encode register902. In turn, the encode register specifies how many leaf nodes appear at different levels of a Huffman tree, and is thus used to generate the trees. More specifically,FIG. 9illustrates several states of the branch-leaf stack, denoted at802nand802d-802a, along with corresponding entries in the encoding register. Other items introduced previously may be carried forward intoFIG. 9and denoted by similar reference numbers, only for ease of description, but not to limit possible implementations.

Turning toFIG. 9in more detail, this figure carries forward fromFIG. 8the branch-leaf stack in the state802n, to provide a starting point for the description ofFIG. 9. It is noted that these examples are illustrative in nature, rather than limiting, and that implementations of this description may process a branch-leaf stack having contents other than the ones shown in these examples.

In the illustrative initial state802n, the branch-leaf stack may contain five entries, denoted respectively at904a-904n(collectively, branch-leaf stack entries904). Assuming hardware implementations, these entries may correspond to registers or other storage elements in a memory. In software implementations (which in some cases may simulate hardware implementations), these elements may correspond to variables or data structures.

FIG. 9labels the entries to indicate whether they represent branch or leaf nodes (“B” or “L”), as well as indicating how many nodes these entries represent (expressed as an integer). For example, the entry904acontains one leaf node (1L), the entry904bcontains two branch nodes (2B), the entry904ccontains one leaf node (1L), the entry904dcontains one branch node (1B), and the entry904ncontains three leaf nodes (3L).

From the initial state802n, the branch-leaf stack may pop the top two entries, as denoted at906, because the root node is a single branch node and will have two nodes connected to it. The pop906may transition the branch-leaf stack from the state802nto802d. The pop906also removes the entry904a, which represents one leaf node, and removes one of the two branch nodes represented by the entry904b. Thus, the branch-leaf stack802dcontains an updated entry904wrepresenting one branch node, along with the entries904c-904n, which are carried forward unchanged from the previous state802n.

Turning now to the encode register902in more detail, this register may include entries or storage locations that correspond to levels within a tree structure (e.g., a Huffman tree) that is built based on the contents of the branch-leaf stack. In turn, Huffman codes may be assigned based on the contents of the encode register. More specifically, entries in the encode register may indicate how many leaves appear in the tree at the levels corresponding to the entries.

InFIG. 9, the tree is assumed to have four levels, excluding the root level, with the resulting Huffman code having a maximum length of four bits. However, it is noted that implementations of the description herein may include trees and code lengths having any suitable depth or length, as appropriate in different applications. As shown, the encode register may include four entries, denoted respectively at808a-808n(collectively, encode register entries808). These entries808a-808ncorrespond to respective levels in the tree, with the entry808aindicating how many leaves appear in the first level of the tree, the entry808bindicating how many leaves appear in the second or next deeper level, and so on until the deepest level of the tree (level “4” inFIG. 9). The branch count register924is initially 1 to represent the root of the tree. It is updated at each level of the tree to determine the number of the nodes at the next level down. It is not necessary to store the branch count in the encode register since it is sufficient to know how many leaves are on each level.

Recall that the first two entries popped from the branch-leaf stack802nincluded the leaf node904aand one of the branch nodes904b. In response to popping the leaf node, the branch-leaf stack may update the entry808ain the encode register902to indicate that the current level of the tree (the “root” level) is to contain one leaf node (1L).FIG. 9denotes this update by the dashed line910.

Popping one of the branch nodes904bindicates that the current level of the tree, level1, will contain a branch node as indicated by the branch count928. The next level down will have two nodes. The number of nodes at the next level down is two times the number of branch nodes at the current level. In response to popping one of the branch nodes904bfrom state802n, the branch-leaf stack may pop the next two top entries from the stack state802d, as denoted at912.

The pop912transitions the branch-leaf stack from state802dto802c. From the state802d, the next two entries popped from the branch-leaf stack are a branch node (904w), and a leaf node (904c). In response to popping the leaf node904c, the branch-leaf stack may update the entry908bin the encode register to indicate that the current level of the tree will contain one leaf node (1L). In the example shown, the current level is level “2”, or the second level of the tree.FIG. 9denotes this update at the dashed line914.

Popping the branch node904wmay indicate that the current level of the tree will contain a branch node as indicated by the branch count930. In response to popping the branch node904w, the branch-leaf stack may pop the next two top entries, as represented at916. The pop916transitions the branch-leaf stack from state802cto802b. From the state802c, the pop916removes a branch node904d, and removes one of the three leaf nodes represented by the entry904n. Thus, the state802bcontains only one entry904y, which is updated to represent two leaf nodes.

Turning to the two entries popped from state802c, in response to popping one of the leaf nodes904n, the branch-leaf stack may update the entry908cin the encode register to indicate that the current level of the tree (level “3”) will contain one leaf node (1L).FIG. 9denotes this update by the dashed line918.

Popping the branch node904dfrom the state902cindicates that the tree will contain a branch node at the current level (level “3”) as indicated by the branch count932. Accordingly, the branch-leaf stack may pop the next top two entries, as denoted at920. The pop920transitions the branch-leaf stack from state802bto802a, and results in the two leaf nodes904ybeing removed from the branch-leaf stack, resulting in an empty stack as denoted at802A.

In response to popping the two leaf nodes904y, the branch-leaf stack may update the entry908nto indicate that the current level of the tree (in the example, level “4” or the deepest level of the tree) is to contain two leaf nodes (2L).FIG. 9denotes this update at the dashed line922.

Because the branch-leaf stack is now empty, the encode register has been completely populated. Additionally, because the branch-leaf stack did not pop any branch nodes from the state802b, there will be no branch nodes at the current level of the tree (level “4” in this example). The encode register may now be written506.

It is important to note the exemplary nature of these diagrams. For example,FIG. 8shows the branch leaf stack being filled, whileFIG. 9shows the branch leaf stack being emptied. So,802conFIGS. 8 and 802conFIG. 9as portrayed here will not always be in the same state.

FIG. 10is a block diagram illustrating how the exemplary Huffman tree ofFIG. 8is constructed.

FIG. 10illustrates examples of dynamic Huffman trees1000that may be generated using the tools described herein. For convenience and conciseness of description, but not to limit possible implementations, some items described previously are carried forward intoFIG. 10and denoted by the same reference numbers.

The trees1000as shown inFIG. 10may correspond to the processes800shown inFIG. 8relating to generating dynamic Huffman codes and related trees (e.g.,118). Additionally, the trees may, without limitation, result from the transitions in sorter state shown inFIG. 8. More specifically, the sorter states114a-114eare carried forward intoFIG. 10. Sorter state114arepresents the initial state in which the sorter contains the five literals, represented as leaves106a-106n. Sorter state114brepresents the creation of the branch node804a, sorter state114crepresents the creation of the branch node804b, and sorter state114drepresents the creation of the branch node804c. Finally, the sorter state114erepresents the creation of the root node804d.

FIG. 11is a block diagram illustrating how the leaves of the exemplary Huffman tree constructed inFIG. 8may be assigned codes by an encode register. For convenience and conciseness of description, but not to limit possible implementations, some items described previously are carried forward intoFIG. 11and denoted by the same reference numbers.

The code or tree generation process (e.g.,118) may generate the dynamic Huffman code to the leaves by assigning binary “zero” or “one” values to the links connecting various branch nodes to their leaf nodes. In addition, the tree examples1100elaborate further on the code assignment process. For example, beginning at the root node804d, the code assignment or generation process may assign a “zero” value to a link1102from the root node804dto the branch node804c, and may assign a “one” value to a link1104from the root node804dto the leaf106n.

From the branch node804c, the code generation process may assign a “zero” value to a link1106from the branch node804cto the branch node804b, and may assign a “one” value to a link1108from the branch node804cto the leaf106d.

From the branch node804b, the code generation process may assign a “zero” value to a link1110from the branch node804bto the branch node804a, and may assign a “one” value to a link1112from the branch node804bto the leaf106c.

From the branch node804a, the code generation process may assign a “zero” value to a link1114from the branch node804ato the leaf106a, and may assign a “one” value to a link1116from the branch node804ato the leaf106b.

It is noted that the assignments of “zero” and “one” binary values as shown inFIG. 11could readily be reversed, if appropriate in different implementations. For example, the link1102could be assigned a “one” value, the link1104could be assigned a “zero” value, and so on. Thus, the bit assignments shown inFIG. 11are illustrative, but not limiting.

To ascertain the respective dynamic Huffman codes assigned to the leaves106a-106n, the code generation process may traverse the tree from the root node804dto each of the leaves106a-106n. Recall that the weights assigned to the leaves106a-106nreflect how frequently the literals represented by those leaves occur in a given block. The leaf106nhas the highest weight (0.5), which indicates that it occurs most frequently in the block. As indicated by traversing from the root node804dto the leaf106nvia the link1104, the leaf106nis encoded with the binary bit string “1”.FIG. 11denotes this assigned bit string at1118.

In similar manner, the leaf106dis assigned the bit string “01”, as shown at1120. The leaf106cis assigned the bit string “001”, as shown at1022. The leaf106bis assigned the bit string “0001”, as shown at1124, and the leaf106ais assigned the bit string “0000”, as shown at1126.

Having described the code assignments shown inFIG. 11, several observations are noted. The leaves with the highest weights occur more frequently, and these leaves are encoded with the shortest bit strings. For example, the leaf106noccurs most frequently, and is encoded with a bit string including only a single bit. Conversely, the leaves that occur less frequently are assigned longer bit strings. If the code assignment process is deployed to compress a set of input symbols, then the code assignment process enhances the efficiency of the compression by encoding the leaves that occur most frequently with the shortest bit strings.

As described previously,FIGS. 8-11pertain to scenarios in which branch nodes having weights equal to existing entries in the sorter are placed above those existing entries, as represented generally at block614inFIG. 6.FIGS. 12-15illustrate how the sorter states, code trees, and code assignments may be changed if the branch nodes are placed below these existing entries in the sorter, as represented generally at block616inFIG. 6.

FIG. 12illustrates another set of states1200through which the sorter may pass as processes for generating dynamic Huffman codes execute. For convenience and conciseness of description, but not to limit possible implementations, some items described previously are carried forward intoFIG. 12and denoted by the same reference numbers.

FIG. 12illustrates a branch-leaf stack structure that is associated with the sorter114.FIG. 12provides five examples of the branch-leaf stack structure, several states of which are denoted at1202a,1202w,1202x,1202y, and1202z. These states of the branch-leaf stack are associated with corresponding states of the sorter, as denoted at114a,114w,114x,114y, and114z.

Sorter state114ais carried forward fromFIG. 8, and contains the same example elements described above inFIG. 8. As before, the two lowest stack entries (106aand106b) are popped from the sorter and replaced with a branch node, denoted inFIG. 12at1204a. The new branch node1204ahas a weight of 0.2 (1206a), which is equal to the weight of existing leaf106d. InFIG. 8, the new branch node804awas placed above the existing leaf106d. However, inFIG. 12, the new branch node1204ais placed below the existing leaf106d, as shown at sorter state114w.

Turning to the branch-leaf stack, it may transition from an initial empty state1202ato the state1202w, as the sorter transitions from state114ato114w. As indicated by the label “(2L)” in block1202w, the branch-leaf stack may count the two leaves (106aand106b) that were popped from the sorter114a.

From sorter state114w, the two leaves106cand106dwith respective weights 0.1 and 0.2 are popped from the sorter, and a new branch node1204bis instantiated and pushed onto the sorter to replace them. The new branch node1204bhas weight 0.3, as denoted at1206bin sorter state114x.

Turning to the branch-leaf stack, it may transition from state1202wto the state1202x, as the sorter transitions from state114wto114x. As indicated by the label “(4L)” in block1202x, the branch-leaf stack may continue counting leaves, since two more leaves (106cand106d) were popped from the sorter114w. Combined with the two leaves106aand106bpopped previously from the sorter state114a, the branch-leaf stack may indicate at114xthat four consecutive leaves have been popped from the sorter.

From sorter state114x, the two branch nodes1204aand1204bare popped from the sorter, and a new branch node1204chaving weight 0.5 is pushed onto the sorter as a replacement. The new branch node1204chas the same weight as the leaf106n, and the new branch node1204cis placed below the leaf106n, as shown at sorter state114y. Finally, at sorter state114z, a new root node1204dreplaces the leaf106nand the branch node1204c. The root node1204dhas weight 1.0 (1206d).

Turning to the branch-leaf stack, it may transition from the state1202xto the state1202y, as the sorter transitions from state114xto114y. As the two branches1204aand1204bare popped from the sorter114x, the branch-leaf stack may stop counting leaves, push the entry labeled (4L) onto the stack, and begin counting branch nodes. As indicated by the label “(2B)” in block1202y, the branch-leaf stack may count the two branch nodes (1204aand1204b) that were popped from the sorter114x, as the latter passes from state114xto114y.

Finally, when the sorter transitions from114yto114z, the branch-leaf stack may transition from1202yto1202z. When the leaf106nis popped from the sorter114y, the branch-leaf stack114zmay stop counting branches, push the entry labeled (2B) onto the stack, and begin counting leaves. In this example, one leaf106npops from the sorter, followed by one branch node1204c. When the branch node1204cis popped, the branch-leaf stack1202zstops counting leaves (at one leaf—1L), pushes the element labeled1L onto the stack, and begins counting branch nodes. When the branch node1204cis popped from the sorter, the sorter is empty, and the branch-leaf stack1202zthen pushes the entry labeled (1B) onto the stack.

FIG. 13illustrates examples, denoted generally at1300, of how the branch-leaf stack structure constructed inFIG. 12may be used to populate an encode register1302. In turn, the encode register specifies how many leaf nodes appear at different levels of a Huffman tree, and is thus used to generate the trees. More specifically,FIG. 13illustrates several states of the branch-leaf stack, denoted at1202z,1202y,1202x,1202w-b, and1202aalong with corresponding entries in the encoding register. Other items introduced previously may be carried forward intoFIG. 13and denoted by similar reference numbers, only for ease of description, but not to limit possible implementations.

Turning toFIG. 13in more detail, this figure carries forward fromFIG. 12the branch-leaf stack in the state1202z, to provide a starting point for the description ofFIG. 13. It is noted that these examples are illustrative in nature, rather than limiting, and that implementations of this description may process a branch-leaf stack having contents other than the ones shown in these examples.

In the illustrative initial state1202z, the branch-leaf stack may contain four entries, denoted respectively at1304b-1304n(collectively, branch-leaf stack entries1304). Assuming hardware implementations, these entries may correspond to registers or other storage elements in a memory. In software implementations (which in some cases may simulate hardware implementations), these elements may correspond to variables or data structures.

FIG. 13labels the entries to indicate whether they represent branch or leaf nodes (“B” or “L”), as well as indicating how many nodes these entries represent (expressed as an integer). For example, the entry1304bcontains one branch node (1B), the entry1304ccontains one leaf node (1L), the entry1304dcontains two branch nodes (2B), and the entry1304ncontains four leaf nodes (4L).

From the initial state1202z, the branch-leaf stack may pop two times the top two entries, as denoted at1306. The pop1306may transition the branch-leaf stack from the state1202zto1202y. The pop1306also removes the entries1304band1304c, which represents one leaf node and one branch node. Thus, the branch-leaf stack1202ycontains an updated entry1304drepresenting one leaf node and one branch node, along with the entry1304n, which are carried forward unchanged from the previous state1202z.

Turning now to the encode register1302in more detail, this register may include entries or storage locations that correspond to levels within a tree structure (e.g., a Huffman tree) that is built based on the contents of the branch-leaf stack. In turn, Huffman codes may be assigned based on the contents of the encode register. More specifically, entries in the encode register may indicate how many leaves appear in the tree at the levels corresponding to the entries.

InFIG. 13, the tree is assumed to have three levels, with the resulting Huffman code having a maximum length of three bits. However, it is noted that implementations of the description herein may include trees and code lengths having any suitable depth or length, as appropriate in different applications. As shown, the encode register may include four entries, denoted respectively at1308a-1308n(collectively, encode register entries1302). These entries1308a-1308ncorrespond to respective levels in the tree, with the entry1308aindicating how many leaves appear in the first level of the tree, the entry1308bindicating how many leaves appear in the second or next deeper level, and so on until the deepest level of the tree (level “3” inFIG. 13).

Recall that the first two entries popped from the branch-leaf stack1202zincluded the branch node1304band one of the leaf nodes1304c. In response to popping the leaf node, the branch-leaf stack may update the entry1308ain the encode register1302to indicate that the current level of the tree (level1) is to contain one leaf node (1L).FIG. 13denotes this update by the dashed line1310.

Popping one of the branch nodes1304bindicates that the current level of the tree (the “root” level) will contain a branch node. In response to popping one of the branch nodes1304bfrom state1202z, the branch-leaf stack may pop the next two top entries from the stack state1202y, as denoted at1312.

The pop1312transitions the branch-leaf stack from state1202yto1202x. From the state1202y, the next two entries popped from the branch-leaf stack are a branch nodes (1304d). In response to popping the two branch nodes, the branch-leaf stack may update the entry1308bin the encode register to indicate that the current level of the tree will contain zero leaf nodes (0L). In the example shown, the current level is level “2”, or the second level of the tree.FIG. 13denotes this update at the dashed line1314. The branch count is now2B (1330).

The pop1316transitions the branch-leaf stack from state1202xto1202w-b. From the state1202xthe remaining four leaf entry1304nis popped from the branch-leaf stack. In response to popping the entry, the branch-leaf stack may update the entry1308cin the encode register to indicate that the current level of the tree will contain four leaves (4L). In the example shown, the current level is level “3”, or the third level of the tree.FIG. 13denotes this update at the dashed line1318. The branch count is now0B (1332).

Because the branch-leaf stack is now empty, the encode register has been completely populated. Additionally, because the branch-leaf stack did not pop any branch nodes from the state1202x, there will be no branch nodes at the current level of the tree (level “3” in this example).

FIG. 14illustrates additional examples of dynamic Huffman trees that may be generated in response to the sorter state transitions shown inFIG. 12. For convenience and conciseness of description, but not to limit possible implementations, some items described previously are carried forward intoFIG. 14and denoted by the same reference numbers.

InFIG. 12, state114a, the sorter contains the five leaves106a-106n, with the weights as shown inFIG. 14. In state114w, the branch node1204areplaces the leaves106aand106b, and has weight 0.2. In state114x, the branch node1204breplaces the leaves106cand106d, and has weight 0.3. In state114y, the branch node1204creplaces the branch nodes1204aand1204b, and has weight 0.5. In state114z, the root node1204dreplaces the branch node1204cand the leaf106n, and has weight 1.0.

Comparing the code trees shown inFIGS. 10 and 14, it is noted that the code tree shown inFIG. 14has less depth than the code tree shown inFIG. 10. As will be demonstrated inFIG. 15, these different code trees may result in different code assignments.

FIG. 15illustrates examples1500of code assignments that are possible, given the code tree shown inFIG. 14. For convenience and conciseness of description, but not to limit possible implementations, some items described previously are carried forward intoFIG. 15and denoted by the same reference numbers.

FIG. 15illustrates code assignments that may be performed similarly to the code assignments shown inFIG. 11. Applying similar assignment methodology to the tree carried forward fromFIG. 14, a code generation or assignment process (e.g.,1302) may, beginning with the root node1204d, assign a “zero” to a link1502, and may assign a “one” to a link1504. From the branch node1204c, the code generation process may assign a “zero” to a link1506, and may assign a “one” to a link1508. From the branch node1204b, the code generation process may assign a “zero” to a link1510, and may assign a “one” to a link1512. From the branch node1204a, the code generation process may assign a “zero” to a link1514, and may assign a “one” to a link1516.

Given the above bit assignments, the leaves106a-106nmay be encoded as follows. The leaf106nis assigned the bit string “1”, as indicated at1518. The leaf106dis assigned the bit string “011”, as indicated at1520. The leaf106cis assigned the bit string “010”, as indicated at1522. The leaf106bis assigned the bit string “001”, as indicated at1524. Finally, the leaf106ais assigned the bit string “000”, as indicated at1526.

The same observations regarding the code assignment illustrated inFIG. 11apply largely to the code assignment shown inFIG. 15. For example, the leaves that occur most frequently are assigned the shortest code strings, thereby enhancing coding efficiency and maximizing compression. However, the differences in the code trees are reflected in the assigned bit strings. More specifically, the maximum length of the assigned code words varies according to the depth of the code trees. Thus, inFIG. 11, the longest code word is four bits long, and the code tree shown inFIG. 11includes at most four branch nodes in sequence (804a-804d). However, inFIG. 15, the longest code word assigned is three bits long, and the code tree includes at most three branch nodes in sequence (1204aor12024, combined with1204cand1204d).

Having described the above tools and techniques for generating Huffman codes, the discussion now turns to a description of tools and techniques for repairing Huffman trees and codes. Given that Huffman codes may be derived from Huffman trees, this description refers to Huffman codes and related trees synonymously, for convenience, unless noted otherwise expressly or by context.

In some instances where the maximum tree depth may be constrained, the trees generated using the above techniques may or may not be valid because they can result in a tree that exceeds the maximum depth constraint. In instances where the tree is invalid, the tools and techniques may repair the Huffman. These repairs may be performed to bring the trees into compliance with pre-defined standards. As a non-limiting example of such standards, the DEFLATE data compression and decompression algorithm was jointly developed by Jean-Loup Gailly and Mark Adler and is specified in RFC 1951. The DEFLATE algorithm provides that Huffman codewords may have a limit of either 7 bits or 15 bits, in different scenarios. Thus, the Huffman trees that define these codewords would be limited to a maximum depth of, for example, 7 levels or 15 levels.

As shown in the examples in the preceding Figures, it is possible for Huffman trees to expand to somewhat arbitrary levels or depths in different scenarios. These levels or depths may exceed limits on depth or levels set by pre-defined standards (e.g., the DEFLATE algorithm). In such cases, the tools and techniques for repairing these Huffman trees may bring the Huffman trees into compliance with such pre-defined standards or limits.

In addition to bringing the trees into compliance with any predefined standards, the tools for repairing the Huffman trees may also optimize the trees to generate codes that offer improved performance in compression or decompression. It is noted that the tools described herein for repairing and/or optimizing these trees may operate within certain constraints, and may optimize the trees as well as possible within such constraints.

Turning in more detail to a description of these tools for repairing the Huffman trees,FIG. 16illustrates transformations, denoted generally at1600, of an example illegal tree1602into an example legal tree1604. The illegal tree1602may be “illegal” because, for example only, its depth exceeds some specified maximum limit. Trees in such a state may be characterized as having an overflowed condition. Recalling the above example of the limits specified by the DEFLATE algorithm, it is also noted that other examples of illegality are also possible. The DEFLATE algorithm is provided only as an example to aid in the description and illustration of these tools for repairing Huffman trees.

Turning to the illegal tree1602in more detail,FIG. 16denotes the maximum depth of the tree at1606a. Given this maximum depth, some nodes of the tree may be above this depth and thus “legal”, as denoted at1608a. Other nodes within the tree may be below this depth and thus “illegal”, as denoted at1610.

FIG. 16illustrates a tree repair module1612, which generally represents the tools and techniques described herein for repairing illegal trees1602into legal trees1604. As described in more detail inFIG. 17below, the tree repair module1612may be implemented as hardware and/or software.

Turning to the legal tree1604in more detail, the maximum level or depth is carried forward from the illegal tree1602, and denoted at1606b. Also, the legal nodes are carried forward and denoted at1608b. However, in the legal tree1604, the formerly illegal nodes1610in the illegal tree1602have been repositioned as repaired nodes1614. Various examples and techniques for repairing the nodes1614are presented in the drawings below.

FIG. 17illustrates operating environments1700in which the tree repair module may be implemented. For convenience and conciseness of description, but not to limit possible implementations, some items described previously are carried forward intoFIG. 17and denoted by the same reference numbers.

FIG. 17depicts hardware implementations of the tree repair module generally at1702. The tree repair module as implemented in hardware is denoted at1612a. The hardware implementations1702may include one or more substrates1704on which the tree repair module1612amay reside. The substrates1704may include, for example, printed circuit boards or chip dies on which circuit-based implementations of the tree repair module1612amay be mounted or manufactured.

FIG. 17also depicts software implementations of the tree repair module generally at1706. The tree repair module as implemented in software is denoted at1612b. The tree repair module1612bmay include computer-executable instructions that may be stored in one or more computer-readable storage media1708, and fetched into a processor1710and executed.

In some implementations, the computer-executable instructions may include software that simulates the performance of one or more hardware circuits that implement the tree repair module1612afor design, testing, or optimization purposes. In other implementations, the computer-executable instructions may include software that, when executed by the processor1710, cause a device or system to repair the trees as described herein.

The hardware or software implementations of the tree repair modules1612aand/or1612b(collectively, the tree repair modules1612) may operate in different system environments. For example only,FIG. 17shows a server system1712and a workstation1714. The server system1712and/or the workstation1714may include the substrate1704and/or the computer-readable storage medium1708.

The server system1712may offer computing services to one or more different users, by (for example) hosting applications, content, or media accessible made available to the users. The server system1712may host, for example, a website accessible over a local or wide area network. The workstation1714may enable one or more users to access the applications, content, or media from the server. Thus, the server and/or the workstation may encode or compress data using any of the tools or techniques described herein for repairing trees that are created in connection with such encoding or compression.

FIG. 18illustrates a repair, represented generally at1800, in which an illegal tree is transformed into a legal tree. For convenience and conciseness of description, but not to limit possible implementations, some items described previously are carried forward intoFIG. 18and denoted by the same reference numbers. For example, the tree repair module1612may perform the repairs illustrated inFIG. 18.

In the example shown inFIG. 18, an illegal tree1602includes two illegal nodes, denoted collectively at1610, that fall below a maximum depth1606. The illegal tree1602includes branch nodes that define a plurality of different depths or levels, labeled inFIG. 18for convenience as “Level0” through “Level5”, arranged as shown. Any leaf nodes attached to branch nodes at Levels0-4may be considered “legal”, provided the tree is legal, while any leaf nodes attached to branch nodes at Level5or below may be considered “illegal”.

FIG. 18shows a tree in a graphical form. A tree can also be described by a set of registers that define the number of leaf nodes that exist at each level of the tree. Any remaining nodes at a level in the tree will be branch nodes so it is not necessary to store the number of leaves and branches at each level. An implementation could chose to store the branch nodes rather than the leaf nodes, or store both.

Assuming that the trees1602and1604are implemented as binary trees, a given branch node may have up to two nodes attached to it. These nodes may be additional branch nodes or leaf nodes.FIG. 16denotes branch nodes by the letter “B”, and denotes leaf nodes by the letter “L”.

The example shown inFIG. 18, shows a legal Huffman tree that was made illegal by introducing a maximum depth to the tree. Setting maximum depth is the same as setting the maximum number of bits in a code word assigned to any leaf node. In this example, the maximum depth is set at Level4indicating a maximum of 4 bits can be used in a code word. The two nodes1610are illegal because they are below the maximum depth1606of the tree1602.FIG. 18thus illustrates a scenario, in which two illegal nodes1610are made legal by moving them upwards in the tree, so that they are above the maximum depth. The two repaired leaf nodes1614are shown on Level4of the repaired tree1604. The repaired tree1604does not have to be constructed as shown in this example as long as no leaf nodes are below the maximum depth and it is a legal Huffman tree. The definition of a legal tree will be provided later.

The process of moving leaf nodes that are below the maximum depth1606to a legal location is performed by the Tree Repair Module1612.

FIGS. 19 and 20provide additional examples of repaired Huffman trees.

Having provided the graphical representations of several examples of tree repairs shown inFIGS. 18-20the description proceeds to a discussion of how an encoding register (e.g.,902inFIG. 9) may be manipulated to effectuate the tree repairs described above.

FIG. 21illustrates an example, denoted generally at2100, of altering the contents of the encode register to implement the tree repairs described inFIGS. 18-20. As such,FIG. 21illustrates further aspects of the tree repair module1612. For convenience and conciseness of description, but not to limit possible implementations,FIG. 21may carry forward some items described previously, as denoted by the same reference numbers.

Turning toFIG. 21in detail, this Figure carries forward an example of an encode register, as denoted at902. An initial state of the encode register appears at902a. The encode register may contain an arbitrary number of storage locations or entries (“N”) that correspond to levels in a binary tree being constructed based on this register. N also represents the number of bits used to encode nodes at level N of the tree. In the example ofFIG. 8, the encode register is building a tree of depth4. Thus, the encode register shown inFIG. 21includes four entries or storage locations, carried forward at908a-908n. These storage locations, K=3 down to K=0, correspond respectively to levels1-4of the tree, with 4 being the deepest level. Data stored in these locations indicate how many leaf nodes are assigned to the tree level corresponding to that location.FIG. 21denotes this number of nodes at the respective blocks2102a-2102n.

FIG. 21illustrates an example scenario in which block2102aindicates that five leaf nodes appear at the deepest level of the tree, block2102bindicates that zero leaf nodes appear at the next-higher level of the tree, block2102cindicates that three leaf nodes appear at the next-higher level of the tree, and block2102nindicates that zero leaf nodes appear at the highest level of the tree. Assuming that the tree is N levels deep (i.e., the Huffman codes generated for the leaf nodes may have at most N bits), a legal Huffman tree may have a codeword space of 2N. The example ofFIG. 21assumes a four-level tree, with N=4. Therefore, one goal of the encode register is to create a tree whose node allocation results in a codeword space of 24=16.

The codeword space of a given tree configuration is expressed by the summation:

Where codewordskis the number of leaf nodes at the level of the tree equal to the current value of k. The tree is a valid Huffman tree when the codeword space equals 2N.

Applying the above summation to the encode register state902aresults in a codeword space count of 17, as denoted in block2104. This count represents a “delta” of +1. The positive delta indicating that leaf nodes should be moved “down” the tree to move the count closer to the goal of 2Nor 16. The magnitude indicates that the desired move is from the level k=1 to k=0; however, there are no leaves at level k=0.

To attempt to achieve this goal, the encode register may transition from a state902ato a state902b, by reassigning one leaf node from the level908cto the level908b, as represented by a dashed line2106. Thus, the number of leaf nodes at the level908cdecreases from three to two, as indicated at2108. Also, the number of leaf nodes at the level908bincreases from zero to one, as indicated at2110. The levels908nand908aremain unchanged from encode register states902ato902b.

From encode register state902b, repeating the summation above results in an updated codespace count of 15, as denoted at2112. This updated count represents a delta of −1. This negative delta indicates that leaf nodes should be moved “up” the tree to move closer to the goal count of 16. The magnitude indicates that the desired move is from level k=0 to level k=1.

To attempt to achieve this goal, the encode register may transition from a state902bto a state902c, by reassigning one leaf node from the level908ato the level908b, as represented by a dashed line2114. Thus, the number of leaf nodes at the level908bincreases from one to two, as indicated at2116. Also, the number of leaf nodes at the level908adecreases from five to four, as indicated at2118. The levels908nand908cremain unchanged from encode register states902bto902c.

From encode register state902c, repeating the summation above results in an updated codespace count of 16, as denoted at2120. This updated count represents a delta of 0, and indicates that a tree based on these leaf allocations would be legal.

FIG. 21shows examples indicating how the delta value may be adjusted depending on whether leaf nodes are moved up and/or down the tree. Generalizing from these examples, in positive-delta scenarios, the codespace count may be decreased by (2k(initial level)−2k(reassigned level)) times the number of leaf nodes moved, where the initial level represents the location where the leaf was prior to the move and the reassigned level the leaf was moved to. Additionally, in negative-delta scenarios, the codespace count may be increased by (2k(reassigned level)−2k(initial level)) times the number of leaf nodes moved.

In the examples shown inFIG. 21, only one bit is moved as the encode register transitions from state to state. However, in other scenarios, multiple leaf nodes may be moved, by reassigning multiple bits between various entries in the encode register. Algorithms implemented in hardware and/or software may analyze the codespace count, compare it to the 2Ngoal value, and select one or more appropriate leaf nodes to move, or move one leaf node more than one level, to drive the delta value to zero. Additionally, while multiple moves are shown to illustrate the results of moving nodes up or down the tree, these algorithms may identify moves that correct the tree in one iteration, and that may be performed in one clock pulse.

FIG. 22illustrates components and signal flows, denoted generally at2200, for assigning bit values to particular leaf nodes. For convenience and conciseness of description, but not to limit possible implementations, some items described previously may be carried forward intoFIG. 22and denoted by the same reference numbers. In those instances where the trees are initially illegal, the components and signal flows shown inFIG. 22may operate after the encode register is altered to repair the illegal trees.

An example of an insertion sorter is carried forward intoFIG. 22at114, although this sorter need not necessarily be the same insertion sorter referenced above. An example of an encode register is also carried forward at902. An example storage stack604,FIG. 6, is carried forward. As before, the encode register may include N entries, with N representing the maximum depth of the tree. InFIG. 22, the tree depth is set to four (i.e., N=4), and thus the encode register may include four entries908a-908nthat correspond respectively to the four levels of the tree. The encode register may indicate how many nodes or leaves are assigned to particular levels at2202a-2202n. In the example shown, the tree contains a total of five leaves, with level1of the tree assigned one leaf (2202n), and level3assigned four leaves (2202b).

Leaves appearing at different levels of the tree may be represented by Huffman codewords having different lengths. More specifically, the leaves assigned to level1may be represented with one bit, the leaves assigned to level2may be represented with two bits, the leaves assigned to level3may be represented with three bits, and the leaves assigned to level4may be represented with four bits. For example, one leaf could be encoded with 1-bit codewords, while the other four leaves will be encoded with 3-bit codewords.

As described above, the sorter114initially sorted representations of leaf nodes based on their frequencies of occurrence, as reflected in an appropriate weighting scheme. Those leaves that are closer to the bottom of the stack occur more frequently, and thus are represented by shorter bit strings to achieve greater compression. This order was reversed as the leaves were stored in the storage stack. In the storage stack the leaves that occur more frequently are at the top of the stack. Once the encode register repairs the tree (if appropriate), the storage stack may pop the leaves106n-106ain sequence, and assign bit lengths to the leaves using the entries in the encode register. For example, the sorter may pop the leaf106n, and refer to the encode register to determine the bit length used to encode this leaf. Starting at the top of the encode register, the first entry908nindicates that one leaf will be encoded as a 1-bit codeword, so the leaf106nis assigned a bit length of one.

The foregoing may be repeated for the other leaves106d-106ain the storage stack, resulting in these leaves106d-106abeing assigned their corresponding bit lengths from the encode register. In this example, the leaves106d-106aare assigned to 3-bit codewords. In this example, the storage stack is processed heaviest weight to lightest weight and correspondingly the encode register is processed from shortest code length to longest code length. These memories could be processed in the reverse order.

Optionally, once the codeword lengths are assigned to the leaves, the leaves may be pushed into an insertion sorter, to be sorted based on their codeword lengths and lexical value within groups of equal codeword lengths. For example, but not limitation, leaves could be pushed back into the insertion sorter114. However, it is noted that another sorter could readily be used also.

In the example shown, the sorter114first sorts the leaves based on the lengths of their codeword representations. Put differently, the leaves may be sorted based on their level within the tree. This first sort results in the arrangement shown, with the top-level leaf106aon the top of the stack and the lower-level leaves106b-106nunderneath. In some instances, one or more levels in the tree may contain multiple leaf nodes. When multiple leaves appear at the same level, the sorter may sort these multiple leaves lexically, if so specified in, for example, GZIP or DEFLATE implementations. In more generic cases, these multiple leaf nodes occurring on the same level may be left as is, and not sorted lexically. The fields2214of the input to the sorter can be arranged to sort first by the weight or bit length field (which ever is being used); then by the branch/leaf flag (if one is being used); then by the lexical value. With these fields defined the same sorter structure could be used for all sorting processes previously discussed. Once the leaves are assigned codeword lengths and optionally sorted, the leaves may be assigned particular bit strings or patterns2210. For example, GZIP or DEFLATE implementations may specify particular rules for assigning the bit strings, while other implementations may be more arbitrary.

Conclusion

Although the system and method has been described in language specific to structural features and/or methodological acts, it is to be understood that the system and method defined in the appended claims is not necessarily limited to the specific features or acts described. Rather, the specific features and acts are disclosed as exemplary forms of implementing the claimed system and method.

In addition, regarding certain data and process flow diagrams described and illustrated herein, it is noted that the processes and sub-processes depicted therein may be performed in orders other than those illustrated without departing from the spirit and scope of the description herein. Also, while these data and process flows are described in connection with certain components herein, it is noted that these data and process flows could be performed with other components without departing from the spirit and scope of the description herein