|
|||||
|
|
On the possible patterns of inputs for block sorting in the Burrows-Wheeler transformation |
|
| Authors: | Takashi Saso Atsuyoshi Nakamura |
| Affiliation: | a Graduate School of Engineering, Soka University, 1-236, Tangi-cho, Hachioji-shi, Tokyo, 192-8577, Japan b Graduate School of Information Science and Technology, Hokkaido University, Kita 14, Nishi 9, Kita-ku, Sapporo, Hokkaido, 060-0814, Japan |
| 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. |
| Keywords: | Burrows-Wheeler transformation Block sorting Suffix arrays Data compression Analysis of algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ | |