Data Compression Algorithms

c++ c algorithm compression signal-processing
Veridian picture Veridian · May 9, 2013 · Viewed 75.4k times · Source

I was wondering if anyone has a list of data compression algorithms. I know basically nothing about data compression and I was hoping to learn more about different algorithms and see which ones are the newest and have yet to be developed on a lot of ASICs.

I'm hoping to implement a data compression ASIC which is independent of the type of data coming in (audio,video,images,etc.)

If my question is too open ended, please let me know and I'll revise. Thank you

Answer

user123 picture user123 · May 9, 2013

There are a ton of compression algorithms out there. What you need here is a lossless compression algorithm. A lossless compression algorithm compresses data such that it can be decompressed to achieve exactly what was given before compression. The opposite would be a lossy compression algorithm. Lossy compression can remove data from a file. PNG images use lossless compression while JPEG images can and often do use lossy compression.

Some of the most widely known compression algorithms include:

ZIP archives use a combination of Huffman coding and LZ77 to give fast compression and decompression times and reasonably good compression ratios.

LZ77 is pretty much a generalized form of RLE and it will often yield much better results.

Huffman allows the most repeating bytes to represent the least number of bits. Imagine a text file that looked like this:

aaaaaaaabbbbbcccdd

A typical implementation of Huffman would result in the following map:

Bits Character
   0         a
  10         b
 110         c
1110         d

So the file would be compressed to this:

00000000 10101010 10110110 11011101 11000000
                                       ^^^^^
                              Padding bits required

18 bytes go down to 5. Of course, the table must be included in the file. This algorithm works better with more data :P

Alex Allain has a nice article on the Huffman Compression Algorithm in case the Wiki doesn't suffice.

Feel free to ask for more information. This topic is pretty darn wide.

Related questions

Printing prime numbers from 1 through 100

This c++ code prints out the following prime numbers: 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97. But I don't think that's the way my book wants it to be written. It mentions something about square root of a number. So I did try changing my 2nd loop …

Read More
Fast ceiling of an integer division in C / C++

Given integer values x and y, C and C++ both return as the quotient q = x/y the floor of the floating point equivalent. I'm interested in a method of returning the ceiling instead. For example, ceil(10/5)=2 and ceil(11/5)=3. The …

Read More
Searching in a sorted and rotated array

While preparing for an interview I stumbled upon this interesting question: You've been given an array that is sorted and then rotated. For example: Let arr = [1,2,3,4,5], which is sorted Rotate it twice to the right to give [4,5,1,2,3]. Now how best …

Read More