On Bijective Variants of the Burrows-Wheeler Transform

Details On Bijective Variants of the Burrows-Wheeler Transform On Bijective Variants of the Burrows-Wheeler Transform

2009-08-03

arxiv.org/abs/0908.0239v1

Computer Science

Data Structures and Algorithms

15 pages, presented at the Prague Stringology Conference 2009 (PSC 2009)

Scientific paper

The sort transform (ST) is a modification of the Burrows-Wheeler transform (BWT). Both transformations map an arbitrary word of length n to a pair consisting of a word of length n and an index between 1 and n. The BWT sorts all rotation conjugates of the input word, whereas the ST of order k only uses the first k letters for sorting all such conjugates. If two conjugates start with the same prefix of length k, then the indices of the rotations are used for tie-breaking. Both transforms output the sequence of the last letters of the sorted list and the index of the input within the sorted list. In this paper, we discuss a bijective variant of the BWT (due to Scott), proving its correctness and relations to other results due to Gessel and Reutenauer (1993) and Crochemore, Desarmenien, and Perrin (2005). Further, we present a novel bijective variant of the ST.

Affiliated with

Also associated with

No associations

Rating

On Bijective Variants of the Burrows-Wheeler Transform does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Bijective Variants of the Burrows-Wheeler Transform, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Bijective Variants of the Burrows-Wheeler Transform will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-453855