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 character 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 = \varOmega (\log n)\) but having only \(r=2\) maximal character 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 an \(o(n^2)\) algorithm for computing an optimal rotation giving the smallest \(r_B\) is still open, we show how to compute the Lyndon factorizations – a component for computing BBWT – of all cyclic rotations in O(n) time. 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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Bijective BWT Based Compression Schemes

  • Golnaz Badkobeh,
  • Hideo Bannai,
  • Dominik Köppl

摘要

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 character 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 = \varOmega (\log n)\) but having only \(r=2\) maximal character 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 an \(o(n^2)\) algorithm for computing an optimal rotation giving the smallest \(r_B\) is still open, we show how to compute the Lyndon factorizations – a component for computing BBWT – of all cyclic rotations in O(n) time. 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.