Rank and select revisited and extended |
| |
Authors: | Veli Mäkinen Gonzalo Navarro |
| |
Affiliation: | 1. Department of Computer Science, P. O. Box 68 (Gustaf Hällströmin katu 2b), FIN-00014 University of Helsinki, Finland;2. Center for Web Research, Department of Computer Science, University of Chile, Blanco Encalada 2120, Santiago, Chile |
| |
Abstract: | The deep connection between the Burrows–Wheeler transform (BWT) and the so-called rank and select data structures for symbol sequences is the basis of most successful approaches to compressed text indexing. Rank of a symbol at a given position equals the number of times the symbol appears in the corresponding prefix of the sequence. Select is the inverse, retrieving the positions of the symbol occurrences. It has been shown that improvements to rank/select algorithms, in combination with the BWT, turn into improved compressed text indexes. |
| |
Keywords: | Succinct data structures Compressed data structures Gap encoding Range searching Position-restricted substring searching Wavelet trees Substring rank and select |
本文献已被 ScienceDirect 等数据库收录! |
|