An alphabet-friendly FM-index

We show that, by combining an existing compression boosting technique with the wavelet tree data structure, we are able to design a variant of the FM-index which scales well with the size of the input alphabet ∑. The size of the new index built on a string T[1, n] is bounded by nH_κ(T)+O((n log log n)/ log_|∑| n) bits, where H_κ(T) is the κ-th order empirical entropy of T. The above bound holds simultaneously for all κ < α log_|∑| n and 0 < α < 1. Moreover, the index design does not depend on the parameter κ, which plays a role only in analysis of the space occupancy. Using our index, the counting of the occurrences of an arbitrary pattern P[1, p] as a substring of T takes O(p log |∑|) time. Locating each pattern occurrence takes O(log |∑| (log² n/ log log n)) time. Reporting a text substring of length ℓ takes O((ℓ + log² n/ log log n) log |∑|) time.