Data Structure Lower Bounds on Random Access to Grammar-Compressed Strings

Autor:	Wei Yu, Elad Verbin
Rok vydání:	2013
Předmět:	Discrete mathematics Combinatorics Character (mathematics) String (computer science) Structure (category theory) Type (model theory) Space (mathematics) Data structure Random access Exponential function Mathematics
Zdroj:	Combinatorial Pattern Matching ISBN: 9783642389047 CPM
DOI:	10.1007/978-3-642-38905-4_24
Popis:	In this paper we investigate the problem of building a static data structure that represents a string s using space close to its compressed size, and allows fast access to individual characters of s. This type of data structures was investigated by the recent paper of Bille et al. [3]. Let n be the size of a context-free grammar that derives a unique string s of length L. (Note that L might be exponential in n.) Bille et al. showed a data structure that uses space O(n) and allows to query for the i-th character of s using running time O(logL). Their data structure works on a word RAM with a word size of logL bits.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::a96d029dcde528eff516cfaf06cdcbbf https://doi.org/10.1007/978-3-642-38905-4_24 Zobrazit plný text záznamu