Documents
Poster
Poster
On different variants of the Burrows-Wheeler-Transform of string collections
- Citation Author(s):
- Submitted by:
- Davide Cenzato
- Last updated:
- 5 March 2022 - 8:18am
- Document Type:
- Poster
- Document Year:
- 2022
- Event:
- Presenters:
- Davide Cenzato
- Paper Code:
- 217
- Categories:
- Keywords:
- Log in to post comments
The extended Burrows-Wheeler-Transform (eBWT), introduced by Mantaci et al. [Theor. Comput. Sci., 2007], is a generalization of the Burrows-Wheeler-Transform (BWT) to multisets of strings. While the original BWT is based on the lexicographic order, the eBWT uses the omega-order, which differs from the lexicographic order in important ways. A number of tools are available that compute the BWT of string collections; however, the data structures they generate in most cases differ from the one originally defined, as well as from each other. In this paper, we review the differences between these BWT variants, both from a theoretical and from a practical point of view, comparing them on several real-life data sets with different characteristics.