Skeleton Trees for the Efficient Decoding of Huffman Encoded Texts.
A new data structure is investigated, which allows fast decoding of texts encoded by canonical Huffman codes. The storage requirements are much lower than for conventional Huffman trees, O(log^2 n) for trees of depth O(log n), and decoding is faster, because a part of the bit-comparisons necessary for the decoding may be saved. Empirical results on large real-life distributions show a reduction of up to 50% and more in the number of bit operations. The basic idea is then generalized, yielding further savings.
Introduction
The importance and usefulness of Data Compression for Information Retrieval (IR) Systems is
today well-established, and many authors have commented on it [1, 17, 31, 27]. Large full-text
IR Systems are indeed voracious consumers of storage space realtive to the size of the raw
textual database, because not only the text has to be kept, but also various auxiliary files like
dictionaries and concordances, which are usually adjoined to the system to make the retrieval
process efficient. Moreover, certain data structures, such as decoding tables or trees, have to
be resident in RAM, so that large systems require more and more powerful machines. It is
therefore quite natural that efforts have been made to compress the text and other necessary
files, thereby reducing the demand for storage or RAM, or equivalently, for a fixed machine
with given resources, effectively increasing the size of the data base that can still be handled
efficiently.
Most of the popular compression methods are based on the works of Lempel and Ziv
[29, 30], but these are adaptive methods which are not always suitable for IR applications. In
the context of full-text retrieval, a large number of small passages is accessed simultaneously,
e.g., when producing a KWIC (Key-Word-In-Context) index in response to a submitted query,
and all these text fragments should be decodable, regardless of their exact location. When
an adaptive coding method has been used, this would then force us to start the decoding
at the beginning of the text or the logical block that contains the retrieved passage. So we
would either decode much more than needed, which may imply increased processing time, or
prepare a priori smaller blocks, which would cost us compression efficiency. In both cases,
the advantage of using adaptive methods, which often yield better compression than static
ones, may be lost.
Huffman coding [14] is still one of the best known and most popular static data compression
methods. While for certain applications, such as data transmission over a communication
channel, both coding and decoding ought to be fast, for other applications, like the IR scenario
we focus on in this paper, compression and decompression are not symmetrical tasks.
Compression is done only once, while building the system, whereas decompression is needed
during the processing of every query and directly affects response time. There is thus a special
interest in fast decoding techniques (see e.g., [15]).
The data structures needed for the decoding of a Huffman encoded file (a Huffman tree or
lookup table) are generally considered negligible overhead relative to large texts. However, not
all texts are large, and if Huffman coding is applied in connection with a Markov model [2],
the required Huffman forest may become itself a storage problem. Moreover, the "alphabet"
to be encoded is not necessarily small, and may, e.g., consist of all the different words in the
text, so that Huffman trees with thousands and even millions of nodes are not uncommon [23].
We try, in this paper, to reduce the necessary internal memory space by devising efficient ways
to encode these trees. In addition, the new suggested data structure also allows a speed-up of
the decompression process, by reducing the number of necessary bit comparisons.
The manipulation of individual bits is indeed the main cause for the slow decoding of
Huffman encoded text. A method based on large tables constructed in a pre-processing stage
is suggested in [5], with the help of which the entire decoding process can be performed using
only byte oriented commands (see also [26]). However, the internal memory required for the
storage of these tables may be very large. Another possibility to avoid accessing individual bits
is by using 256-ary instead of the optimal binary Huffman codes. This obviously reduces the
compression efficiency, but de Moura et al. [6] report that the degradation is not significant.
In the next section, we recall the necessary definitions of canonical Huffman trees as they
are used below. Section 3 presents the new suggested data structure and includes experimental
results. In Section 4, the main idea is then extended, yielding yet smaller trees and even faster
decoding.
2. Canonical Huffman codes

Figure

1: Canonical
Huffman code for
For a given probability distribution, there might be quite a large number
of different Huffman trees, since interchanging the left and right subtrees
of any internal node will result in a different tree whenever the two
subtrees are different in structure, but the weighted average path length
is not affected by such an interchange. There are often also other optimal
trees, which cannot be obtained via Huffman's algorithm. One may
thus choose one of the trees that has some additional properties. The
preferred choice for many applications is the canonical tree, defined by
Schwartz and Kallick [25], and recommended by many others (see, e.g.,
[15, 27]).
Denote by (p
we assume that be the length in bits
of the codeword assigned by Huffman's procedure to the element with
probability is the depth of the leaf corresponding to p i in the
Huffman tree. A tree is called canonical if, when scanning its leaves
from left to right, they appear in non-decreasing order of their depth
(or equivalently, in non-increasing order, as in [22]). The idea is that
Huffman's algorithm is only used to generate the lengths f' i g of the
codewords, rather than the codewords themselves; the latter are easily
obtained as follows: the i-th codeword consists of the first ' i bits immediately
to the right of the "binary point" in the infinite binary expansion
of
Many properties of canonical codes
are mentioned in [15, 3].
The following will be used as a running example in this paper.
Consider the probability distribution implied by Zipf's law, defined by
the weights
is the n-th harmonic number. This law is believed to govern the distribution
of the most common words in a large natural language text
[28]. A canonical code can be represented by the string hn 1
called a source, where k denotes, here and below, the length of the longest codeword (the
depth of the tree), and n i is the number of codewords of length k. The source
corresponding to Zipf's distribution for 74i. The code is
depicted in Figure 1.
We shall assume, for the ease of description, that the source has no "holes", i.e., there
are no three integers This is true for many
real-life distributions, and in particular for all the examples below. On the other hand, the
distribution of one of the alphabets used for compressing a set of sparse bitmaps in [8] is
All the techniques suggested herein can be easily adapted
to the general case using a vector succ(i), giving for each codeword length i, the next larger
codeword length j for which But to make the exposition clearer, we shall suppress
reference to succ(i), since for all distributions without holes,
One of the properties of canonical codes is that the set of codewords having the same length
comprises the binary representations of consecutive integers. For example, in our case, the
codewords of length 9 bits are the binary integers in the range from 110011100 to 111011010.
This fact can be exploited to enable efficient decoding with relatively small overhead: once a
codeword of ' bits is detected, one can get its relative index within the sequence of codewords
of length ' by simple subtraction.
The following information is thus needed: let be the length of the
shortest codeword, and let base(i) be the integer value of the first codeword of length i. We
then have
denote the standard s-bit binary representation of the integer k (with leading zeros,
if necessary). Then the j-th codeword of length i, for
Let seq(i) be the sequential index of the first codeword of length i:
Suppose now that we have detected a codeword w of length '. If I(w) is the integer value of the
binary string w (i.e., is the relative index of w within the
block of codewords of length '. Thus seq(') is the relative index of w within
the full list of codewords. This can be rewritten as I(w) \Gamma diff('), for
Thus all one needs is the list of integers diff('). Table 1 gives the values of n i , base(i), seq(i)
and diff(i) for our example.
9

Table

1: Decode values for canonical Huffman code for Zipf-200
We suggest in the next section a new representation of canonical Huffman codes, which
not only is space-efficient, but may also speed up the decoding process, by permitting, at
times, the decoding of more than a single bit in one iteration.
3. Skeleton trees for fast decoding
The following small example, using the data above, shows how such savings are possible.
Suppose that while decoding, we detect that the next codeword starts with 1101. This information
should be enough to decide that the following codeword ought to be of length 9 bits.
We should thus be able, after having detected the first 4 bits of this codeword, to read the
following 5 bits as a block, without having to check after each bit if the end of a codeword
has been reached. Our goal is to construct an efficient data-structure, that permits similar
decisions as soon as they are possible. The fourth bit was the earliest possible in the above
example, since there are also codewords of length 8 starting with 110.
3.1 Decoding with sk-trees
The suggested solution is a binary tree, called below an sk-tree (for skeleton-tree), the structure
of which is induced by the underlying Huffman tree, but which has generally significantly fewer
nodes. The tree will be traversed like a regular Huffman tree. That is, we start with a pointer
to the root of the tree, and another pointer to the first bit of the encoded binary sequence.
This sequence is scanned, and after having read a zero (resp., a 1), we proceed to the left
right) child of the current node. In a regular Huffman tree, the leaves correspond to full
codewords that have been scanned, so the decoding algorithm just outputs the corresponding
item, resets the tree-pointer to the root and proceeds with scanning the binary string. In our
case, however, we visit the tree only up to the depth necessary to identify the length of the
current codeword. The leaves of the sk-tree then contain the lengths of the corresponding
codewords.
f
tree pointer /\Gamma root
start
length of string
f
if string
else tree pointer /\Gamma right (tree pointer)
if value (tree pointer) ? 0
f
codeword string [start
output
tree pointer /\Gamma root
start
else

Figure

2: Decoding procedure using sk-tree
The formal decoding process using an sk-tree is depicted in Figure 2. The variable start
points to the index of the bit at the beginning of the current codeword in the encoded string,
which is stored in the vector string [ ]. Each node of the sk-tree consists of three fields: a left
and a right pointer, which are not null if the node is not a leaf, and a value-field, which is
zero for internal nodes, but contains the length in bits of the current codeword, if the node
is a leaf. In an actual implementation, we can use the fact that any internal node has either
zero or two children, and store the value-field and the right-field in the same space, with
serving as flag for the use of the right pointer. The procedure also uses two tables:
table giving the j-th element (in non-increasing order of frequency) of the
encoded alphabet; and diff [i] defined above, for i varying from m to k, that is from the length
of the shortest to the length of the longest codeword.
The procedure passes from one level in the tree to the one below according to the bits of
the encoded string. Once a leaf is reached, the rest of the current codeword can be read in
one operation. Note that not all the bits of the input vector are individually scanned, which
yields possible time savings.
9 91010
Figure

3: sk-tree for Zipf-200 distribution

Figure

3 shows the sk-tree corresponding to Zipf's distribution for 200. The tree is
tilted by 45 ffi , so that left (right) children are indicated by arrows pointing down (to the right).
The framed leaves correspond to the last codewords of the indicated length. The sk-tree of
our example consists of only 49 nodes, as opposed to 399 nodes of the original Huffman tree.
An idea similar to the sk-tree, but based on tables rather than on trees, has been suggested
by Moffat and Turpin [22]. Instead of identifying roots of subtrees in which all codewords
have the same depth, they essentially form a complete tree to a fixed depth no less than the
depth of the code tree (by extending any shorter branches), and examine the code tree nodes
at that depth to determine the minimum codeword length in each subsidiary subtree. To find
the length of a codeword, a fixed-sized window of the compressed bitstream, considered as a
binary value, is compared with left-justified base values in a sequence of hard-coded cascading
if-statements. Each such comparison is equivalent to a transition to a left or right child of the
sk-tree, and the replacement of bit comparisons by equivalent byte or word based comparisons
is reminiscent of a mechanism suggested in [5].
3.2 Construction of sk-trees
While traversing a standard canonical Huffman tree to decode a given codeword, one may
stop as soon as one gets to the root of any full subtree of depth h, for h - 1, i.e., a subtree of
depth h that has 2 h leaves, since at this stage it is known that exactly h more bits are needed
to complete the codeword. One way to look at sk-trees is therefore as standard Huffman trees
from which all full subtrees of depth h - 1 have been pruned. A more direct and much more
efficient construction is as follows.
The one-to-one correspondence between the codewords and the paths from the root to the
leaves in a Huffman tree can be extended to define, for any binary string
path P (S) induced by it in a tree with given root r 0 . This path will consist of e
e, where for i ? 0, r i is the left (resp. right) child of r
For example, in Figure 3, P(111) consists of the four nodes represented as bullets in the top
line. The skeleton of the sk-tree will consist of the paths corresponding to the last codeword
of every length. Let these codewords be denoted by L are, for our example,
etc. The idea is that P (L i ) serves as "demarcation line": any node
to the left (resp. right) of P (L i ), i.e., a left (resp. right) child of one of the nodes in P (L i ),
corresponds to a prefix of a codeword with length -
As a first approximation, the construction procedure thus takes the tree obtained by
(there is clearly no need to include the longest codeword L k , which is always a
string of k 1's), and adjoins the missing children to turn it into a complete tree in which each
internal node has both a left and a right child. The label on such a new leaf is set equal to
the label of the closest leaf following it in an inorder traversal. In other words, when creating
the path for L i , one first follows a few nodes in the already existing tree, then one branches
off creating new nodes; as to the labeling, the missing right child of any node in the path will
be labeled (basing ourselves on the assumption that there are no holes), but only the
missing left children of any new node in the path will be labeled i.
A closer look then implies the following refinement. Suppose a codeword L i has a zero in
its rightmost position, i.e., L string ff of length i \Gamma 1. Then the first codeword
of length It follows that only when getting to the i-th bit one can decide if the
length of the current codeword is i or i + 1. But if L i terminates in a string of 1's, L
with a ? 0 and jfij then the first codeword of length so the length
of the codeword can be deduced already after having read the bit following fi. It follows that
one does not always need the full string L i in the sk-tree, but only its prefix up to and not
including the rightmost zero. Let L
prefix. The revised version of the above
procedure starts with the tree obtained by
The nodes of this tree are depicted
as bullets in Figure 3. For each path P (L
there is a leaf in the tree, and the left child of
this leaf is the new terminal node, represented in Figure 3 by a box containing the number i.
The additional leaves are then filled in as explained above.
3.3 Space complexity
To evaluate the size of the sk-tree, we count the number of nodes added by path P (L
k. Since the codewords in a canonical code, when ordered by their corresponding
frequencies, are also alphabetically sorted, it suffices to compare L i to L i\Gamma1 . Let
empty string, and for i ? m, let fl(i) be the longest common prefix of L i and L
is the string 10 in our example. Then the number of nodes in the sk-tree is given by:
since the summation alone is the number of internal nodes (the bullets in Figure 3).
The maximum function comes to prevent an extreme case in which the difference might
be negative. For example, if L then the longest common prefix
is but since we consider only the bits up to and not including the rightmost zero,
we have L
In this case, indeed, no new nodes are added for P (L
An immediate bound on the number of nodes in the sk-tree is O(min(n; k 2 )), since on the
one hand, there are up to
2, but on the other hand, it
cannot exceed the number of nodes in the underlying Huffman tree, which is 2n \Gamma 1. To get
a tighter bound, consider the nodes in the upper levels of the sk-tree belonging to the full
binary tree F with leaves and having the same root as the sk-tree. The depth of F is
1)e, and all its leaves are at level d or d \Gamma 1. The tree F is the part of the
sk-tree where some of the paths P (L
must be overlapping, so we account for the nodes in F
and for those below separately. There are at most 2k \Gamma 1 nodes in F ; there are at most k \Gamma 1
disjoint paths below it, with path P (L
extending at most
F , for log This yields as bound for the number of nodes in the sk-tree:
There are no savings in the worst case, e.g., when there is only one codeword of each
length (except for the longest, for which there are always at least two). More generally, if
the depth of the Huffman tree is \Omega\Gamma n), the savings might not be significant. But such trees
are optimal only for some very skewed distributions. In many applications, like for most
distributions of characters or character pairs or words in most natural languages, the depth
of the Huffman tree is O(log n), and for large n, even the constant c, if the depth is c log 2 n,
must be quite small. For suppose the Huffman tree has a leaf on depth d. Then by [16,
Theorem 1], the probability of the element corresponding to this leaf is
F j is the j-th Fibonacci number, and we get from [18, Exercise 1.2.1-4], that
5)=2 is the golden ratio. Thus if d ? c log 2 n, we have
To give a numeric example, in Section 4 below one of the Huffman trees corresponds to the
different words in English, with leaves. The probability for a tree of this size
to have a leaf at level 3 log 2 n is less than 4:4 \Theta 10 \Gamma12 , meaning that such a word occurs only
once every 4400 billion words; the existence of such a rare word then puts a lower limit on the
size of the text, which in our case must be large enough to fill about 35,000 CD-Roms! For
all the distributions given in Table 2 in the experiments below, the ratio of the depth of the
Huffman tree to log 2 n is between 1.31 and 2.61. But even if the original Huffman tree would
be deeper, it is sometimes convenient to impose an upper limit of O(log n) on the depth,
which often implies only a negligible loss in compression efficiency [10]. In any case, given a
logarithmic bound on the depth, the size of the sk-tree is about
log n (log
3.4 Time complexity
When decoding is based on a standard Huffman tree, the average number of comparisons
per codeword is the sum, taken over all the leaves i, of the depth of i in the tree times the
probability to get to i. A similar sum holds for sk-trees, with the difference that a leaf does
not correspond to a single element, but to several consecutive codewords of the same length.
Let w be the prefix of a codeword corresponding to a leaf of the sk-tree labeled
and denote codewords corresponding to this leaf of the sk-tree are
correspond, using the notations of Section 2, to indices in the range from
diff('). The average number of comparisons per codeword using
the sk-tree can thus be evaluated as:
i2fleaves in sk-treeg@ d i
where w i is the binary string corresponding to the leaf i, d is the depth of i in the tree,
' i is a shortcut for label(i), and Prob(j) is the probability of the element with index j.
As an approximation, we assume that the probability of an element on level i in the tree
is 2 \Gammai . This corresponds to a dyadic probability distribution, where all the probabilities are
integral powers of 1. There cannot be too great a difference between the actual probability
distribution and this dyadic one, since they both yield the same Huffman tree (see [20] for
bounds on the "distance" between such distributions). Given this model, eqn. (2) becomes
i2fleaves in sk-treeg
A similar sum, but taken over all the leaves of the original Huffman tree gives the average
codeword length for a dyadic distribution. There are therefore large savings whenever the
number of nodes in the sk-tree is much smaller than in the underlying full Huffman tree.
3.5 Experimental Results
To test the effectiveness of the use of sk-trees, the following real-life distributions were used.
The data for French was collected from the Tr'esor de la Langue Fran-caise, a database of
680 MB of French language texts (115 million words) of the 17 th -20 th centuries [4]; for English,
the source are 500 MB (87 million words) of the Wall Street Journal [24]; and for Hebrew,
a part of the Responsa Retrieval Project , 100 MB of Hebrew and Aramaic texts (15 million
words) written over the past ten centuries [7]. The first set of alphabets consists of the bigrams
in the three languages (the source for English for this distribution was [13]); for the next set,
the elements to be encoded are the different words, which yields very large "alphabets"; and
the final set contains the distribution of trigrams in French. For completeness, the Zipf-200
distribution used in the above examples was also added.
total average number of average relative
Source k number of codeword nodes in number of savings in #
elements length sk-tree comparisons comparisons
bigrams French 29 2192 7.784 285 4.620 40.6%
Hebrew 24 743 8.037 127 4.183 48.0%
English 26 289101 11.202 425 5.726 48.9%
words French 27 439191 10.473 443 5.581 46.7%
Hebrew
trigrams French 28 25781 10.546 381 5.026 52.3%

Table

2: Time and Space requirements for real-life distributions

Table

2 displays the results. The first three columns give some statistics about the various
distributions: the depth k of the Huffman tree, the size n of the encoded alphabet, and the
weighted average length of a codeword, measured in bits, which equals the average number of
comparisons if the standard Huffman tree is used. The next two columns bring the number
of nodes in the sk-tree, as given in eqn. (1), and the average number of comparisons per
codeword when decoding is based on the sk-tree, as given in eqn. (2). The final column shows
the relative savings in the number of comparisons, measured in percent. We see that for large
distributions, roughly half of the comparisons may be saved. Note that these savings are in
spite of the fact that the high-probability symbols with short codewords have relatively few
bits in common. The weighted average takes this into account: few bits are saved for the
shorter codewords, and the savings are multiplied by higher probabilities; more bits are saved
for the longer codewords, but even if their probabilities are very small, their large number
have a cumulative effect. Note also that the cost of storing the sk-tree is only several percent
of the cost for the full Huffman tree.
4. Reduced sk-trees
We now wish to explore what might be gained by pruning the sk-tree at some internal node:
one would thus get to leaves at which it is not yet possible to deduce the length of the
current codeword, but at which some partial information is already available. For example,
in

Figure

3, if the bits already processed were 111 (corresponding to the internal node in the
rightmost upper corner), we know already that the length of the current codeword is either 9
or 10. We therefore need only one more comparison to know the exact length: concatenate
the following seven bits with the three already processed to get a 10-bit string w; if the binary
value of w is smaller than base(10), the next codeword must be of length 9, otherwise it is of
length 10. If we had used the original sk-tree as explained in the previous section, we would
have had at least one more comparison, possibly even more, e.g., if the bits after 111 were
0110, we would have performed four more comparisons and still not know if the length is 9 or
This reflection leads to the idea of a reduced sk-tree, which is obtained from the sk-tree by
pruning some of its branches. On the one hand, this reduced tree is obviously smaller, on the
other, as we saw, it may also decrease the number of comparisons. More formally, define for
each node v of the sk-tree two values lower(v) and upper(v) by:
if v is a leaf lower(v)
if v is an internal node lower(v) = lower(left(v))
that is, for each node v, the codewords corresponding to leaves of the sub-tree rooted by v
have their lengths in the interval [lower(v); upper(v)]. In terms of our earlier notation we have
We define the reduced sk-tree as the smallest sub-tree
of the sk-tree for which all the leaves w correspond to a range of at most two consecutive
codeword lengths, i.e.,
5-6

Figure

4: Reduced sk-tree for Zipf-200 distribution

Figure

4 is the reduced sk-tree obtained from the sk-tree of Figure 3. Leaves are now
also indicated as bullets, with the corresponding range underneath. Recall that the original
Huffman tree had 399 nodes, and the sk-tree 49; in the reduced sk-tree we are left with only
13. Note that all the leaves of the original sk-tree are deleted, but also entire sub-trees. The
nodes corresponding to the part of P (L
which is not overlapping with P (L
eqn. (3), but since we seek the minimal tree, for each such path, only the node highest up in
the tree need be kept, so the rest of this branch and its offsprings are pruned.
A generalized view of both regular and reduced sk-trees would be as follows: consider a
full canonical Huffman tree and assign to each node the values lower and upper. Delete now
some of the nodes, starting at any leaf and proceeding to the parent nodes, until you get to the
smallest tree for which every leaf w satisfies lower(w) = upper(w), i.e., all the corresponding
codewords have the same length; this is the sk-tree. If the process is continued and more
nodes are deleted until the codewords corresponding to the new leaves have lengths i or
for some i, we get the reduced sk-tree. We henceforth adopt the notation sk 1 -tree and sk 2 -tree
for the original and the reduced sk-trees, respectively, the subscript referring to the maximal
size of the set of codeword-lengths associated with each of the leaves of the tree.
We cannot use equality in eqn. (3), which would impose a range of exactly two codeword
lengths for each leaf of the sk 2 -tree. In the example of Figure 4 all the leaves do have equality
Last elements
of codeword blocks
5-6 6-7
12Corresponding sk 2 -tree

Figure

5: Example of sk 2 -tree with special leaves
in eqn. (3), but for other examples, leaves may exist, the parent nodes of which correspond
already to ranges of 3 or more codeword lengths. In this case, the original leaf of the sk 1 -
tree must be kept. Let us call such leaves in the sk 2 -tree special leaves. For the example
distributions above, special leaves exist only for the distribution of the Hebrew bigrams, the
first few elements of the source being h0; 0; 0; 0; In the left
part of Figure 5, the last codewords L i for the codeword lengths up to 13 are listed, and the
right part of Figure 5 is the corresponding section of the sk 2 -tree. The special leaves w are
indicated as rectangles, containing the value lower(w) (which is equal to upper(w)), the other
leaves are depicted as bullets as above.
For example, we see that only codewords of length 8 can have the prefix 011, but the
parent node of the corresponding leaf is associated with the prefix 01, which may be extended
to codewords of lengths 6, 7 or 8. Similarly, a prefix 11110 implies the codeword length 11,
but 1111 is the prefix of codewords of lengths 11 to 24.
The decoding procedure for sk 2 -trees is similar to that of the sk 1 -trees given in Figure 2,
and only the if-block has to be replaced by the one in Figure 6. We now use a f lag field for
each leaf w, with f otherwise. The value
field of w stores lower(w) if w is a leaf, and 0 if w is an internal node.
if value (tree pointer) ? 0
f
len /\Gamma value (tree pointer)
codeword string [start
if f lag (tree
f
codeword string [start
len
output
tree pointer /\Gamma root
start

Figure

Decoding using sk 2 -tree
When a leaf w is reached, the current codeword is initialized as having length lower(w).
This is the correct setting if w is a special leaf or if the next codeword has indeed length
lower(w). When w is not a special leaf (f lag(w) = 1), we check if by appending a zero at the
right end of the codeword, we get an integer value larger or equal to that of the first codeword
of length lower(w) + 1. If so, we update the current codeword to include also the following
bit.
The construction of sk 2 -trees is similar to that of the underlying sk 1 -tree. We again consider
the paths of nodes
only those nodes that appear in at least two different
paths; these are the internal nodes of the sk 2 -tree. The leaves are then added by filling in the
missing left and right children, some of which may be special leaves.
As to the space complexity of sk 2 -trees, note that in principle, several special leaves may
emanate from a single branch P (L
leaves the upper bound for the number of nodes
at O(min(n; k 2 )) as for sk 1 -trees. But in practice, special leaves are rare, because they appear
only in the very particular case when P (L
contained in either P (L
In the former case, the special leaves are right children of nodes in P (L
in the latter they are
left children. For example, referring to the tree in Figure 5, L
is a prefix of L
and generates a special leaf as a right child, whereas L
contains L
as a prefix and generates special leaves as left children. If for a given Huffman tree, there are
no special leaves in its associated sk 2 -tree, as was the case in all our examples beside the one
of

Figure

5, then the number of nodes is clearly there is exactly one
leaf for each range and the sk 2 -tree is a complete tree, i.e., each internal
node has exactly two children.
The sizes of the sk 2 -trees for our earlier example distributions are listed in Table 3. As can
be seen, even for huge Huffman trees with hundreds of thousands of nodes, this size is reduced
to several tens, and there is a 70-90% reduction even relative to the sizes of the sk 1 -trees.
number of Savings average Savings
Source nodes in rel. to number of rel. to
sk2 -tree sk1 -tree comparisons sk1 -tree
English 15 78% 3.444 18.0%
bigrams French 47 84% 3.757 18.7%
Hebrew
English 41 90% 4.842 15.4%
words French 41 91% 4.725 15.3%
Hebrew 33 90% 4.715 17.2%
trigrams French 43 89% 4.157 17.3%

Table

3: Time and Space requirements for sk 2 -trees
To evaluate the average number of comparisons, we take a sum similar to eqn. (2) over
all the leaves of the sk 2 -tree. For the special leaves, the formula of eqn. (2) applies. For
the others, let w be the prefix of the corresponding codeword, assume the leaf is labeled ',
jwj. Then the codewords corresponding to this leaf of the sk 2 -
tree are w0 . The first few of them are of length ' and the following ones of length
'+1. The exact cutoff point is not important, as the codewords correspond to the consecutive
indices in the range from I(w0 t 1). The probability of each
of these codewords should be multiplied by the number of necessary comparisons to detect
them, which is jwj + 1, since we need an additional comparison to decide if the length is ' or
1. This yields, using the same notations as for eqn. (2), the following formula:
i2fleaves in sk-treeg@ d

Table

3 gives the resulting averages for our examples. For the real-life examples, they give
a reduction of 50-64% relative to the regular Huffman decoding algorithm, and of 15-19%
relative to the algorithm using sk 1 -trees.
5. Final remarks
If pruning the skeleton tree turned out to be profitable in terms of both time and space,
shouldn't we climb up even higher and define sk d -trees accordingly, for d ? 2?
We can associate a value range-size with each node v of the sk 1 -tree, giving the size of
the set of the corresponding codeword lengths. The leaves of the sk 1 -tree have all range-size
those of the sk 2 -tree have range-size - 2. Consider a path that starts at any leaf of the
moves through parent pointers towards the root. The range-size values of the
nodes in this path form a non-decreasing sequence, the first value being 1, followed possibly
by several 2's, etc. Fixing, for all such paths, the last node with value 2 (if it exists) as a new
leaf yields the sk 2 -tree. Similarly, proceeding even further up to the last node with value 3
would yield an sk 3 -tree, etc.
However, the savings incurred by passing from the sk 1 -tree to the sk 2 -tree were caused
by the fact that several consecutive nodes on these paths had the range-size value 2, so that
the new leaves were several levels higher, and accordingly several comparisons could be saved.
But if the parent node of a node with range-size value 3 has also range-size value 3, the other
child of this parent node must have range-size value 1, which means that it is a special leaf.
We argued earlier that such cases are rare. Therefore, whenever no special leaf is involved,
passing from the lowest node with range-size value 2 to the lowest node with range-size value
3 would just let us climb one level and save one comparison. On the other hand, we need now
an additional comparison within the range of 3 values, so that in all these cases, nothing is
gained.
Of course, for the price of two additional comparisons, we could process, using binary
search, ranges of size 4 and not just 3. More generally, we need only r additional comparisons
after reaching a leaf of an sk 2 r -tree. Pushing this idea to its extreme with
would be no skeleton-tree at all, and we would find the correct length of a codeword using
a sequence of binary search steps in the list of first (or last) codewords for every codeword
length, as suggested in [22]. But with standard binary search, the search in a code with
maximal codeword length k takes exactly dlog 2 ke comparisons, which would be 4 or 5 for
our example distributions. Note that while the average number of comparisons with sk 1 -trees
is above that threshold for all the examples (Table 2), all the corresponding values for the
are below it (Table 3). It does therefore not seem necessarily worthwhile to pass to
sk d -trees, for d ? 2.
Moffat and Turpin [22] further suggest to use a biased binary search, since the probability
distribution of the codeword lengths is itself very skewed. For the first few bits of any code-
word, this approaches then a linear search. The skeleton-trees introduced in this paper are a
convenient data structure to perform a similar search efficiently.



--R



Is Huffman coding dead?
Ziff D.
Perl Y.
Fast searching on compressed text allowing errors
All about the Responsa Retrieval Project you always wanted to know but were afraid to ask



Rabinowitz J.
Moore E.
Information Retrieval
A method for the construction of minimum redundancy codes

Nemetz T.

The Art of Computer Programming

An application of informational divergence to Huffman codes

On the implementation of minimum redundancy prefix codes

Text compression for dynamic document databases
Kallick B.
Fast decoding of the Huffman codes

The Psycho-Biology of Language
A universal algorithm for sequential data compression
Compression of individual sequences via variable-rate coding
Adding compression to a full-text retrieval system
--TR

--CTR
Dana Shapira , Ajay Daptardar, Adapting the Knuth-Morris-Pratt algorithm for pattern matching in Huffman encoded texts, Information Processing and Management: an International Journal, v.42 n.2, p.429-439, March 2006
canonical Huffman codes;skeleton trees;huffman trees;decoding