Constructing the Bijective BWT

• Item type: SIG Technical Reports(1)
• 公開日: 2019-11-21
• タイトル: Constructing the Bijective BWT
• タイトル / 言語: en
• タイトル: Constructing the Bijective BWT
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Department of Informatics, Kyushu University
• 著者所属: Helsinki Institute of Information Technology (HIIT)
• 著者所属: Department of Informatics, Kyushu University / Japan Society for Promotion of Science
• 著者所属: Nicolaus Copernicus University
• 著者所属(英): en
• 著者所属(英): Department of Informatics, Kyushu University
• 著者所属(英): en
• 著者所属(英): Helsinki Institute of Information Technology (HIIT)
• 著者所属(英): en
• 著者所属(英): Department of Informatics, Kyushu University / Japan Society for Promotion of Science
• 著者所属(英): en
• 著者所属(英): Nicolaus Copernicus University
• 著者名: Hideo, Bannai; Juha, Kärkkäinen; Dominik, Köppl; Marcin, Piątkowski
• 著者名(英): Hideo, Bannai; Juha, Kärkkäinen; Dominik, Köppl; Marcin, Piątkowski
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2019-AL-175, 号 19, p. 1-6, 発行日 2019-11-21
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会