文章基本信息

标题：Constructing the Bijective and the Extended Burrows-Wheeler Transform in Linear Time
本地全文：下载
作者：Bannai, Hideo ; K\"{a}rkk\"{a}inen, Juha ; K\"{o}ppl, Dominik 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：191
页码：7:1-7:16
DOI：10.4230/LIPIcs.CPM.2021.7
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 in the word RAM model 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. Since we can reduce the problem of constructing the extended BWT to constructing the BBWT in linear time, we obtain a linear-time algorithm computing the extended BWT at the same time.
关键词：Burrows-Wheeler Transform; Lyndon words; Circular Suffix Array; Suffix Array Construction Algorithm