Sublinear Algorithms for Approximating String Compressibility

Sublinear Algorithms for Approximating String Compressibility

We raise the question of approximating the compressibility of a string with respect to a fixed compression scheme, in sublinear time. We study this question in detail for two popular lossless compression schemes: run-length encoding (RLE) and a variant of Lempel-Ziv (LZ77), and present sublinear alg...

Full description

Bibliographic Details
Main Authors: Raskhodnikova, Sofya, Ron, Dana, Rubinfeld, Ronitt, Smith, Adam
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Article
Language:en_US
Published: Springer-Verlag 2012
Online Access:http://hdl.handle.net/1721.1/73520
https://orcid.org/0000-0002-4353-7639

Internet

http://hdl.handle.net/1721.1/73520
https://orcid.org/0000-0002-4353-7639

Similar Items