- Generally speakingm there are 2 classes
of data compression algorithms:
- Lossless data compression:
- When we uncompress the
compressed data, we will obtain
an exact copy of
the original data:
- Examples of usage of
lossless data compression:
- Compress text/binary data files for archival purpose
- When we uncompress the
compressed data, we will obtain
an exact copy of
the original data:
- Lossy data compression:
- When we uncompress the
compressed data, we
do not obtain
an exact copy of
the original data:
Rather: we obtain an approximate copy only .....
- Examples of usage of
lossless data compression:
- Audio compression (MP3)
- Video compression (MP4)
- When we uncompress the
compressed data, we
do not obtain
an exact copy of
the original data:
- Lossless data compression:
- Compression ratio:
- Compression ratio = the ratio between the size of the result data file and the size of the source data file
The smaller the compression ratio, the better is the compression algorithm
- Input file and compression ratio:
- The content of the
input data file has an
extremely great effect of
the compression ratio:
- The more regular the input data file is ("less enthropy"), the smaller the compression ratio
Example: the input file
0000000000000000000.....00000can be compressed into a single integer: n = number of 0 in the file.
- The content of the
input data file has an
extremely great effect of
the compression ratio:
- Advantage of
lossy compression
over lossless compression:
- The compression ratio of lossy compression algorithm is much better than lossless compression algorithms !!!
- Important areas where
lossy compression algorithm:
- Video (Lower quality video vs. high definition video)
- Audio
(lower quality audio (e.g., mono/telephone quality) vs.
surround sound stereo quality)
In general:
- these are applications where some loss in quality does not compromise the content of the message.
- Example:
- Here is the picture data file
compressed using almost no loss
in quality:
The size of this file = 57,242 bytes
- Here is a compressed file
using a
highly lossy compression:
The size of this file = only 4,009 bytes
- Compression ratio =
4,009 / 57,242 =
0.07 !!!
(That's extremely good !)
(But picture quality is degraded severely)
- Compression ratio =
4,009 / 57,242 =
0.07 !!!
(That's extremely good !)
- Here is the picture data file
compressed using almost no loss
in quality:
- If you're interested in JPEG, you can check my write up here: click here
- Lossless data compression
techniques will usually:
- gather information on
the input file
- what is the most frequent pattern (entrophy coder
- where can I find some pattern in the text (dictionary code)
- Then use the gathered information to encode the input data file
- gather information on
the input file
- Data compression is
a huge area
(data compression is closely related to
information theory and I am
not a speciality
in that area)
- I will basically follow Goodrich's treatise in data compression and will add some background information on the topic to set the context.....