Questions tagged [data-compression]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
33
votes
5answers
6k views

Enumerate all non-isomorphic graphs of a certain size

I'd like to enumerate all undirected graphs of size $n$, but I only need one instance of each isomorphism class. In other words, I want to enumerate all non-isomorphic (undirected) graphs on $n$ ...
8
votes
4answers
2k 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 other ...
39
votes
7answers
4k views

Can PRNGs be used to magically compress stuff?

This idea occurred to me as a kid learning to program and on first encountering PRNG's. I still don't know how realistic it is, but now there's stack exchange. Here's a 14 year-old's scheme for an ...
10
votes
4answers
6k views

Compression of Random Data is Impossible?

A few days ago this appeared on HN http://www.patrickcraig.co.uk/other/compression.htm. This refers to a challenge from 2001 - where someone was offering a prize of \$5000 for any kind of reduction to ...
6
votes
2answers
2k views

Compressing normally distributed data

Given normally distributed integers with a mean of 0 and a standard deviation $\sigma$ around 1000, how do I compress those numbers (almost) perfectly? Given the entropy of the Gaussian distribution, ...
25
votes
11answers
9k views

Is von Neumann's randomness in sin quote no longer applicable?

Some chap said the following: Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin. That's always taken to mean that you can't generate ...
7
votes
4answers
628 views

Compression functions are only practical because “The bit strings which occur in practice are far from random”?

I would have made a comment, as this pertains to Andrej Bauer's answer in this thread; however, I believe it is worth a question. Andrej explains that given the set of all bit strings of length 3 or ...
38
votes
5answers
6k views

Is there a known maximum for how much a string of 0's and 1's can be compressed?

A long time ago I read a newspaper article where a professor of some sort said that in the future we will be able to compress data to just two bits (or something like that). This is of course not ...
21
votes
7answers
8k views

Why are these (lossless) compression methods of many similar png images ineffective?

I just came across the following thing: I put multiple identical copies of a png image into a folder and then tried to compress that folder with the following methods: ...
23
votes
3answers
1k 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 (...
23
votes
5answers
6k views

Data compression using prime numbers

I have recently stumbled upon the following interesting article which claims to efficiently compress random data sets by always more than 50%, regardless of the type and format of the data. Basically ...
8
votes
4answers
3k 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 ...
1
vote
2answers
92 views

Arithmetic code: from interval to code value

I've not clear how to pass from final interval to code value, for example: Suppose we have the set of symbols={0,1,2,3} with probability={0.2, 0.5, 0.2 , 0.1} and that we have to encode a source S={2,...
6
votes
1answer
5k views

Does there exist a data compression algorithm that uses a large dataset distributed with the encoder/decoder?

If my goal were to compress say 10,000 images and I could include a dictionary or some sort of common database that the compressed data for each image would reference, could I use a large dictionary ...
4
votes
1answer
77 views

Why does the last step of Decompression Transformation of the cited report work?

The report referred in the title is the following: A Block-sorting Lossless Data Compression Algorithm, by M. Burrows and D.J. Wheeler, SRC Research Report, 1994 The step I do not understand is step ...
4
votes
1answer
6k views

When would the worst case for Huffman coding occur?

I am doing a project on Huffman coding and wanted to know when it wouldn't be ideal to use or rather when would the Huffman coding produce low compression. Since it mainly revolves around the ...
3
votes
2answers
4k views

How to decode multiple-digit gamma codes and get the gap sequence?

How to decode gamma code ($\gamma$ code): 1110001110101011111101101111011 and get the gap sequence? Detailed information about Gamma codes ($\gamma$ codes) ...
3
votes
1answer
397 views

Is there a limit to data compression without mentioning Kolmogorov complexity?

I want to develop a previous answer to Is there a known maximum for how much a string of 0's and 1's can be compressed?. I've looked at the Hutter Prize and various compression benchmarks. The ...
2
votes
2answers
596 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 ...
0
votes
0answers
29 views

How to decode multiple-digit gamma codes and get the gap sequence? [duplicate]

How to decode gamma code ($\gamma$ code): 1110001110101011111101101111011 and get the gap sequence? Detailed information about Gamma codes ($\gamma$ codes) ...
0
votes
1answer
83 views

Compression technique exploiting common similarities

I asked this on StackOverflow, but it was determined more appropriate to post here. So it goes like this.. For people concerned about users having slow connections and timeout issues, it is known ...