Abstract
In this paper we introduce the V transform (V BWT), a variant of the classic Burrows–Wheeler Transform. The original BWT uses lexicographic order, whereas we apply a distinct total ordering of strings called V order. V order string comparison and Lyndonlike factorization of a string x = x[1..n] into V words have recently been shown to be linear in their use of time and space (Daykin et al., 2011). Here we apply these subcomputations, along with Θ(n) suffixsorting (Ko and Aluru, 2003), to implement linear V sorting of all the rotations of a string. When it is known that the input string x is a V word, we compute the V transform in Θ(n) time and space, and also outline an efficient algorithm for inverting the V transform and recovering x. We further outline a bijective algorithm in the case that x is arbitrary. We propose future research into other variants of transforms using lexextension orderings (Daykin et al., 2013). Motivation for this work arises in possible applications to data compression.
Original language  English 

Pages (fromto)  7789 
Number of pages  13 
Journal  Theoretical Computer Science 
Volume  531 
Early online date  12 Mar 2014 
DOIs  
Publication status  Published  24 Apr 2014 
Externally published  Yes 
Keywords
 algorithm
 bijective
 BurrowsWheeler Transform
 complexity
 lexicographic order
 lexextension order
 linear
 lyndon word
 string
 suffix array
 total order
 VBWT
 V order
 V transform
 V word
 word
Fingerprint
Dive into the research topics of 'A bijective variant of the Burrows–Wheeler Transform using Vorder'. Together they form a unique fingerprint.Profiles

Jacqueline Daykin
 Faculty of Business and Physcial Sciences, Department of Computer Science  Honorary Research Fellow
Person: Other