Time-Space Trade-Offs for Lempel-Ziv Compressed Indexing
| Autor: | Hjalte Wedel Vildhøj, Philip Bille, Inge Li Gørtz, Mikko Berggren Ettienne |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
FOS: Computer and information sciences
Polynomial Time-space LZ77 General Computer Science E.4 Prefix search Social Sciences Space bounds 0102 computer and information sciences 02 engineering and technology Data_CODINGANDINFORMATIONTHEORY 01 natural sciences Theoretical Computer Science Information Sources and Analysis Combinatorics Leading terms Pattern strings Integer 020204 information systems Computer Science - Data Structures and Algorithms Compression scheme 0202 electrical engineering electronic engineering information engineering C++ string handling Data Structures and Algorithms (cs.DS) Pattern matching Input string Mathematics 060201 languages & linguistics 000 Computer science knowledge general works Economic and social effects Trade offs Search engine indexing Commerce 06 humanities and the arts Substring Compressed indexing F.2.2 E.1 Time space 010201 computation theory & mathematics Bounded function 0602 languages and literature Computer Science Indexing (of information) 020201 artificial intelligence & image processing Algorithm |
| Zdroj: | Bille, P, Ettienne, M B, Gørtz, I L & Vildhøj, H W 2017, Time-space trade-offs for lempel-ziv compressed indexing . in Proceedings of 28th Annual Symposium on Combinatorial Pattern Matching . Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Leibniz International Proceedings in Informatics, 28th Annual Symposium on Combinatorial Pattern Matching, Warsaw, Poland, 04/07/2017 . https://doi.org/10.4230/LIPIcs.CPM.2017.16 |
| DOI: | 10.48550/arxiv.1706.10094 |
| Popis: | 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 + occ lg lg n ) time using O ( z lg ( n / z ) lg lg z ) space, or (ii) O ( m ( 1 + lg ϵ z lg ( n / z ) ) + occ ( lg lg n + lg ϵ z ) ) time using O ( z lg ( n / z ) ) space, For integer alphabets polynomially bounded by n (iii) O ( m ( 1 + lg ϵ z lg ( n / z ) ) + 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 ( m lg 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 + lg ϵ z lg ( n / z ) ) ) . However, for any polynomial compression ratio, i.e., z = O ( n 1 − δ ) , for constant δ > 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|