Skip to main content
Login | Suomeksi | På svenska | In English

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

Show full item record

Title: Analysis and experimental evaluation of an approximation algorithm for the length of an optimal Lempel-Ziv parsing
Author(s): Nietosvaara, Joonas
Contributor: University of Helsinki, Faculty of Science, Tietojenkäsittelytieteen osasto
Discipline: Tietojenkäsittelytiede
Language: English
Acceptance year: 2019
Abstract:
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.


Files in this item

Files Size Format View
Nietosvaara_Joonas_Pro_gradu_2019.pdf 760.2Kb PDF

This item appears in the following Collection(s)

Show full item record