2026-06-10T09:07:50Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00200707 2025-01-19T21:16:29Z 1164:2592:9674:9981

Constructing the Bijective BWT Constructing the Bijective BWT Hideo, Bannai Juha, Kärkkäinen Dominik, Köppl Marcin, Piątkowski Hideo, Bannai Juha, Kärkkäinen Dominik, Köppl Marcin, Piątkowski The Burrows-Wheeler transform (BWT) is a permutation whose applications are prevalent in data compression and text indexing. The bijective BWT (BBWT) is a bijective variant of it. Although it is known that the BWT can be constructed in linear time for integer alphabets by using a linear time suffix array construction algorithm, it was up to now only conjectured that the BBWT can also be constructed in linear time. We confirm this conjecture by proposing a construction algorithm that is based on SAIS, improving the best known result of O(n lg n/ lg lg n) time to linear. The Burrows-Wheeler transform (BWT) is a permutation whose applications are prevalent in data compression and text indexing. The bijective BWT (BBWT) is a bijective variant of it. Although it is known that the BWT can be constructed in linear time for integer alphabets by using a linear time suffix array construction algorithm, it was up to now only conjectured that the BBWT can also be constructed in linear time. We confirm this conjecture by proposing a construction algorithm that is based on SAIS, improving the best known result of O(n lg n/ lg lg n) time to linear. technical report 情報処理学会 2019-11-21 application/pdf 研究報告アルゴリズム（AL） 19 2019-AL-175 1 6 2188-8566 AN1009593X https://ipsj.ixsq.nii.ac.jp/record/200707/files/IPSJ-AL19175019.pdf eng