arXiv:1605.06615v2 [] 14 Dec 2016

Efficient and Compact Representations of
Some Non-Canonical Prefix-Free Codes⋆
Antonio Fariña1 , Travis Gagie2 , Giovanni Manzini3,4 ,
Gonzalo Navarro5, and Alberto Ordóñez6
1

Database Laboratory, University of A Coruña, Spain
Helsinki Institute for Information Technology (HIIT)
Department of Computer Science, University of Helsinki, Finland
Institute of Computer Science, University of Eastern Piedmont, Italy
4
IIT-CNR, Pisa, Italy
5
Department of Computer Science, University of Chile, Chile
6
Yoop SL, Spain
2

3

Abstract. For many kinds of preﬁx-free codes there are eﬃcient and
compact alternatives to the traditional tree-based representation. Since
these put the codes into canonical form, however, they can only be used
when we can choose the order in which codewords are assigned to characters. In this paper we ﬁrst show how, given a probability distribution
over an alphabet of σ characters, we can store a nearly optimal alphabetic preﬁx-free code in o(σ) bits such that we can encode and decode
any character in constant time. We then consider a kind of code introduced recently to reduce the space usage of wavelet matrices (Claude,
Navarro, and Ordóñez, Information Systems, 2015). They showed how
to build an optimal preﬁx-free code such that the codewords’ lengths are
non-decreasing when they are arranged such that their reverses are in lex
icographic order. We show how to store such a code in O σ log L + 2ǫL
bits, where L is the maximum codeword length and ǫ is any positive
constant, such that we can encode and decode any character in constant
time under reasonable assumptions. Otherwise, we can always encode
and decode a codeword of ℓ bits in time O(ℓ) using O(σ log L) bits of
space.

1

Introduction

Binary prefix-free codes can be represented as binary trees whose leaves are
labelled with the characters of the source alphabet, so that the ancestor at
⋆

Funded in part by European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 690941 (project
BIRDS). The ﬁrst author was supported by: MINECO (PGE and FEDER) grants
TIN2013-47090-C3-3-P and TIN2015-69951-R; MINECO and CDTI grant ITC20151305; ICT COST Action IC1302; and Xunta de Galicia (co-founded with
FEDER) grant GRC2013/053. The second author was supported by Academy of
Finland grants 268324 and 250345 (CoECGR). The fourth author was supported by
Millennium Nucleus Information and Coordination in Networks ICM/FIC P10-024F,
Chile.

2

Fariña et al.

depth d of the leaf labelled x is a left child if the dth bit of the codeword for
x is a 0, and a right child if it is a 1. To encode a character, we start at the
root and descend to the leaf labelled with that character, at each step writing
a 0 if we go left and a 1 if we go right. To decode an encoded string, we start
at the root and descend according to the bits of the encoding until we reach a
leaf, at each step going left if the next bit is a 0 and right if it is a 1. Then we
output the character associated with the leaf and return to the root to continue
decoding. Therefore, a codeword of length ℓ is encoded/decoded in time O(ℓ).
This all generalizes to larger code alphabets, but for simplicity we consider only
binary codes in this paper.
There are, however, faster and smaller representations of many kinds of
prefix-free codes. If we can choose the order in which codewords are assigned
to characters then, by the Kraft Inequality [8], we can put any prefix-free code
into canonical form [13] — i.e., such that the codewords’ lexicographic order
is the same as their order by length, with ties broken by the lexicographic order of their characters — without increasing any codeword’s length. If we store
the first codeword of each length as a binary number then, given a codeword’s
length and its rank among the codewords of that length, we can compute the
codeword via a simple addition. Given a string prefixed by a codeword, we can
compute that codeword’s length and its rank among codewords of that length
via a predecessor search. If the alphabet consists of σ characters and the maximum codeword length is L, then we can build an O(σ log L)-bit data structure
with O(log L) query time that, given a character, returns its codeword’s length
and rank among codewords of that length, or vice versa. If L is at most a constant times the size of a machine word (which it is when we are considering, e.g.,
Huffman codes for strings in the RAM model) then in theory we can make the
predecessor search and the data structure’s queries constant-time, meaning we
can encode and decode in constant time [5].
There are applications for which there are restrictions on the codewords’ order, however. For example, in alphabetic codes the lexicographic order of the
codewords must be the same as that of the characters. Such codes are useful
when we want to be able to sort encoded strings without decoding them (because the lexicographic order of two encodings is always the same as that of the
encoded strings) or when we are using data structures that represent point sets
as sequences of coordinates [10], for example. Interestingly, since the mapping
between symbols and leaves is fixed, alphabetic codes need only to store the
tree topology, which can be represented more succinctly than optimal prefix-free
codes, in 2σ + o(σ) bits [9], so that encoding and decoding can still be done in
time O(ℓ). There are no, however, equivalents to the faster encoding/decoding
methods used on canonical codes [5].
In Section 2 we show how, given a probability distribution over the alphabet,
we can store a nearly optimal alphabetic prefix-free code in o(σ) bits such that
we can encode and decode any character in constant time. We note that we
can still use our construction even if the codewords must be assigned to the

Non-Canonical Preﬁx-Free Codes

3

characters according to some non-trivial permutation of the alphabet, but then
we must store that permutation such that we can evaluate and invert it quickly.
In Section 3 we consider another kind of non-canonical prefix-free code, which
Claude, Navarro, and Ordóñez [1] introduced recently to reduce the space usage
of their wavelet matrices. (Wavelet matrices are alternatives to wavelet trees [6,
10] that are more space efficient when the alphabet is large.) They showed how
to build an optimal prefix-free code such that the codewords’ lengths are nondecreasing when they are arranged such that their reverses are in lexicographic
order. They represent the code in O(σL) bits, and encode and decode a codeword
of length ℓ in time O(ℓ). We show how to store such a code in O(σ log L) bits,
and still encode and decode
any character in O(ℓ) time. We also show that, by

using O σ log L + 2ǫL bits, where ǫ is any positive constant, we can encode and
decode any character in constant time when L is at most a constant times the
size of a machine word. Our first variant is simple enough to be implementable.
We show experimentally that it uses 23–30 times less space than a classical
implementation, at the price of being 10–21 times slower at encoding and 11–30
at decoding.

2

Alphabetic Codes

Our approach to storing an alphabetic prefix code compactly has two parts: first,
we show that we can build such
codeword length is
 such that the

√expected
√ a code
1 + O 1/ log n greater than optimal,
at most a factor of (1 + O 1/ log n )2 = √
the code-tree √
has height at most lg σ + lg σ + 3, and each subtree rooted at
depth ⌈lg σ − lg σ⌉ is completely balanced; then, we show how to store such a
code-tree in o(σ) bits such that encoding and decoding take constant time.
Evans and Kirkpatrick [2] showed how, given a binary tree on n leaves, we
can build a new binary tree of height at most ⌈lg n⌉ + 1 on the same leaves in
the same left-to-right order, such that the depth of each leaf in the new tree is
at most 1 greater than its depth in the original tree. We can use their result
to restrict the maximum codeword length of an optimal
√ alphabetic prefix code,
its
for an alphabet of σ characters, to be at most lg σ + lg σ + 3, while forcing

√
expected codeword length to increase by at most a factor of 1 + O 1/ log σ .
To do so, we build the tree Topt for an optimal alphabetic prefix code and then
rebuild, according
to Evans and Kirkpatrick’s construction, each
√ subtree rooted
√
at depth ⌈ lg σ⌉. The resulting tree, Tlim , has height at most ⌈ lg σ⌉+⌈lg
σ⌉+1
√
and any leaf whose depth increases was already at depth at least ⌈ lg σ⌉.
There are better ways to build a tree Tlim with such a height limit. Itai [7] and
Wessner [14] independently showed how, given a probability distribution over an
alphabet of σ characters, we can build an alphabetic
prefix code Tlim that has
√
maximum codeword length at most lg σ + lg σ + 3 and is optimal among all
such codes. Our construction in the previous paragraph, even if not optimal,

√
shows that the expected codeword length of Tlim is at most 1 + O 1/ log σ
times times that of an optimal code with no length restriction.

4

Fariña et al.

Further,
√ let us take Tlim and completely balance√each subtree rooted at depth
⌈lg σ − lg σ⌉. The height remains at most lg σ + lg σ√+ 3 and any leaf whose
depth increases was already at depth at least ⌈lg σ − lg σ⌉, so the expected
codeword length increases by at most a factor of
√

 p
lg σ + lg σ + 3
√
= 1 + O 1/ log σ .
⌈lg σ − lg σ⌉
Let Tbal be the resulting tree. Since
√ the expected codeword length of Tlim is in
turn at most a factor of 1 + O 1/ log n larger than that of Topt , the expected
√
codeword length
of Tbal is also at most a factor of (1 + O 1/ log n )2 = 1 +

√
O 1/ log n larger than the optimal. Tbal then describes our suboptimal code.
To represent Tbal , we store a bitvector B[1..σ] in which B[i] = 1 if and
only if the
√ codeword for the ith character in the alphabet has length at most
⌈lg σ − lg σ⌉,√or if the ith leaf in T is the leftmost leaf in a subtree rooted at
depth ⌈lg σ − lg
√σ⌉. With Pǎtraşcu’s implementation [12] for B this takes a
total of O 2lg σ− lg σ log σ + σ/ logc σ = O(σ/ logc σ) bits for any constant c,
and allows us to perform in constant time O(c) the following operations on B:
(1) access, that is, inspecting any B[i]; (2) rank, that is, rank(B, i) counts the
number of 1s in any prefix B[1..i]; and select, that is, select(B, j) is the position
of the jth 1 in B, for any j.
Let us for simplicity assume that the √alphabet is [1..σ]. For encoding in

constant time we store an array S[1..2⌈lg σ− lg σ⌉ ], which stores the explicit code
assigned to the leaves of Tbal where B[i] = 1, in the same order of B. That is,
if B[i] = 1, then the code assigned to the character i is stored
 at S[rank(B,
i)],
√
√
lg σ− lg σ
log σ =
using lg σ+ lg σ+3 = O(log σ) bits. Therefore S requires O 2
c
o(σ/ log σ) bits of space, for any constant c. We can also store the length of the
code within the same asymptotic space.
To encode the character i, we check whether B[i] = 1 and, if so, we simply
look up the codeword in S as explained. If B[i] = 0, we find the preceding 1 at
i′ = select(B, rank(B,
√ i)), which marks the leftmost leaf in the subtree rooted
at depth ⌈lg σ − lg σ⌉ that contains the ith leaf in T . Since the subtree is
completely balanced, we can compute the code for the character i in constant
time from that of the character i′ : The size of the balanced subtree is r = i′′ − i′ ,
where i′′ = select(B, rank(B, i′ ) + 1), and its height is h = ⌈lg r⌉. Then the
first 2r − 2h codewords are of the same length of the codeword for i′ , and the
last 2h − r have one bit less. Thus, if i − i′ < 2r − 2h , the codeword for i′ is
S[rank(B, i′ )]+i−i′, of the same length of that of i; otherwise it is one bit shorter,
′
h−1
(S[rank(B, i′ )]+2r−2h)/2+i−i′ −(2r−2h ) = S[rank(B, i′ )]/2+i−i
).
√ −(r−2
To be able to decode
quickly, we store an array A[1..2⌈lg σ− lg σ⌉ ] such that,
√
√
⌈lg σ− lg σ⌉
for 1 ≤ j ≤ 2
, if the ⌈lg σ − lg σ⌉-bit binary representation of j − 1 is
prefixed by the ith codeword,
then A[j] stores i and the length of that codeword.
√
If, instead, the ⌈lg σ − lg σ⌉-bit binary representation of j is the path label to
the root of a subtree of Tbal with size more than 1, then A[j] stores the position

Non-Canonical Preﬁx-Free Codes

5

′
i′ in B of√the leftmost
 leaf in that subtree (thus B[i ] = 1). Again, A takes
O 2log σ− log σ log σ = o(σ/ logc σ) bits, for any constant c.
Given
√ a string prefixed by the ith codeword, we take the prefix of length
⌈lg σ − lg σ⌉ of that string (padding with 0s on the right if necessary), view it
as the binary representation of a number j, and check A[j]. This either tells us
immediately i and the length of the ith codeword, or tells us the position i′ in B
of the leftmost leaf in the subtree containing the desired leaf. In the latter case,
since the subtree is completely balanced, we can compute i in constant time: We
find i′′ , r, and h as done for encoding. We then take the first h bits of the string
(including the prefix we had already read, and padding with a 0 if necessary),
and interpret it as the number j ′ . Then, if d = j ′ − S[rank(B, i′ )] < 2r − 2h , it
holds i = i′ + d. Otherwise, the code is of length h − 1 and the decoded symbol
is i = i′ + 2r − 2h + ⌊(d − (2r − 2h ))/2⌋ = i′ + r − 2h−1 + ⌊d/2⌋.

Theorem 1. Given a probability distribution over an alphabet of σ characters,
we can build an alphabetic
prefix code whose expected codeword length is at most
√
a factor of 1 + O 1/ log σ more than optimal and store it in O(σ/ logc σ) bits,
for any constant c, such that we can encode and decode any character in constant
time O(c).

3

Codes for Wavelet Matrices

As we mentioned in Section 1, in order to reduce the space usage of their wavelet
matrices, Claude, Navarro, and Ordóñez [1] recently showed how to build an
optimal prefix code such that the codewords’ lengths are non-decreasing when
they are arranged such that their reverses are in lexicographic order. Specifically,
they first build a normal Huffman code and then use the Kraft Inequality to build
another code with the same codeword lengths with the desired property. They
store an O(σL)-bit mapping between characters and their codewords, where
again σ is the alphabet size and L is the maximum length of any codeword,
which allows them to encode and decode codewords of length ℓ in time O(ℓ). (In
the wavelet matrices, they already spend O(ℓ) time in the operations associated
with encoding and decoding.)
Assume we are given a code produced by Claude et al.’s construction. We
reassign the codewords of the same length such that the lexicographic order
of the reversed codewords of that length is the same as that of their characters. This preserves the property that codeword lengths are non-decreasing with
their reverse lexicographic order. The positive aspect of this reassignment is
that all the information on the code can be represented in σ lg L bits as a sequence D = d1 , . . . , dσ , where di is the depth of the leaf encoding character i in
the code-tree T . We can then represent D using a wavelet tree [6], which uses
O(σ log L) bits and supports the following operations on D in time O(log L):
(1) access any D[i], which gives the length ℓ of the codeword of character i; (2)
compute r = rankℓ (D, i), which gives the number of occurrences of ℓ in D[1..i],
which if D[i] = ℓ gives the position (in reverse lexicographic order) of the leaf

6

Fariña et al.

representing character i among those of codeword length ℓ; and (3) compute
i = selectℓ (D, r), which gives the position in D of the rth occurrence of ℓ, or
which is the same, the character i corresponding to the rth codeword of length
ℓ (in reverse lexicographic order).
If, instead of O(log L) time, we wish to perform the operations in time O(ℓ),
where ℓ is the length of the codeword involved in the operation, we can simply
give the wavelet tree of D the same shape of the tree T . We can even perform
the operations in time O(log ℓ) by using a wavelet tree shaped like the trie for
the first σ codewords represented with Elias γ- or δ-codes [4, Observation 1].
The size stays O(σ log L) if we use compressed bitmaps at the nodes [6, 10].
We are left with two subproblems. For decoding the first character encoded
in a binary string, we need to find the length ℓ of the first codeword and the
lexicographic rank r of its reverse among the reversed codewords of that length,
since then we can decode i = selectℓ (D, r). For encoding a character i, we find its
length ℓ = D[i] and the lexicographic rank r = rankℓ (D, i) of its reverse among
the reversed codewords of length ℓ, and then we must find the codeword given
ℓ and r. We first present a solution that takes O(L log σ) = O(σ log L) further
bits7 and works in O(ℓ) time. We then present a solution that takes O 2ǫL
further bits and works in constant time.
Let T be the code-tree and, for each depth d between 0 and L, let nodes(d)
be the total number of nodes at depth d in T and let leaves(d) be the number of
leaves at depth d. Let v be a node other than the root, let u be v’s parent, let rv
be the lexicographic rank (counting from 1) of v’s reversed path label among all
the reversed path labels of nodes at v’s depth, and let ru be defined analogously
for u. Notice that since T is optimal it is strictly binary, so half the nodes at
each positive depth are left children and half are right children. Moreover, the
reversed path labels of all the left children at any depth are lexicographically
less than the reversed path labels of all the right children at the same depth (or,
indeed, at any depth). Finally, the reversed path labels of all the leaves at any
depth are lexicographically less than the reversed path labels of all the internal
nodes at that depth. It follows that
– v is u’s left child if and only if rv ≤ nodes(depth(v))/2,
– if v is u’s left child then rv = ru − leaves(depth(u)),
– if v is u’s right child then rv = ru − leaves(depth(u)) + nodes(depth(v))/2.
Of course, by rearranging terms we can also compute ru in terms of rv .
Suppose we store nodes(d) and leaves(d) for d between 0 and L. With the
three observations above, given a codeword of length ℓ, we can start at the root
and in O(ℓ) time descend in T until we reach the leaf v whose path label is that
codeword, then return its depth ℓ and the lexicographic rank r = rv of its reverse
path label among all the reversed path labels of nodes at that depth.8 Then we
compute i from ℓ and r as described, in further O(log ℓ) time. For encoding i,
7
8

Since the code tree has height L and σ leaves, it follows that L < σ.
This descent is conceptual; we do not have a concrete node v at each level, but we
do know rv .

Non-Canonical Preﬁx-Free Codes

7

we obtain as explained its length ℓ and the rank r = rv of its reversed codeword
among the reversed codewords of that length. Then we use the formulas to walk
up towards the root, finding in each step the rank ru of the parent u of v, and
determining if v is a left or right child of u. This yields the ℓ bits of the codeword
of i in reverse order (0 when v is a left child of u and 1 otherwise), in overall
time O(ℓ). This completes our first solution, which we evaluate experimentally
in Section 4.
Theorem 2. Suppose we are given an optimal prefix code in which the codewords’ lengths are non-decreasing when they are arranged such that their reverses
are in lexicographic order. We can store such a code in O(σ log L) bits — possibly after swapping characters’ codewords of the same length — where σ is the
alphabet size and L is the maximum codeword length, such that we can encode
and decode any character in O(ℓ) time, where ℓ is the corresponding codeword
length.
If we want to speed up descents, we can build a table that takes as arguments
a depth and several bits, and returns the difference between ru and rv for any
node u at that depth and its descendant v reached by following edges corresponding to those bits. Notice that this difference depends only on the bits and
the numbers of nodes and leaves at the intervening levels. If the table accepts
t bits as arguments at once, then it takes L2t log σ bits and we can descend in
O(L/t) time. Setting t = ǫL/2, and since L ≥ lg σ, we use O 2ǫL space and
descend from the root to any leaf in constant time.
Speeding up ascents is slightly more challenging. Consider all the path labels
of a particular length that end with a particular suffix of length t: the lexicographic ranks of their reverses form a consecutive interval. Therefore, we can
partition the nodes at any level by their r values, such that knowing which part
a node’s r value falls into tells us the last t bits of that node’s path label, and the
difference between that node’s r value and the r value of its ancestor at depth t
less. For each depth, we store the first r value in each interval in a predecessor
data structure, implemented as a trie with degree σ ǫ/3 ; since there are at most
2t intervals in the partition for each depth
and L ≥ lg σ, setting t = ǫL/2 again

we use a total of O L2ǫL/2σ ǫ/3 log σ ⊂ O 2ǫL bits and ascend from any leaf
to the root in constant time.
Finally, the operations on the wavelet tree can be made constant-time by
using a balanced multiary variant [3].
Theorem 3. Suppose we are given an optimal prefix code in which the codewords’ lengths are non-decreasing when they are arranged such that their reverses
are in lexicographic order. Let L be the maximum codeword length, so that it is
at most a constant times the size of the machine word. Then we can store such
a code in O σ log L + 2ǫL bits — possibly after swapping characters’ codewords
of the same length — where ǫ is any positive constant, such that we can encode
and decode any character in constant time.

8

Fariña et al.
Collection
EsWiki
EsInv
Indo

Length
(n)
200,000,000
300,000,000
120,000,000

Alphabet Entropy max code Entropy of level
size (σ) (H(P )) length(L) entries (H0 (D))
1,634,145
11.12
28
2.24
1,005,702
5.88
28
2.60
3,715,187
16.29
27
2.51

Table 1. Main statistics of the texts used.

4

Experiments

We have run experiments to compare the solution of Theorem 2 (referred to as
WMM in the sequel, for Wavelet Matrix Model) with the only previous encoding,
that is, the one used by Claude et al. [1] (denoted by TABLE). Note that our
codes are not canonical, so other solutions [5] do not apply.
Claude et al. [1] use for encoding a single table of σL bits storing the code
of each symbol, and thus they easily encode in constant time. For decoding,
they have tables separated by codeword length ℓ. In each such table, they store
the codewords of that length and the associated character, sorted by codeword.
This requires σ(L + lg σ) further bits, and permits decoding binary searching the
codeword found in the wavelet matrix. Since there are at most 2ℓ codewords of
length ℓ, the binary search takes time O(ℓ).
For the sequence D used in our WMM, we use binary Huffman-shaped wavelet
trees with plain bitmaps. The structures for supporting rank/select efficiently
require 37.5% space overhead, so the total space is 1.37 σH0 (D), where H0 (D) ≤
lg L is the per-symbol zero-order entropy of the sequence D. We also add a
small index to speed up select queries [11] (that is, decoding), which can be
parameterized with a sampling value that we set to {16, 32, 64, 128}. Finally, we
store the values leaves and nodes, which add an insignificant L2 bits in total.
We used a prefix of three datasets in http://lbd.udc.es/research/ECRPC.
The first one, EsWiki, contains a sequence of word identifiers generated by using
the Snowball algorithm to apply stemming to the Spanish Wikipedia. The second one, EsInv, contains a concatenation of differentially encoded inverted lists
extracted from a random sample of the Spanish Wikipedia. The third dataset,
Indo was created with the concatenation of the adjacency lists of Web graph
Indochina-2004 available at http://law.di.unimi.it/datasets.php. In Table 1 we provide some statistics about the datasets. We include the the number
of symbols in the dataset (n) and the alphabet size (σ). Assuming P is the relative frequency of the alphabet symbols, H(P ) indicates (in bits per symbol)
the empirical entropy of the sequence. This is approximates the average ℓ value
of queries. Finally we show L, the maximum code length, and the zero-order
entropy of the sequence D, H0 (D), in bits per symbol. The last column is then
a good approximation of the size of our Huffman-shaped wavelet tree for D.
Our test machine has a Intel(R) Core(tm) i7-3820@3.60GHz CPU (4 cores/8
siblings) and 64GB of DDR3 RAM. It runs Ubuntu Linux 12.04 (Kernel 3.2.0-99generic). The compiler used was g++ version 4.6.4 and we set compiler optimiza-

Non-Canonical Preﬁx-Free Codes

9

tion flags to −O9. All our experiments run in a single core and time measures
refer to CPU user-time.

Collection EsWiki
Compression
200

Collection EsWiki
Decompression
700

TABLE
WMM

150

[7.7;512.1]

ηs/symbol

ηs/symbol

500
100

400
300
200

50
[96.0;18.34]

[96.0;39.6]

100

0

0
0

10

20

30
40
50
60
70
Space (bits/alphabet symbol)

80

90

100

0

20

Collection EsInv
Compression
250

40
60
Space (bits/alphabet symbol)

80

100

Collection EsInv
Decompression
600

TABLE
WMM

[3.6;232.6]

TABLE
WMM

500

ηs/symbol

200
ηs/symbol

TABLE
WMM

[3.7;694.4]
600

[3.2;175.2]

150
100

[8.8;505.8]

[4.2;556.4]

400
300
200

50

100

[96.0;11.0]

[96.0;18.6]

0

0
0

10

20

30
40
50
60
70
Space (bits/alphabet symbol)

80

90

100

0

20

Collection Indo
Compression
150

80

100

Collection Indo
Decompression
600

TABLE
WMM

ηs/symbol

100

50

TABLE
WMM

[4.2;513.5]

500

[3.5;132.7]
ηs/symbol

40
60
Space (bits/alphabet symbol)

400
[8.7;300.5]

300
200

[96.0;45.9]

100

[96.0;8.8]
0

0
0

10

20

30

40

50

60

70

Space (bits/alphabet symbol)

80

90

100

0

20

40

60

80

100

Space (bits/alphabet symbol)

Fig. 1. Size of code representations versus either compression time (left) or decompression time (right). Time is measured in nanoseconds per symbol.

Figure 1 compares the space required by both code representations and their
compression and decompression times. As expected, the space per character of
our new code representation, WMM, is close to 1.37 H0 (D), whereas that of TABLE
is close to 2L + lg σ. This explains the large difference in space between both
representations, a factor of 23–30 times. For decoding we show the mild effect
of adding the structure that speeds up select queries.
The price of our representation is the encoding and decoding time. While the
TABLE approach encodes using a single table access, in 8–18 nanoseconds, our

10

Fariña et al.

representation needs 130–230, which is 10 to 21 times slower. For decoding, the
binary search performed by TABLE takes 20–50 nanoseconds, whereas our WMM
representation requires 510–700 in the slowest and smallest variant (i.e., 11–30
times slower). Our faster variants require 300–510 nanoseconds, which is still
several times slower.

5

Conclusions

A classical prefix code representation uses O(σL) bits, where σ is the alphabet
size and L the maximum codeword length, and encodes in constant time and
decodes a codeword of length ℓ in time O(ℓ). Canonical prefix codes can be represented in O(σ log L) bits, so that one can encode and decode in constant time
under reasonable assumptions. In this paper we have considered two families of
codes that cannot be put in canonical form. Alphabetic codes can be represented
in O(σ) bits, but encoding and decoding takes time O(ℓ). We gave an √
approx
imation that worsens the average code length by a factor of 1 + O 1/ log σ ,
but in exchange requires o(σ) bits and encodes and decodes in constant time.
We then consider a family of codes that are canonical when read right to left.
For those we obtain a representation using O(σ log L) bits and encoding and
decoding in
 time O(ℓ), or even in O(1) time under reasonable assumptions if we
use O 2ǫL further bits, for any constant ǫ > 0.
We have implemented the simple version of these right-to-left codes, which
are used for compressing wavelet matrices, and shown that our encodings are
significantly smaller than classical ones in practice (up to 30 times), albeit also
slower (up to 30 times). For the journal version of the paper, we plan to implement the wavelet tree of D with a shape that lets it operate in time O(ℓ)
or O(log ℓ), as used to prove Theorem 2; currently we gave it Huffman shape
in order to minimize space. Since there are generally more longer than shorter
codewords, the Huffman shape puts them higher in the wavelet tree of D, so
the longer codewords perform faster and the shorter codewords perform slower.
This is the opposite effect as the one sought in Theorem 2. Therefore, a faithful
implementation may lead to a slightly larger but also faster representation.
An interesting challenge is to find optimal alphabetic encodings that can
encode and decode faster than in time O(ℓ), even if they use more than O(σ)
bits of space. Extending our results to other non-canonical prefix codes is also
an interesting line of future work.

Acknowledgements
This research was carried out in part at University of A Coruña, Spain, while
the second author was visiting and the fifth author was a PhD student there.
It started at a StringMasters workshop at the Research Center on Information
and Communication Technologies (CITIC) of the university. The workshop was
partly funded by EU RISE project BIRDS (Bioinformatics and Information Retrieval Data Structures). The authors thank Nieves Brisaboa and Susana Ladra.

Non-Canonical Preﬁx-Free Codes

11

References
1. F. Claude, G. Navarro, and A. Ordóñez. The wavelet matrix: An eﬃcient wavelet
tree for large alphabets. Inf. Systems, 47:15–32, 2015.
2. W. Evans and D. G. Kirkpatrick. Restructuring ordered binary trees. J. Algorithms, 50:168–193, 2004.
3. P. Ferragina, G. Manzini, V. Mäkinen, and G. Navarro. Compressed representations of sequences and full-text indexes. ACM Trans. Alg., 3(2):article 20, 2007.
4. T. Gagie, M. He, J. I. Munro, and P. K. Nicholson. Finding frequent elements in
compressed 2d arrays and strings. In Proc. SPIRE, pages 295–300, 2011.
5. T. Gagie, G. Navarro, Y. Nekrich, and A. Ordóñez. Eﬃcient and compact representations of preﬁx codes. IEEE Trans. Inf. Theory, 61(9):4999–5011, 2015.
6. R. Grossi, A. Gupta, and J. S. Vitter. High-order entropy-compressed text indexes.
In Proc. SODA, pages 841–850, 2003.
7. A. Itai. Optimal alphabetic trees. SIAM J. Comp., 5:9–18, 1976.
8. L. G. Kraft. A device for quantizing, grouping, and coding amplitude modulated
pulses. M.Sc. thesis, EE Dept., MIT, 1949.
9. J. I. Munro and V. Raman. Succinct representation of balanced parentheses and
static trees. SIAM J. Comp., 31(3):762–776, 2001.
10. G. Navarro. Wavelet trees for all. J. Discr. Alg., 25:2–20, 2014.
11. G. Navarro and E. Providel. Fast, small, simple rank/select on bitmaps. In Proc.
SEA, LNCS 7276, pages 295–306, 2012.
12. M. Pǎtraşcu. Succincter. In Proc. FOCS, pages 305–313, 2008.
13. E. S. Schwartz and B. Kallick. Generating a canonical preﬁx encoding. Comm. of
the ACM, 7:166–169, 1964.
14. R. L. Wessner. Optimal alphabetic search trees with restricted maximal height.
Inf. Proc. Letters, 4:90–94, 1976.

