We prove that for every integer n > 0 and for every alphabet Σₖ of size k ≥ 3, there exist words of length n whose Burrows-Wheeler Transform (BWT) is totally unclustered, i. e. , it consists of exactly n runs with no two consecutive equal symbols. These words represent the worst-case behavior of the clustering effect of the BWT. We also establish a lower bound on their number. This contrasts with the binary case, where the existence of infinitely many totally unclustered BWT images is still an open problem, related to Artin’s conjecture on primitive roots.
Fici et al. (Thu,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: