Data compression is the function of presentation layer in OSI reference model. Compression is often used to maximize the use of bandwidth across a network or to optimize disk space when saving data.
There are two general types of compression algorithms:
1. Lossless compression
2. Lossy compression
We’ll be covering the following topics in this tutorial:
Lossless Compression
Lossless compression compresses the data in such a way that when data is decompressed it is exactly the same as it was before compression i.e. there is no loss of data.
A lossless compression is used to compress file data such as executable code, text files, and numeric data, because programs that process such file data cannot tolerate mistakes in the data.
Lossless compression will typically not compress file as much as lossy compression techniques and may take more processing power to accomplish the compression.
Lossless Compression Algorithms
The various algorithms used to implement lossless data compression are :
1. Run length encoding
2. Differential pulse code modulation
3. Dictionary based encoding
1. Run length encoding
• This method replaces the consecutive occurrences of a given symbol with only one copy of the symbol along with a count of how many times that symbol occurs. Hence the names ‘run length’.
• For example, the string AAABBCDDDD would be encoded as 3A2BIC4D.
• A real life example where run-length encoding is quite effective is the fax machine. Most faxes are white sheets with the occasional black text. So, a run-length encoding scheme can take each line and transmit a code for while then the number of pixels, then the code for black and the number of pixels and so on.
• This method of compression must be used carefully. If there is not a lot of repetition in the data then it is possible the run length encoding scheme would actually increase the size of a file.
2. Differential pulse code modulation
• In this method first a reference symbol is placed. Then for each symbol in the data, we place the difference between that symbol and the reference symbol used.
• For example, using symbol A as reference symbol, the string AAABBC DDDD would be encoded as AOOOl123333, since A is the same as reference symbol, B has a difference of 1 from the reference symbol and so on.
3. Dictionary based encoding
• One of the best known dictionary based encoding algorithms is Lempel-Ziv (LZ) compression algorithm.
• This method is also known as substitution coder.
• In this method, a dictionary (table) of variable length strings (common phrases) is built.
• This dictionary contains almost every string that is expected to occur in data.
• When any of these strings occur in the data, then they are replaced with the corresponding index to the dictionary.
• In this method, instead of working with individual characters in text data, we treat each word as a string and output the index in the dictionary for that word.
• For example, let us say that the word “compression” has the index 4978 in one particular dictionary; it is the 4978th word is usr/share/dict/words. To compress a body of text, each time the string “compression” appears, it would be replaced by 4978.
Lossy Compression
Lossy compression is the one that does not promise that the data received is exactly the same as data send i.e. the data may be lost.
This is because a lossy algorithm removes information that it cannot later restore.
Lossy algorithms are used to compress still images, video and audio.
Lossy algorithms typically achieve much better compression ratios than the lossless algorithms.
Audio Compression
• Audio compression is used for speech or music.
• For speech, we need to compress a 64-KHz digitized signal; For music, we need to compress a 1.411.MHz signal
• Two types of techniques are used for audio compression:
1. Predictive encoding
2. Perceptual encoding
Predictive encoding
• In predictive encoding, the differences between the samples are encoded instead of encoding all the sampled values.
• This type of compression is normally used for speech.
• Several standards have been defined such as GSM (13 kbps), G. 729 (8 kbps), and G.723.3 (6.4 or 5.3 kbps).
Perceptual encoding
• Perceptual encoding scheme is used to create a CD-quality audio that requires a transmission bandwidth of 1.411 Mbps.
• MP3 (MPEG audio layer 3), a part of MPEG standard uses this perceptual encoding.
• Perceptual encoding is based on the science of psychoacoustics, a study of how people perceive sound.
• The perceptual encoding exploits certain flaws in the human auditory system to encode a signal in such a way that it sounds the same to a human listener, even if it looks quite different on an oscilloscope.
• The key property of perceptual coding is that some sounds can mask other sound. For example, imagine that you are broadcasting a live flute concert and all of a sudden someone starts striking a hammer on a metal sheet. You will not be able to hear the flute any more. Its sound has been masked by the hammer.
• Such a technique explained above is called frequency masking-the ability of a loud sound in one frequency band to hide a softer sound in another frequency band that would have been audible in the absence of the loud sound.
• Masking can also be done on the basis of time. For example: Even if the hammer is not striking on a metal sheet, the flute will be inaudible for a short period of time because the ears turn down its gain when they start and take a finite time to turn up again.
• Thus, a loud sound can numb our ears for a short time even after the sound has stopped. This effect is called temporal masking.
MP3
• MP3 uses these two phenomena, i.e. frequency masking and temporal masking to compress audio signals.
• In such a system, the technique analyzes and divides the spectrum into several groups. Zero bits are allocated to the frequency ranges that are totally masked.
• A small number of bits are allocated to the frequency ranges that are partially masked.
• A larger number. of bits are allocated to the frequency ranges that are not masked.
• Based on the range of frequencies in the original analog audio, MP3 produces three data rates: 96kbps, 128 kbps and 160 kbps.
Dinesh Thakur holds an B.C.A, MCDBA, MCSD certifications. Dinesh authors the hugely popular