The Burrows-Wheeler transform (BWT) is a reversible transformation that was introduced in 1994 in the field of data compression and it has also become a fundamental tool for self-indexing data structures. It is a context-dependent transformation that produces a permutation of the input text that is likely to have runs of equal letters (clusters) longer than the ones in the original text. Such a combinatorial property of BWT make it a versatile tool also in several other applications, especially in bioinformatics [4, 6]. In [5], a complexity measure that counts the number of equal-letter runs produced by the BWT is introduced, by exploring how the number of clusters of the BWT output varies depending on the number of clusters of the input. Over the years other variants of the BWT have been proposed, without, however, obtaining transformations entirely capable of playing the same variegated role as the BWT. Very recently, a whole new class of transformations, called local ordering trasformation, has been introduced |3J. They have all the same prerogatives as BWT, i.e., they can be computed and inverted in linear time, they produce provably highly compressible output, and they support linear time pattern search directly on the transformed text. Such a class is a special case of a more general family of transformations based on context-adaptive alphabet orderings. This more general class includes also the alternating BWT (ABWT), another invertible transformation recently introduced in connection with a generalization of Lyndon words. Algorithmic and combinatorial issues on ABWT have been investigated in [1,2] In this talk an overview of the aforementioned transformations is presented, by focusing on some distinctive algorithmic and combinatorial features that could represent effective tools for investigating and handling the structure of the input text.
展开▼
