| 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 |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2019-AL-175,
号 19,
p. 1-6,
発行日 2019-11-21
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL19175019.pdf (699.3 kB)
