|
Title |
Alphabet-Independent Compressed Text Indexing |
|
Authors |
Djamal Belazzougui, Gonzalo Navarro |
|
Publication date |
2011 |
|
Abstract |
Self-indexes can represent a text in asymptotically optimal space under the k-th order entropy model, give access to text substrings, and support indexed pattern searches. Their time complexities are not optimal, however: they always depend on the alphabet size. In this paper we achieve, for the first time, full alphabet-independence in the time complexities of self-indexes, while retaining space optimality. We obtain also some relevant byproducts on compressed suffix trees. |
|
Downloaded |
13 times |
|
Pages |
748-759 |
|
Conference name |
Annual European Symposium on Algorithms |
|
Publisher |
Springer-Verlag (Berlin/Heidelberg, Germany) |
|
PDF |
|
|
Reference URL |
|
