Bit catastrophes for the Burrows-Wheeler Transform

Abstract

A bit catastrophe, loosely defined, is when a change in just one character of a string causes a significant change in the size of the compressed string. We study this phenomenon for the Burrows-Wheeler Transform (BWT), a string transform at the heart of several of the most popular compressors and aligners today. The parameter determining the size of the compressed data is the number of equal-letter runs of the BWT, commonly denoted $r$. We exhibit infinite families of strings in which insertion, deletion, resp. substitution of one character increases $r$ from constant to $\hat{I}˜(\log n)$, where $n$ is the length of the string. These strings can be interpreted both as examples for an increase by a multiplicative or an additive $\hat{I}˜(\log n)$-factor. As regards multiplicative factor, they attain the upper bound given by Akagi, Funakoshi, and Inenaga [Inf & Comput. 2023] of $O(\log n\log r)$, since here $r=O(1)$. We then give examples of strings in which insertion, deletion, resp. substitution of a character increases $r$ by a $\hat{I}˜(\sqrt{n})$ additive factor. These strings significantly improve the best known lower bound for an additive factor of $\hat{I}\text{c◯}(\log n)$ [Giuliani et al., SOFSEM 2021].

This preprint is an extended version of our conference article with the same title, published in the proceedings of DLT 2023. Full version of this preprint can be found at Theory of Computing Systems: https://link.springer.com/article/10.1007/s00224-024-10212-9