Find an infinite set of strings that are compressable better than in $O(\log n)$ space
-
29-09-2020 - |
Question
The task is to find an infinite set of strings $a_1,a_2\ldots$, where $|a_{i+1}|>|a_i|$ and to find a compression algorithm $f$ for these strings, such that $|f(a_i)|=o(\log_2 |a_i|)$ with $i\to\infty$.
I have considered a set of strings with minimal entropy: $a_1=b, a_2=bb$, etc. The optimal compression algorithm for these strings is $f : a_i\mapsto |a_i|$, but this compresses each string only to $O(\log i)$ space.
Solution
Hint:
Instead of $a_i = b^i$, try $a_i = b^{f(i)}$ for some function $f$.
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange