Questions tagged [data-compression]
The data-compression tag has no usage guidance.
270
questions
40
votes
7
answers
5k
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 ...
user15782
37
votes
5
answers
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 ...
- 481
35
votes
6
answers
8k
views
Do lossless compression algorithms reduce entropy?
According to Wikipedia:
Shannon's entropy measures the information contained in a message as opposed to the portion of the message that is determined (or predictable). Examples of the latter ...
- 453
35
votes
5
answers
9k
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$ ...
D.W.♦
- 159k
29
votes
7
answers
30k
views
Efficient compression of simple binary data
I have a file containing ordered binary numbers from $0$ to $2^n - 1$:
0000000000
0000000001
0000000010
0000000011
0000000100
...
1111111111
7z did not compress ...
- 484
26
votes
12
answers
11k
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 ...
- 1,602
25
votes
1
answer
1k
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 ...
- 359
23
votes
5
answers
7k
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 ...
- 1,100
23
votes
3
answers
2k
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 (...
- 333
22
votes
7
answers
10k
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:
...
- 323
20
votes
4
answers
2k
views
Compressing two integers disregarding order
Comparing an ordered pair (x,y) to an unordered pair {x, y} (set), then information theoretically, the difference is only one bit, as whether x comes first or y requires exactly a single bit to ...
- 634
19
votes
4
answers
6k
views
Can data be compressed to size smaller than Shannon data compression limit?
I was reading about data compression algorithms and the theoretical limit for data compression. Recently I encountered a compression method called "Combinatorial Entropy Encoding", the main idea of ...
- 315
18
votes
7
answers
3k
views
Can random suitless $52$ playing card data be compressed to approach, match, or even beat entropy encoding storage? If so, how?
I have real data I am using for a simulated card game. I am only interested in the ranks of the cards, not the suits. However it is a standard $52$ card deck so there are only $4$ of each rank ...
- 124
17
votes
5
answers
7k
views
Are there any compression algorithms based on PI?
What we know is that π is infinite and quite likely it contains every possible finite string of digits (disjunctive sequence).
I've seen recently some prototype of πfs which assume that every file ...
- 275
15
votes
1
answer
477
views
12
votes
4
answers
8k
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 ...
- 387
12
votes
2
answers
2k
views
Is there a generalization of Huffman Coding to Arithmetic coding?
In trying to understand the relationships between Huffman Coding, Arithmetic Coding, and Range Coding, I began to think of the shortcomings of Huffman coding to be related to the problem of fractional ...
- 6,191
10
votes
1
answer
5k
views
Why does a MP3 encoder use a fast Fourier transform before applying the psychoacoustic model?
Karlheinz Brandenburg depicts a MP3 encoder like this:
Source: MP3 and AAC Explained
I marked the FFT as I'm not quite sure why it is actually necessary to perform one. Why can't the psychoacoustic ...
- 203
9
votes
4
answers
3k
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 ...
- 264
9
votes
3
answers
13k
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 ...
user1422
8
votes
5
answers
4k
views
Using base 80 for compressing files
I want to compress file size through making my own numbering system which is 80-based number, I do really want to know whether this even possible ? I learnt that Hexadecimal uses symbols like A, B, C, ...
- 93
8
votes
4
answers
767
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 ...
- 213
8
votes
4
answers
4k
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 ...
8
votes
4
answers
1k
views
compressed information = randomness?
Suppose I have a compressed file and it is not possible to compress it more without loss of information. We say that this file is random or pseudorandom.
So, if the randomness means not ...
- 397
8
votes
1
answer
321
views
Understanding compression/encoding in linear time
I'm reading the paper N. J. Larsson, A. Moffat: Offline Dictionary-Based Compression, which describes a compression algorithm that, if I understand it correctly, is quite similar to Byte pair encoding....
- 219
7
votes
2
answers
578
views
Compression type that can be searched
Is there ANY compression type that can compress a file, and then that compressed file can be searched without uncompressing the file?
- 173
7
votes
2
answers
131
views
How to find the minimal description for an array?
The following array occupies 10000 slots in memory:
a = [0,1,2,3,4,5,6,7,8,9,10,...,10000]
But one could easily represent the same array as:
...
- 441
7
votes
2
answers
1k
views
What are all the differences between the Gibbs phenomenon artefects and JPEG artefacts?
I thought the Gibbs phenomenom is the result of Fourier analysis estimation (but was it Fourier Series estimation or can it also be Fourier Transform estimation?)
JPEG uses the Discrete cosines ...
- 91
7
votes
3
answers
618
views
Are there lossless data compression techniques that do not exploit repetitive patterns?
Lossless Data compression (source coding) algorithms heavily rely on repetitive pattern (redundancy).
Is there a Lossless Data compression method/algorithm that is independent of repetitive pattern ...
- 291
7
votes
2
answers
2k
views
How does one choose an optimal alphabet for finding a Huffman encoding?
Huffman encoding will perform best when the distribution of symbols of an alphabet that the string to be encoded uses is dyadic.
Given an arbitrary bit string S, ...
- 317
7
votes
2
answers
3k
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, ...
- 243
7
votes
1
answer
295
views
Most space-efficient lossy dictionary?
Short version: What is the most space-efficient lossy dictionary (with given false positive and false negative rates)?
Long version: A lossy dictionary is a data structure $D$ that encodes a set $S$ ...
- 391
7
votes
1
answer
407
views
LZ-type compression with a limited recursion depth
I would like to begin by apologizing. I am not a computer scientist, so my use of terminology will be off. I came across an interesting problem, which I believe to be pretty hard and would love to get ...
- 213
6
votes
1
answer
809
views
Optional prefix code for the naturals
The naturals $\mathbb{N}$ can be encoded with a binary unary code such as
$$
\begin{align}
1&=0_b\\
2&=10_b\\
3&=110_b\\
&...
\end{align}
$$
The length this the ...
- 345
6
votes
3
answers
2k
views
Arithmetic coding and "the optimal compression ratio"
Trying to learn more about compression techniques and found something in the wikipedia article on arithmetic coding that I'm not sure I fully grok. In describing how Huffman Coding can sometimes be ...
- 394
6
votes
4
answers
225
views
Minimal size of a context-free grammar which defines $L_n=\{a^k\mid 1\le k\le n\}$
I am looking for the minimal size of a context-free grammar which defines the finite language $$L_n=\{a^k\mid 1\le k\le n\}.$$
The size of a grammar is defined as the total length of all right-hand ...
- 994
6
votes
2
answers
239
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 a,b,a,aba,baaba,ab$....
6
votes
1
answer
1k
views
Why does the Huffman coding algorithm produce a valid tree?
I am not asking about the Huffman Code, but the most widely described algorithm for generating one, also described on the english wikipedia: https://en.wikipedia.org/wiki/Huffman_coding#Compression
...
6
votes
1
answer
607
views
How do incompressible strings and random strings share the same properties?
I came across the following theorem in Sipser's about incompressible strings.
Let $\;f$ be some computable function which holds for almost all strings. The for any $b > 0 $, the property $\;f$ ...
- 2,972
6
votes
1
answer
2k
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,\: 99\...
- 63
6
votes
1
answer
105
views
What properties must a string satisfy to be a possible output of the Burrows-Wheeler transform?
The Buttows-Wheeler transform is a function that takes a string $S$ to a new string $S'$ and an index $I$. The new string $S'$ is always an anagram (rearrangement) of the input string $S$.
However, if ...
- 181
6
votes
1
answer
360
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 ...
- 911
6
votes
1
answer
2k
views
How to calculate Huffman code length without generating the actual huffman code?
Given a vector of elements, how can I calculate the length of the Huffman codewords without generating the Huffman code itself?
Using Matlab, I was able to compute the Huffman code and and get the ...
- 211
6
votes
2
answers
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 ...
- 161
6
votes
1
answer
1k
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 ...
- 727
5
votes
1
answer
158
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 ...
- 153
5
votes
1
answer
10k
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 ...
user47605
5
votes
1
answer
143
views
To what factor can I compress information from binary to Quinary
I am trying to think if we can have an injective mapping $\mathcal{f}$, say something like $\Sigma_{bool}= \{0,1\}^* $ to $\Sigma_{5} = \{0,1,2,3,4\}^* $ such that $|x| \leq 2.|\mathcal{f}(x)|$
The ...
- 1,696
5
votes
0
answers
143
views
What is the intuition behind the Geometric Burrows-Wheeler Transform?
What is the intuition behind the Geometric Burrows-Wheeler Transform? And how can I use a GBWT with blocking factor $d$ to match a given pattern $P$ of length $|P| = m$ with
$m \ge d$
$m < d$
...
- 175
5
votes
0
answers
136
views
Evaluating sums of subsets
Let $X=\{x_1,...,x_N\}$ be a set of real numbers. We consider $M$ sums over its subsets, e.g. $N=9$, $M=3$
$$
\begin{align*}
s_1&=x_1+x_2+x_3+x_9,\\
s_2&=x_1+x_2+x_4+x_9,\\
s_3&=x_1+x_2+...
- 187