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

Jacqueline W. Daykin, William F. Smyth

Research output: Contribution to journalArticlepeer-review

15 Citations (Scopus)
31 Downloads (Pure)

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) suffix-sorting (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 lex-extension orderings (Daykin et al., 2013). Motivation for this work arises in possible applications to data compression.
Original languageEnglish
Pages (from-to)77-89
Number of pages13
JournalTheoretical Computer Science
Volume531
Early online date12 Mar 2014
DOIs
Publication statusPublished - 24 Apr 2014
Externally publishedYes

Keywords

  • algorithm
  • bijective
  • Burrows-Wheeler Transform
  • complexity
  • lexicographic order
  • lex-extension order
  • linear
  • lyndon word
  • string
  • suffix array
  • total order
  • V-BWT
  • V- order
  • V -transform
  • V -word
  • word

Fingerprint

Dive into the research topics of 'A bijective variant of the Burrows–Wheeler Transform using V-order'. Together they form a unique fingerprint.

Cite this