Data Compression Techniques: RLE and Shannon-Fano

Data Compression

• Data compression is a method of reducing the size of information.
• It's used to reduce storage needs and speed up communication.
• Key reasons for data compression include storage requirements, memory requirements and communication speed.
• Compression reduces the physical size of information.
• It uses simple, efficient digital representation.

Data Compression/Decompression Tradeoff

• Compressor reduces the size of the data.
• Decompressor reconstructs the original data.

Data Compression Schemes

• Common schemes include pattern substitution, run-length encoding (RLE), Lempel-Ziv-Welch (LZW), Huffman encoding, and Discrete Cosine Transform (DCT).
• Motion Picture Experts Group (MPEG) is used frequently.
• Bitmap files only compress the bitmap data; headers, palette, and footer remain unchanged.
• Vector file image data is already compressed. Compressing vector files usually compresses the whole file.

Data Compression Terminology

• Raw data is data before any compression.
• Compressed data is data after compression.
• Compression Ratio measures the ratio of uncompressed to compressed data.

Types of Compression

• Symmetric Methods use similar algorithms in both directions with the same amount of work.
• Asymmetric Methods use more work in one direction than the other.

Encoder Schemes

• Dictionary-based encoders may be adaptive or non-adaptive.
• Non-adaptive encoders use static dictionaries and need prior statistics.
• Adaptive encoders adjust to any type of data.
• Semi-adaptive encoders build a dictionary in an initial pass and then perform encoding in a second pass.

Lossy and Lossless Compression

• Lossless compression preserves all original information. -Lossy compression discards some information (typically high-frequency components) resulting in decreased file size.

Classification of Compression Techniques

• Entropy coding (lossless): Used regardless of media characteristics
• Source coding (lossy): considers semantics of data, variable compression ratio and uses extensive use of specific medium characteristics
• Hybrid coding: combination of entropy coding and source coding

Information Theory

• Information theory provides a lower limit on the size to which information can be reduced.
• Based on the distribution of actual values.
• Entropy (H): The number of bits needed to code each symbol.
• Shannon's entropy formula determines the theoretical compression limit.

Pixel Packing

• Pixel packing is used to reduce the memory requirement of image data
• Bit-oriented representation reduces the storage requirement of image data from 4096 bytes to 2048 bytes.

Lossless Data Compression

• Statistical Encoding: Form of encoding involves substituting a repeating pattern to predefined codes.
• Codes are usually smaller than the repeating symbols.
• Count occurrences, sort in descending order and assign symbols to the highest patterns.
• Use symbol table to assign codes.

Run-Length Encoding (RLE)

• Suitable for encoding repeating strings.
• Encodes repeating strings of characters using two bytes
• The first byte represents the number of characters in the run.
• The second byte identifies the character.
• RLE is limited to encoding sequences of identical characters.

Run Length Encoding (RLE) - Variants

• Encoding may be along the X axis, Y axis, or diagnally along a zigzag path.
• Encoding may be different depending on the file format, e.g. BMP, PCX, TIFF, or PDF.
• Variant implementations of RLE are used in specific and specialized applications.

Vertical Replication Packets

• A method to reduce storing repeated scanline data.
• Reduces storage by storing only the count, rather than the data for each scanline.

Huffman Coding

• A popular lossless data compression method.
• It builds a binary tree based on symbol probabilities to assign variable-length codes.
• Symbols with higher probabilities get shorter codes.
• Huffman coding assigns codes to symbols for efficient encoding.
• Works effectively when certain symbols occur more frequently than others.

Huffman Coding (Binary Tree Construction)

• Leaves represent symbols in a sorted list.
• Nodes represent the sum of the children's frequencies.
• Codes are assigned recursively to the left and right subtree depending on whether the bit is 0 or 1.

Huffman Decoding

• It involves using the Huffman tree to traverse through the binary code.
• If a 0 is encountered, it moves to the left node.
• If a 1 is encountered, it moves to a right node.
• The decoding process stops at a leaf node.
• The character assigned to this leaf is then output.

Lempel-Ziv-Welch (LZW) Compression

• An adaptive dictionary-based compression technique.
• Codes are assigned to repetitive patterns and substituted with shorter codes.
• As codes are created, they are added to the dictionary.
• LZW codes are variable length.

JPEG Compression

• Lossy compression technique used for images and graphics.
• Achieves compression by discarding less significant information.
• Works by using a series of transformations followed by quantization.

JPEG Compression - Variations

• Compression quality and compression choices can be tuned to control the amount of information retained in the image.

Video and Animation Compression

• Reduces video data by discarding less visually important information.
• Strategies used to reduce data include reducing frame rate, using spatial and temporal redundancy.
• Types of frames include I-frames, P-frames and B-frames, which are coded differently depending on the content to optimize compression.

Explore the fundamentals of run-length encoding (RLE) and the Shannon-Fano algorithm through this quiz. Test your understanding of data encoding, limitations, and practical applications. Perfect for students interested in data compression methods in computer science.