2026-10-20T18:36:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7325 2024-03-06T09:40:07Z ddc:004 open_access

Time-Space Trade-Offs for Lempel-Ziv Compressed Indexing Bille, Philip Ettienne, Mikko Berggren Gørtz, Inge Li Vildhøj, Hjalte Wedel compressed indexing pattern matching LZ77 prefix search 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. Let n, and z denote the size of the input string, and the compressed LZ77 string, respectively. We obtain the following time-space trade-offs. Given a pattern string P of length m, we can solve the problem in (i) O(m + occ lglg n) time using O(z lg(n/z) lglg z) space, or (ii) O(m(1 + lg^e z / lg(n/z)) + occ(lglg n + lg^e z)) time using O(z lg(n/z)) space, for any 0 < e < 1 In particular, (i) improves the leading term in the query time of the previous best solution from O(m lg m) to O(m) at the cost of increasing the space by a factor lglg z. Alternatively, (ii) matches the previous best space bound, but has a leading term in the query time of O(m(1+lg^e z / lg(n/z))). However, for any polynomial compression ratio, i.e., z = O(n^{1-d}), for constant d > 0, this becomes O(m). Our index also supports extraction of any substring of length l in O(l + 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Philip Bille and Mikko Berggren Ettienne and Inge Li Gørtz and Hjalte Wedel Vildhøj 2017 Is Part Of LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2017.16 urn:nbn:de:0030-drops-73254 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.16 eng https://creativecommons.org/licenses/by/3.0/legalcode