Analysis and experimental evaluation of an approximation algorithm for the length of an optimal Lempel-Ziv parsing

Visa fullständig post



Permalänk

http://urn.fi/URN:NBN:fi:hulib-201908133201
Titel: Analysis and experimental evaluation of an approximation algorithm for the length of an optimal Lempel-Ziv parsing
Författare: Nietosvaara, Joonas
Medarbetare: Helsingfors universitet, Matematisk-naturvetenskapliga fakulteten
Utgivare: Helsingin yliopisto
Datum: 2019
Språk: eng
Permanenta länken (URI): http://urn.fi/URN:NBN:fi:hulib-201908133201
http://hdl.handle.net/10138/304699
Nivå: pro gradu-avhandlingar
Ämne: Tietojenkäsittelytiede
Abstrakt: We examine a previously known sublinear-time algorithm for approximating the length of a string’s optimal (i.e. shortest) Lempel-Ziv parsing (a.k.a. LZ77 factorization). This length is a measure of compressibility under the LZ77 compression algorithm, so the algorithm also estimates a string’s compressibility. The algorithm’s approximation approach is based on a connection between optimal Lempel-Ziv parsing length and the number of distinct substrings of different lengths in a string. Some aspects of the algorithm are described more explicitly than in earlier work, including the constraints on its input and how to distinguish between strings with short vs. long optimal parsings in sublinear time; several proofs (and pseudocode listings) are also more detailed than in earlier work. An implementation of the algorithm is provided. We experimentally investigate the algorithm’s practical usefulness for estimating the compressibility of large collections of data. The algorithm is run on real-world data under a wide range of approximation parameter settings. The accuracy of the resulting estimates is evaluated. The estimates turn out to be consistently highly inaccurate, albeit always inside the stated probabilistic error bounds. We conclude that the algorithm is not promising as a practical tool for estimating compressibility. We also examine the empirical connection between optimal parsing length and the number of distinct substrings of different lengths. The latter turns out to be a suprisingly accurate predictor of the former within our test data, which suggests avenues for future work.


Filer under denna titel

Totalt antal nerladdningar: Laddar...

Filer Storlek Format Granska
Nietosvaara_Joonas_Pro_gradu_2019.pdf 760.2Kb PDF Granska/Öppna

Detta dokument registreras i samling:

Visa fullständig post