Given a string S, the compressed indexing problem is to preprocess S into a compressed representation that supports fast substring queries. The goal is to use little space relative to the compressed size of S while supporting fast queries. We present a compressed index based on the Lempel–Ziv 1977 compression scheme. We obtain the following time–space trade-offs: For constant-sized alphabets (i) O(m+occlg⁡lg⁡n) time using O(zlg⁡(n/z)lg⁡lg⁡z) space, or(ii) O(m(1+[Formula presented])+occ(lg⁡lg⁡n+lgϵ⁡z)) time using O(zlg⁡(n/z)) space,For integer alphabets polynomially bounded by n (iii) O(m(1+[Formula presented])+occ(lg⁡lg⁡n+lgϵ⁡z)) time using O(z(lg⁡(n/z)+lg⁡lg⁡z)) space, or(iv) O(m+occ(lg⁡lg⁡n+lgϵ⁡z)) time using O(z(lg⁡(n/z)+lgϵ⁡z)) space,where n and m are the length of the input string and query string respectively, z is the number of phrases in the LZ77 parse of the input string, occ is the number of occurrences of the query in the input and ϵ&gt;0 is an arbitrarily small constant. In particular, (i) improves the leading term in the query time of the previous best solution from O(mlg⁡m) to O(m) at the cost of increasing the space by a factor lg⁡lg⁡z. Alternatively, (ii) matches the previous best space bound, but has a leading term in the query time of O(m(1+[Formula presented])). However, for any polynomial compression ratio, i.e., z=O(n1−δ), for constant δ&gt;0, this becomes O(m). Our index also supports extraction of any substring of length ℓ in O(ℓ+lg⁡(n/z)) time. Technically, our results are obtained by novel extensions and combinations of existing data structures of independent interest, including a new batched variant of weak prefix search.

### On the weak prefix-search problem

#### Abstract

Given a string S, the compressed indexing problem is to preprocess S into a compressed representation that supports fast substring queries. The goal is to use little space relative to the compressed size of S while supporting fast queries. We present a compressed index based on the Lempel–Ziv 1977 compression scheme. We obtain the following time–space trade-offs: For constant-sized alphabets (i) O(m+occlg⁡lg⁡n) time using O(zlg⁡(n/z)lg⁡lg⁡z) space, or(ii) O(m(1+[Formula presented])+occ(lg⁡lg⁡n+lgϵ⁡z)) time using O(zlg⁡(n/z)) space,For integer alphabets polynomially bounded by n (iii) O(m(1+[Formula presented])+occ(lg⁡lg⁡n+lgϵ⁡z)) time using O(z(lg⁡(n/z)+lg⁡lg⁡z)) space, or(iv) O(m+occ(lg⁡lg⁡n+lgϵ⁡z)) time using O(z(lg⁡(n/z)+lgϵ⁡z)) space,where n and m are the length of the input string and query string respectively, z is the number of phrases in the LZ77 parse of the input string, occ is the number of occurrences of the query in the input and ϵ>0 is an arbitrarily small constant. In particular, (i) improves the leading term in the query time of the previous best solution from O(mlg⁡m) to O(m) at the cost of increasing the space by a factor lg⁡lg⁡z. Alternatively, (ii) matches the previous best space bound, but has a leading term in the query time of O(m(1+[Formula presented])). However, for any polynomial compression ratio, i.e., z=O(n1−δ), for constant δ>0, this becomes O(m). Our index also supports extraction of any substring of length ℓ in O(ℓ+lg⁡(n/z)) time. Technically, our results are obtained by novel extensions and combinations of existing data structures of independent interest, including a new batched variant of weak prefix search.
##### Scheda breve Scheda completa Scheda completa (DC)
2013
Ferragina, Paolo
File in questo prodotto:
File
ferragina.pdf

accesso aperto

Tipologia: Documento in Post-print
Licenza: Creative commons
Dimensione 544.54 kB
Formato Adobe PDF
On the weak prefix-search problem.pdf

non disponibili

Tipologia: Versione finale editoriale
Licenza: NON PUBBLICO - accesso privato/ristretto
Dimensione 611.18 kB
Formato Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11568/211744`
• ND
• 4
• 1