Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation
| Autor: | Hjalte Wedel Vildhøj, Søren Vind, Anders Roy Christiansen, Frederik Rye Skjoldjensen, Patrick Hagge Cording, Inge Li Gørtz, Philip Bille |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
General Computer Science
Computer science Applied Mathematics String (computer science) Concatenation Wildcard character Data_CODINGANDINFORMATIONTHEORY 0102 computer and information sciences 02 engineering and technology computer.file_format Data structure 01 natural sciences Substring Computer Science Applications 010201 computation theory & mathematics Compression (functional analysis) 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Pattern matching Algorithm computer Random access |
| Zdroj: | Bille, P, Christiansen, A R, Cording, P H, Gørtz, I L, Skjoldjensen, F R, Vildhøj, H W & Vind, S 2018, ' Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation ', Algorithmica, vol. 80, no. 11, pp. 3207-3224 . https://doi.org/10.1007/s00453-017-0380-7 |
| ISSN: | 1432-0541 0178-4617 |
| DOI: | 10.1007/s00453-017-0380-7 |
| Popis: | Given a static reference string R and a source string S, a relative compression of S with respect to R is an encoding of S as a sequence of references to substrings of R. Relative compression schemes are a classic model of compression and have recently proved very successful for compressing highly-repetitive massive data sets such as genomes and web-data. We initiate the study of relative compression in a dynamic setting where the compressed source string S is subject to edit operations. The goal is to maintain the compressed representation compactly, while supporting edits and allowing efficient random access to the (uncompressed) source string. We present new data structures that achieve optimal time for updates and queries while using space linear in the size of the optimal relative compression, for nearly all combinations of parameters. We also present solutions for restricted and extended sets of updates. To achieve these results, we revisit the dynamic partial sums problem and the substring concatenation problem. We present new optimal or near optimal bounds for these problems. Plugging in our new results we also immediately obtain new bounds for the string indexing for patterns with wildcards problem and the dynamic text and static pattern matching problem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink