Resolution of the Burrows-Wheeler Transform Conjecture

The Burrows-Wheeler Transform (BWT) is an invertible text transformation that permutes symbols of a text according to the lexicographical order of its suffixes. BWT is the main component of popular lossless compression programs (such as bzip2) as well as recent powerful compressed indexes (such as r-index [Gagie et al., J. ACM, 2020]), central in modern bioinformatics. The compression ratio of BWT is quantified by the number r of equal-letter runs. Despite the practical significance of BWT, no non-trivial bound on the value of r is known. This is in contrast to nearly all other known compression methods, whose sizes have been shown to be either always within a polylog n factor (where n is the length of text) from z, the size of Lempel-Ziv (LZ77) parsing of the text, or significantly larger in the worst case (by a n ε factor for ε > 0).

In this paper, we show that r = O(z log 2 n) holds for every text. This result has numerous implications for text indexing and data compression; for example: (1) it proves that many results related to BWT automatically apply to methods based on LZ77, e.g., it is possible to obtain functionality of the suffix tree in O(z polylog n) space; (2) it shows that many text processing tasks can be solved in the optimal time assuming the text is compressible using LZ77 by a sufficiently large polylog n factor; (3) it implies the first non-trivial relation between the number of runs in the BWT of the text and its reverse.

In addition, we provide an O(z polylog n)-time algorithm converting the LZ77 parsing into the run-length compressed BWT. To achieve this, we develop a number of new data structures and techniques of independent interest. In particular, we introduce a notion of compressed string synchronizing sets (generalizing the recently introduced powerful technique of string synchronizing sets [STOC 2019]) and show how to efficiently construct them.

Next, we propose a new variant of wavelet trees for sequences of long strings, establish a non-trivial bound on their size, and describe efficient construction algorithms. Finally, we describe new indexes that can be constructed directly from the LZ77-compressed text and efficiently support pattern matching queries on substrings of the text.