Logo image
Back
A bijective variant of the Burrows–Wheeler Transform using V-order
Journal article   Peer reviewed

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

J.W. Daykin and W.F. Smyth
Theoretical Computer Science, Vol.531, pp.77-89
2014
DOI: https://doi.org/10.1016/j.tcs.2014.03.014
url
Link to Published Version *Subscription may be requiredView

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.

Details

Metrics

76 Record Views
12 Times Cited - Web of Science

InCites Highlights

These are selected metrics from InCites Benchmarking & Analytics tool, related to this output

Collaboration types
Domestic collaboration
International collaboration
Citation topics
4 Electrical Engineering, Electronics & Computer Science
4.182 Data Structures, Algorithms & Complexity
4.182.1103 Efficient Algorithms
Web Of Science research areas
Computer Science, Theory & Methods
ESI research areas
Computer Science
Logo image