<p>Suppose we have a lossless compression algorithm A, which compresses a string of length <span class="math-container">$n$</span>.The symbols in the string are chosen uniformly at random from an alphabet with cardinality <span class="math-container">$p$</span>. Different initial strings (all of length <span class="math-container">$n$</span>) will be compressed to a different extent (more uniform strings can be compressed more, etc.). Suppose <span class="math-container">$$ L_A(n,p)$$</span> is the  <strong>average</strong> length of <strong>all</strong> the compressed strings. So we know <span class="math-container">$$L_A(1,p) = 1$$</span> and <span class="math-container">$$L_A(n,1) = K$$</span> for some constant <span class="math-container">$K$</span>. Question: What is
(a) the dependence of <span class="math-container">$L_A(n,p)$</span> on <span class="math-container">$n$</span> (for fixed <span class="math-container">$p$</span>)? (b) the dependence of <span class="math-container">$L_A(n,p)$</span> on <span class="math-container">$p$</span> (for fixed <span class="math-container">$n$</span>)?
(To be specific: Let A be the LZ77 lossless compression algorithm.)</p>

CC BY-SA 4.0
2024-07-10T20:22:43.343Z
There is no guarantee that $L_A(1,p)=1$ holds for all lossless compression algorithms.  Normally, that won't be true; normally, most compression algorithms add some overhead.  Also, it's not true that $L_A(n,1)$ is a constant independent of $n$; the length of the output surely must depend on $n$.  So the question looks like it is based on faulty premises.
D.W.
CC BY-SA 4.0
2024-07-10T20:23:06.110Z
Regarding your specific questions, surely the dependence of $L_A$ depends on $A$, so I'm not sure what kind of answer your expecting; the question seems too broad.  If you only want an answer for one compression algorithm, please don't put it in a parenthetical at the end -- you should lead with that.  I'm not sure these questions about LZ77 are research-level.  What prevents you from understanding how LZ77 works, and then calculating the answer?
D.W.
<fl.formal-languages><it.information-theory><kolmogorov-complexity>
Dependence of lossless compression (e.g. Lempel-Ziv) on string length and alphabet size
Michael Mc Gettrick
# Dependence of lossless compression (e.g. Lempel-Ziv) on string length and alphabet size

(Asked by: username_0 on 2024-07-10)

Suppose we have a lossless compression algorithm A, which compresses a string of length $n$.The symbols in the string are chosen uniformly at random from an alphabet with cardinality $p$. Different initial strings (all of length $n$) will be compressed to a different extent (more uniform strings can be compressed more, etc.). Suppose $$ L\_A(n,p)$$ is the **average** length of **all** the compressed strings. So we know $$L\_A(1,p) = 1$$ and $$L\_A(n,1) = K$$ for some constant $K$. Question: What is
(a) the dependence of $L\_A(n,p)$ on $n$ (for fixed $p$)? (b) the dependence of $L\_A(n,p)$ on $p$ (for fixed $n$)?
(To be specific: Let A be the LZ77 lossless compression algorithm.)

**Tags:** fl.formal-languages, it.information-theory, kolmogorov-complexity
> **Comments:**
> **username_1**: There is no guarantee that $L_A(1,p)=1$ holds for all lossless compression algorithms.  Normally, that won't be true; normally, most compression algorithms add some overhead.  Also, it's not true that $L_A(n,1)$ is a constant independent of $n$; the length of the output surely must depend on $n$.  So the question looks like it is based on faulty premises.  
> **username_1**: Regarding your specific questions, surely the dependence of $L_A$ depends on $A$, so I'm not sure what kind of answer your expecting; the question seems too broad.  If you only want an answer for one compression algorithm, please don't put it in a parenthetical at the end -- you should lead with that.  I'm not sure these questions about LZ77 are research-level.  What prevents you from understanding how LZ77 works, and then calculating the answer?  

---

## 0 answers

