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

Näytä kaikki kuvailutiedot



Pysyväisosoite

http://urn.fi/URN:NBN:fi:hulib-201908133201
Julkaisun nimi: Analysis and experimental evaluation of an approximation algorithm for the length of an optimal Lempel-Ziv parsing
Tekijä: Nietosvaara, Joonas
Muu tekijä: Helsingin yliopisto, Matemaattis-luonnontieteellinen tiedekunta
Julkaisija: Helsingin yliopisto
Päiväys: 2019
Kieli: eng
URI: http://urn.fi/URN:NBN:fi:hulib-201908133201
http://hdl.handle.net/10138/304699
Opinnäytteen taso: pro gradu -tutkielmat
Oppiaine: Tietojenkäsittelytiede
Tiivistelmä: 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.


Tiedostot

Latausmäärä yhteensä: Ladataan...

Tiedosto(t) Koko Formaatti Näytä
Nietosvaara_Joonas_Pro_gradu_2019.pdf 760.2KB PDF Avaa tiedosto

Viite kuuluu kokoelmiin:

Näytä kaikki kuvailutiedot