We prove that for every integer n > 0 and for every alphabet Σ_k of size k ≥ 3, there exist words of length n whose Burrows-Wheeler Transform (BWT) is totally unclustered, i.e., it consists of exactly n runs with no two consecutive equal symbols. These words represent the worst-case behavior of the clustering effect of the BWT. We also establish a lower bound on their number. This contrasts with the binary case, where the existence of infinitely many totally unclustered BWT images is still an open problem, related to Artin’s conjecture on primitive roots.

Abstract The problem of detecting and measuring the repetitiveness of one-dimensional strings has been extensively studied in data compression and text indexing. Our understanding of these issues has been significantly improved by the introduction of the notion of string attractor (Kempa and Prezza 2018) and by the results showing the relationship between attractors and other measures of compressibility. When the input data are structured in a non-linear way, as in two-dimensional strings, inherent redundancy often offers an even richer source for compression. However, systematic studies on repetitiveness measures for two-dimensional strings are still scarce. In this paper, we extend to two or more dimensions the main measures of complexity introduced for one-dimensional strings. We distinguish between the measures $$\delta $$ δ and $$\gamma $$ γ , defined in terms of the substrings of the input, and the measures g , $$g_{rl}$$ g rl , and b , which are based on copy-paste mechanisms. We study the properties and mutual relationships between these two classes and we show that the two classes become incomparable for d -dimensional inputs as soon as $$d\geqslant 2$$ d ⩾ 2 . Moreover, we show that our grammar-based representation of a d -dimensional string of size N enables direct access to any symbol in $$O(\log N)$$ O ( log N ) time. We also compare our measures for two-dimensional strings with the 2D Block Tree data structure (Brisaboa et al., Comput. J. 67 (1), 391–406, 2024) and provide some insights for the design of future effective two-dimensional compressors. A preliminary version of this paper appeared in the proceedings of the conference SPIRE 2024.

A suffixient set is a novel combinatorial object that captures the essential information of repetitive strings in a way that, provided with a random access mechanism, supports various forms of pattern matching. In this paper, we study the size χ of the smallest suffixient set as a repetitiveness measure. First, we study its sensitivity to various string operations. We show that χ cannot increase by more than 2 after appending or prepending a character to the string. As a consequence, we are able to give simple linear-time online algorithms to compute smallest suffixient sets. We also show that, although reversing the string can increase χ by an arbitrary O ( n ) value, it always holds χ ( T )/ χ ( T R ) ≤ 2. We also prove lower and upper bounds for the additive or multiplicative increase of χ after applying arbitrary edit operations, or rotating the text. In particular, we show that the additive increase can be as large as Ω ( n ) for all those operations. Secondly, we place χ among known repetitiveness measures. In particular, we show χ ≤ 2 r (where r is the number of runs in the Burrows-Wheeler Transform of the string), that there are string families where χ = o ( v ) (where v is the size of the smallext lexicographic parse of the string), and that χ is uncomparable to almost all reachable measures based on copy-paste mechanisms. In passing, we give precise bounds for χ for some relevant string families, for example χ ≤ σ + 2 on episturmian words over alphabets of size σ (e.g., χ ≤ 4 on Fibonacci strings, for which we precisely characterize the only two smallest suffixient sets).

We study how the application of morphisms affects the number r of equal-letter runs in the Burrows–Wheeler Transform (BWT). This parameter has emerged as a key repetitiveness measure in compressed indexing. We focus on the notion of BWT-run sensitivity after application of morphisms. For binary alphabets, we characterize the class of injective morphisms that preserve the number of BWT-runs up to a bounded additive increase by showing that it coincides with the known class of primitivity-preserving morphisms, which are those that map primitive words to primitive words. We further prove that deciding whether a given binary morphism has bounded BWT-run sensitivity is possible in polynomial time with respect to the total length of the images of the two letters. Additionally, we explore new structural and combinatorial properties of synchronizing and recognizable morphisms. These results establish new connections between BWT-based compressibility, code theory, and symbolic dynamics.

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 $$\Theta (\log n)$$ Θ ( 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 $$\Theta (\log n)$$ Θ ( log n ) -factor. As regards the multiplicative factor, they attain the upper bound given by Akagi, Funakoshi, and Inenaga [Inf & Comput. 2023] of $$\mathcal{O}(\log n \log r)$$ O ( log n log r ) , since here $$r=\mathcal{O}(1)$$ r = O ( 1 ) . We then give examples of strings in which insertion, deletion, resp. substitution of a character increases r by a $$\Theta (\sqrt{n})$$ Θ ( n ) additive factor. These strings significantly improve the best known lower bound for an additive factor of $$\Omega (\log n)$$ Ω ( log n ) [Giuliani et al., SOFSEM 2021].

The Bijective Burrows-Wheeler Transform (BBWT) is a variant of the famous BWT [Burrows and Wheeler, 1994]. The BBWT was introduced by Gil and Scott in 2012, and is based on the extended BWT of Mantaci et al. [TCS 2007] and on the Lyndon factorization of the input string. In the original paper, the compression achieved with the BBWT was shown to be competitive with that of the BWT, and it has been gaining interest in recent years. In this work, we present the first study of the number r B of runs of the BBWT, which is a measure of its compression power. We exhibit an infinite family of strings on which r B of the string and of its reverse differ by a multiplicative factor of Θ ( log ⁡ n ) , where n is the length of the string. We also give several theoretical results on the BBWT, including a characterization of binary strings for which the BBWT has two runs. Finally, we present experimental results and statistics on r B ( s ) and r B ( s rev ) , as well as on the number of Lyndon factors in the Lyndon factorization of s and s rev .

The study of the compressibility of repetitive sequences is an issue that is attracting great interest. We consider purely morphic words, which are highly repetitive sequences generated by iterating a morphism$\varphi$that admits a fixed point (denoted by$\varphi^{\infty}(a)$) starting from a given character$a$belonging to the finite alphabet$A$, i.e.$\varphi^{\infty}(a)=\lim\nolimits_{i\rightarrow\infty}\varphi^{i}(a)$. Such morphisms are called prolongable on$a$. Here we focus on the compressibility via the Burrows-Wheeler Transform ($BWT$) of infinite families of finite sequences generated by morphisms. In particular, denoted by$r(w)$the number of equal-letter runs of a word$w$, we provide new upper bounds on$r(\mathsf{bwt} (\varphi^{i}(a)))$, i.e. the number of equal-letter runs produced when$BWT$is applied on$\varphi^{i}(a)$. Such bounds depend on the factor complexity$f_{x}(n)$of the infinite word$x=\varphi^{\infty}(a)$, that counts, for each$n\geq 0$, the number of distinct factors of$x$having length$n$.

In recent years, pangenomes received increasing attention from the scientific community for their ability to incorporate population variation information and alleviate reference genome bias. Maximal Exact Matches (MEMs) and Maximal Unique Matches (MUMs) have proven themselves to be useful in multiple bioinformatic contexts, for example short-read alignment and multiple-genome alignment. However, standard techniques using suffix trees and FM-indexes do not scale to a pangenomic level. Recently, Gagie et al. [JACM 20] introduced the $r$-index that is a Burrows-Wheeler Transform (BWT)-based index able to handle hundreds of human genomes. Later, Rossi et al. [JCB 22] enabled the computation of MEMs using the $r$-index, and Boucher et al. [DCC 21] showed how to compute them in a streaming fashion. In this paper, we show how to augment Boucher et al.'s approach to enable the computation of MUMs on the $r$-index, while preserving the space and time bounds. We add additional $O(r)$ samples of the longest common prefix (LCP) array, where $r$ is the number of equal-letter runs of the BWT, that permits the computation of the second longest match of the pattern suffix with respect to the input text, which in turn allows the computation of candidate MUMs. We implemented a proof-of-concept of our approach, that we call mum-phinder, and tested on real-world datasets. We compared our approach with competing methods that are able to compute MUMs. We observe that our method is up to 8 times smaller, while up to 19 times slower when the dataset is not highly repetitive, while on highly repetitive data, our method is up to 6.5 times slower and uses up to 25 times less memory.