Let @math @math be a given set of @math string documents of total length @math , our task is to index @math , such that the @math most relevant documents for an online query pattern @math of length @math can be retrieved efficiently. We propose an index of size @math bits and @math query time for the basic relevance metric , where @math is the size (in bits) of a compressed full text index of @math , with @math time for searching a pattern of length @math . We further reduce the space to @math bits, however the query time will be @math , where @math is the alphabet size and @math is any constant.
@cite_2: Self-indexes are able to represent a text asymptotically within the information-theoretic lower bound under the kth order entropy model and offer access to any text substring and indexed pattern searches. Their time complexities are not optimal, however; in particular, they are always multiplied by a factor that depends on the alphabet size. In this article, we achieve, for the first time, full alphabet independence in the time complexities of self-indexes while retaining space optimality. We also obtain some relevant byproducts.
Table gives a summary of the major results in the top- @math frequent document retrieval problem. The time complexities are simplified by assuming that we are using the full text index proposed by Belazzougui and Navarro, of size @math bits and @math , where @math is the @math th order empirical entropy of @math @cite_2 . We also assume @math for some @math and @math is any constant.