#  Bounds and Algorithms for Alphabetic Codes and Binary Search Trees

R. Bruno  R. De Prisco  A. De Santis  and U. Vaccaro The authors are with the
Dipartimento di Informatica, Università di Salerno, Fisciano (SA), Italy
(email: {rbruno, robdep, ads, uvaccaro}@unisa.it). This work was partially
supported by project SERICS (PE00000014) under the NRRP MUR program funded by
the EU-NGEU.

###### Abstract

Alphabetic codes and binary search trees are combinatorial structures that
abstract search procedures in ordered sets endowed with probability
distributions. In this paper, we design new linear-time algorithms to
construct alphabetic codes, and we show that the obtained codes are not too
far from being optimal. Moreover, we exploit our results on alphabetic codes
to provide new bounds on the average cost of optimal binary search trees. Our
results improve on the best-known bounds on the average cost of optimal binary
search trees present in the literature.

Key words: Alphabetic codes, searching, variable-length codes, binary search
trees, data structures.

##  I Introduction

The Theory of Variable-Length Codes and Search Theory are strongly
intertwined. In fact, any search procedure that identifies objects in a given
space, by sequentially executing appropriate tests naturally defines a
variable-length encoding of elements in the space. To wit, one can encode each
possible test outcome with a different symbol of a finite alphabet, and the
concatenation of the (encoded) test outcomes, leading to the identification of
an object $x$, gives a bona fide encoding of $x$, for any $x$ in the search
space.

More specifically, binary alphabetic codes and binary search trees are basic
combinatorial structures that naturally arise in Search Theory [2, 3, 15]. In
fact, alphabetic codes are equivalent to search procedures (in ordered sets)
that operate through comparison queries with binary results, while binary
search trees correspond to search procedures that use comparison queries whose
outcome is ternary.

Alphabetical codes have been extensively studied in the Information Theory
community (see, e.g., [9, 11, 12, 13, 14, 25, 28, 29] and references therein
quoted). Equally, binary search trees have been studied in the Computer
Science community, because of the important application scenarios where they
appear (see, e.g., [18, 21, 22, 26] and references therein quoted). The two
survey papers [1, 24] contain many more references.

It is well known that optimal binary alphabetic codes (i.e., with minimum
average length) can be constructed in time $O(m\log m)$ [13], where $m$ is the
number of codewords, and that optimal binary search trees (again, with minimum
possible average path length) can be constructed in time $O(n^{2})$ [18],
where $n$ is the number of nodes in the tree. Most of the research activity
that followed [13] and [18] has concentrated on the following issues:
constructing close-to-optimal binary alphabetic codes (equivalently, close-to-
optimal binary search trees) via linear-time algorithms, and providing
explicit upper bounds on the cost (average path length) of the constructed
objects. In this paper, we provide novel upper bounds on the cost of optimal
binary alphabetic codes and optimal binary search trees. Our bounds improve on
the best bounds known in the literature. Our new results are obtained by
accurately analyzing novel linear-time construction algorithms.

##  II Preliminaries

Let $S=\\{s_{1},\ldots,s_{m}\\}$ be a set of symbols, ordered according to a
given total order relation $\prec$, that is, for which it holds that
$s_{1}\prec\dots\prec s_{m}$. A binary alphabetical code is an order-
preserving mapping $w:\\{s_{1},\ldots,s_{m}\\}\mapsto\\{0,1\\}^{+}$, where the
order relation on the set of all binary strings $\\{0,1\\}^{+}$ is the
standard alphabetical order. We denote by $C$ the set of codewords
$C=\\{w(s):s\in S\\}$, and by $\phi=(\phi_{1},\ldots,\phi_{m})$ the
probability distribution on the symbols in $S$, that is, $\phi_{i}$ is the
probability of the $i^{th}$ symbol $s_{i}$. For each $s_{i}\in S$ we denote by
$w(s_{i})$ the codeword associated to $s_{i}$, and by $\ell(w(s_{i}))$, or
simply by $\ell_{i}$, the length of $w(s_{i})$.

Given an alphabetic code $C$, an order-preserving mapping
$w:s\in\\{s_{1},\ldots,s_{m}\\}\mapsto w(s)\in\\{0,1\\}^{+}$, and a
probability distribution $\phi=(\phi_{1},\ldots,\phi_{m})$ on $S$, we denote
the average code length of the code $C$ by

$\mathbb{E}[C]=\sum_{i=1}^{m}\phi_{i}\,\ell_{i}.$

In the following sections, we will occasionally see an alphabetic code as a
binary tree $T$ where each edge is labeled either by bit 0 or 1, and each leaf
of the tree corresponds to a different symbol $s\in S$. Sometimes, it will be
convenient to identify an arbitrary leaf $s_{i}$ of the tree $T$ with the
probability $\phi_{i}$ of the symbol $s_{i}\in S$ that is associated to the
leaf. The codeword $w(s)$ for the symbol $s\in S$ is equal to the
concatenation of all the 0’s and 1’s in the path from the root of $T$ to the
leaf associated with $s$. The order-preserving property of alphabetic codes
implies that the leaves of $T$, read from the leftmost leaf to the rightmost
one, appear in the order $s_{1}\prec\dots\prec s_{m}$. As said before,
alphabetic codes, in their binary tree representation, naturally correspond to
a search procedure that makes use of comparison queries with binary outcomes.

Binary search trees represent, in a sense, a generalization of binary trees
associated to alphabetic codes, since the former can take into account both
successful and unsuccessful searches. More precisely, any comparison-based
search algorithm on an ordered list of elements $x_{1}\prec\dots\prec x_{n}$
can be represented as a binary search tree, with an internal node associated
to each element $x_{i}$ and a leaf associated to each of the $n+1$ gaps
$(-\infty,x_{1}),(x_{1},x_{2}),\dots,(x_{n-1},x_{n}),(x_{n},+\infty)$ among
the $x_{i}$’s. Let $x$ be an element that we want to seek for in the list.
Each internal node represents a comparison operation between $x$ and the
content $x_{i}$ of the node. The outcome of the comparison can be either
$x\prec x_{i}$, $x=x_{i}$ or $x\succ x_{i}$ (see Section 6.2 of [18]). Thus,
the internal nodes correspond to successful searches, and the leaves to the
unsuccessful ones.

The cost of a binary search tree $T$ is defined as the average number of
questions needed to identify an arbitrary input element $x$. More precisely,
given a probability distribution
$\sigma=(\sigma_{1},\dots,\sigma_{2\,n+1})=(p_{0},q_{1},p_{2},\dots,q_{n},p_{n})$,
where the probabilities of successful searches are $q_{1},\dots,q_{n}$, and
$p_{0},\dots,p_{n}$ are the probabilities of unsuccessful searches, the cost
of the binary search tree $T$, for the probability distribution $\sigma$, is
equal to

$\mathbb{E}[T]=\sum_{i=1}^{n}q_{i}\,\ell(q_{i})+\sum_{i=0}^{n}p_{i}\,\ell(p_{i}),$
(1)

where $\ell(q_{i})$ denotes the level of $q_{i}$ in the tree, i.e., the number
of nodes from the root of $T$ to $q_{i}$, whereas $\ell(p_{i})$ is the level
of the parent of $p_{i}$ in the tree [18]. We stipulate that the level of the
root of $T$ is equal to 1.

Note that when the probabilities of successful searches, $q_{1},\dots,q_{n}$,
are all 0’s, the problem of finding an optimal binary search tree for the
probability distribution $\sigma$ is equivalent to the problem of finding an
optimal alphabetic code for the probability distribution
$\phi=(p_{0},\dots,p_{n})$.

##  III Our contributions in perspective

Alphabetic codes have been extensively studied. In this section, we limit
ourselves to discussing the work that is most closely related to our findings.
We will present our results in Section IV and Section V.

In their classic paper [9], Gilbert and Moore designed a $O(m^{3})$ time
dynamic programming algorithm for the construction of optimal alphabetic codes
(that is, of minimum average length), where $m$ is the number of symbols. Hu
and Tucker [13] improved Gilbert and Moore’s result by providing an algorithm
of time complexity $O(m\log m)$. Subsequent studies have mostly concentrated
on the problem of giving linear time algorithms for the construction of almost
optimal alphabetic codes and in providing explicit upper bounds on the average
length of the constructed codes. It is clear that the derived bounds are upper
bounds on the length of optimal alphabetic codes, as well.

Gilbert and Moore [9] gave a linear time algorithm to construct an alphabetic
code for a set of symbols $S$, with associated probability distribution
$\phi$, whose average length is less than $H(\phi)+2$. Here,
$H(\phi)=-\sum_{i=1}^{m}\phi_{i}\log\phi_{i}$ is the Shannon entropy of the
distribution $\phi$. Since the average length of any alphabetic code is lower
bounded by $H(\phi)$, one gets that Gilbert and Moore’s codes are at most two
bits away from the optimum. We note that Gilbert and Moore’s upper bound
cannot be improved, unless one has some additional information on the
probability distribution $\phi$. In fact, one can see that the average length
of the best alphabetical code for a set of three symbols $s_{1}\prec
s_{2}\prec s_{3}$, with probability distribution
$\phi=(\epsilon,1-2\epsilon,\epsilon)$, is equal to $2-\epsilon$. On the other
hand, $H(\phi)$ can be arbitrarily small. Remarkably, the average length of
the Huffman code for the same $\phi=(\epsilon,1-2\epsilon,\epsilon)$ is equal
to $1+2\epsilon$, thus there can be a difference of (approximatively) 1 bit
between the average length of the best alphabetical code and that of the
Huffman code, for the same $\phi$. The general characterization of the “shape”
of worst-case probability distributions for alphabetical codes is given in the
paper [16].

Horibe [12] provided a better upper bound than the $H(\phi)+2$ bound of
Gilbert and Moore, by giving an algorithm to construct alphabetic codes of
average length less than

$H(\phi)+2-(m+2)\phi_{\min},$ (2)

where $\phi_{\min}$ is the smallest probability of $\phi$.

Nakatsu [25] claimed a different upper bound on the minimum average length of
alphabetical codes. Successively, Sheinwald [28] pointed out a gap in the
analysis carried out in [25].

Yeung [29] also improved the $H(\phi)+2$ bound of Gilbert and Moore, by
proving the following upper bound on the average length $L_{\min}$ of optimal
binary alphabetic codes:

$\displaystyle L_{\min}$ $\displaystyle\leq
H(\phi)+2-\phi_{1}\left(2-\log\phi_{1}-\lceil-\log\phi_{1}\rceil\right)$
$\displaystyle\quad-\phi_{m}\left(2-\log\phi_{m}-\lceil-\log\phi_{m}\rceil\right)$
(3) $\displaystyle\leq H(\phi)+2-\phi_{1}-\phi_{m},$ (4)

where $\phi_{1}$ and $\phi_{m}$ are the probabilities of the first and the
last symbol of the ordered set of symbols $S$, respectively. In general, the
bounds (2) and (III) are not comparable, in the sense that there are
probability distributions $\phi$ for which (2) is better than (III), and
probability distributions $\phi$ for which the opposite holds.

A new upper bound on the average length of optimal alphabetic codes was
recently given by Dagan  et al. [4]. Their bound claims that

$\displaystyle L_{\min}$ $\displaystyle\leq
H(\phi)+2-\left(\phi_{1}+\phi_{m}+\sum_{i=1}^{m-1}\min(\phi_{i},\phi_{i+1})\right)$
(5)
$\displaystyle=H(\phi)+1-\frac{\phi_{1}+\phi_{m}}{2}+\frac{1}{2}\sum_{i=1}^{m-1}|\phi_{i}-\phi_{i+1}|.$
(6)

While the upper bound (5) is correct, in Remark 1 (which will be given in
Section IV) we point out an unresolved issue in the analysis given in [4] that
leads to (5).

Our results for alphabetic codes consist of a series of improvements to the
upper bound (5) of Dagan  et al. on the average length of optimal alphabetic
codes $L_{\min}$. For instance, we will prove that

$\displaystyle L_{\min}$ $\displaystyle\leq
H(\phi)+2-\phi_{1}\,(2-\log_{2}\phi_{1}-\lceil-\log_{2}\phi_{1}\rceil)$
$\displaystyle\quad-\phi_{m}\,(2-\log_{2}\phi_{m}-\lceil-\log_{2}\phi_{m}\rceil)$
$\displaystyle\quad-\sum_{i=1}^{m-1}\min(\phi_{i},\phi_{i+1}).$ (7)

More importantly, we design a $O(m)$ time algorithm to construct alphabetic
codes of average length at most the right-hand side of (7). The $O(m)$ time
algorithm that we design will be instrumental in deriving the results on
binary search trees of Section V. We derive further improvements to (5) in
Section IV.

In Section V we turn our attention to binary search trees. Binary search trees
have been extensively investigated (e.g., [5, 21, 22, 26]). Knuth [17] gave an
$O(n^{2})$ time and $O(n^{2})$ space complexity algorithm to construct an
optimum binary search tree, i.e., a binary search tree with minimum cost, as
defined in (1). The quadratic complexity of the algorithm designed in [17] may
be prohibitive in many applications, as Mehlhorn remarked in [21]. Therefore,
Mehlhorn [21] proposed a linear time algorithm to construct a binary search
tree for an arbitrary probability distribution

$\sigma=(\sigma_{1},\ldots,\sigma_{2n+1})=(p_{0},q_{1},p_{1},q_{2},\ldots,q_{n},p_{n}),$

where the $p_{i}$’s are probabilities of unsuccessful searches and the
$q_{i}$’s are probabilities of successful searches, whose cost is not greater
than

$H(\sigma)+1+\sum_{i=0}^{n}p_{i}.$ (8)

De Prisco and De Santis [5] proposed a different linear time algorithm for
constructing binary search trees and they claimed an upper bound on their cost
given by

$H(\sigma)+1-p_{0}-p_{n}+p_{\max},$ (9)

where $p_{\max}$ is the maximum value among $p_{0},\dots,p_{n}$.
Unfortunately, the bound (9) does not hold in general, as pointed out in [4,
19].

In Section V we correct the analysis of the algorithm derived in [5], and we
explicitly estimate the cost of the produced binary search trees. The simplest
of our bounds states that the cost $\mathbb{E}[T]$ of the tree $T$ constructed
by the algorithm of [5] is upper bounded by

$\displaystyle\mathbb{E}[T]$ $\displaystyle\leq
H(\sigma)+1+\sum_{i=0}^{n}p_{i}-\Biggl{(}p_{0}+p_{n}+\sum_{i=0}^{n-1}\min(p_{i},q_{i+1})$
$\displaystyle\quad+\sum_{i=1}^{n}\min(q_{i},p_{i})+\sum_{i=0}^{n-1}\min(p_{i},p_{i+1})\Biggr{)}$
$\displaystyle=H(\sigma)+1+\sum_{i=0}^{n}p_{i}-\Biggl{(}1-\sum_{i=0}^{n-1}\frac{|p_{i}-q_{i+1}|}{2}$
$\displaystyle\quad-\sum_{i=1}^{n}\frac{|q_{i}-p_{i}|}{2}+\sum_{i=0}^{n}p_{i}-\sum_{i=0}^{n-1}\frac{|p_{i}-p_{i+1}|}{2}\Biggr{)}.$
(10)

It is apparent that (10) significantly improves the Melhorn bound (8). We
derive additional and better upper bounds than (10) in Section V. Clearly, our
results also represent upper limits on the cost of optimal binary search
trees. The new bounds on the cost of binary search trees are crucially
dependent on the new results on alphabetic codes that we derive in Section IV.

##  IV On Alphabetic codes

We first develop some useful machinery. Given a probability distribution
$\phi=(\phi_{1},\dots,\phi_{m})$, let us denote with

$\nu=(\nu_{1},\dots,\nu_{2\,m-1})=(\phi_{1},0,\phi_{2},\dots,0,\phi_{m})$

its partially extended distribution, and with

$\nu\,^{\prime}=(\nu_{1},\dots,\nu_{2\,m+1})=(0,\phi_{1},0,\phi_{2},\dots,0,\phi_{m},0)$

its fully extended distribution.

We also need some auxiliary tools and results from Nakatsu [25].

######  Definition 1.

[25] Let $L=\langle\ell_{1},\dots,\ell_{m}\rangle$ be a list of positive
integers. For a binary fraction $x$ and integer $i\geq 1$, let the function
trunc be defined as

$\mbox{\tt trunc}(i,x)=\frac{\lfloor 2^{i}\,x\rfloor}{2^{i}}$ (11)

that is, $\mbox{\tt trunc}(i,x)$ is the fraction obtained by considering only
the first $i$ bits in the binary representation of $x$.

Let $\alpha_{i}=\min(\ell_{i-1},\ell_{i})$, for $i=2,\dots,m$. The recursive
function sum is defined as

$\mbox{\tt sum}(L,i)=\begin{cases}\mbox{\tt trunc}(\alpha_{i},\mbox{\tt
sum}(L,i-1))+2^{-\alpha_{i}}&\text{if }i\geq 2,\\\ 0&\text{if
}i=1.\end{cases}$ (12)

To better comprehend the functions trunc and sum defined above, let us work
out a small numerical example. Let $L=\\{4,2,3,3\\}$ be a list of integers. We
have $\alpha_{2}=\min(4,2)=2$, $\alpha_{3}=\min(2,3)=2$ and
$\alpha_{4}=\min(3,3)=3$. Now, we can compute the value of sum for $L$. By
definition $\mbox{\tt sum}(L,1)=0$. It holds that

$\displaystyle\mbox{\tt sum}(L,2)$ $\displaystyle=\mbox{\tt
trunc}(\alpha_{2},\mbox{\tt sum}(L,1))+2^{-\alpha_{2}}$
$\displaystyle=\mbox{\tt trunc}(2,0)+2^{-2}=2^{-2},$

since $\mbox{\tt trunc}(2,0)$ takes the value whose binary expansion is the
same of the first 2 bits of the binary representation of $0$ (that are all
$0$’s). Similarly, we have

$\displaystyle\mbox{\tt sum}(L,3)$ $\displaystyle=\mbox{\tt
trunc}(\alpha_{3},\mbox{\tt sum}(L,2))+2^{-\alpha_{3}}$
$\displaystyle=\mbox{\tt trunc}(2,2^{-2})+2^{-2}=2^{-2}+2^{-2}=2^{-1},$

since $\mbox{\tt trunc}(2,2^{-2})$ takes the value whose binary expansion is
the same of the first 2 bits of the binary representation of
$2^{-2}=\frac{1}{4}$, which correspond to the same value $2^{-2}$ since the
binary representation of $\frac{1}{4}$ is $0\,\frac{1}{2}+1\,\frac{1}{4}$.
Finally, we have

$\displaystyle\mbox{\tt sum}(L,4)$ $\displaystyle=\mbox{\tt
trunc}(\alpha_{4},\mbox{\tt sum}(L,3))+2^{-\alpha_{4}}$
$\displaystyle=\mbox{\tt trunc}(3,2^{-1})+2^{-3}=2^{-1}+2^{-3}.$

Intuitively, when $\mbox{\tt sum}(L,i)<1$, one can see that $\mbox{\tt
sum}(L,i)$ enjoys the property of being the smallest value strictly greater
than $\mbox{\tt sum}(L,i-1)$ that differs from $\mbox{\tt sum}(L,i-1)$ on at
least the $\alpha_{i}^{th}$ bit of their binary expansion, where
$\alpha_{i}=\min(\ell_{i-1},\ell_{i})$. Thus, by denoting with $w_{i}$ the
first $\ell_{i}$ bits of the binary expansion of $\mbox{\tt sum}(L,i)$ and
with $w_{i-1}$ the first $\ell_{i-1}$ bits of the binary expansion of
$\mbox{\tt sum}(L,i-1)$, the property ensures that $w_{i-1}$ comes before
$w_{i}$ in the standard alphabetic order among binary sequences. Moreover,
neither $w_{i}$ is a prefix of $w_{i-1}$ nor $w_{i-1}$ is a prefix of $w_{i}$.

Nakatsu [25] proved the following important result (an equivalent result was
independently given by Yeung [29]).

######  Theorem 1.

[25] Let $L=\langle\ell_{1},\dots,\ell_{m}\rangle$ be a list of integers,
associated with the ordered symbols $s_{1}\prec\dots\prec s_{m}$. There exists
an alphabetical code for which the codeword assigned to symbol $s_{i}$ has
length $\ell_{i}$, for each $i=1,\ldots,m$, if and only if $\mbox{\tt
sum}(L,m)<1$.

Nakatsu proved the sufficient part of Theorem 1 by showing that the first
$\ell_{i}$ digits of the binary representation of $\mbox{\tt sum}(L,i)$, for
$i=1,\ldots,m$, (under the hypothesis that $\mbox{\tt sum}(L,m)<1$) give the
alphabetic code for the ordered set of symbols $s_{1}\prec\dots\prec s_{m}$.
In the following Lemma 2 we show that an alphabetic code, whose existence is
guaranteed by Theorem 1, can be constructed in time $O(m)$. We first need the
following technical result, whose proof is given in Appendix A.

######  Lemma 1.

Let $L=\langle\ell_{1},\dots,\ell_{m}\rangle$ be a list of integers such that
$\mbox{\tt sum}(L,m)<1$, let $i$, $j$ be integers such that $1\leq i<j\leq m$,
and let $\\{\mbox{\tt sum}(L,i),\mbox{\tt sum}(L,i+1),\dots,\mbox{\tt
sum}(L,j)\\}$ be a subset of consecutive elements of $\\{\mbox{\tt
sum}(L,1),\dots,\mbox{\tt sum}(L,m)\\}$. For each $k=i,\dots,j-1$, let $t_{k}$
be the _smallest_ integer $s$ for which the binary expansion of $\mbox{\tt
sum}(L,k)$ differs from the binary expansion of $\mbox{\tt sum}(L,k+1)$ on the
$s^{th}$ bit, and define $t_{ij}=\min_{i\leq k<j}t_{k}$. Then, it holds that:

  1. 1.

$t_{ij}=\lceil-\log_{2}(\mbox{\tt sum}(L,i)\oplus\mbox{\tt sum}(L,j))\rceil,$
(13)

where $\mbox{\tt sum}(L,i)\oplus\mbox{\tt sum}(L,j)$ is the _numerical_ value
whose binary expansion is the result of the XOR operation between the binary
expansions of $\mbox{\tt sum}(L,i)$ and $\mbox{\tt sum}(L,j)$, and

  2. 2.

there exists an index $z\in\\{i,\ldots,j-1\\}$ such that $\mbox{\tt
sum}(L,z)<\mbox{\tt trunc}(t_{ij},\mbox{\tt sum}(L,i))+2^{-t_{ij}}$ _and_
$\mbox{\tt sum}(L,z+1)\geq\mbox{\tt trunc}(t_{ij},\mbox{\tt
sum}(L,i))+2^{-t_{ij}}.$

For completeness, we recall that the XOR $\mbox{\tt sum}(L,i)\oplus\mbox{\tt
sum}(L,j)$ is easily computable, in most programming languages, with a single
built-in instruction. Armed with Lemma 1, we now prove our constructive
result. To avoid overburdening the notation, when the pair of integers $(i,j)$
in (13) is clear from the context, we will simply denote $t_{ij}$ with $t$.

######  Lemma 2.

Let $L=\langle\ell_{1},\dots,\ell_{m}\rangle$ be a list of integers,
associated with the ordered symbols $s_{1}\prec\dots\prec s_{m}$. If
$\mbox{\tt sum}(L,m)<1$, then one can construct in $O(m)$ time an alphabetic
code $C$ for which the codeword assigned to symbol $s_{i}$ has length at most
$\min(\ell_{i},m-1)$, for each $i=1,\dots,m.$

###### Proof.

To prove the lemma, we design a $O(m)$ time algorithm to construct the binary
tree associated with the code $C$, that is, the binary tree whose root-to-
leaves paths give the codewords of $C$.

It is useful to recall that Nakatsu [25, Theorem 1] showed that the code
constructed by taking the first $\ell_{i}$ bits of the binary expansion of
$\mbox{\tt sum}(L,i)$ as the codeword associated to the symbol $s_{i}$, for
each $i=1,\dots,m$, is alphabetic. Our algorithm constructs the binary code
tree by using a subset of the first $\ell_{i}$ bits of the binary expansion of
$\mbox{\tt sum}(L,i)$, for each $i=1,\dots,m$. The algorithm builds the
desired tree in a top-down fashion, proceeding by iterated bisections of the
set

${\cal S}=\\{\mbox{\tt sum}(L,1),\mbox{\tt sum}(L,2),\ldots,\mbox{\tt
sum}(L,m)\\}.$ (14)

Initially, the root of the tree is associated to the whole set ${\cal S}$. To
perform the first bisection, we proceed as follows.

For each $a=1,\dots,m-1$, let $t_{a}$ be the smallest integer for which the
binary expansions of the pair $\mbox{\tt sum}(L,a)$ and $\mbox{\tt
sum}(L,a+1)$ differ on the $t_{a}^{th}$ bit, and let $t=t_{1m}=\min_{1\leq
a<m}t_{a}$. From Lemma 1, we have that $t=\lceil-\log_{2}(\mbox{\tt
sum}(L,1)\oplus\mbox{\tt sum}(L,m))\rceil$. We now compute the index
$k\in\\{1,\ldots,m-1\\}$ for which it holds that

$\mbox{\tt sum}(L,k)<\mbox{\tt trunc}(t,\mbox{\tt sum}(L,1))+2^{-t}$ (15)

and

$\mbox{\tt sum}(L,k+1)\geq\mbox{\tt trunc}(t,\mbox{\tt sum}(L,1))+2^{-t}.$
(16)

We associate the left child of the root to the subset

$\\{\mbox{\tt sum}(L,1),\ldots,\mbox{\tt sum}(L,k)\\},$

and the right child of the root to the subset

$\\{\mbox{\tt sum}(L,k+1),\ldots,\mbox{\tt sum}(L,m)\\}.$

By 2) of Lemma 1, both $\\{\mbox{\tt sum}(L,1),\ldots,\mbox{\tt sum}(L,k)\\}$
and $\\{\mbox{\tt sum}(L,k+1),\ldots,\mbox{\tt sum}(L,m)\\}$ are non empty.
The subset $\\{\mbox{\tt sum}(L,1),\ldots,\mbox{\tt sum}(L,k)\\}$ represents
the nodes that are in the left subtree of the root. Moreover, by the
definition of the function trunc and from (15) and (16), each numerical value
$\mbox{\tt sum}(\cdot,\cdot)\in\\{\mbox{\tt sum}(L,1),\ldots,\mbox{\tt
sum}(L,k)\\}$ has a binary expansion with $0$ in the $t^{th}$ position.
Analogously, the subset $\\{\mbox{\tt sum}(L,k+1),\ldots,\mbox{\tt
sum}(L,m)\\}$ represents the nodes that are in the right subtree of the root
and each value $\mbox{\tt sum}(\cdot,\cdot)\in\\{\mbox{\tt
sum}(L,k+1),\ldots,\mbox{\tt sum}(L,m)\\}$ has a binary expansion with $1$ in
the $t^{th}$ position. The algorithm proceeds recursively on the left subset
$\\{\mbox{\tt sum}(L,1),\ldots,\mbox{\tt sum}(L,k)\\}$ and right subset
$\\{\mbox{\tt sum}(L,k+1),\ldots,\mbox{\tt sum}(L,m)\\}$. It stops when the
cardinality of the subset is equal to $1$, in such a case we have just a leaf,
or when it is equal to $2$, where we have a final subtree with two sibling
leaves. The complete pseudo-code of the algorithm is presented in Algorithm 2.

1 if  _$i=j$_ then

2 Construct the leaf $v$ associated with symbol $s_{i}$.

3 return $v$

4else if  _$i+1=j$_ then

5 Construct a node $v$ whose left child is the leaf $s_{i}$ and whose right
child is the leaf $s_{j}$.

6 return $v$

7else

8 $t=\lceil-\log_{2}(\mbox{\tt sum}(L,i)\oplus\mbox{\tt sum}(L,j))\rceil$

9 Let $k\in\\{i,\ldots,j-1\\}$ be the index such that $\mbox{\tt
sum}(L,k)<\mbox{\tt trunc}(t,\mbox{\tt sum}(L,i))+2^{-t}$ and $\mbox{\tt
sum}(L,k+1)\geq\mbox{\tt trunc}(t,\mbox{\tt sum}(L,i))+2^{-t}$.

10 $l$ = SubTree($i$,$k$)

11 $r$ = SubTree($k+1$,$j$)

12 Construct a node $v$ whose left child is the tree $l$ and whose right child
is the tree $r$.

13 return $v$

Algorithm 1 SubTree($i$,$j$)

Input: The list of lengths $L=\langle\ell_{1},\dots,\ell_{m}\rangle$

Output: An alphabetic code tree with codeword lengths
$\ell^{\prime}_{i}\leq\min(\ell_{i},m-1)$, for each $i=1,\dots,m.$

1 Compute $\mbox{\tt sum}(L,i)$ for each $i=1,\dots,n$.

2return SubTree(1,$m$)

Algorithm 2 ConstructTree($L$)

The procedure presented above for the construction of the binary tree can be
implemented to work in $O(m)$ time and space, by exploiting a technique
devised in [7]. In fact, the crucial operation in Line 9 of Algorithm 1 can be
implemented in $O(\log\min(s,j-s))$ time, where $s=k-i+1$, by first checking
if $\mbox{\tt sum}(L,r)<\mbox{\tt trunc}(t,\mbox{\tt sum}(L,i))+2^{-t}$ with
$r=\lceil(j-1+i)/2\rceil$ to discover whether the index $k$ belongs to
$\\{i,\dots,r-1\\}$ or to $\\{r,\dots,j-1\\}$. Successively, we use an
exponential search to find the interval in which the value $k$ is located,
and, finally, a binary search in such interval to find $k$. More precisely, we
proceed in the following way: if $k\in\\{i,\dots,r-1\\}$, we check the
validity of the inequality $\mbox{\tt sum}(L,i+2^{v})<\mbox{\tt
trunc}(t,\mbox{\tt sum}(L,i))+2^{-t}$ in Line 9 for increasing values
$v=0,1,2,3,\ldots,$ till we find the first value of $v$ that satisfies the
inequality $\mbox{\tt sum}(L,i+2^{v})\geq\mbox{\tt trunc}(t,\mbox{\tt
sum}(L,i))+2^{-t}$. After $\log s$ step we shall have located the value of $k$
we seek within an interval of size at most $2s$. A successive binary search
will exactly determine the value of $k$. All together, this procedure takes
$O(\log s)$ steps. Similarly, if $k\in\\{r,\dots,j-1\\}$, we apply the same
procedure with the caveat that we start the exponential search from the right-
end of the interval $\\{r,\dots,j-1\\}$. In this way, the procedure will take
$O(\log(j-s))$ time. Putting the two cases together, the whole operation takes
$O(\log\min(s,j-s))$ time.

Therefore, by denoting with $T(m)$ the number of operations performed by the
algorithm to construct the tree with $m$ leaves, because of Line 9, 10, and
11, we have that

$\displaystyle T(m)$ $\displaystyle\leq\max_{1\leq k\leq m-1}\\{T(m-k)+T(k)$
$\displaystyle\quad+\alpha\log_{2}\min(k,m-k)+\beta\\}$
$\displaystyle=\max_{1\leq k\leq m/2}\\{T(m-k)+T(k)+\alpha\log_{2}k+\beta\\},$
(17)

for suitable constant values $\alpha$ and $\beta$.

One can see that the right-hand-side of (17) grows at most linearly with $m$
(e.g., Theorem 11, p. 185 of [23]); therefore the algorithm ConstructTree($L$)
requires total time $O(m)$.

The tree produced by algorithm ConstructTree($L$) is alphabetic by
construction since the recursive bisections of the set

$\\{\mbox{\tt sum}(L,1),\mbox{\tt sum}(L,2),\ldots,\mbox{\tt sum}(L,m)\\}$

preserves the symbol order $s_{1}\prec\dots\prec s_{m}$. What is left to prove
is that the procedure constructs a tree whose root-to-leaves paths (i.e.,
codewords) have length $\ell^{\prime}_{a}\leq\min(\ell_{a},m-1)$, for each
$a=1,\dots,m$.

The inequality $\ell^{\prime}_{a}\leq m-1$ holds because the constructed
binary tree is full, that is, each node internal node of the tree has two
children. This is due to 2) of Lemma 1 and Line 9,10 and 11 of Algorithm 1.

We now prove that $\ell^{\prime}_{a}\leq\ell_{a}$, for each $a=1,\dots,m$.
Consider first the cases $a\in\\{2,\dots,m-1\\}$. By definition of sum, we
have that

$\mbox{\tt sum}(L,a)=\mbox{\tt trunc}(\alpha_{a},\mbox{\tt
sum}(L,a-1))+2^{-\alpha_{a}},$ (18)

where $\alpha_{a}=\min(\ell_{a-1},\ell_{a})$. Therefore, since $\mbox{\tt
trunc}(b,x)$ is the binary fraction one gets by considering only the first $b$
bits of the binary expression of $x$ (cfr. (11)), from (18) one obtains that
the binary expansion of $\mbox{\tt sum}(L,a)$ differs from the binary
expansion of $\mbox{\tt sum}(L,a-1)$ on at least the $\alpha_{a}^{th}$ bit.
Because of Line 9,10 and 11 of Algorithm 1, this implies that after at most
$\alpha_{a}$ bisection steps the value of $\mbox{\tt sum}(L,a)$ can no longer
be in the same subset of $\mbox{\tt sum}(L,a-1)$. By symmetry, after at most
$\alpha_{a+1}$ steps the value $\mbox{\tt sum}(L,a)$ can no longer be in the
same subset of $\mbox{\tt sum}(L,a+1)$. All together, after at most
$\max(\alpha_{a},\alpha_{a+1})$ bisection steps the value $\mbox{\tt
sum}(L,a)$ does not belong to the same subset of either $\mbox{\tt
sum}(L,a-1)$ or $\mbox{\tt sum}(L,a+1)$, that is, $\mbox{\tt sum}(L,a)$ must
correspond to a leaf in the code-tree. Therefore, the corresponding root-to-
leaves path has length

$\displaystyle\ell^{\prime}_{a}$
$\displaystyle\leq\max(\alpha_{a},\alpha_{a+1})=\max(\min(\ell_{a-1},\ell_{a}),\min(\ell_{a},\ell_{a+1}))$
$\displaystyle\leq\ell_{a}.$

Analogously, for $a=1$ it holds that

$\ell^{\prime}_{1}\leq\alpha_{2}=\min(\ell_{1},\ell_{2})\leq\ell_{1},$

and for $a=m$ it holds that

$\ell^{\prime}_{m}\leq\alpha_{m}=\min(\ell_{m-1},\ell_{m})\leq\ell_{m}.$

∎

Figure 1 shows the alphabetic trees produced on the list of lengths $L=\langle
6,6,5,2,9,9,8,6,3,2\rangle$, by taking the first $\ell_{i}$ bits of the binary
expansion of $\mbox{\tt sum}(L,i)$ (as done by Nakatsu [25]) and by the
application of our linear time algorithm, respectively. As an example, one can
see how the codeword associated with the symbol $s_{7}$ in our code tree,
which is $10001$, is only a subsequence of the codeword associated with the
symbol $s_{7}$ in the first tree, that is
$\underline{100}00\underline{0}0\underline{1}$, where the underlined bits are
those that correspond to the codeword of our code tree.

$s_{1}$$s_{2}$$s_{3}$$s_{4}$$s_{5}$$s_{6}$$s_{7}$$s_{8}$$s_{9}$$s_{\scriptscriptstyle
10}$
---

$s_{1}$$s_{2}$$s_{3}$$s_{4}$$s_{5}$$s_{6}$$s_{7}$$s_{8}$$s_{9}$$s_{\scriptscriptstyle
10}$
---

Figure 1: The alphabetic trees constructed on the list of lengths $L=\langle
6,6,5,2,9,9,8,6,3,2\rangle$. On the left the tree constructed by taking the
first $\ell_{i}$ bits of the binary expansion of $\mbox{\tt sum}(L,i)$,
(according to Nakatsu [25]), on the right the tree constructed by our
algorithm ConstructTree($L$).

Before presenting our results on the length of the optimal alphabetic code
that improves upon the upper bound (5), we briefly show a problematic issue in
the analysis of the bound (5) claimed in [4].

######  Remark 1.

In the proof of the upper bound (5) presented in [4], the authors proceed in
the following way: Starting from an input probability distribution
$\phi=(\phi_{1},\dots,\phi_{m})$, they first consider the fully extended
distribution $\nu\,^{\prime}=(0,\phi_{1},0,\dots,0,\phi_{m},0)$ and,
subsequently, apply the classic algorithm of Gilbert and Moore [9] to
construct an alphabetic code $C$ for the distribution
$\nu\,^{\prime}=(0,\phi_{1},0,\dots,0,\phi_{m},0)$. The average length of the
constructed code is less than $H(\nu\,^{\prime})+2=H(\phi)+2$. Successively,
the authors prune the binary tree representing the alphabetical code $C$ and
show that the average length of the new code so obtained satisfies the upper
bound (5). The codeword lengths associated with the null probabilities are
left unspecified in [4], while for non-null probabilities the codeword lengths
are equal to $\lceil-\log_{2}\phi_{i}\rceil+1$, as it is required in the
algorithm by Gilbert and Moore.

Next, we uncover the problematic issue in the analysis claimed in [4] by a
numeric example. Successively, in Lemma 4 of the Appendix B, we generalize our
example to an infinite number of cases.

Let
$\phi=(\phi_{1},\phi_{2},\phi_{3})=\left(\frac{1}{2},\frac{1}{4},\frac{1}{4}\right)$
and $\nu\,^{\prime}$ be its fully extended distribution
$\left(0,\frac{1}{2},0,\frac{1}{4},0,\frac{1}{4},0\right)$. As said above, the
length of the codeword produced by the algorithm of Gilbert and Moore for the
symbol of probability $\phi_{1}$ is equal to
$\lceil-\log_{2}\phi_{1}\rceil+1=2$, the length of the codeword produced for
the symbol of probability $\phi_{2}$ is equal to 3, and the length of the
codeword produced for the symbol of probability $\phi_{3}$ is equal to 3.
However, we will show that there does not exist any alphabetic code for
$\nu\,^{\prime}$ with lengths of the codewords

$L=\langle f_{1},\ldots,f_{7}\rangle=\langle
x_{1},2,x_{2},3,x_{3},3,x_{4}\rangle,$ (19)

for any choice of the codewords length
$x_{1},x_{2},x_{3},{x_{4}}\in\mathbb{N}_{+}$ associated to the symbols of null
probability.

Let us start with the choice $x_{1}=2$ and $x_{2}=x_{3}=x_{4}=3$. It is
immediate to verify that in such a case $\mbox{\tt sum}(L,7)=1$. Therefore, by
Theorem 1 there cannot exist an alphabetic code with the chosen lengths. In
fact:

$\displaystyle\mbox{\tt sum}(L,2)$ $\displaystyle=\mbox{\tt trunc}(2,\mbox{\tt
sum}(L,1))+2^{-2}=2^{-2}$ $\displaystyle\mbox{\tt sum}(L,3)$
$\displaystyle=\mbox{\tt trunc}(2,\mbox{\tt sum}(L,2))+2^{-2}=2^{-1}$
$\displaystyle\mbox{\tt sum}(L,4)$ $\displaystyle=\mbox{\tt trunc}(3,\mbox{\tt
sum}(L,3))+2^{-3}=2^{-1}+2^{-3}$ $\displaystyle\mbox{\tt sum}(L,5)$
$\displaystyle=\mbox{\tt trunc}(3,\mbox{\tt sum}(L,4))+2^{-3}=2^{-1}+2^{-2}$
$\displaystyle\mbox{\tt sum}(L,6)$ $\displaystyle=\mbox{\tt trunc}(3,\mbox{\tt
sum}(L,5))+2^{-3}=2^{-1}+2^{-2}+2^{-3}$ $\displaystyle\mbox{\tt sum}(L,7)$
$\displaystyle=\mbox{\tt trunc}(3,\mbox{\tt
sum}(L,6))+2^{-3}=2^{-1}+2^{-2}+2^{-2}$ $\displaystyle=1.$

Similarly, if we increase the lengths $x_{i}$, the value of the function sum
remains the same, since the values of $\alpha_{i}=\min(f_{i-1},f_{i})$ do not
change. If we decrease the lengths $x_{i}$, considering all possible
combinations, we can also verify that the value of sum remains greater than or
equal to 1. In fact, let us take for example $x_{1}=1$, $x_{2}=x_{3}=2$ and
$x_{4}=3$, we have that:

$\displaystyle\mbox{\tt sum}(L,2)$ $\displaystyle=\mbox{\tt trunc}(1,\mbox{\tt
sum}(L,1))+2^{-1}=2^{-1}$ $\displaystyle\mbox{\tt sum}(L,3)$
$\displaystyle=\mbox{\tt trunc}(2,\mbox{\tt sum}(L,2))+2^{-2}=2^{-1}+2^{-2}$
$\displaystyle\mbox{\tt sum}(L,4)$ $\displaystyle=\mbox{\tt trunc}(2,\mbox{\tt
sum}(L,3))+2^{-2}=2^{-1}+2^{-2}+2^{-2}$ $\displaystyle=1$
$\displaystyle\mbox{\tt sum}(L,5)$ $\displaystyle=\mbox{\tt trunc}(2,\mbox{\tt
sum}(L,4))+2^{-2}={2^{-1}+2^{-2}+2^{-2}}$ $\displaystyle\quad+2^{-2}{=1.25}$
$\displaystyle\mbox{\tt sum}(L,6)$ $\displaystyle=\mbox{\tt trunc}(2,\mbox{\tt
sum}(L,5))+2^{-2}=2^{-1}+2^{-2}+2^{-2}$
$\displaystyle\quad+2^{-2}+2^{-2}{=1.5}$ $\displaystyle\mbox{\tt sum}(L,7)$
$\displaystyle=\mbox{\tt trunc}(3,\mbox{\tt
sum}(L,6))+2^{-3}=2^{-1}+2^{-2}+2^{-2}$
$\displaystyle\quad+2^{-2}+2^{-2}+2^{-3}{=1.625}.$

Therefore, by Theorem 1 there cannot exist an alphabetic code with lengths
(19).

We now present our new results for alphabetic codes. We will divide our
analysis into two cases: The first is about dyadic distributions, the second
case is for everything else. We recall that a dyadic distribution
$\phi=(\phi_{1},\dots,\phi_{m})$ is a probability distribution where each
$\phi_{i}$ is equal to $2^{-k_{i}}$, for suitable integers $k_{i}>0$.

######  Theorem 2.

For any dyadic probability distribution $\phi=(\phi_{1},\dots,\phi_{m})$ on
the symbols $s_{1}\prec\dots\prec s_{m}$, we can construct in linear time an
alphabetic code $C$ with

$\displaystyle\mathbb{E}[C]{\leq}H(\phi)+1-\phi_{1}-\phi_{m}.$ (20)

###### Proof.

The idea of the proof is simple and is based on Yeung’s analysis [29, Thm. 5].
Yeung proved that, given a probability distribution
$\phi=(\phi_{1},\dots,\phi_{m})$, there exists an alphabetic code $C$ for
$\phi$ with lengths of the codewords $L=\langle\ell_{1},\dots,\ell_{m}\rangle$
equal to:

$\ell_{i}=\begin{cases}\lceil-\log_{2}\phi_{i}\rceil&\text{ if either
}i=1\text{ or }i=m,\\\ \lceil-\log_{2}\phi_{i}\rceil+1&\text{
otherwise}.\end{cases}$

From Lemma 2, the code $C$ can be constructed in $O(m)$ time.

Using the additional hypothesis that $\phi$ is a dyadic distribution we have
that $\lceil-\log_{2}\phi_{i}\rceil=-\log_{2}\phi_{i}$ for each
$i=1,\ldots,m$. Therefore, the average length of the alphabetic code $C$ with
lengths $L$ is

$\displaystyle\mathbb{E}[C]$
$\displaystyle{\leq}\sum_{i=1}^{m}\phi_{i}\,\ell_{i}$
$\displaystyle=\phi_{1}\,(-\log_{2}\phi_{1})+\phi_{m}\,(-\log_{2}\phi_{m})$
$\displaystyle\quad+\sum_{i=2}^{m-1}\phi_{i}\,(-\log_{2}\phi_{i}+1)$
$\displaystyle=-\sum_{i=1}^{m}\phi_{i}\,\log_{2}\phi_{i}+\sum_{i=2}^{m-1}\phi_{i}$
$\displaystyle=H(\phi)+1-\phi_{1}-\phi_{m}.$

∎

We now turn our attention to the general case of non-dyadic probability
distributions $\phi=(\phi_{1},\dots,\phi_{m})$.

Let us first consider the case in which $\phi_{1}$ and $\phi_{m}$ are
positives. We also need the following property of the function sum.

######  Lemma 3.

Let $\ell_{1},\dots,\ell_{m}$ be a sequence of positive integers, and let
$k\geq\max_{i}\ell_{i}$. The function sum on the list $L=\langle
f_{1},f_{2},\ldots,f_{2m-1}\rangle=\langle\ell_{1},k,\ell_{2},k,\dots,k,\ell_{m}\rangle$
of $2m-1$ elements satisfies the following inequality:

$\mbox{\tt sum}(L,2m-1)\leq
2^{-\ell_{1}}+2^{-\ell_{m}}+2\,\sum_{i=2}^{m-1}2^{-\ell_{i}}.$ (21)

###### Proof.

By the definition of number $\alpha_{i}$ (see Definition 1), it holds that

$\alpha_{2}=\min(f_{1},f_{2})=\ell_{1},$

and

$\alpha_{2m-1}=\min(f_{2m-2},f_{2m-1})=\ell_{m}.$

For each $i\in\\{3,5,\dots,2m-3\\}$, it holds that

$\alpha_{i}=\min(f_{i-1},f_{i})=\min(f_{i},f_{i+1})=\alpha_{i+1}=\ell_{\frac{i+1}{2}}.$

By the definition of the function sum, for each index $i$ we have that

$\displaystyle\mbox{\tt sum}(L,i)$ $\displaystyle=\mbox{\tt
trunc}(\alpha_{i},\mbox{\tt sum}(L,i-1))+2^{-\alpha_{i}}$
$\displaystyle\leq\mbox{\tt sum}(L,i-1)+2^{-\alpha_{i}}.$

Thus, noticing that $\mbox{\tt sum}(L,1)=0$, we have that

$\displaystyle\mbox{\tt sum}(L,2m-1)$
$\displaystyle\leq\sum_{i=2}^{2m-1}2^{-\alpha_{i}}$
$\displaystyle=2^{-\ell_{1}}+2^{-\ell_{m}}+2\,\sum_{i=2}^{m-1}2^{-\ell_{i}}.$

∎

######  Theorem 3.

For any non-dyadic probability distribution $\phi=(\phi_{1},\dots,\phi_{m})$
on the symbols $s_{1}\prec\dots\prec s_{m}$ with $\phi_{1},\phi_{m}>0$, we can
construct in linear time an alphabetic code $C$ with

$\displaystyle\mathbb{E}[C]$
$\displaystyle{\leq}H(\phi)+2-\phi_{1}\,(2-\log_{2}\phi_{1}-\lceil-\log_{2}\phi_{1}\rceil)$
$\displaystyle\quad-\phi_{m}\,(2-\log_{2}\phi_{m}-\lceil-\log_{2}\phi_{m}\rceil)$
$\displaystyle\quad-\sum_{i=1}^{m-1}\min(\phi_{i},\phi_{i+1})$ (22)
$\displaystyle<H(\phi)+2-\phi_{1}-\phi_{m}-\sum_{i=1}^{m-1}\min(\phi_{i},\phi_{i+1}).$
(23)

###### Proof.

We first show that there exists an alphabetic code $C^{\prime}$ for the
partially extended distribution

$\nu=(\nu_{1},\nu_{2},\ldots,\nu_{2m-1})=(\phi_{1},0,\dots,0,\phi_{m}),$

with average length upper bounded by

$\displaystyle
H(\phi)+2-\phi_{1}\,(2-\log_{2}\phi_{1}-\lceil-\log_{2}\phi_{1}\rceil)$
$\displaystyle\quad-\phi_{m}\,(2-\log_{2}\phi_{m}-\lceil-\log_{2}\phi_{m}\rceil).$
(24)

Successively, we will prune the binary tree representing $C^{\prime}$ by
removing the additional $m-1$ leaves (corresponding to the $m-1$ null
probabilities in $\nu$), thus reducing the quantity (24) to (22).

Let $k$ be an integer greater than
$\max_{j:\phi_{j}>0}\lceil-\log_{2}\phi_{j}\rceil+1$ (the value of $k$ will be
chosen later, in order to satisfy necessary inequalities), and let
$L=\langle\ell_{1},\dots,\ell_{2\,m-1}\rangle$ be the lengths of the codewords
for the distribution $\nu=(\phi_{1},0,\dots,0,\phi_{m})$, defined as follows:

$\ell_{i}=\begin{cases}k&\text{ if }\nu_{i}=0,\\\
\lceil-\log_{2}\nu_{i}\rceil&\text{ if }i=1\text{ or }i=2m-1,\\\
\lceil-\log_{2}\nu_{i}\rceil+1&\text{ if }\nu_{i}>0.\end{cases}$ (25)

From Lemma 3 we have that

$\displaystyle\mbox{\tt sum}(L,2\,m-1)$ $\displaystyle\leq
2^{-\lceil-\log_{2}\phi_{1}\rceil}+2^{-\lceil-\log_{2}\phi_{m}\rceil}$
$\displaystyle\quad+2\,\sum_{i\neq
1,m:\phi_{i}>0}2^{-(\lceil-\log_{2}\phi_{i}\rceil+1)}+2\,\sum_{i:\phi_{i}=0}2^{-k}$
$\displaystyle=\sum_{i:\phi_{i}>0}2^{-\lceil-\log_{2}\phi_{i}\rceil}+2\,\sum_{i:\phi_{i}=0}2^{-k}<1,$

where the last inequality holds because
$\sum_{i:\phi_{i}>0}2^{-\lceil-\log_{2}\phi_{i}\rceil}<1$ since $\phi$ is _a
non-dyadic_ distribution111Notice that if the distribution is dyadic, this
inequality might not hold. However, as we will see later the theorem can be
extended to dyadic distributions., and we can choose a sufficiently large
value for $k$.

By Theorem 1 there exists an alphabetic code with lengths $\ell_{i}$ defined
in (25), and from Lemma 2 we can construct a code $C^{\prime}$ in linear time.
The average length of such a code satisfies

$\displaystyle\mathbb{E}[C^{\prime}]$
$\displaystyle\leq\phi_{1}\lceil-\log_{2}\phi_{1}\rceil+\phi_{m}\lceil-\log_{2}\phi_{m}\rceil$
$\displaystyle\quad+\sum_{i\neq
1,m:\phi_{i}>0}\phi_{i}(\lceil-\log_{2}\phi_{i}\rceil+1)$
$\displaystyle\leq\phi_{1}\lceil-\log_{2}\phi_{1}\rceil+\phi_{m}\lceil-\log_{2}\phi_{m}\rceil$
$\displaystyle\quad+\sum_{i\neq 1,m:\phi_{i}>0}\phi_{i}(-\log_{2}\phi_{i}+2)$
(since $\lceil x\rceil<x+1$)
$\displaystyle=-\phi_{1}(-\log_{2}\phi_{1}+2-\lceil-\log_{2}\phi_{1}\rceil)$
$\displaystyle\quad-\phi_{m}(-\log_{2}\phi_{m}+2-\lceil-\log_{2}\phi_{m}\rceil)$
$\displaystyle\quad+\sum_{i:\phi_{i}>0}\phi_{i}(-\log_{2}\phi_{i}+2)$
$\displaystyle=-\sum_{i:\phi_{i}>0}\phi_{i}\log_{2}\phi_{i}+2$
$\displaystyle\quad-\phi_{1}(-\log_{2}\phi_{1}+2-\lceil-\log_{2}\phi_{1}\rceil)$
$\displaystyle\quad-\phi_{m}(-\log_{2}\phi_{m}+2-\lceil-\log_{2}\phi_{m}\rceil)$
$\displaystyle=H(\phi)+2-\phi_{1}(2-\log_{2}\phi_{1}-\lceil-\log_{2}\phi_{1}\rceil)$
$\displaystyle\quad-\phi_{m}(2-\log_{2}\phi_{m}-\lceil-\log_{2}\phi_{m}\rceil).$
(26)

We now eliminate the $m-1$ leaves associated with the additional null
probabilities in $\nu$, proceeding similarly to [4, 5]. First, observe that
the leaves associated with the probabilities $\nu_{i}$ appear, from left to
right, in the same order as the probabilities $\nu_{i}$ (this is due to the
fact that the tree represents an alphabetic code). Moreover, observe that the
binary tree of the code $C^{\prime}$ is full by construction, i.e., each node
has exactly zero or two children. When we prune a leaf $x$ associated with an
additional null probability, we bring up one level the whole sub-tree $T$
whose root $r$ is the sibling of $x$. The tree $T$ contains either the leaf
associated with a probability in $\nu$ that immediately follows the additional
null probability associated with $x$, or it contains the leaf associated to a
probability in $\nu$ that immediately precedes $x$. Hence, if $x$ is the
“left” child of $a$, its pruning causes a bump up of one level of the leaf
that follows $x$, and if $x$ is the “right” child of $a$, it causes a bump up
of one level of the leaf that precedes $x$. Figure 2 explains the procedure
pictorially.

Figure 2: The figure shows the two cases discussed above: the elimination of
$x$ bumps up of one level the leaf that precedes it (above), and the leaf that
follows it (below).

Hence, the elimination of each leaf $x$ associated with an additional null
probability in $\nu$ bumps up one level at least one leaf among the two leaves
that precede and follow $x$. In total, we bump up leaves whose total
probability is at least

$\sum_{i=1}^{m-1}\min(\phi_{i},\phi_{i+1}).$ (27)

We recall that the construction of the alphabetic code with average cost (26)
requires linear time. Similarly, the elimination of the $m-1$ leaves
associated with the additional null probabilities in $\nu$ requires linear
time too, since it can be implemented through a simple tree visit.

Thus, from (26) and (27) we conclude that the new alphabetic code has a cost
upper bounded by

$\displaystyle
H(\phi)+2-\phi_{1}\,(2-\log_{2}\phi_{1}-\lceil-\log_{2}\phi_{1}\rceil)$
$\displaystyle\quad-\phi_{m}\,(2-\log_{2}\phi_{m}-\lceil-\log_{2}\phi_{m}\rceil)-\sum_{i=1}^{m-1}\min(\phi_{i},\phi_{i+1}).$

∎

Let us now consider the case where $\phi_{1}$ and $\phi_{m}$ can be zero.

######  Theorem 4.

For any non-dyadic probability distribution $\phi=(\phi_{1},\dots,\phi_{m})$
on the symbols $s_{1}\prec\dots\prec s_{m}$, we can construct in linear time
an alphabetic code $C$ with

$\displaystyle\mathbb{E}[C]$ $\displaystyle\leq
H(\phi)+2-\phi_{\ell}\,(2-\log_{2}\phi_{\ell}-\lceil-\log_{2}\phi_{\ell}\rceil)$
$\displaystyle\quad-\phi_{k}\,(2-\log_{2}\phi_{k}-\lceil-\log_{2}\phi_{k}\rceil)$
$\displaystyle\quad-\sum_{i=\ell}^{k-1}\min(\phi_{i},\phi_{i+1})+\phi_{\ell}+\phi_{k}$
$\displaystyle=H(\phi)+2-\phi_{\ell}\,(1-\log_{2}\phi_{\ell}-\lceil-\log_{2}\phi_{\ell}\rceil)$
$\displaystyle\quad-\phi_{k}\,(1-\log_{2}\phi_{k}-\lceil-\log_{2}\phi_{k}\rceil)-\sum_{i=\ell}^{k-1}\min(\phi_{i},\phi_{i+1}),$
(28)

where $\ell=\arg\min_{i}\\{\phi_{i}>0\\}$ and
$k=\arg\max_{i}\\{\phi_{i}>0\\}$.

###### Proof.

Let $\phi^{\prime}=(\phi_{\ell},\dots,\phi_{k})$ be the probability
distribution obtained by considering only the elements of $\phi$ between
$\phi_{\ell}$ and $\phi_{k}$. From Theorem 3, we know that we can construct in
linear time an alphabetic code $C^{\prime}$ for $\phi^{\prime}$ with

$\displaystyle\mathbb{E}[C^{\prime}]$ $\displaystyle\leq
H(\phi^{\prime})+2-\phi_{\ell}\,(2-\log_{2}\phi_{\ell}-\lceil-\log_{2}\phi_{\ell}\rceil)$
$\displaystyle\quad-\phi_{k}\,(2-\log_{2}\phi_{k}-\lceil-\log_{2}\phi_{k}\rceil)-\sum_{i=\ell}^{k-1}\min(\phi_{i},\phi_{i+1}).$
(29)

We need to address four cases:

  1. 1.

$\ell=1$ and $k=m$: in this case $\phi=\phi^{\prime}$ and the result follows
from Theorem 3.

  2. 2.

$\ell>1$ and $k<m$: then
$\phi=(0,\dots,0,\phi_{\ell},\dots,\phi_{k},0,\dots,0)$ and we have to create
the leaves to allocate the symbols $s_{1},\dots,s_{\ell-1}$ and
$s_{k+1},\dots,s_{n}$. To do so, we let the leaves associated to $s_{\ell}$
and $s_{k}$ descend by one level and we insert the subtrees $T$ and
$T^{\prime}$ with leaves $s_{1},\dots,s_{\ell-1}$ and $s_{k+1},\dots,s_{n}$,
respectively, as shown in Figure 3.

Figure 3: The figure shows the insertion of the subtrees $T$ and $T^{\prime}$,
with leaves $s_{1},\dots,s_{\ell-1}$ and $s_{k+1},\dots,s_{n}$, respectively.

Thus, from (29) and since $H(\phi)=H(\phi^{\prime})$ we get that the average
length of the new code $C$ obtained satisfies

$\displaystyle\mathbb{E}[C]$ $\displaystyle\leq
H(\phi)+2-\phi_{\ell}\,(2-\log_{2}\phi_{\ell}-\lceil-\log_{2}\phi_{\ell}\rceil)$
$\displaystyle\quad-\phi_{k}\,(2-\log_{2}\phi_{k}-\lceil-\log_{2}\phi_{k}\rceil)$
$\displaystyle\quad-\sum_{i=\ell}^{k-1}\min(\phi_{i},\phi_{i+1})+\phi_{\ell}+\phi_{k}.$

  3. 3.

$\ell=1$ and $k<m$: then $\phi=(\phi_{1},\dots,\phi_{k},0,\dots,0)$ and we
have to create the leaves for the symbols $s_{k+1},\dots,s_{n}$. Therefore,
proceeding similarly to case 2) we get that

$\displaystyle\mathbb{E}[C]$ $\displaystyle\leq
H(\phi)+2-\phi_{\ell}\,(2-\log_{2}\phi_{\ell}-\lceil-\log_{2}\phi_{\ell}\rceil)$
$\displaystyle\quad-\phi_{k}\,(2-\log_{2}\phi_{k}-\lceil-\log_{2}\phi_{k}\rceil)$
$\displaystyle\quad-\sum_{i=\ell}^{k-1}\min(\phi_{i},\phi_{i+1})+\phi_{k}$
$\displaystyle<H(\phi)+2-\phi_{\ell}\,(2-\log_{2}\phi_{\ell}-\lceil-\log_{2}\phi_{\ell}\rceil)$
$\displaystyle\quad-\phi_{k}\,(2-\log_{2}\phi_{k}-\lceil-\log_{2}\phi_{k}\rceil)$
$\displaystyle\quad-\sum_{i=\ell}^{k-1}\min(\phi_{i},\phi_{i+1})+\phi_{\ell}+\phi_{k}.$

  4. 4.

$\ell>1$ and $k=m$: then $\phi=(0,\dots,0,\phi_{\ell},\dots,\phi_{m})$ and we
have to create the leaves for the symbols $s_{1},\dots,s_{\ell-1}$. Therefore,
again proceeding similarly to case 2) we get a new code $C$ with

$\displaystyle\mathbb{E}[C]$ $\displaystyle\leq
H(\phi)+2-\phi_{\ell}\,(2-\log_{2}\phi_{\ell}-\lceil-\log_{2}\phi_{\ell}\rceil)$
$\displaystyle\quad-\phi_{k}\,(2-\log_{2}\phi_{k}-\lceil-\log_{2}\phi_{k}\rceil)$
$\displaystyle\quad-\sum_{i=\ell}^{k-1}\min(\phi_{i},\phi_{i+1})+\phi_{\ell}$
$\displaystyle<H(\phi)+2-\phi_{\ell}\,(2-\log_{2}\phi_{\ell}-\lceil-\log_{2}\phi_{\ell}\rceil)$
$\displaystyle\quad-\phi_{k}\,(2-\log_{2}\phi_{k}-\lceil-\log_{2}\phi_{k}\rceil)$
$\displaystyle\quad-\sum_{i=\ell}^{k-1}\min(\phi_{i},\phi_{i+1})+\phi_{\ell}+\phi_{k}.$

∎

We have proved Theorem 3 under the hypothesis that the probability
distribution $\phi=(\phi_{1},\dots,\phi_{m})$ is non-dyadic. One of the
referees suggested the following way to extend Theorem 3 also to dyadic
distributions.

######  Corollary 4.1.

For any dyadic probability distribution $\phi=(\phi_{1},\dots,\phi_{m})$ on
the symbols $s_{1}\prec\dots\prec s_{m}$, we can construct in linear time an
alphabetic code $C$ with

$\displaystyle\mathbb{E}[C]$ $\displaystyle\leq
H(\phi)+2-\phi_{1}\,(2-\log_{2}\phi_{1}-\lceil-\log_{2}\phi_{1}\rceil)$
$\displaystyle\quad-\phi_{m}\,(2-\log_{2}\phi_{m}-\lceil-\log_{2}\phi_{m}\rceil)-\sum_{i=1}^{m-1}\min(\phi_{i},\phi_{i+1})$
(30)
$\displaystyle=H(\phi)+2-2\phi_{1}-2\phi_{m}-\sum_{i=1}^{m-1}\min(\phi_{i},\phi_{i+1}).$
(31)

###### Proof.

Let $m\geq 4$. For a given dyadic probability distribution
$\phi=(\phi_{1},\dots,\phi_{m})$, let us define

$\hat{\phi}=(\hat{\phi}_{1},\hat{\phi}_{2},\hat{\phi}_{3}\dots,\hat{\phi}_{m})=(\phi_{1},\phi_{2}-\epsilon,\phi_{3}+\epsilon,\phi_{4},\dots,\phi_{m})$
(32)

for a sufficiently small $\epsilon>0$. Since $\hat{\phi}$ is a non-dyadic
probability distribution, we obtain from Theorem 3 that we can construct in
linear time an alphabetic code $C$ with

$\displaystyle\mathbb{E}[C]$ $\displaystyle\leq
H(\hat{\phi})+2-\hat{\phi_{1}}\,(2-\log_{2}\hat{\phi_{1}}-\lceil-\log_{2}\hat{\phi_{1}}\rceil)$
$\displaystyle\quad-\hat{\phi}_{m}\,(2-\log_{2}\hat{\phi}_{m}-\lceil-\log_{2}\hat{\phi}_{m}\rceil)-\sum_{i=1}^{m-1}\min(\hat{\phi}_{i},\hat{\phi}_{i+1})$
$\displaystyle\leq
H(\hat{\phi})+2-{\phi_{1}}\,(2-\log_{2}{\phi_{1}}-\lceil-\log_{2}{\phi_{1}}\rceil)$
$\displaystyle\quad-{\phi_{m}}\,(2-\log_{2}{\phi_{m}}-\lceil-\log_{2}{\phi_{m}}\rceil)$
$\displaystyle\quad-\min(\phi_{1},\phi_{2}-\epsilon)-\min(\phi_{2}-\epsilon,\phi_{3}+\epsilon)$
$\displaystyle\quad-\min(\phi_{3}+\epsilon,\phi_{4})-\sum_{i=4}^{m-1}\min({\phi_{i}},{\phi_{i+1}}).$

Since the Shannon entropy $H(\cdot)$ and the operator $\min(\cdot,\cdot)$ are
continuous functions for $\epsilon>0$, by letting $\epsilon\to 0$ we obtain
that

$\displaystyle\mathbb{E}[C]$ $\displaystyle\leq
H(\phi)+2-\phi_{1}\,(2-\log_{2}\phi_{1}-\lceil-\log_{2}\phi_{1}\rceil)$
$\displaystyle\quad-\phi_{m}\,(2-\log_{2}\phi_{m}-\lceil-\log_{2}\phi_{m}\rceil)-\sum_{i=1}^{m-1}\min(\phi_{i},\phi_{i+1}).$

The probability distribution $\hat{\phi}$ is not equal to $\phi$ for
$\epsilon>0$. However, the code tree constructed for $\hat{\phi}$ can be used
for $\phi$, provided that $\epsilon>0$ is sufficiently small. ∎

We remark that the bounds (20) and (30) are not comparable, in the sense that
there are dyadic probability distributions $\phi$ for which (20) is better
than (30), and probability distributions $\phi$ for which it holds the
opposite. For instance, if a dyadic $\phi=(\phi_{1},\dots,\phi_{m})$ is
ordered in non decreasing fashion, then (30) becomes

$\mathbb{E}[C]\leq H(\phi)+1-2\phi_{1}-\phi_{m},$

that is better than the bound (20). On the other hand, if a dyadic
$\phi=(\phi_{1},\dots,\phi_{m})$ is ordered according to the “saw-tooth”
order, that is, is such that

$\phi_{1}<\phi_{2}>\phi_{3}<\phi_{4}>\ldots>\phi_{m-1}<\phi_{m},$

with $m$ even, then (30) becomes

$\mathbb{E}[C]\leq H(\phi)+2\phi_{2}+2\phi_{4}\ldots+2\phi_{m-2}-\phi_{1}.$
(33)

One can easily see that there are dyadic probability distributions
$\phi=(\phi_{1},\dots,\phi_{m})$ for which (20) is better than (33).

######  Remark 2.

It might be worthwhile to point out a way to (possibly) improve the upper
bound (22) of Theorem 3. For simplicity, let us assume that all probabilities
$\phi_{i}$ have distinct values (but the reasoning holds in general).

The idea is the following. Let us consider the lengths defined in (25). After
the pruning phase described in Theorem 3 we have that between $\phi_{i}$ and
$\phi_{i+1}$ it is the smaller probability to be bumped up, in the worst case.
Therefore, let $S_{1}$ be the set of all indexes $i\in\\{2,\dots,m-1\\}$ for
which holds that $\phi_{i}=\min(\phi_{i-1},\phi_{i})$ and
$\phi_{i}=\min(\phi_{i},\phi_{i+1})$, i.e., the set of the symbols that in the
worst case are bumped up at least two times. Similarly, let $S_{2}$ be the set
of all indexes $i\in\\{2,\ldots,m-1\\}$ for which holds that
$\phi_{i}=\min(\phi_{i-1},\phi_{i})$ or $\phi_{i}=\min(\phi_{i},\phi_{i+1})$
(but not both), i.e., the set of all symbols that in the worst case are bumped
up at least one time (except the first and last symbol). Whereas, for the
first and last symbol, let $S_{3}\subseteq\\{1,m\\}$ be a set such that $1\in
S_{3}$ if $\min(\phi_{1},\phi_{2})=\phi_{1}$, and similarly $m\in S_{3}$ if
$\min(\phi_{m-1},\phi_{m})=\phi_{m}$. Finally, let $S_{4}$ be the set of the
remaining indexes (expect the first and the last one) that in the worst case
are not bumped up, i.e. $S_{4}=\\{2,\ldots,m-1\\}\setminus(S_{1}\cup S_{2})$.
Consequently, we can upper bound the average length of the obtained alphabetic
code in the following way:

$\displaystyle\mathbb{E}[C]$
$\displaystyle\leq\sum_{i=2}^{m-1}\phi_{i}(\lceil-\log_{2}\phi_{i}\rceil+1)+\phi_{1}(\lceil-\log_{2}\phi_{1}\rceil)$
$\displaystyle\quad+\phi_{m}(\lceil-\log_{2}\phi_{m}\rceil)-2\sum_{i\in
S_{1}}\phi_{i}-\sum_{i\in S_{2}}\phi_{i}-\sum_{i\in S_{3}}\phi_{i}$
$\displaystyle=\sum_{i\in S_{4}}\phi_{i}(\lceil-\log_{2}\phi_{i}\rceil+1)$
$\displaystyle\quad+\sum_{i\in S_{1}\cup
S_{2}\cup\\{1,m\\}}\phi_{i}(\lceil-\log_{2}\phi_{i}\rceil)-\sum_{i\in
S_{1}}\phi_{i}-\sum_{i\in S_{3}}\phi_{i}$ (34) $\displaystyle<\sum_{i\in
S_{4}}\phi_{i}(-\log_{2}\phi_{i}+2)+\sum_{i\in S_{1}\cup
S_{2}\cup\\{1,m\\}}\phi_{i}(\lceil-\log_{2}\phi_{i}\rceil)$
$\displaystyle\quad-\sum_{i\in S_{1}}\phi_{i}-\sum_{i\in S_{3}}\phi_{i}\hskip
28.45274pt\mbox{(since $\lceil x\rceil<x+1$)}$ $\displaystyle=\sum_{i\in
S_{4}}\phi_{i}(-\log_{2}\phi_{i}+2)+\sum_{i\in S_{1}\cup
S_{2}\cup\\{1,m\\}}\phi_{i}(\lceil-\log_{2}\phi_{i}\rceil)$
$\displaystyle\quad-\sum_{i\in S_{1}}\phi_{i}-\sum_{i\in
S_{3}}\phi_{i}-\sum_{i\in S_{1}\cup
S_{2}\cup\\{1,m\\}}\phi_{i}(-\log_{2}\phi_{i}+2)$
$\displaystyle\quad+\sum_{i\in S_{1}\cup
S_{2}\cup\\{1,m\\}}\phi_{i}(-\log_{2}\phi_{i}+2)$
$\displaystyle=\sum_{i=1}^{m}\phi_{i}(-\log_{2}\phi_{i}+2)$
$\displaystyle\quad-\sum_{i\in S_{1}\cup
S_{2}\cup\\{1,m\\}}\phi_{i}(2-\log_{2}\phi_{i}-\lceil-\log_{2}\phi_{i}\rceil)$
$\displaystyle\quad-\sum_{i\in S_{1}}\phi_{i}-\sum_{i\in S_{3}}\phi_{i}$
$\displaystyle=H(\phi)+2-\sum_{i\in S_{1}\cup
S_{2}\cup\\{1,m\\}}\phi_{i}(2-\log_{2}\phi_{i}-\lceil-\log_{2}\phi_{i}\rceil)$
$\displaystyle\quad-\sum_{i\in S_{1}}\phi_{i}-\sum_{i\in S_{3}}\phi_{i}$ (35)
$\displaystyle<H(\phi)+2-\phi_{1}(2-\log_{2}\phi_{1}-\lceil-\log_{2}\phi_{1}\rceil)$
$\displaystyle\quad-\phi_{m}(2-\log_{2}\phi_{m}-\lceil-\log_{2}\phi_{m}\rceil)-\sum_{i\in
S_{1}\cup S_{2}}\phi_{i}-\sum_{i\in S_{1}\cup S_{3}}\phi_{i}$ (since
$2-\log_{2}\phi_{i}-\lceil-\log_{2}\phi_{i}\rceil>1$)
$\displaystyle=H(\phi)+2-\phi_{1}\,(2-\log_{2}\phi_{1}-\lceil-\log_{2}\phi_{1}\rceil)$
$\displaystyle\quad-\phi_{m}\,(2-\log_{2}\phi_{m}-\lceil-\log_{2}\phi_{m}\rceil)-\sum_{i=1}^{m-1}\min(\phi_{i},\phi_{i+1})$
(since $\sum_{i\in S_{1}\cup S_{2}}\phi_{i}+\sum_{i\in S_{1}\cup
S_{3}}\phi_{i}=\sum_{i=1}^{m-1}\min(\phi_{i},\phi_{i+1})).$

Therefore, (35) and (34) cannot be worse than the upper bound (22) of Theorem
3. We notice that the right-hand side of (34) and (35) depends on the content
of the sets $S_{1},S_{2}$, $S_{3}$ and $S_{4}$. Working out an explicit
estimate of the sums appearing on the right-hand side of (34) and (35) would
provide further improvements to (22). However, so doing seems challenging. We
leave it as an open problem for future investigations.

Theorem 3 can be explicitly improved (under a slightly stronger hypothesis),
as shown in the following Corollary.

######  Corollary 4.2.

For any probability distribution $\phi=(\phi_{1},\dots,\phi_{m})$ on the
symbols $s_{1}\prec\dots\prec s_{m}$, with
${\phi_{1}},\phi_{2},\phi_{m-1},{\phi_{m}}>0$, we can construct in linear time
an alphabetic code $C$ with

$\displaystyle\mathbb{E}[C]$
$\displaystyle{\leq}H(\phi)+2-\phi_{1}(2-\log_{2}\phi_{1}-\lceil-\log_{2}\phi_{1}\rceil)$
$\displaystyle\quad-\phi_{m}(2-\log_{2}\phi_{m}-\lceil-\log_{2}\phi_{m}\rceil)$
$\displaystyle\quad-\sum_{i=1}^{m-1}\min(\phi_{i},\phi_{i+1})$
$\displaystyle\quad-\phi_{1}\max(0,\lceil-\log_{2}\phi_{1}\rceil-\lceil-\log_{2}\phi_{2}\rceil-2)$
$\displaystyle\quad-\phi_{m}\max(0,\lceil-\log_{2}\phi_{m}\rceil-\lceil-\log_{2}\phi_{m-1}\rceil-2).$

###### Proof.

Assume first that $\phi$ is non dyadic. We consider the same code $C$
(equivalently, tree) constructed in Theorem 3, and we take advantage of the
knowledge of the lengths of the codewords of the first two symbols and of the
last two symbols. In fact, such knowledge in these two particular cases allows
us to state more precisely how many levels we bump up the first and last
symbol during the construction of the code $C$.

Let $\ell_{1}=\lceil-\log_{2}\phi_{1}\rceil$ and
$\ell_{2}=\lceil-\log_{2}\phi_{2}\rceil+1$ be the lengths of the codewords
associated to symbols $s_{1}$ and $s_{2}$, according to (25). When the level
of the codeword associated to $s_{1}$ exceeds the level of the codeword of
$s_{2}$ by more than one unit, that is when $\ell_{1}-\ell_{2}\geq 2$, it
holds that for each of these additional levels, there would have been an
internal node having only one child in the tree representation of the code.
However, these nodes are removed since the intermediate code $C^{\prime}$
constructed through Lemma 2 is full in its tree representation. The
elimination of such nodes bumps up the symbol $s_{1}$, since the nodes would
have been on the path from the lowest common ancestor of $s_{1}$ and $s_{2}$
to $s_{1}$. Thus, when $\ell_{1}-\ell_{2}-1>0$ we can bump up $\phi_{1}$ of at
least $\ell_{1}-\ell_{2}-1$ additional levels. This gives the
$-\phi_{1}\max(0,\lceil-\log_{2}\phi_{1}\rceil-\lceil-\log_{2}\phi_{2}\rceil-2)$
term of the bound.

A similar reasoning can be made with $s_{m}$ and $s_{m-1}$, where
$\ell_{m}=\lceil-\log_{2}\phi_{m}\rceil$ and
$\ell_{m-1}=\lceil-\log_{2}\phi_{m-1}\rceil+1$. Note that such a reasoning
cannot be applied to the other pairs of probabilities, since the knowledge of
the codeword lengths alone is not sufficient to understand which of the
symbols will be bumped up. We have to look at the whole codewords set to have
enough information.

The bound (4.2) can be extended to dyadic probability distributions proceeding
as in Corollary 4.1. ∎

##  V On Binary search trees

In this section, we exploit the results on alphabetic codes we have derived in
Section IV to provide new bounds on the average cost of optimal binary search
trees. We recall that Knuth’s algorithm [17] to construct an optimum binary
search tree has quadratic time and space complexity; here we provide a linear-
time algorithm and give upper bounds on the cost of the trees our algorithm
produces. It is clear that our upper bounds apply to optimal trees as well; we
will also see that our bounds improve on the best previous results. Since our
algorithms to construct almost-optimal search trees take in input almost-
optimal alphabetic trees, in order to get linear time complexity it is
essential that we can construct almost-optimal alphabetic trees in linear time
as well. This is one of the main reasons why we have stressed this feature of
the algorithms presented in Section IV.

We start this section by amending the analysis of the algorithm presented by
De Prisco and De Santis [5] (actually, our presentation is slightly more
general than that of [5]).

######  Theorem 5.

Let
$\sigma=(\sigma_{1},\dots,\sigma_{2\,n+1})=(p_{0},q_{1},p_{1},\dots,q_{n},p_{n})$
be a probability distribution that contains the probabilities
$q_{1},\dots,q_{n}$ and $p_{0},\dots,p_{n}$ for successful and unsuccessful
searches, respectively, on an ordered sequence $x_{1}\prec\dots\prec x_{n}$.
Let $C$ be _any_ alphabetic code for $\sigma$, of average length
$\mathbb{E}[C]$. Then, one can construct in linear time a binary search tree
$T$ for $\sigma$ of cost

$\mathbb{E}[T]\leq\mathbb{E}[C]-\sum_{i=1}^{n}q_{i}-\sum_{i=0}^{n-1}\min(p_{i},p_{i+1}).$
(36)

###### Proof.

Let us start from the binary tree $B$ corresponding to the alphabetic code
$C$. The tree $B$ has $2n+1$ leaves, that we identify with the ordered
sequence of probabilities $p_{0},q_{1},p_{1},\dots,q_{n},p_{n}$. We transform
the leaves corresponding to the $q_{i}$’s into internal nodes. As in [5], we
raise each $q_{i}$ to the lowest common ancestor of $p_{i-1}$ and $p_{i}$,
which is at least two levels above $q_{i}$. Hence, $\ell(q_{i})$, i.e. the
number of nodes from the root to $q_{i}$, decreases by at least of one unit,
for each $i$. In addition, when we bring up $q_{i}$ the whole sub-tree whose
root is the sibling of $q_{i}$ goes up by at least one level. Hence, at least
one between $p_{i-1}$ and $p_{i}$ goes up one level. 222The analysis of [5] is
incorrect since it claims that all but only one probability goes up one level.
One can see that this is not the case, as also observed by the authors of [4]
and by [19]. Figure 4 provides an example of the described process.

$p_{0}$$q_{1}$$p_{1}$$q_{2}$$p_{2}$$q_{3}$$p_{3}$
---
(a) The initial alphabetic tree

$q_{1}$$p_{0}$$p_{1}$$q_{2}$$p_{2}$$q_{3}$$p_{3}$
---
(b) The tree after transforming $q_{1}$ into an internal node

$q_{2}$$q_{1}$$p_{0}$$p_{1}$$q_{3}$$p_{2}$$p_{3}$
---
(c) The final binary search tree

Figure 4: Figure (a) shows the initial alphabetic tree; Figure (b) shows the
tree after performing the first step; Figure (c) shows the tree after the
application of the algorithm.

Therefore, in total we bump up leaves whose total probability is at least

$\sum_{i=1}^{n}q_{i}+\sum_{i=0}^{n-1}\min(p_{i},p_{i+1}).$ (37)

Let us show that the tree $T$, constructed according to the above procedure,
is a correct binary search tree for the distribution
$\sigma=(\sigma_{1},\dots,\sigma_{2\,n+1})=(p_{0},q_{1},p_{1},\dots,q_{n},p_{n})$.

To that purpose, let us observe that the search property holds in a binary
tree if and only if its in-order visit gives the nodes in the order
$p_{0},q_{1},p_{1},\ldots,q_{n},p_{n}$. To show that such a property holds in
our tree $T$, we first point out that each probability $q_{i}$ necessarily
occupies a distinct internal node in $T$. By the sake of contradiction let us
suppose that it is not the case, that is, there exist $q_{i}$ and $q_{j}$,
with $i<j$, that have been assigned to the same node $x$. Then, $x$ is the
lowest common ancestor both of $p_{i-1}$ and $p_{i}$, and of $p_{j-1}$ and
$p_{j}$. This implies that $p_{i-1}$ and $p_{j-1}$ are in the left sub-tree of
$x$, while $p_{i}$ and $p_{j}$ are in the right sub-tree of $x$. This
flagrantly contradicts the fact that in the tree $B$, from which we started,
the leaves appear in the order $p_{0},q_{1},p_{1},\dots,q_{n},p_{n}$ (i.e.,
that $B$ represents an alphabetic code).

Thus, each $q_{i}$ is assigned to a distinct lowest common ancestor, and the
order of the $p_{i}$’s is not affected by the transformation of the $q_{i}$’s
in internal nodes. Therefore, an in-order visit of the tree gives the nodes in
the order $p_{0},q_{1},p_{1},\ldots,q_{n},p_{n}$. We conclude that $T$ is a
correct binary search tree for $\sigma$.

The manipulation of the $q_{i}$’s to transform them from leaves of $B$ to
internal nodes of $T$ can be implemented in linear time, as shown in [5].

Finally, we evaluate the cost of the obtained binary search tree $T$. From
(37) the cost of $T$ satisfies the inequality

$\mathbb{E}[T]\leq\mathbb{E}[C]-\sum_{i=1}^{n}q_{i}-\sum_{i=0}^{n-1}\min(p_{i},p_{i+1}).$

This concludes the proof of the theorem. ∎

By plugging into (36) either formula (20) of Theorem 2, or formula (22) of
Theorem 3, or formula (4.2) of Corollary 4.2 (according to the hypothesis that
holds) we get a series of upper bounds on the cost of optimal binary search
trees that considerably improve on the bound (8) of [21], as we asserted in
Section III. For instance, by using formula (23) of Theorem 3 in formula (36),
we get the upper bound

$\displaystyle
H(\sigma)+2-\sigma_{1}-\sigma_{2n+1}-\sum_{i=1}^{2n}\min(\sigma_{i},\sigma_{i+1})$
$\displaystyle\quad-\sum_{i=1}^{n}q_{i}-\sum_{i=0}^{n-1}\min(p_{i},p_{i+1}),$
(38)

already mentioned in Section III.

We remark that our upper bounds on the cost of optimal binary search trees
are, in fact, upper bounds on the cost of binary search trees constructed by
the linear time algorithm outlined in Theorem 5.

It is worth noting that the binary search trees constructed according to
Theorem 5 are not too far from being optimal, and this is due to the lower
bounds on the cost of any binary search tree given in [6]. For example, the
authors of [6] proved that the cost of any binary search tree is lower bounded
by

$H(\sigma)+\sum_{i=1}^{n}q_{i}+H(\sigma)\log_{2}(H(\sigma))-(H(\sigma)+1)\log_{2}(H(\sigma)+1).$
(39)

One can see that (38) and (39) are not too far apart. In fact, the difference
between the upper bound (38) and the lower bound (39) is smaller than

$\displaystyle 2$
$\displaystyle-\sigma_{1}-\sigma_{2n+1}-\sum_{i=1}^{2n}\min(\sigma_{i},\sigma_{i+1})-2\sum_{i=1}^{n}q_{i}$
$\displaystyle-\sum_{i=0}^{n-1}\min(p_{i},p_{i+1})$
$\displaystyle-H(\sigma)\log_{2}(H(\sigma))+(H(\sigma)+1)\log_{2}(H(\sigma)+1)$
$\displaystyle<2+\log_{2}(H(\sigma)+1)+\log_{2}e-\sigma_{1}-\sigma_{2n+1}$
$\displaystyle\quad-\sum_{i=1}^{2n}\min(\sigma_{i},\sigma_{i+1})-2\sum_{i=1}^{n}q_{i}-\sum_{i=0}^{n-1}\min(p_{i},p_{i+1}).$
(40)

Additionally, other results in [6] strengthen the lower bound (39) for
particular range of values of the entropy $H$ and thus can be used the reduce
the gap between the upper bound and lower bound given in (40). Therefore, in
situations where the optimal but onerous $O(n^{2})$ time algorithm by Knuth
[17] cannot be used, our analysis shows that the $O(n)$ time algorithm of [5]
is a valid alternative. An additional merit of Theorem 5 is that any possibly
improved bounds on the average length of alphabetic codes will immediately
translate into improved bounds on the cost of binary search trees.

## Acknowledgments

The authors would like to thank the referees for their comments, corrections,
and insightful suggestions. Our paper has been greatly improved by the
generous help of the referees.

## References

  * [1] J. Abrahams, “Code and parse trees for lossless source encoding”, Commun. Inf. Syst., vol. 1, pp. 113–146, 2001.
  * [2] R. Ahlswede and I. Wegener, Search Problems. John Wiley & Sons, 1987.
  * [3] M. Aigner, Combinatorial Search, John Wiley & Sons and B. G. Teubner, Stuttgart, 1988.
  * [4] Y. Dagan, Y. Filmus, A. Gabizon and S. Moran, “Twenty (simple) questions”, Proceedings of The 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC2017, pp. 9–21, 2017.
  * [5] R. De Prisco and A. De Santis, “On binary search trees”, Information Processing Letters, vol. 45, pp. 249–253, 1993.
  * [6] R. De Prisco and A. De Santis, “New lower bounds on the cost of binary search trees”, Theoretical Computer Science, vol. 156, pp. 315–325, 1996.
  * [7] M. Fredman, “Two applications of a probabilistic search technique: Sorting X + Y and building balanced search trees”, Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, STOC ’75, pp. 240–244, 1975.
  * [8] M. Garey, “Optimal binary identification procedures”, SIAM Journal on Applied Mathematics, vol. 23, pp. 173–186, 1972.
  * [9] E. Gilbert and E. Moore, “Variable-length binary encodings”, Bell System Technical Journal, vol. 38, pp. 933–967, 1959.
  * [10] R. Hassin and A. Sarid, “Operations research applications of dichotomous search”, European Journal of Operational Research, vol. 265, Issue 3, pp. 795–812, 2018.
  * [11] T. Hiraoka and H. Yamamoto, “Alphabetic AIFV codes constructed from Hu-Tucker codes”. In: Proceedings of the 2018 IEEE International Symposium on Information Theory (ISIT 2018), pp. 2182–2186, 2018.
  * [12] Y. Horibe, “An improved bound for weight-balanced tree”, Information and Control, vol. 34, 148–151, 1977.
  * [13] T. Hu and A. Tucker, “Optimal computer search trees and variable-length alphabetical codes”, SIAM Journal on Applied Mathematics, vol. 21, pp. 514–532, 1971.
  * [14] K.-i. Iwata and H. Yamamoto, “An algorithm for constructing the optimal code trees for binary alphabetic AIFV-m codes”. In: Proceedings of the 2020 IEEE Information Theory Workshop (ITW 2020), pp. 1–5, 2021.
  * [15] G.O.H. Katona, “Combinatorial Search Problems”, in: Survey of Combinatorial Theory, J.N. Srivastava (Ed.), North Holland/American Elsevier, Amsterdam/New York), pp. 285–308, 1973.
  * [16] D.J. Kleitman and M.E. Saks, “Set orderings requiring costliest alphabetic binary trees”, SIAM Journal on Algebraic Discrete Methods, vol. 2, No. 2, pp. 142–146, 1981.
  * [17] D.E. Knuth, “Optimum binary search trees”, Acta Informatica, vol. 1, pp. 14–-25, (1971).
  * [18] D. Knuth, The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching, Addison Wesley Longman Publishing Co., Inc., 1998.
  * [19] J. Kujala, personal communication.
  * [20] E.S. Laber, R.L. Milidiu, and A.A. Pessoa, “Practical constructions of L-restricted alphabetic prefix codes”. In: Proceedings of the 6th International Symposium on String Processing and Information Retrieval, pp. 115–119, 1999.
  * [21] K. Mehlhorn, “Nearly optimal binary search trees”, Acta Informatica, vol. 5, pp. 287–295, 1975.
  * [22] K. Mehlhorn, “Searching, sorting, and information theory”. In: J. Becvar (eds) Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol 74, pp. 131–145, Springer, Berlin, Heidelberg, 1979.
  * [23] K. Mehlhorn, Data Structures and Algorithms 1: Sorting and Searching, Springer-Verlag, Berlin, Heidelberg, 1984.
  * [24] S.V. Nagaraj, “Optimal binary search trees”, Theoretical Computer Science vol. 188, pp. 1–44, 1997.
  * [25] N. Nakatsu, “Bounds on the redundancy of binary alphabetical codes”, IEEE Transactions on Information Theory, vol. 37, pp. 1225–1229, 1991.
  * [26] J. Nievergelt, “Binary search trees and file organization”, ACM Computing Surveys, Vol. 6, No. 3, pp. 195–207, 1974.
  * [27] K. Pattipati and M. Alexandridis, “Application of heuristic search and information theory to sequential fault diagnosis”, IEEE Transactions on Systems, Man, and Cybernetics, vol. 20, pp. 872–887, 1990.
  * [28] D. Sheinwald, “On binary alphabetical codes”, Data Compression Conference, IEEE Press, pp. 112–113, 1992.
  * [29] R. Yeung, “Alphabetic codes revisited”, IEEE Transactions on Information Theory, vol. 37, pp. 564–572, 1991.

## Appendix A: Proof of Lemma 1

###### Proof.

To prove claim 1) of the lemma, let $s$ be the smallest integer for which the
binary expansions of the pair $\mbox{\tt sum}(L,i)$ and $\mbox{\tt sum}(L,j)$
differ on the $s^{th}$ bit. We first prove that $s$ and $t=t_{ij}$ (cfr, eq.
(13)) have the same value.

First of all, by definition of $s$, we know that the binary expansions of
$\mbox{\tt sum}(L,i)$ and $\mbox{\tt sum}(L,j)$ are equal on the first $s-1$
bits. Moreover, since $\mbox{\tt sum}(L,i)$ and $\mbox{\tt sum}(L,j)$ are
equal on the first $s-1$ bits and $\mbox{\tt sum}(L,i)<\dots<\mbox{\tt
sum}(L,j)$, it follows that for each $k=i,\dots,j-1$, the binary expansions of
$\mbox{\tt sum}(L,k)$ and $\mbox{\tt sum}(L,k+1)$ are equal on the first $s-1$
bits, too. Therefore, it holds that $s\leq t$.

Since $\mbox{\tt sum}(L,i)$ and $\mbox{\tt sum}(L,j)$ differ on the $s^{th}$
bit and $\mbox{\tt sum}(L,i)<\mbox{\tt sum}(L,j)$, we know that the $s^{th}$
bit of $\mbox{\tt sum}(L,i)$ is 0, while the $s^{th}$ bit of $\mbox{\tt
sum}(L,j)$ is 1. As a consequence, since $\mbox{\tt sum}(L,i)<\dots<\mbox{\tt
sum}(L,j)$ and for each $k=i,\dots,j-1$, both the binary expansions of
$\mbox{\tt sum}(L,k)$ and of $\mbox{\tt sum}(L,k+1)$ are equal on the first
$s-1$ bits, there must exist an index $k\in\\{i,\dots,j-1\\}$ such that the
$s^{th}$ bit of $\mbox{\tt sum}(L,k)$ is 0, and the $s^{th}$ bit of $\mbox{\tt
sum}(L,k+1)$ is 1. Therefore, since $t=t_{ij}=\min_{i\leq k<j}t_{k}$ and there
exists $k$ such that $t_{k}=s$, it holds that $s\geq t$. Thus, we finally get
that $s=t$.

One can also see that $s=\lceil-\log_{2}(\mbox{\tt sum}(L,i)\oplus\mbox{\tt
sum}(L,j))\rceil$, where $\mbox{\tt sum}(L,i)\oplus\mbox{\tt sum}(L,j)$ is the
numerical value whose binary expansion is equal to the XOR operation between
the binary expansions of $\mbox{\tt sum}(L,i)$ and $\mbox{\tt sum}(L,j)$.
Indeed, since the binary expansions of $\mbox{\tt sum}(L,i)$ and $\mbox{\tt
sum}(L,j)$ are equal on the first $s-1$ bits, it holds that the binary
expansion of the value $\mbox{\tt sum}(L,i)\oplus\mbox{\tt sum}(L,j)$ contains
the first bit equal to 1 exactly in the $s^{th}$ position. Therefore, one gets
that $s$ is the smallest integer for which it holds that

$2^{-s}\leq\mbox{\tt sum}(L,i)\oplus\mbox{\tt sum}(L,j).$ (41)

From (41), we get that $s=\lceil-\log_{2}(\mbox{\tt sum}(L,i)\oplus\mbox{\tt
sum}(L,j))\rceil$.

To prove claim 2) of the lemma, let $z\in\\{i,\dots,j-1\\}$ denote the index
for which it holds that $t_{z}=t_{ij}$. Then, we have that the binary
expansion of $\mbox{\tt sum}(L,z)$ differs from the binary expansion of
$\mbox{\tt sum}(L,z+1)$ on the $t_{ij}^{th}$ bit. In particular, from the
definition of $t_{z}$, the binary expansions of $\mbox{\tt sum}(L,z)$ and
$\mbox{\tt sum}(L,z+1)$ are equal on the first $t_{ij}-1$ bits, and, since
$\mbox{\tt sum}(L,z)<\mbox{\tt sum}(L,z+1)$, we have that $\mbox{\tt
sum}(L,z)$ has a binary expansion with $0$ in the $t_{ij}^{th}$ position,
while $\mbox{\tt sum}(L,z+1)$ has a binary expansion with $1$ in the
$t_{ij}^{th}$ position. Finally, since $\mbox{\tt sum}(L,i)<\dots<\mbox{\tt
sum}(L,j)$ and since the binary expansions of the values in the subset
$\\{\mbox{\tt sum}(L,i),\dots,\mbox{\tt sum}(L,j)\\}$ are equal on the first
$t_{ij}-1$ bits (this comes from the definition of $t_{ij}$), we get that for
the index $z$ it holds that

$\mbox{\tt sum}(L,z)<\mbox{\tt trunc}(t_{ij},\mbox{\tt sum}(L,i))+2^{-t_{ij}}$

and

$\mbox{\tt sum}(L,z+1)\geq\mbox{\tt trunc}(t_{ij},\mbox{\tt
sum}(L,i))+2^{-t_{ij}}.$

This concludes the proof.

∎

## Appendix B

######  Lemma 4.

For any non-increasing dyadic distribution $\phi=(\phi_{1},\dots,\phi_{m})$,
let $\nu\,^{\prime}=(0,\phi_{1},0,\dots,0,\phi_{m},0)$ be its fully extended
distribution, then there does not exist any alphabetic code with lengths
$L=\langle\ell_{1},\dots,\ell_{2\,m+1}\rangle$ defined as follows

$\ell_{i}=\begin{cases}x_{i}&\text{ if }\nu\,^{\prime}_{i}=0,\\\
\lceil-\log_{2}\nu\,^{\prime}_{i}\rceil+1&\text{ if }\nu\,^{\prime}_{i}>0,\\\
\end{cases}$

where $x_{i}\in\mathbb{N}_{+}$ are arbitrarily chosen values.

###### Proof.

Without loss of generality let us assume that $\phi_{m}>0$. Otherwise, we can
simply show that the lemma holds for $(\phi_{1},\dots,\phi_{m-1})$ and hence
for $\phi$.

Let $L=\langle\ell_{1},\dots,\ell_{2\,m+1}\rangle$ be the list of lengths as
defined in the statement of the Lemma. We will consider two cases. The first
corresponds to the case in which, for each $i\in\\{1,3,\dots,2\,m-1\\}$, we
have $x_{i}=\ell_{i}\geq\ell_{i+1}$ and
$x_{2\,m+1}=\ell_{2\,m+1}\geq\ell_{2\,m}$; the second case is for all other
possible choices of the $x_{i}$.

Case 1: Recall that, for $i\in\\{2,\dots,m\\}$, we have that
$\alpha_{i}=\min(\ell_{i-1},\ell_{i})$. Since $\phi$ is non-increasing, for
each $i\in\\{2,4,\dots,2\,m-2\\}$, we have that $\ell_{i}\leq\ell_{i+2}$.
Thereby, for each $i\in\\{2,\dots,2\,m\\}$, it holds that
$\alpha_{i}\leq\alpha_{i+1}$. In particular, for each
$i\in\\{2,4,\dots,2\,m\\}$, we have that

$\alpha_{i}=\alpha_{i+1}=\lceil-\log_{2}\phi_{\frac{i}{2}}\rceil+1=-\log_{2}\phi_{\frac{i}{2}}+1.$

Putting it all together we obtain that

$\displaystyle\mbox{\tt sum}(L,i)$ $\displaystyle=\mbox{\tt
trunc}(\alpha_{i},\mbox{\tt sum}(L,i-1))+2^{-\alpha_{i}}$
$\displaystyle=\mbox{\tt sum}(L,i-1)+2^{-\alpha_{i}}$ $\displaystyle=\mbox{\tt
sum}(L,i-1)+2^{-\left(-\log_{2}\phi_{\lfloor\frac{i}{2}\rfloor}+1\right)}$
$\displaystyle=\mbox{\tt
sum}(L,i-1)+\frac{\phi_{\lfloor\frac{i}{2}\rfloor}}{2},$

where the second equality holds because the $\alpha_{i}$ are non-decreasing,
and therefore the binary representation of $\mbox{\tt sum}(L,i-1)$ contains
bits equal to 1 only in the positions less than or equal to $\alpha_{i}$.

Since we add up each $\phi_{i}$ exactly once without any truncation,
$\mbox{\tt sum}(L,2\,m+1)=\sum_{i=1}^{m}\phi_{i}=1$ and by Theorem 1 there
does not exist any alphabetic code for the lengths $L$.

Case 2: In this case, there is at least one $\ell_{i}=x_{i}$ that does not
satisfy the condition of Case 1. Let us suppose that $\mbox{\tt
sum}(L,2\,m+1)<1$ and show that this leads to a contradiction.

Consider the sub-case in which we increase by 1 $x_{i}$, with $1<i<2m+1$. Let
$L^{\prime}=\langle\ell_{1},\dots,\ell_{i-1},\ell_{i}+1,\ell_{i+1},\dots,\ell_{2\,m+1}\rangle$
be the list of lengths after increasing such $x_{i}$ by 1. Let us show that
$\mbox{\tt sum}(L^{\prime},2\,m+1)$ can only decrease with respect to
$\mbox{\tt sum}(L,2\,m+1)$. Since $x_{i}$ can only affect $\alpha_{i}$ and
$\alpha_{i+1}$, we have four cases:

  * •

$\alpha_{i}$ increases by 1 and $\alpha_{i+1}$ does not change:

$\displaystyle\mbox{\tt sum}(L^{\prime},i)$ $\displaystyle=\mbox{\tt
trunc}(\alpha_{i}+1,\mbox{\tt sum}(L,i-1))+2^{-(\alpha_{i}+1)}$
$\displaystyle\leq\mbox{\tt trunc}(\alpha_{i},\mbox{\tt
sum}(L,i-1))+2^{-(\alpha_{i}+1)}$ $\displaystyle\quad+2^{-(\alpha_{i}+1)}$
$\displaystyle=\mbox{\tt trunc}(\alpha_{i},\mbox{\tt
sum}(L,i-1))+2^{-\alpha_{i}}$ $\displaystyle=\mbox{\tt sum}(L,i).$

  * •

$\alpha_{i}$ does not change and $\alpha_{i+1}$ increases by 1:

$\displaystyle\mbox{\tt sum}(L^{\prime},i+1)$ $\displaystyle=\mbox{\tt
trunc}(\alpha_{i+1}+1,\mbox{\tt sum}(L,i))$
$\displaystyle\quad+2^{-(\alpha_{i+1}+1)}$ $\displaystyle\leq\mbox{\tt
trunc}(\alpha_{i+1},\mbox{\tt sum}(L,i))$
$\displaystyle\quad+2^{-(\alpha_{i+1}+1)}+2^{-(\alpha_{i+1}+1)}$
$\displaystyle=\mbox{\tt trunc}(\alpha_{i+1},\mbox{\tt
sum}(L,i))+2^{-\alpha_{i+1}}$ $\displaystyle=\mbox{\tt sum}(L,i+1).$

  * •

Both $\alpha_{i}$ and $\alpha_{i+1}$ increase by 1: then
$\alpha_{i}=\alpha_{i+1}$ and

$\displaystyle\mbox{\tt sum}(L^{\prime},i+1)$ $\displaystyle=\mbox{\tt
trunc}(\alpha_{i+1}+1,\mbox{\tt sum}(L^{\prime},i))$
$\displaystyle\quad+2^{-(\alpha_{i+1}+1)}$ $\displaystyle=\mbox{\tt
trunc}(\alpha_{i+1}+1,$ $\displaystyle\quad\quad\mbox{\tt
trunc}(\alpha_{i}+1,\mbox{\tt sum}(L,i-1))$
$\displaystyle\quad\quad+2^{-(\alpha_{i}+1)})$
$\displaystyle\quad+2^{-(\alpha_{i+1}+1)}$ $\displaystyle=\mbox{\tt
trunc}(\alpha_{i}+1,\mbox{\tt sum}(L,i-1))$
$\displaystyle\quad+2^{-(\alpha_{i}+1)}+2^{-(\alpha_{i+1}+1)}$
$\displaystyle\quad{\mbox{(since $\alpha_{i}=\alpha_{i+1}$})}$
$\displaystyle=\mbox{\tt trunc}(\alpha_{i}+1,\mbox{\tt sum}(L,i-1))$
$\displaystyle\quad+2^{-(\alpha_{i}+1)}+2^{-(\alpha_{i}+1)}$
$\displaystyle=\mbox{\tt trunc}(\alpha_{i}+1,\mbox{\tt
sum}(L,i-1))+2^{-\alpha_{i}}$ $\displaystyle\leq\mbox{\tt
trunc}(\alpha_{i},\mbox{\tt sum}(L,i-1))$
$\displaystyle\quad+2^{-\alpha_{i}}+2^{-(\alpha_{i}+1)}$
$\displaystyle<\mbox{\tt trunc}(\alpha_{i},\mbox{\tt sum}(L,i-1))$
$\displaystyle\quad+2^{-\alpha_{i}}+2^{-\alpha_{i+1}}$
$\displaystyle=\mbox{\tt trunc}(\alpha_{i+1},$
$\displaystyle\quad\quad\mbox{\tt trunc}(\alpha_{i},\mbox{\tt
sum}(L,i-1))+2^{-\alpha_{i}})$ $\displaystyle\quad+2^{-\alpha_{i+1}}$
$\displaystyle={\mbox{\tt trunc}(\alpha_{i+1},\mbox{\tt
sum}(L,i))+2^{-\alpha_{i+1}}}$ $\displaystyle=\mbox{\tt sum}(L,i+1).$

  * •

Both $\alpha_{i}$ and $\alpha_{i+1}$ do not change: the final sum remains the
same.

Therefore, we have that $\mbox{\tt sum}(L^{\prime},2\,m+1)\leq\mbox{\tt
sum}(L,2\,m+1)$.

Consider now the sub-cases in which we increase by 1 $x_{1}$ or $x_{2\,m+1}$.
In such sub-cases, only $\alpha_{2}$ and $\alpha_{2\,m+1}$ can be affected.
Let us consider the case when $x_{1}$ is increased and let
$L^{\prime}=\langle\ell_{1}+1,\dots,\ell_{2\,m+1}\rangle$ be the list of
lengths after increasing $x_{1}$. We have two possibilities:

  * •

$\alpha_{2}$ increases by 1:

$\displaystyle\mbox{\tt sum}(L^{\prime},2)$ $\displaystyle=\mbox{\tt
trunc}(\alpha_{{2}}+1,\mbox{\tt sum}(L,1))+2^{-\alpha_{{2}}-1}$
$\displaystyle=\mbox{\tt trunc}(\alpha_{{2}},\mbox{\tt
sum}(L,1))+2^{-\alpha_{{2}}-1}$ $\displaystyle<\mbox{\tt
trunc}(\alpha_{{2}},\mbox{\tt sum}(L,1))+2^{-\alpha_{{2}}}$
$\displaystyle=\mbox{\tt sum}(L,2)$

  * •

$\alpha_{2}$ does not change: then $\mbox{\tt sum}(L^{\prime},2)=\mbox{\tt
sum}(L,2)$.

A similar reasoning holds for $x_{2\,m+1}$ too. By denoting with
$L^{\prime}=\langle\ell_{1},\dots,\ell_{2\,m+1}+1\rangle$ the list of lengths
after increasing $x_{2\,m+1}$, we have two possibilities:

  * •

$\alpha_{2\,m+1}$ increases by 1:

$\displaystyle\mbox{\tt sum}(L^{\prime},2\,m+1)$ $\displaystyle=\mbox{\tt
trunc}(\alpha_{2\,m+1}+1,\mbox{\tt sum}(L,2\,m))$
$\displaystyle\quad+2^{-(\alpha_{2\,m+1}+1)}$ $\displaystyle\leq\mbox{\tt
trunc}(\alpha_{2\,m+1},\mbox{\tt sum}(L,2\,m))$
$\displaystyle\quad+2^{-(\alpha_{2\,m+1}+1)}+2^{-(\alpha_{2\,m+1}+1)}$
$\displaystyle=\mbox{\tt trunc}(\alpha_{2\,m+1},\mbox{\tt sum}(L,2\,m))$
$\displaystyle\quad+2^{-\alpha_{2\,m+1}}$ $\displaystyle=\mbox{\tt
sum}(L,2\,m+1)$

  * •

$\alpha_{2\,m+1}$ does not change: then $\mbox{\tt
sum}(L^{\prime},2\,m+1)=\mbox{\tt sum}(L,2\,m+1)$.

Therefore, in such cases too, we have that $\mbox{\tt
sum}(L^{\prime},2\,m+1)\leq\mbox{\tt sum}(L,2\,m+1)$.

However, the above conclusions readily lead to a contradiction since, if we
repeat the process iteratively for each $x_{i}$, we obtain that when
$x_{i}=\ell_{i+1}$ for each $i\in\\{1,3,\dots,2\,m-1\\}$, and
$x_{2\,m+1}=\ell_{2\,m}$, it holds that $\mbox{\tt sum}(L^{\prime},2\,m+1)<1$
and by Theorem 1 there exists an alphabetic codes with lengths $L^{\prime}$.
But, for such lengths $L^{\prime}$, we are in Case 1 and we know that this is
not possible. Thus, even for values of $x_{i}$ arbitrarily chosen, we have
that $\mbox{\tt sum}(L,2\,m+1)\geq 1$ and by Theorem 1 there does not exist
any alphabetic code for the list of length $L$. ∎