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 <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2024_10212_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="60" /> </InlineMediaObject> <EquationSource Format="TEX">$\Theta (\log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, 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 <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2024_10212_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="60" /> </InlineMediaObject> <EquationSource Format="TEX">$\Theta (\log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-factor. As regards the multiplicative factor, they attain the upper bound given by Akagi, Funakoshi, and Inenaga [Inf & Comput. 2023] of <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2024_10212_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="95" /> </InlineMediaObject> <EquationSource Format="TEX">$\mathcal{O}(\log n \log r)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>n</mi> <mo>log</mo> <mi>r</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, since here <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2024_10212_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="66" /> </InlineMediaObject> <EquationSource Format="TEX">$r=\mathcal{O}(1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>=</mo> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. We then give examples of strings in which insertion, deletion, resp. substitution of a character increases r by a <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2024_10212_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">$\Theta (\sqrt{n})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <msqrt> <mi>n</mi> </msqrt> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> additive factor. These strings significantly improve the best known lower bound for an additive factor of <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2024_10212_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="59" /> </InlineMediaObject> <EquationSource Format="TEX">$\Omega (\log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> [Giuliani et al., SOFSEM 2021].

Bit Catastrophes for the Burrows-Wheeler Transform

期刊论文
出版模式：

开放获取
发表日期：

2025年4月15日

查看全文

Sara Giuliani,
Shunsuke Inenaga,
Zsuzsanna Lipták,
Giuseppe Romana,
Marinella Sciortino,
Cristian Urbina

摘要

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})$ $Θ (\sqrt{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].