Bijective BWT Based Compression Schemes

Abstract We investigate properties of the bijective Burrows-Wheeler transform (BBWT). We show that for any string w , a bidirectional macro scheme of size $$ O ( r_B{} )$$ O ( r B ) can be induced from the BBWT of w , where $$ r_B{} $$ r B is the number of maximal same-symbol runs in the BBWT. We also show that $$ r_B{} = O ( z \, \log ^{ 2 }\, n ) $$ r B = O ( z log 2 n ) , where n is the length of w and z is the number of Lempel-Ziv 77 factors of w . Then, we show a separation between BBWT and BWT by a family of strings with $$ r_B{} = \Omega ( \log \, n ) $$ r B = Ω ( log n ) but having only $$ r= 2 $$ r = 2 , where $${r}$$ r is the maximal same-symbol runs in the standard Burrows–Wheeler transform (BWT). However, we observe that the smallest $$ r_B{} $$ r B among all cyclic rotations of w is always at most $$ r{} $$ r . While computing an optimal rotation yielding the smallest $$ r_B$$ r B in $$ o ( n ^ {2} ) $$ o ( n 2 ) time remains an open problem, we show how to compute the Lyndon factorizations – a component for computing BBWT – of all cyclic rotations in O ( n ) time using right and left Lyndon trees. We also show that the optimal rotations can be computed in $$ \tilde{O} (nh) $$ O ~ ( n h ) time, where