2026-06-17T12:43:34Z 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. 情報処理学会 2019-11-21 eng technical report https://ipsj.ixsq.nii.ac.jp/records/200707 2188-8566 AN1009593X 研究報告アルゴリズム（AL） 2019-AL-175 19 1 6 https://ipsj.ixsq.nii.ac.jp/record/200707/files/IPSJ-AL19175019.pdf application/pdf 699.3 kB 2021-11-21