Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees
From MaRDI portal
Publication:672989
DOI10.1016/0304-3975(94)00298-WzbMath0874.68179OpenAlexW2073613132MaRDI QIDQ672989
Wojciech Szpankowski, Philippe Jacquet
Publication date: 28 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(94)00298-w
Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Theory of compilers and interpreters (68N20)
Related Items (15)
On the distribution for the duration of a randomized leader election algorithm ⋮ Analytical depoissonization and its applications ⋮ On optimal parsing for LZ78-like compressors ⋮ Gaussian Distribution of Trie Depth for Strongly Tame Sources ⋮ An analytic approach to the asymptotic variance of trie statistics and related structures ⋮ A general limit theorem for recursive algorithms and combinatorial structures ⋮ On the variance of a class of inductive valuations of data structures for digital search ⋮ The expected profile of digital search trees ⋮ D?E?K=(1000)8 ⋮ Size and path length of Patricia tries: Dynamical sources context ⋮ On the average redundancy rate of the Lempel-Ziv code with the \(k\)-error protocol ⋮ The Diagonal Poisson Transform and its application to the analysis of a hashing scheme ⋮ A Central Limit Theorem for Non-Overlapping Return Times ⋮ On the variance of the internal path length of generalized digital trees -- the Mellin convolution approach ⋮ The Wiener Index of Random Digital Trees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- General combinatorial schemas: Gaussian limit distributions and exponential tails
- A diffusion limit for a class of randomly-growing binary trees
- A characterization of digital search trees from the successful search viewpoint
- A functional equation often arising in the analysis of algorithms (extended abstract)
- Coding theorems for individual sequences
- Digital Search Trees Revisited
- Exact and asymptotic distributions in digital and binary search trees
- Upper bounds on the probability of sequences emitted by finite-state sources and on the redundancy of the Lempel-Ziv algorithm
- Generalized Digital Trees and Their Difference—Differential Equations
- The Lempel-Ziv algorithm and message complexity
- On the Complexity of Finite Sequences
- A universal algorithm for sequential data compression
- Compression of individual sequences via variable-rate coding
- Universal redundancy rates do not exist
- A Generalized Suffix Tree and Its (Un)Expected Asymptotic Behaviors
- Digital Search Trees Again Revisited: The Internal Path Length Perspective
- Asymptotic properties of data compression and suffix trees
- Limiting Distribution for the Depth in PATRICIA Tries
- New results on the size of tries
- Average profile and limiting distribution for a phrase size in the Lempel-Ziv parsing algorithm
This page was built for publication: Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees
