Introduction to Data Compression

Introduction to Data Compression

1. Problems

   • Finding an efficient algorithm to remove various redundancy from a certain type of data
     • Solutions
       • Compression (Compressor): Derive an alternative sequence of symbols which contains fewer number of bits in total
       • Decompression (Decompressor): Recover the original thing

2. Coder & Decoder

   • can be located at two ends of a communication channel, at the source and at the destination repectively
     • compressor at the source is often called the coder
     • decompressor at the destination of the message is called the decoder

3. Definition

   • Data: The information in digital form on which computer programs operate
   • Compression: Process of removing redundancy in the data
   • Compressing Data: Deriving techniques / designing efficient algorithms to :
     • represent data in a less redundant fashion
     • remove the redundancy in data
     • implement compression algorithms, including both compression & decompression

4. Lossless & Lossy

   • Lossless Compression
     • No loss of any information during the compression process.
     • Reversible compression since the original data may be recovered perfectly by decompression
     • Used when the original data of source are so important that cannot afford to lose any details
   • Lossy Compression
     • Not possible to reconstruct the original exactly from the compressed version
     • Irreversible compression since it is impossible to recover the original data exactly by the decompression
     • Effect
       • Distortion-rate Problem : Given a constraint on transmitted data rate / storage capacity, the problem is to compress the source file at, or below this rate but at the highest fidelity possible
       • Rate-distortion Problem : Given a requirement to achieve a certain pre-specified fidelity, the problem is to meet requirements with as few bits per second as possible

5. Deriving Algorithmic Problems

   • 1. Description of the problem
   • 2. Mathematical modelling
   • 3. Design of the algorithm
   • 4. Verification of the algorithm
   • 5. Estimation of the computational complexity
   • 6. Implementation
   • 7. Program testing
   • 8. Documentation

6. Measure of Compression Quality

   • Lossless Compression
   • Lossy Compression
     • Need to measure the quality of the decompressed data as well as the compression effect
     • Fidelity: To describe the closeness between the source & decompressed file
     • Distortion: The source before compression & the file after decompression

Imagens e arquivos do mapa