Comprehensive Guide to Data Compression and Metadata

Introduction to Data Compression

• Definition: Data compression is the process of encoding information using fewer bits than the original representation.
• The Binary Foundation: All data, such as the word "HELLO," is stored as binary (e.g., $01001000\,01000101\,01001100\,01001100\,01001111$). Compression looks for ways to represent these bitstreams more efficiently.
• General Learning Objectives:
  • Define lossless compression and explain the preservation of original data.
  • Identify data patterns and apply Run Length Encoding (RLE).
  • Calculate space savings percentages.
  • Distinguish between lossless and lossy compression in real-world contexts.
  • Determine which algorithms suit specific data types based on their requirements.

Why Compress Data? (Motivations and Trade-offs)

• Scale of Compression: An uncompressed 4K movie occupies approximately $300\,GB$. The same movie compressed can fit into $1\,GB$, making it $43\times$ smaller while maintaining acceptable quality.
• Saving Storage Space: Physical devices such as smartphones have limited storage capacities. Compression allows high-definition content to fit on devices that could not otherwise store raw, uncompressed files.
• Saving Bandwidth: Transmission speed is limited by bandwidth. Fewer bits to transmit results in faster downloads and smoother streaming. This is critical for email attachments, web pages, and video streaming services.
• Trading Computation for Storage:
  • Computation is relatively cheap and fast.
  • Storage is relatively expensive and slow.
  • Compression exploits this by using processing power to shrink data for storage and then decompressing it on demand.

Lossless Compression Fundamentals

• Core Definition: A process that reduces the number of bits needed to store data without losing any information.
• Key Characteristics:
  • Zero Data Loss: Not a single bit is changed or removed permanently.
  • Full Reversibility: The decompression algorithm reverses the process exactly, meaning the decompressed file is identical to the original.
  • Efficiency Diagram:
    • Original Data: $2400\,bits$
    • Compression Algorithm application.
    • Compressed Data: $56\,bits$
    • Decompression Algorithm application.
    • Resulting Data: $2400\,bits$ (Identical to original).
• Ideal Use Cases: Situations where every bit is critical, such as text files, computer code, and spreadsheets.
• Common Formats: $.zip$, $.png$, and $.flac$.

Mechanics of Compression: Patterns and Placeholders

• Step 1: Find Repeated Patterns: The algorithm scans for data recurring more than once. This includes repeating characters, blocks of color in an image, word sequences, or specific byte sequences.
  • Example: In the string HAAAAAAHAAAAA, the character 'A' repeats in a predictable pattern.
• Step 2: Replace with a Shorter Placeholder: Swap the recurring pattern with a compact code.
  • Example: Replacing six 'A's with a code like 'A6'.
  • Dictionary/Key: The system stores a mapping that allows the computer to translate codes back to the original data.
• Variable Reduction: The amount of size reduction depends on two factors:
  1. The level of redundancy in the original data representation.
  2. The specific compression algorithm applied.

Run Length Encoding (RLE) — Algorithm Deep Dive

• The RLE Rule: For each "run" of identical consecutive characters, store the character followed by the count of its repetitions.
• Step-by-Step Example: HAAAAAAHAAAAAA
  • 1st Run: H (Count: 1) → Encoded as H1
  • 2nd Run: AAAAAA (Count: 6) → Encoded as A6
  • 3rd Run: H (Count: 1) → Encoded as H1
  • 4th Run: AAAAAA (Count: 6) → Encoded as A6
  • Final Encoded String: H1A6H1A6 (reduces 14 characters to 8 characters).
• Effectiveness Constraints:
  • RLE performs best on data with long consecutive runs of identical values (like simple icons or logos).
  • Negative Compression: If data has no repetition (e.g., ABCDE), RLE could actually make the file larger (e.g., A1B1C1D1E1).

Measuring Compression — Space Savings

• The Formula:     $\text{Space Savings} = \left( 1 - \frac{\text{size of compressed}}{\text{size of original}} \right) \times 100$
• Calculation Example (String: HAAAAAAHAAAAAA):
  • Step 1 (Original): 14 characters $\times$ 8 bits/char = $112\,bits$.
  • Step 2 (Compressed): 8 characters $\times$ 8 bits/char = $64\,bits$.
  • Step 3 (Savings Calculation):         $\text{Space Savings} = \left( 1 - \frac{64}{112} \right) \times 100$$\text{Space Savings} = (1 - 0.571) \times 100 = 42.9\%$

Case Study: Identifying and Fixing RLE Errors

• Scenario: A student compresses AABBBCCCCDDDDDD (15 total characters) as A2B3C4D5.
• The Error: In the original string, there are 6 'D's. The student's version A2B3C4D5 only accounts for 5 'D's.
• The Correction: The correct version is A2B3C4D6.
• Impact of Mistakes: Because lossless compression must be perfectly reversible, a miscount of a single character renders the data unrecoverable in its original form, effectively making it "lossy by mistake."
• Calculated Savings for Corrected Version:
  • Original: 15 chars.
  • Compressed: 8 chars.
  • Savings: $(1 - \frac{8}{15}) \times 100 \approx 46.7\%$.

Real-World Lossless Algorithms

• Huffman Coding: Used specifically for text. It assigns the shortest binary codes to the most common characters and longer codes to rare characters (e.g., the common letter 'E' might be coded as 0, while 'Z' is coded as 11101).
• LZ77 / LZ78: General-purpose text and binary algorithms. They store repeated patterns as references to earlier occurrences (e.g., ABCABCABC becomes ABC followed by a instruction to repeat the previous ABC twice).
• Deflate (ZIP): A hybrid approach used for files and folders that combines LZ77 and Huffman Coding to maximize efficiency.

Lossless vs. Lossy Compression

The Mechanics of Lossy Trade-Offs

• The Principle: Accept permanent data loss to achieve significantly smaller file sizes.
• Why it Works for Media:
  • Audio (MP3): Human ears typically cannot detect frequencies above approximately $20\,kHz$. Lossy algorithms remove these inaudible frequencies.
  • Photos (JPEG): Human eyes are more sensitive to changes in brightness than fine color details. Algorithms reduce color precision in ways generally unnoticed by the human eye.
• Where it Fails:
  • Text/Code: One missing byte can corrupt an entire program or change the legal meaning of a document.
  • Medical Imaging: A blurry X-ray (artifacts from compression) could hide a tumor or pathology. Lossless compression is often legally required for diagnostics.

Digital Information and Metadata

• System Overview: Programs take input data (spreadsheets, images, mouse/keyboard inputs), manipulate them, and produce output data (sounds, HTTP responses).
• Definition of Metadata: "Data about data." It provides the context needed to structure and organize primary data.
• Metadata Content: Includes information on where data was collected, who collected it, how long ago, data set size, and accuracy.
• Metadata Examples by Data Type:
  • Photo: Date/time, GPS location, camera model.
  • Email: Sender, recipient, date, message size.
  • Music: Title, artist, album, genre.
  • Video: Duration, resolution, creation date.
  • Web Page Visit: IP address, browser type, timestamp.
  • Phone Call: Caller/receiver numbers, duration.
  • GPS: Coordinates, speed, timestamp.

Metadata in File Management

• Identification: Metadata identifies what compression type was used so the OS can decompress it without guessing.
• The Process:
  1. File Extension: (e.g., .png, .jpg, .zip) signals the algorithm.
  2. File Header: The first few bytes of a file contain metadata identifying the format.
  3. Application: The OS reads the header and triggers the correct decompression algorithm (e.g., .zip triggers the Deflate/LZ77 decompressor).

Practice Problem: Bitwise RLE Calculation

• Problem String: BBBBBWWWBWWWWWWBB (17 total characters).
• Apply RLE:
  • B5 (5 Bs)
  • W3 (3 Ws)
  • B1 (1 B)
  • W6 (6 Ws)
  • B2 (2 Bs)
  • Compressed String: B5W3B1W6B2 (10 characters).
• Original Bits: 17 characters $\times$ 8 bits = $136\,bits$.
• Compressed Bits: 10 characters $\times$ 8 bits = $80\,bits$.
• Space Savings:     $\text{Savings} = \left( 1 - \frac{80}{136} \right) \times 100 \approx 41.2\%$

Key Vocabulary Summary

• Data Compression: Encoding information using fewer bits.
• Lossless Compression: A process where the original data can be perfectly restored.
• Lossy Compression: Compression that reduces file size by permanently removing data.
• Run Length Encoding (RLE): Replacing consecutive identical characters with the character and a count.
• Space Savings: The percentage reduction in file size calculated as $(1 - \text{compressed}/\text{original}) \times 100$.
• Decompression: The reversal of compression to recover the original data.
• File Extension: An indicator of which compression algorithm was used (e.g., $.flac, .mp3, .png$).