Data Compression Chapter Notes | AP Computer Science Principles - Grade 9 PDF Download

Introduction

This chapter explores data compression, a key technique for managing large digital files in the AP Computer Science Principles course. It covers why compression is needed, methods like run-length encoding and LZW, and the differences between lossless and lossy compression. Understanding data compression helps optimize storage and transmission, especially for files like photos or videos.

Data Compression

• Digital data, such as photos and videos, can be large, consuming significant storage space and making it hard to send via email or text.
• Data compression reduces the size of stored or shared data, decreasing the number of bits required.
• The extent of compression depends on:
  • The amount of redundancy (repeated information) that can be removed from the data.
  • The compression method used.
• Many compression methods use symbols to represent data more efficiently.

Data Compression Examples

• Run-Length Encoding (RLE): This straightforward compression method replaces sequences of repeated data with a count and the repeated value. For instance, the sequence "AAAAABBBCC" could be compressed to "5A3B2C," significantly reducing the data size. RLE is commonly used in bitmap images and fax machines due to its simplicity and effectiveness.
• LZW Compression Algorithm: Another method that replaces repetitive data with shorter codes, LZW is widely used for compressing text and images, particularly in GIF file formats.

Lossless vs. Lossy Compression

Data compression is divided into two main types: lossless and lossy.

Lossless Compression

• Reduces file size without losing any original data, allowing full restoration of the original file.
• Examples include run-length encoding and the LZW algorithm, which shorten data without altering information.
• Preferred when file quality or exact reconstruction is critical.
• Used in:
  • Databases, where data accuracy is essential to avoid skewed information.
  • Medical and satellite imaging, where small data differences could have significant consequences.
  • Software downloads, where exact recreation of the program is necessary for functionality.

Lossy Compression

• Achieves greater compression by removing some data, often details like similar colors in a photo.
  • Example: A compressed taco image using 62% less data looks nearly identical to the original.
• Ideal for minimizing file size or speeding up file transmission, especially when changes are barely noticeable.
• Commonly used in photo, audio, and video compression for downloading purposes.
• Many modern compression systems combine lossless and lossy methods for optimal results.

Key Terms