136

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 platter. From there, it should be obvious that storing plain text data takes up exactly the same amount of space as storing binary data. But plaintext is just ...


58

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). So the total number is (256 + 255 + ... + 1) = 257 * 128 = 32,896. As this is slightly higher than 215 = 32,768, you'll still need at least 16 bits (2 bytes) to ...


18

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 English Neuf in French 9 in Arabic numerals IX in Roman numerals 1001 in Binary with Arabic numerals on off off on in Binary with on/off high low low high in ...


17

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 average case by encoding ranges with the start value and a delta. Lets assume the domain is the integers, so 32 bits. With the naive approach, you need 64 bits (...


15

How is it possible to reduce an image by 90% without losing quality? Formats and compression options There are three popular image storage formats for web (not counting the promising WebP), and each format has its own compression options. A clueless coder may pick the wrong format and use wrong options, resulting in less-than-optimal image quality and ...


14

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. Storing something as plain text versus binary just signals how the computer should interpret that identical binary stream. It seems to me like using letters ...


13

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 write it as 12*5. So you need to find the information that you can make redundant. For example the sequence 1,2,3,4,5,6,7,18,19,20,21 is nonrepeating, yet there ...


11

Huffman codes have their basis in the probability that a given character will appear in a sequence. This is why when generating a Huffman prefix tree, the most common characters (those with the highest probability of appearing) are given priority for the shortest prefix. For example, in the sample text "ABAABACABEDCA" the character 'A' appears 6 times and ...


11

It's called deduplication. Some filesystems do it (like ZFS), some block-level storage systems do it (like NetApp), some backup systems do it (rsnapshot), source code managment systems do it (Git, bzr, fossil) It's not so rare, just that until recently it was an expensive option for generic filesystems. Note that it's not a good idea to do it as you ...


11

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 be easily understood should at least have proper indentation and comments. Otherwise, it will become an unmaintainable mess. So if it is really that hard to ...


9

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 use letters as well as digits to represent the number probably accomplishes exactly what you're after. For example, here's the largest possible 32-bit integer ...


9

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 "leave traces"? I don't know, and you'd have to try it out to get a reliable answer. However, it's almost certainly a better idea to store all these frames as a ...


8

If anybody interested I ended up using gzip from zlib. Never figured out why LZ4 doesn't work, as suggested in the comments this could be an endianess problem or a 64/32-bit mismatch. However, I tested this on a single machine compressing and decompressing a local file. The same compilation settings worked for gzip. C/C++ sample compressor code int ...


8

You need to look a little closer at the format page on the FLAC website. The "prediction" paragraph leads to this article, which describes the AudioPak algorithm in detail, and also Shorten. You should learn and understand these algorithms and the associated math before digging into the source code. That might take awhile.


8

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 idea is that the number of bits used to encode a range is inversely proportional to the probability of that range occurring. For example, suppose the range 45-...


7

The most compact possible representation of your arrays would be 1 bit per entry. You have two arrays, each of length 6. I.e. your compressed file is 6+6 bits long, while your original file is 6 bits long. This is an increase of 100%. Also, as @jk pointed out in his comment: your second array is identical to your input data. The first array is identical to ...


7

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 error can be quite significant. It also makes a number of logical compression techniques harder. Fixed Point Deltas If you were to go with fixed-point numbers ...


7

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 achieve compression. There are many cases where this won't even result in efficient compression (if done in a naive way), such as skewed data distribution (think "...


6

To solve this you need to create the huffman tree and compute the bits needed to represent every symbol. Then you can compute total bits needed for original string in huffman encoding and divide by number of characters. First you map your input string based on the original character encoding : 00 A 10 B 10 B 01 C 01 C 01 C 00 A 10 B 11 D 01 C 01 C 01 C 01 ...


6

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 Karadimitriou in 1996). There are four well-known types of SRC techniques: Min-Max differential method (MMD) Min-Max predictive method (MMP) centroid method ...


5

Normally, a hash is calculated before compression. That way, the receiver can verify the hash after decompression, which verifies not only the data transmission but also the compression and decompression implementations.


5

Both LZ4 and Snappy has been ported to .NET recently. You can find LZ4 .NET port here at http://lz4net.codeplex.com. You can find Snappy .NET port (actually P/Invoke wrapper) here at http://snappy4net.codeplex.com. You can also check performance comparison (of .NET ports) here. To answer your question I did use both to test C++ compression and C# ...


5

Since you allow false positives, you do not need a perfect hash. Instead, you can use a bloom filter. A bloom filter consists of a bit vector and a set of different hash functions. To add an item to the bloom filter, you has the item with each hash function and use each hash as an index to the bit vector. You then set each addressed bit to true. To test ...


5

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. A good example would be images. If you used TCP's gzip compression on a bitmap, which has no built in compression, you are applying a purely generic solution. ...


4

According to Wikipedia: Rather than try to simulate infinite precision, most arithmetic coders instead operate at a fixed limit of precision which they know the decoder will be able to match, and round the calculated fractions to their nearest equivalents at that precision. [...] A process called renormalization keeps the finite precision from ...


4

Consider: Mode 1 is only more efficient when you have a run of the same tens digit. Mode 1 saves 1 character for each same tens digit, except the first It costs 2 characters to switch to mode 1. Therefore Mode 1 only becomes advantageous after 4 similar 10s characters (costs 2, saves 3) For example, consider if you are running in mode 0. A switch to mode 1 ...


4

While this is probably a better question for ServerFault, I believe there is a clear answer: do compression on nginx. There are a couple of reasons for this: Compression is moderately CPU-intensive, and Node is single-threaded. Therefore, compression in node will potentially reduce the total number of requests a single server is able to handle. You will ...


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