On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation.
Golnaz BadkobehTravis GagieShunsuke InenagaDmitry KosolobovSimon J. PuglisiPublished in: CoRR (2017)
Keyphrases
- compressed text
- pattern matching
- data structure
- compression scheme
- data compression
- lempel ziv
- approximate string matching
- upper bound
- exact and approximate
- compressed pattern matching
- random access
- compressed data
- worst case
- huffman coding
- compression ratio
- compression algorithm
- run length encoding
- suffix tree
- vc dimension
- upper and lower bounds
- grammatical inference
- error bounds
- lower bound
- multiscale