Skip to main content
Share Your Experience: Take the 2024 Developer Survey
138 votes
Accepted

Does storing plain text data take up less space than storing the equivalent message in binary?

Plaintext is binary. When you write an H to a hard drive, the write head doesn't carve two vertical lines and a horizontal line into the platter, it magnetically encodes the bits 010010001 into the ...
8bittree's user avatar
  • 5,646
119 votes
Accepted

How can lossless compression ever exist?

There can be no algorithm that losslessly compresses all inputs. But there are many algorithms that losslessly compress many inputs. And it turns out that most of the strings we like to operate on ...
Kilian Foth's user avatar
59 votes
Accepted

What is the most efficient way to store a numeric range?

Just count the number of possible ranges. There are 256 ranges with lower bound 0 (0-0, 0-1, ... 0-254, 0-255), 255 ranges with lower bound 1, ... and finally 1 range with lower bound 255 (255-255). ...
Glorfindel's user avatar
  • 3,147
35 votes

How can lossless compression ever exist?

Compression works by making more likely patterns shorter at the cost of less likely patterns Suppose we have a data format which is a string of 4 possible values, we could represent it with 2 bits ...
mousetail's user avatar
  • 458
20 votes

Does storing plain text data take up less space than storing the equivalent message in binary?

I find this a great fun thing to think about. Binary is not 1s and 0s in the way you talk about it. Imagine there is a quantity, I can tell you what quantity it is in many different ways: Nine in ...
TessellatingHeckler's user avatar
19 votes

How can lossless compression ever exist?

I recommend learning about Shannon entropy, but the simple answer is: lossless compression can't compress all inputs, but it can compress some inputs, and in practice that is enough. To demonstrate I'...
Jasmijn's user avatar
  • 1,849
17 votes

What is the most efficient way to store a numeric range?

For such small number of bits, it is infeasible to save many bits as Glorfindel has pointed out. However, if the domain you are using has a few more bits, you can achieve significant savings for the ...
Polygnome's user avatar
  • 2,066
15 votes
Accepted

compression algorithm for non-repeating integers

You have to consider that compression - by which I assume you mean lossless compression - equates to the removal of redundant information. If you write 12,12,12,12,12 there's redundance and you can ...
LSerni's user avatar
  • 2,441
15 votes
Accepted

Is it possible to store N bits of unique combinations, in N-1 bits? If not; why does MD5 get reprimanded for collissions?

Of course, the pigeonhole principle states that colisions are inevitable for hashing algorithms. The point of hashing algorithms is not to prevent colisions. But to make intentional collisions ...
Euphoric's user avatar
  • 37.5k
14 votes

Does storing plain text data take up less space than storing the equivalent message in binary?

Does storing plain text data take up less space than storing the equivalent message in binary? No, never. Your computer already stores the plain text data in the equivalent binary representation. ...
Telastyn's user avatar
  • 109k
12 votes

How can lossless compression ever exist?

For example, if you had a file with 16 bit audio, you can obviously represent it with 16 bit per sample. However, a simple lossless compressor will have an algorithm that predicts the next sample, and ...
gnasher729's user avatar
  • 45.7k
11 votes

How to review sql changes more effectively?

You may not like this, but: This is not a problem to be solved easily by additional technologies or tools. An SQL which contains "long nested queries, sometimes calling other procedures" and cannot ...
Doc Brown's user avatar
  • 209k
10 votes
Accepted

Best two-way compression algorithm for 32-bit numbers

A 32-bit id is so little data with so little redundancy to exploit that a true "compression algorithm" is likely not going to help much. On the other hand, simply using a higher numeric base where you ...
Ixrec's user avatar
  • 27.6k
9 votes
Accepted

Best compression algorithm for timelapse photos

That's an interesting question: can popular compression algorithms still make use of the redundancy in frames after they've been individually compressed, or is the individual compression too good to "...
Kilian Foth's user avatar
9 votes

Load and process (compressed) data from filesystem in the blink of an eye

profiling measurements It sounds like you do not yet know where the CPU cycles go, or, more importantly, the sources of I/O + network delay. I didn't see any numeric figures, let alone 98th percentile ...
J_H's user avatar
  • 7,156
8 votes

What is the most efficient way to store a numeric range?

This kind of problem is the subject of Claude Shannon’s seminal paper, A Mathematical Theory of Communication, which introduced the word “bit” and more or less invented data compression. The general ...
Patrick McElhaney's user avatar
8 votes
Accepted

How is it possible to GZIP a stream before the entire contents are known?

Your understanding concerns static compression, where the whole dataset is available when you begin compression. In a very simplified way, yes it replaces common sequences with smaller tokens to ...
Kayaman's user avatar
  • 1,950
7 votes
Accepted

How can I reduce the amount of storage needed for a gravitational n-body simulation?

Float Warning Be aware of floating point precision. The mantessa is only x bits long, which means that for values close to zero they can express very small distances, but at galactic distances the ...
Kain0_0's user avatar
  • 16.2k
7 votes

How can lossless compression ever exist?

If our data was sequences of random values, and longer sequences were less likely than shorter ones, then lossless compression would on-average be worse than useless. But our data is far from random ...
Peter Green's user avatar
  • 2,251
6 votes

Best compression algorithm for timelapse photos

Methods of data compression that exploit redundancy between individual data groups of a set (usually a set of similar images) are named Set Redundancy Compression (SRC was proposed firstly by Kosmas ...
manlio's user avatar
  • 4,216
6 votes
Accepted

some misunderstanding in concept of Huffman algorithm

What is difference between Average length of codes and Average length of codewords By definition, an alphabet is a set of things {A1, . . . , AN} that we might wish to encode. A code C is a mapping ...
lennon310's user avatar
  • 3,222
6 votes

Is it possible to store N bits of unique combinations, in N-1 bits? If not; why does MD5 get reprimanded for collissions?

A hash function maps a larger (potentially infinite) input space into a smaller (usually finite) output space. As a result, every hash function must have collisions. This is a consequence of the ...
Jörg W Mittag's user avatar
5 votes
Accepted

Advantages of application-level data compression?

In an ideal system (read: well programmed), specific is more efficient than generic, but generic is more broadly applicable. You save development time using generic, you save user time using specific. ...
Kevin Fee's user avatar
  • 2,837
4 votes
Accepted

How to deal with large data in Websocket message?

I'll propose an answer since it's been nearly a year. As @Walfrat has pointed out: Note that if you're echanging too much data, it might also be a design problem that would lead to poor ...
Jeff's user avatar
  • 1,844
4 votes

compression algorithm for non-repeating integers

Edit: According to you, you are actually doing this: I have 1024 datasets of size 512 where where each value is a distinct integer between 1 and N (or 0 and N-1), i.e., a permutation of a set of N ...
Krupip's user avatar
  • 1,300
4 votes

A collision-free hash-like function for use in hash tables and other data structures?

You write "Idea #1: use the positional number of a string in the table as its unique ID." but this is not how sequences work. If you want to avoid contention around the sequences, you use sequence ...
JimmyJames's user avatar
  • 27.5k
4 votes
Accepted

Find Randomized Sequence Seed To Compress files statistically

This will not work. A given n-bit seed can only produce at most 2^n distinct sequences. I.e. for m-bit data where m > n, there will be data bit patterns that are produced by no seed. Adding extra ...
amon's user avatar
  • 134k
4 votes
Accepted

Why does WinRAR not compress picture duplicates?

There may not be any differences in the duplicate files, but it takes a lot of effort to notice and verify this. Essentially, you'd have to compare each pair of duplicate files byte for byte in ...
Kilian Foth's user avatar
4 votes

PDF content : text or graphics?

Edited to directly address Massimo's requirement that no external code be used (a.k.a. clean room development). At the minimum, one has to implement all of the mechanics to parse (but not render) ...
rwong's user avatar
  • 16.9k
4 votes
Accepted

Fast, lossless compression of a video stream

You've got temporal prediction, but no spatial. For better compression at the cost of speed, you should be able to use the pixels above and to the left of the current pixel in the current frame as ...
hobbs's user avatar
  • 1,311

Only top scored, non community-wiki answers of a minimum length are eligible