On the possible patterns of inputs for block sorting in the Burrows–Wheeler transformation

On the possible patterns of inputs for block sorting in the Burrows–Wheeler transformation

0.00 Avg rating0 Votes
Article ID: iaor20114452
Volume: 111
Issue: 12
Start Page Number: 595
End Page Number: 599
Publication Date: Jun 2011
Journal: Information Processing Letters
Authors: , ,
Keywords: sorting
Abstract:

Block sorting in the Burrows–Wheeler transformation is to sort all of the n circular shifts of a string of length n lexicographically. We introduce a notion called the width of a sequence of n strings of length n and show that the values of widths are very different between the two types of sequences of strings; (1) a sequence of n randomly generated strings of length n, and (2) the sequence of n circular shifts of a randomly generated string of length n.

Reviews

Required fields are marked *. Your email address will not be published.