The data-compression tag has no wiki summary.
4
votes
2answers
85 views
Lossless data compression must make some messages longer? [duplicate]
I read on Wikipedia and in lecture notes that if a lossless data compression algorithm makes a message shorter, it must make another message longer.
E.g. In this set of notes, it says:
Consider, ...
1
vote
2answers
80 views
How optimal is Lempel-Ziv at reaching the Shannon limit?
I find this a bit difficult to describe, but I am interested in the following idea :
The LZ algorithm factors (verb) an input stream into adjacent factors, these are by definition the maximal ...
5
votes
2answers
78 views
Behavior of iterative application of LZ77
I have been experimenting with LZ77 (naively $O(n^2)$ runtime, infinite window). Applying it to the 7th Fibonacci word $abaababaabaab$ yields the correct LZ factorization:
$\qquad ...
1
vote
0answers
33 views
Bayesian Coding
Suppose you have a sequence generated by an i.i.d. process (such as repeatedly rolling a die and recording the values in order) parameterized by some K-dimensional vector $\vec{\gamma}$ (the ...
3
votes
1answer
88 views
Algorithm for determining minimal set of covering prefixes
I have a set of strings. My goal is to find a minimal set of longest prefixes which will match most of that set.
For instance, if my set is:
...
5
votes
3answers
247 views
No compression algorithm can compress all input messages?
I just started reading a book called Introduction to Data Compression, by Guy E. Blelloch. On page one, he states:
The truth is that if any one message is shortened by an algorithm, then some ...
5
votes
1answer
219 views
Will this algorithm terminate on any input?
One can compress data with straight-line grammars. An algorithm that employs this technique is called Sequitur. If I understood correctly, Sequitur basically starts with one rule representing the ...
3
votes
1answer
206 views
Minimum space needed to sort a stream of integers
This question has gotten a lot of attention on SO:
Sorting 1 million 8-digit numbers in 1MB of RAM
The problem is to sort a stream of 1 million 8-digit numbers (integers in the range $[0,\: ...
2
votes
1answer
51 views
Compression of sequence with Direct Access
I have a sequence of $n$ integers in a small range $[0, k)$ and all the integers have the same frequency $f$ (so the size of the sequence is $n = f * k$). What I'm trying to do now is to compress this ...
8
votes
1answer
109 views
Approximating the Kolmogorov complexity
I've studied something about the Kolmogorov Complexity, read some articles and books from Vitanyi and Li and used the concept of Normalized Compression Distance to verify the stilometry of authors ...
2
votes
4answers
326 views
Is there any theoretically proven optimal compression algorithm?
Is Huffman coding always optimal since it uses Shanon's ideas?
What about text, image, video, ... compression?
Is this subject still active in the field? What classical or modern references should I ...
5
votes
3answers
302 views
Is Huffman Encoding always optimal?
The requirement of the encoding to be prefix free results in large trees due to the tree having to be complete. Is there a threshold where fixed-length non-encoded storage of data would be more ...
5
votes
1answer
125 views
Measuring entropy for a table (e.g., SQL results)
We're running some benchmarks for an approximative query-answering system. It's sufficient to just think of it as running some SQL queries with joins. We are counting the results returned as part of ...
3
votes
0answers
32 views
Lossless Video Compression Pipeline
The only paper I can find about an implementation of a lossless video codec is an article by Michael Niedermayer which explains the FF1V compression pipeline.
I'm wondering if anyone else has found ...
1
vote
0answers
112 views
Optimal asymptotic space complexity after binary-tree compression? [closed]
What is the optimal asymptotic space complexity of a tree after binary-tree compression (without using probablistic techniques)?
E.g. from the (optimal?) techniques shown by Chen, Shenfeng, and John ...
5
votes
1answer
92 views
Why are blocking artifacts serious when there is fast motion in MPEG?
Why are blocking artifacts serious when there is fast motion in MPEG?
Here is the guess I made:
In MPEG, each block in an encoding frame is matched with a block in the reference frame.
If the ...
2
votes
1answer
112 views
Distinguishing between uppercase and lowercase letters in the “move-to-front” method
Is it not necessary to encode both the uppercase and lowercase letter while encoding a message with the move-to-front transform? From an old computer science course exam, the problem was to encode ...
7
votes
1answer
181 views
Compression of domain names
I am curious as to how one might very compactly compress the domain of an arbitrary IDN hostname (as defined by RFC5890) and suspect this could become an interesting challenge. A Unicode host or ...
