Faster space efficient algorithms improve bijective Burrows-Wheeler transform
Revisiting (Bijective) Burrows-Wheeler Transform Space-Time Trade-Off Constructions
Data Structures and Algorithms
Summary
Data compression often uses a method called the Burrows-Wheeler transform (BWT), which rearranges data to make it more compressible. The authors study a special version called the bijective BWT (BBWT) that uses a more complex sorting approach but has benefits like removing a special delimiter. They improved known algorithms that compute and invert the BBWT so they run faster while using little extra memory. This means BBWT could be more practical for large data with limited space.
What this means in practice
- •For data compression engineers: Build compression tools that efficiently transform data with limited memory by using improved BBWT algorithms for faster compression and decompression.
- •For bioinformatics software developers: Implement memory-aware genome indexing algorithms that leverage faster BBWT constructions to handle very large DNA sequence datasets.
Authors
Dominik Köppl, Tomohiro I
Abstract
The bijective Burrows-Wheeler transform (BBWT) replaces the delimiter of the ordinary BWT by a Lyndon factorization and sorts factor conjugates in $ω$-order. It admits quadratic-time constant-workspace algorithms and linear-time linear-space algorithms. We extend the small-space BWT trade-off of Crochemore et al. [JDA,'15] to the BBWT and accelerate both constructions. For $τ\in [3..n]$, let $σ_τ\le\min(σ,τ+1)$ be the maximum construction-batch alphabet size. We construct either transform in $ O\!\left( \frac{n^2}τ \frac{\logτ}{\log\logτ} \right) $ time and $O(τσ_τ)$ additional space, assuming $τσ_τ=O(n)$. This improves the transferred $O((n^2/τ)\logτ)$ bound by a $\log\logτ$ factor. If $σ_τ\in w^{O(1)}$, where $w\inΩ(\log n)$ is the word size, the time improves to $ O\!\left( \frac{n^2}τ + \frac{n\logτ}{\log\logτ} \right). $ For inversion, the same bounds hold with the global alphabet size $σ$ in place of $σ_τ$.