Revisiting (Bijective) Burrows-Wheeler Transform Space-Time Trade-Off Constructions

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 τ∈ [3..n], let σ_τ≤min(σ,τ+1) be the maximum construction-batch alphabet size. We construct either transform in O\!( n²τ logτ/loglogτ ) time and O(τσ_τ) additional space, assuming τσ_τ=O(n). This improves the transferred O((n²/τ)logτ) bound by a loglogτ factor. If σ_τ∈ wO(1), where w∈Ω(log n) is the word size, the time improves to O\!( n²τ + nlogτ/loglogτ ). For inversion, the same bounds hold with the global alphabet size $σ$ in place of σ_τ.