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{} )\) can be induced from the BBWT of w, where \( r_B{} \) is the number of maximal same-symbol runs in the BBWT. We also show that \( 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 ) \) but having only \( r= 2 \) , where \({r}\) is the maximal same-symbol runs in the standard Burrows–Wheeler transform (BWT). However, we observe that the smallest \( r_B{} \) among all cyclic rotations of w is always at most \( r{} \) . While computing an optimal rotation yielding the smallest \( r_B\) in \( 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) \) time, where h is the (maximum) height of the two Lyndon trees which can vary from \( \log \, n \) to n. Furthermore, we conjecture that we can transform two strings having the same Parikh vector to each other by BBWT and rotation operations, and prove this conjecture for the case of binary alphabets and permutations.
