Data Compression/Asymmetric Compression

Asymmetric Compression

edit

The idea of Asymmetric Compression is quite simple, given a method of processing compression in such a way as to continually improve the compression ratio[citation needed], A server would be able to pack the data into a tighter and tighter file structure[citation needed], while replacing the data with a series of instructions that would then recover the data more quickly and in fewer steps. An example of this might be a program that tries different combinations of order injection or entropy injection until it finds the one that allows the greatest compression. Then incorporates a signifier that allows the decompression system to find the exact order/entropy injection used so that it can reverse the effects once the new compression step is completed, as part of the decompression algorythm. [1]

This concept is attractive to the server industry, however so far no such algorythm has become practical.


When a data compression algorithm takes about the same time to generate a compressed file as it does to uncompress that file, we call that algorithm "symmetric".

When a data compression algorithm takes much longer to generate a compressed file than it does to uncompress a file, we call that algorithm "asymmetric".

(Are there any cases where a data compression algorithm takes much *less* time to generate a compressed file than it does to uncompress the file?)


All video compression algorithms use asymmetric compression.

In particular, motion compensation is notorious for requiring a lot of time on the compression side. To get the best compression, the motion compensation subroutine during compression must compare every 16x16 block of pixels in the current frame with every 16x16 block of pixels in the previous frame, which takes many, many comparisons, and figure out which block of the previous frame gives the best match. During decompression, the motion compensation routine takes the coordinates of the "best match" from the compressed data stream, and copies the data from that location in the previous frame to the current 16x16 block of pixels in the current frame.

There are many computers that are plenty fast enough to play back motion-compensated compressed video in real time, but not quite fast enough to motion-compensate and compress video in real time. If you have such a computer, and you want to compress video, you can either:

  • upgrade to a faster computer, one fast enough to do compression with full motion compensation in real time at high compression.
  • use your slow computer to compress it in "batch mode" much slower than real time (perhaps overnight). Do all the same operations as that fast computer, resulting in a bit-for-bit identical compressed video file.
  • use your slow computer, but do less work -- perhaps compare each 16x16 block of pixels with only a small neighborhood around the corresponding block in the previous frame. Since this slower computer does less work per frame, perhaps it will be fast enough to keep up with the video in real time. But because it doesn't do an exhaustive search for the "best" match, it doesn't compress as well, resulting in a larger compressed video file.


Further reading

edit
  1. "Data Compression Explained" by Matt Mahoney: "In particular, it is not possible to compress random data or compress recursively."