2024/04/16 by Sara Giuliani, Giuliani, Sara, Shunsuke Inenaga +9 · 2 citations
Computer Science · #Anomaly Detection Techniques and Applications #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #Music and Audio Processing
paper · pdf · doi:10.48550/arxiv.2404.10426
openalex publication_date 2024/04/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Θ(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 Θ(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 Θ(√(n)) additive factor. These strings significantly improve the best known lower bound for an additive factor of Ω(log n) [Giuliani et al., SOFSEM 2021].