Publication | Closed Access
Rank/select operations on large alphabets
84
Citations
0
References
2006
Year
Ranking AlgorithmEngineeringLearning To RankRank/select OperationsText MiningInformation RetrievalData MiningSize σString ProcessingCombinatorial OptimizationSelect QueriesBinary StringsSorting AlgorithmKnowledge DiscoveryText IndexingComputer ScienceData IndexingOrder-sorted LogicSearch Engine IndexingIndexing Technique
We consider a generalization of the problem of supporting rank and select queries on binary strings. Given a string of length n from an alphabet of size σ, we give the first representation that supports rank and access operations in O(lg lg σ) time, and select in O(1) time while using the optimal n lg σ + o(n lg σ) bits. The best known previous structure for this problem required O(lg σ) time, for general values of σ. Our results immediately improve the search times of a variety of text indexing methods.