Questions tagged [data-compression]

The tag has no usage guidance.

240 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
7k 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$ ...
22k 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 ...
10k 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 ...
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 ...
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 (...
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 ...
9k 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: ...
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 ...
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 ...
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 ...
455 views

...
5k 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 ...
7k views

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 ...
134 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$ ...
130 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+...
Huffman and Hu-Tucker codes are well-known compression schemes, which both come close to the entropy lower bound. It is known that if $L_1$ and $L_2$ are the lengths of a Huffman resp. Hu-Tucker code, ...