Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

A bijective variant of the Burrows–Wheeler Transform using V-order

Daykin, J.W. and Smyth, W.F. (2014) A bijective variant of the Burrows–Wheeler Transform using V-order. Theoretical Computer Science, 531 . pp. 77-89.

Link to Published Version: http://dx.doi.org/10.1016/j.tcs.2014.03.014
*Subscription may be required

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 Lyndon-like factorization of a string x=x[1..n]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) [18]. Here we apply these subcomputations, along with Θ(n)Θ(n) suffix-sorting (Ko and Aluru, 2003) [26], 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)Θ(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 lex-extension orderings (Daykin et al., 2013) [19]. Motivation for this work arises in possible applications to data compression.

Item Type: Journal Article
Publisher: Elsevier BV
Copyright: © 2014 Elsevier B.V.
URI: http://researchrepository.murdoch.edu.au/id/eprint/28277
Item Control Page Item Control Page