On Inverting the Burrows-Wheeler Transform

Sorting is typically one of the introductory topics in a first course on algorithms and data structures. Knuth devotes almost four hundred pages to the problem in the The Art of Computer Programming [12] and Cormen et al. use insertion sort as a first example of an algorithm [3].

Consider a sorted alphabet (i.e., an alphabet endowed with a total order). The problem of sorting can be stated as follows.

For example, if $T=cdba$, then the output of Problem 1 is the permutation $\psi$ of $\{1,2,3,4\}$ such that $\psi (1)=4$, $\psi (2)=3$, $\psi (3)=1$ and $\psi (4)=2$. Note that the permutation $\psi$ of Problem 1 is uniquely defined if and only the $a_i$’s are pairwise distinct. More generally, $\psi$ becomes uniquely defined if we add the additional requirement that, for every $1\le i\le n-1$, if $a_{\psi (i)}=a_{\psi (i+1)}$, then . The permutation $\psi$ that satisfies this additional requirement is the stable sort of $T$.

Both Knuth and Cormen at al.’s consider the comparison model, in which no restriction on the (possibly infinite) sorted alphabet is assumed, and the only way to obtain information on the mutual order between the characters in $T$ is by solving queries $c(i,j)$ of the following type: given $1\le i,j\le n$, decide whether $a_i\le a_j$. We assume that each query $c(i,j)$ takes $O(1)$ time.

In the comparison model, the (worst-case) complexity of Problem 1 is $\mathrm{\Theta }(n\log n)$: there exist algorithms (e.g., merge sort, which computes the stable sort of $T$) solving Problem 1 in $O(n\log n)$ time, and any algorithm solving Problem 1 has complexity $\mathrm{\Omega }(n\log n)$. The (classical) proof of the $\mathrm{\Omega }(n\log n)$ lower bound [12, 3] shows a stronger result: to solve Problem 1, in the worst case we need $\mathrm{\Omega }(n\log n)$ queries $c(i,j)$’s, and this is true even if we know that the $a_i$’s are pairwise distinct. In other words, $\mathrm{\Omega }(n\log n)$ is not only an algorithmic lower bound, but it also captures the minimum number of operations required to have enough information for solving Problem 1.

The comparison model yields a simple, informative, and mathematically appealing setting for studying the complexity of sorting, but it can hardly be considered a realistic computational model. For example, if the $a_i$’s are known to be integers in a polynomial range, Problem 1 can be solved in $O(n)$ time via radix sort, which also computes the stable sort of $T$ [10].

The landscape becomes more complex if one considers alternative models of computations. On the one hand, it is possible to obtain models that are more flexible than the comparison model by allowing more complex queries in $O(1)$ time. Assume that the alphabet is the set of all real numbers, and consider the function $f(x,y)=x-y$. In the comparison model, in $O(1)$ time we can test whether $f(x,y)\le 0$ for any choice of $x,y\in \{a_1,a_2,\mathrm{\dots },a_n\}$. In the linear decision tree model, one is allowed more general tests of the type $f(x_1,x_2,\mathrm{\dots },x_n)⋚0$, where we consider a linear function $f(x_1,x_2,\mathrm{\dots },x_n)=c_0+c_1{x}_1+c_2{x}_2+\mathrm{\cdots }+c_n{x}_n$. In the algebraic decision tree model, we can choose $f(x_1,x_2,\mathrm{\dots },x_n)$ to be an arbitrary polynomial. Even if the linear decision tree model and the algebraic decision tree model are more general than the comparison model, the complexity of Problem 1 in all these models is still $\mathrm{\Theta }(n\log n)$ [4, 1]. On the other hand, it is possible to consider (realistic) variants of the RAM model. In the word-RAM model with word size $w\ge \log N$, where $N$ is the size of the input, the complexity of Problem 1 is still open, even though it is known to be $o(n\log n)$ [8, 9]. Other variants of these models are possible, but we will focus only on the comparison model and the case of integers in a polynomial range, which are arguably the most common settings in the literature.

In this paper, we show that the complexity of Problem 1 (Sorting) is the same as the complexity of other fundamental problems: suffix sorting, element distinctness and BWT inversion. The complexity of these problems in $\mathrm{\Theta }(n\log n)$ in the comparison model and $\mathrm{\Theta }(n)$ in the case of integers in a polynomial range. Our main contribution is an $\mathrm{\Omega }(n\log n)$ lower bound for BWT inversion in the comparison model (Theorem 1). We also show that Theorem 1 implies a new proof of the classical $\mathrm{\Omega }(n\log n)$ lower bound for sorting (Corollary 2), which we believe to be of didactic interest for those who are not familiar with the Burrows-Wheeler transform.

Problem 1 is closely related to several fundamental problems. Here are some examples.

For example, if $T=banana$, then the output of Problem 2 is the permutation $\psi$ of $\{1,2,3,4,5,6\}$ such that $\psi (1)=6$, $\psi (2)=4$, $\psi (3)=2$, $\psi (4)=1$, $\psi (5)=5$ and $\psi (6)=3$. Note that $\psi$ is uniquely defined because the suffixes of a string are pairwise distinct.

For example, if $T=cdba$, then the output of Problem 3 is “no”.

The complexity of Problems 2 and 3 is $\mathrm{\Theta }(n)$ in the case of integers in a polynomial range, and $\mathrm{\Theta }(n\log n)$ in the comparison model. Let us show how to obtain these bounds by reducing these problems to Problem 1 (Sorting).

Let us consider the case of integers in a polynomial range.

• $\mathrm{■}$

  Problem 2 can be solved in $O(n)$ time by using any linear-time algorithm for building the suffix array (see [15] for a survey). Historically, the linear time complexity was first proved by Farach, who solved the more general problem of building the suffix tree of a string in linear time [5]. Conceptually, the easiest algorithm is probably Kärkkäinen et al.’s algorithm [11].

• $\mathrm{■}$

  Problem 3 can be solved in $O(n)$ time by first computing a permutation $\psi$ as in Problem 1 (Sorting) and then checking in $O(n)$ time if there exists $1\le i\le n-1$ such that $a_{\psi (i)}=a_{\psi (i+1)}$.

Let us consider the comparison model.

• $\mathrm{■}$

  On the one hand, Problem 2 can be solved in $O(n\log n)$ time by (i) sorting the $a_i$’s via any $O(n\log n)$ comparison-based algorithm, (ii) replacing each $a_i$ with its rank in the sorted list of all $a_i$’s (which does not affect the mutual order of the suffixes) and (iii) applying any $O(n)$ suffix sorting algorithm mentioned earlier. On the other hand, to solve Problem 2 we need $\mathrm{\Omega }(n\log n)$ queries $c(i,j)$’s in the worst case, and the same lower bound is true even if we know that the $a_i$’s are pairwise distinct. Indeed, given the permutation $\psi$ of Problem 2, we have $a_{\psi (i)}\le a_{\psi (i+1)}$ for every $1\le i\le n-1$ (because the suffix $a_{\psi (i)}{a}_{\psi (i)+1}\mathrm{\dots }{a}_{n-1}{a}_n$ is lexicographically smaller than the suffix $a_{\psi (i+1)}{a}_{\psi (i+1)+1}\mathrm{\dots }{a}_{n-1}{a}_n$), so $\psi$ is also a correct output for Problem 1, and the conclusion follows from the lower bound for Problem 1 mentioned earlier.

• $\mathrm{■}$

  On the one hand, Problem 3 has complexity $O(n\log n)$: we can argue as in the case of integers in a polynomial range, but we use any $O(n\log n)$ comparison-based algorithm to compute a permutation $\psi$ as in Problem 1. On the other hand, to solve Problem 3 we need $\mathrm{\Omega }(n\log n)$ queries $c(i,j)$’s in the worst case, as we show next. Fix an integer $n$, and consider an algorithm that solves Problem 3 for every string $T=a_1{a}_2\mathrm{\dots }{a}_n$. Let $f(n)$ be the number of queries $c(i,j)$’s solved by the algorithm in the worst case. If the $a_i$’s are pairwise distinct, the permutation $\psi$ of Problem 1 is uniquely defined, and the algorithm for Problem 3 must return “no”. To this end, the algorithm must solve the query $c(\psi (i+1),\psi (i))$ for every $1\le i\le n-1$ because otherwise the algorithm could not infer that $a_{\psi (i)}\ne a_{\psi (i+1)}$ from the other queries that it solves and so it would not have enough information to solve Problem 3 correctly on input $T$. Consequently, if for every query $c(i,j)$ solved by the algorithm we also consider the query $c(j,i)$, we obtain at most $2f(n)$ queries. In particular, we consider both the query $c(\psi (i+1),\psi (i))$ and the query $c(\psi (i),\psi (i+1))$ for every $1\le i\le n-1$, from which we can infer that for every $1\le i\le n-1$. We conclude that at most $2f(n)$ queries $c(i,j)$’s are sufficient in the worst case to compute $\psi$ and so solve Problem 1 for every $T=a_1{a}_2\mathrm{\dots }{a}_n$ in which the $a_i$’s are pairwise distinct. Hence, we obtain $f(n)=\mathrm{\Omega }(n\log n)$ from the lower bound for Problem 1 mentioned earlier.

Let us show that Problem 1 is related to another fundamental problem in string processing and compression. To this end, we need to introduce the Burrows-Wheeler transform (BWT) of a string [2]. Let $S=b_1{b}_2\mathrm{\dots }{b}_n$ be a string such that $b_n=\$$, where $\$$ is a special character such that (i) $\$$ does not occur anywhere else in the string and (ii) $\$$ is smaller than all the other characters. For example, we can consider the string $S=banana\$$ (where $n=7$). For $1\le i\le n$, let $S_i=b_i{b}_{i+1}\mathrm{\dots }{b}_n{b}_1{b}_2\mathrm{\dots }{b}_{i-1}$ be the $i$-th circular suffix of $S$. For example, if $S=banana\$$, we have $S_1=banana\$$, $S_2=anana\$b$, $S_3=nana\$ba$, $S_4=ana\$ban$, $S_5=na\$bana$, $S_6=a\$banan$ and $S_7=\$banana$. Note that the circular suffixes of $S$ are pairwise distinct because $\$$ occurs in a different position in each of them.

We build the square matrix $M$ of size $n\times n$ such that, for every $1\le i\le n$, the $i$-th row $R_i[1,n]$ is equal to $i$-th (lexicograhically) smallest circular suffix of $S$ (see Table 1 for the matrix $M$ of size $7\times 7$ obtained from $S=banana\$$). Note that $R_1=b_n{b}_1{b}_2\mathrm{\dots }{b}_{n-1}=S_n$ because $b_n=\$$ is the smallest character.

For $1\le i\le n$, let $C_i[1,n]$ be the $i$-th column of $M$ from left to right. Notice that every $C_i$ is a rearrangement of the characters in $S$. Let $F=C_1$ and $L=C_n$ be the first column and the last column of $M$, respectively. In Table 1, we have $F=\$aaabnn$ and $L=annb\$aa$. Note that $F$ can be obtained by sorting the characters of $S$. By definition, the Burrows-Wheeler transform $\mathrm{𝖡𝖶𝖳}[S]$ of $S$ is the column $F$, that is, $\mathrm{𝖡𝖶𝖳}[S]=F=C_n$. In Table 1, we have $\mathrm{𝖡𝖶𝖳}[S]=annb\$aa$.

Crucially, the Burrows-Wheeler transform $\mathrm{𝖡𝖶𝖳}[S]$ of a string $S$ is an encoding of the string: given $\mathrm{𝖡𝖶𝖳}[S]$, we can retrieve the string $S$. In Table 1, given $\mathrm{𝖡𝖶𝖳}[S]=annb\$aa$, we can retrieve $S=banana\$$. To prove this, we only need to show that from $\mathrm{𝖡𝖶𝖳}[S]$ we can retrieve the matrix $M$, because then the unique row of the matrix ending with $\$$ yields the original string $S$. We can retrieve $M$ by computing all columns $C_i$’s. We know that $C_n=\mathrm{𝖡𝖶𝖳}(S)$, and we can retrieve $C_1$ by sorting all characters in $C_n$. Let us show how to retrieve $C_2$. We know $C_n$ and $C_1$, so we know all pairs of consecutive characters in $S$. If we sort these pairs lexicographically and we pick the last element of each pair, we retrieve $C_2$. In Table 1, all pairs of consecutive characters in $S$ are $a\$$, $na$, $na$, $ba$, $\$b$, $an$, $an$. By sorting these pairs, we obtain $\$b$, $a\$$, $an$, $an$, $ba$, $na$, $na$, and by picking the last element of each pair, we can infer that $C_2=b\$nnaaa$. Let us show how to retrieve $C_3$. We know $C_n$, $C_1$ and $C_2$, so we know all triples of consecutive characters in $S$. If we sort these triples lexicographically and we pick the last element of each triple, we retrieve $C_3$. In Table 1, all triples of consecutive characters in $S$ are $a\$b$, $na\$$, $nan$, $ban$, $\$ba$, $ana$, $ana$. By sorting these triples, we obtain $\$ba$, $a\$b$, $ana$, $ana$, $ban$, $na\$$, $nan$, and by picking the last element of each triple, we can infer that $C_3=abaan\$n$. In the same way, we can retrieve $C_4,C_5,\mathrm{\dots },C_{n-1}$.

Since $\mathrm{𝖡𝖶𝖳}(S)$ is an encoding of $S$, we can store $\mathrm{𝖡𝖶𝖳}(S)$ instead of $S$ without losing information. The reason why storing $\mathrm{𝖡𝖶𝖳}(S)$ may be more beneficial than storing $S$ is that the string $\mathrm{𝖡𝖶𝖳}(S)$ tends to be repetitive if in $S$ several substrings have multiple occurrences, so we can exploit the repetitiveness of $S$ to compress $\mathrm{𝖡𝖶𝖳}(S)$. This property motivated the introduction of the Burrows-Wheeler transform in the original paper [2] and can be stated in precise mathematical terms via the notion of entropy [13]. Surprisingly, it is also possible to solve pattern matching on the original string by augmenting the compressed representation of the Burrows-Wheeler transform with space-efficient data structures, thus obtaining the FM-index [6].

We described an (inefficient) algorithm to invert the Burrows-Wheeler transform. Let us state the problem formally.

For example, if $T=annb\$aa$, then $S=banana\$$ (see Table 1).

In this section, we show that the complexity of Problem 4 in $\mathrm{\Theta }(n\log n)$ in the comparison model and $\mathrm{\Theta }(n)$ in the case of integers in a polynomial range. The only bound that cannot be inferred from the original paper on the Burrows-Wheeler transform [2] is the $\mathrm{\Omega }(n\log n)$ lower bound in the comparison model. Notice that the four problems considered in this paper have the same complexity.

To prove the $\mathrm{\Omega }(n\log n)$ bound for Problem 4, we will proceed differently from Problems 2 and 3. We will prove the lower bound directly, without relying on the lower bound for Problem 1 (Sorting). Then, we will use the lower bound for Problem 4 (BWT inversion) to infer the lower bound for Problem 1 (Sorting). In addition to establishing interesting relationships between fundamental problems, our approach yields a new proof of the celebrated $\mathrm{\Omega }(n\log n)$ bound for sorting, which we believe to be of didactic interest.

Let us start with the lower bound for BWT inversion.

In this paper, we have shown that, in the comparison model, inverting the Burrows-Wheeler transform has complexity $\mathrm{\Theta }(n\log n)$. As a corollary, we have obtained a new proof of the $\mathrm{\Omega }(n\log n)$ sorting lower bound. Our main goal was to highlight how the ideas behind the Burrows-Wheeler transform are deeply intertwined with the most fundamental results in Computer Science.