| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427305 | Information Processing Letters | 2011 | 5 Pages |
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.
► We compare patterns of two types of sequences of n strings of length n. ► A first type sequence is a sequence of n independent random strings. ► A second type sequence is the sequence of n circular shifts of one random string. ► We define a notion called the “width” of a sequence of n strings of length n. ► Second type sequences have smaller widths than first type sequences.
