  The Burrows-Wheeler Transform is a string transformation that plays a
fundamental role for the design of self-indexing compressed data structures.
Over the years, researchers have successfully extended this transformation
outside the domains of strings. However, efforts to find non-trivial
alternatives of the original, now 25 years old, Burrows-Wheeler string
transformation have met limited success. In this paper we bring new lymph to
this area by introducing a whole new family of transformations that have all
the myriad virtues of the BWT: they can be computed and inverted in linear
time, they produce provably highly compressible strings, and they support
linear time pattern search directly on the transformed string. This new family
is a special case of a more general class of transformations based on context
adaptive alphabet orderings, a concept introduced here. This more general class
includes also the Alternating BWT, another invertible string transforms
recently introduced in connection with a generalization of Lyndon words.
