Study guide

13.3 Lossless and Lossy Compression: Run-Length Encoding, Huffman Coding, and Media Formats

Praxis Computer Science 5652

Track your progress as you read

Finished sections get a check mark.

1 Chapter 1: Praxis 5652 Exam Overview and ETS Pseudocode

1.1 Praxis 5652 Test Facts, Scoring, and Registration 1.2 Official ETS Pseudocode Notation and Tracing Strategy

2 Chapter 2: Impacts of Computing: Innovation, Access, and Effects

2.1 Computing for Creativity, Problem Solving, Communication, and Innovation 2.2 Equal Access, the Digital Divide, and Accessibility 2.3 Beneficial and Harmful Effects of Computing Innovations

3 Chapter 3: Impacts of Computing: Intellectual Property, Ethics, Privacy, and Security

3.1 Intellectual Property: Copyright, Open Source, and Creative Commons 3.2 Ethical and Unethical Computing Practices and Their Implications 3.3 Privacy, Security, Data Collection, and Local vs. Cloud Storage

4 Chapter 4: Algorithms and Computational Thinking: Abstraction, Decomposition, Number Bases, and Representation

4.1 Abstraction and Abstraction Hierarchies 4.2 Decomposition, Pattern Recognition, and Developing Algorithms 4.3 Number Bases: Binary, Octal, Decimal, and Hexadecimal 4.4 Algorithm Formats: Natural Language, Flowcharts, Pseudocode, and Tracing

5 Chapter 5: Algorithms: Efficiency, Limits of Computing, and Randomization

5.1 Algorithm Efficiency: Linear, Quadratic, Exponential, and Logarithmic Growth 5.2 Limits of Computing: Unsolvable Problems, Intractability, and Heuristics 5.3 Randomization, Random vs. Pseudorandom Numbers, and Scaling to a Range

6 Chapter 6: Algorithms: Searching, Sorting, and Recursion

6.1 Searching Algorithms: Linear Search and Binary Search 6.2 Sorting Algorithms: Tracing, Comparisons, Correctness, and Efficiency 6.3 Recursion: Base Cases, Tracing, Errors, and Iterative Equivalents

7 Chapter 7: Programming: Variables, Data Types, Strings, and Expressions

7.1 Variables, Data Types, and Type Conversion 7.2 Strings and String Operations 7.3 Operators, Precedence, Expressions, and Formulas 7.4 Boolean Expressions, Truth Tables, and Boolean Algebra

8 Chapter 8: Programming: Selection, Iteration, and Writing Code

8.1 Sequence and Selection: if, else, Chained and Nested Conditions 8.2 Iteration: for, while, do … while, and repeat … until Loops 8.3 Reading, Completing, and Modifying Code

9 Chapter 9: Programming: Procedures, Arrays, and Data Structures

9.1 Procedures, Parameters, Return Values, Nested Calls, and Scope 9.2 Arrays, Lists, and Two-Dimensional Arrays 9.3 Stacks, Queues, and Dictionaries (Maps)

10 Chapter 10: Programming: Correctness, Errors, Testing, and Code Quality

10.1 Program Correctness: Preconditions, Postconditions, Invariants, and Testing vs. Proof 10.2 Error Types and Debugging Techniques 10.3 Choosing Useful Test Cases: Boundaries, Partitions, Coverage, and Regression 10.4 Extensibility, Modifiability, and Reusability: Constants and Parameterization 10.5 Documentation, Code Reviews, Peer Feedback, and End-User Feedback

11 Chapter 11: Programming: Events, Usability, Input Validation, and APIs

11.1 Event-Driven Programming, Asynchronous Events, and Concurrency 11.2 Usability, Meaningful Error Messages, and Input Validation vs. Verification 11.3 Libraries and APIs: Reading Definitions, Making Calls, and Weighing Trade-offs

12 Chapter 12: Programming: Languages, Tools, Paradigms, and Object-Oriented Design

12.1 Low- and High-Level Languages, Compilers and Interpreters, and IDEs 12.2 Programming Paradigms: Procedural, Object-Oriented, and Others 12.3 Classes, Objects, Instance Variables, Methods, and Encapsulation 12.4 Inheritance, Polymorphism, and Overloading vs. Overriding

13 Chapter 13: Data: Bits, Encoding, Compression, and Encryption

13.1 Bits and Bytes: Why Binary, Storage Calculations, and Signed Integers 13.2 Encoding Text, Images, and Sound 13.3 Lossless and Lossy Compression: Run-Length Encoding, Huffman Coding, and Media Formats 13.4 Encoding vs. Encryption, Symmetric and Public-Key Encryption, and Their Trade-offs

14 Chapter 14: Data: Analysis Tools, Simulation, Storage, and Collection

14.1 Analyzing Data with Spreadsheets: Cleaning, Transforming, and Visualizing 14.2 Simulation and Modeling 14.3 Files, Databases, and Storage Requirements: Scale, Redundancy, and Backup 14.4 Collecting, Aggregating, and Generating Data: Public Data Sets, Surveys, Sensors, and Crowdsourcing

15 Chapter 15: Computing Systems: Hardware, Operating Systems, and Computing Environments

15.1 Hardware Components and the Fetch–Decode–Execute Cycle 15.2 Operating Systems, Software Components, and Resource Issues 15.3 Embedded Systems, the Internet of Things, and Types of Computing Systems 15.4 Local, Network, and Cloud Computing and Storage; How Binary Data Are Stored

16 Chapter 16: Networks, the Internet, the Web, and Cybersecurity

16.1 Network Types and Wired and Wireless Communication 16.2 Network Hardware and Layered Network Models (OSI and TCP/IP) 16.3 Network Performance: Bandwidth, Latency, Load, and Estimating Needs 16.4 How the Internet Works: Protocols, IP Addressing, DNS, URLs, and Reliability 16.5 The Web: HTTP, HTML and Markup Languages, Browsers, Servers, and Clients 16.6 Cybersecurity: The Five Pillars, Strong Passwords, Security Strategies, and Trade-offs

13.3 Lossless and Lossy Compression: Run-Length Encoding, Huffman Coding, and Media Formats

Key Takeaways Explain This Topic AI

Lossless compression lets the original data be reconstructed exactly; it is required for text, program code, spreadsheets, and other data where any change is an error.

Lossy compression permanently discards some detail to achieve much smaller files, and is used for photos (JPEG), music (MP3, AAC), and streaming video.

Run-length encoding replaces runs of repeated symbols with a count and the symbol, so WWWWWWWWBBBWW becomes 8W3B2W; it can make data without runs larger.

Huffman coding gives frequent symbols short codes and rare symbols long codes, using a prefix code that decodes unambiguously; it is lossless.

Compression ratio = original size ÷ compressed size; repeatedly re-saving a lossy file compounds its losses.

Last updated: September 2026

What this competency asks

Under "bits as the universal medium," ETS asks you to describe lossy and lossless data compression . ETS's sample question describes Huffman coding, which assigns shorter codes to frequent values and longer codes to rare ones, and asks for its appropriate use: lossless compression . The distinction is the heart of this topic.

Why compress?

Raw media is huge. About 10 MB for one minute of CD-quality audio, and roughly 12 gigabits per second for uncompressed 4K video at 60 frames per second. Compression reduces the bits needed, which saves storage and transmission time.

Compression ratio = original size ÷ compressed size. A 10:1 ratio means the compressed file is one-tenth the size.

Lossless compression

Lossless compression removes redundancy so that decompression restores the original exactly , bit for bit.

Run-length encoding (RLE)

Replace each run of identical symbols with a count and the symbol.

  • Original Encoded
  • WWWWWWWWBBBWW (13 symbols) 8W3B2W (6 symbols)
  • AAAAAAAAAA (10) 10A (3)
  • ABCD (4) 1A1B1C1D (8): larger

RLE works well for images with large areas of one color, such as simple graphics, icons, and faxed documents. It works poorly, and can even expand the data, when there are few runs, as in photographs and ordinary text.

Huffman coding

Huffman coding builds variable-length prefix codes from symbol frequencies. Frequent symbols get short codes, and rare symbols get long ones. No code is the beginning of another, so the bit stream decodes unambiguously.

Worked example: the message AAAAAAABBC has A × 7, B × 2, and C × 1.

Combine the two least frequent: C (1) + B (2) forms a node of weight 3.

Combine that node (3) with A (7) to form the root (10).

Label branches 0 and 1: A = 0 , B = 10 , C = 11 .

  • Encoding Bits for the message
  • 8-bit ASCII 10 × 8 = 80 bits
  • Fixed 2-bit codes (3 symbols need 2 bits) 10 × 2 = 20 bits
  • Huffman 7 × 1 + 2 × 2 + 1 × 2 = 13 bits

Decoding 0010110 reads 0 → A, 0 → A, 10 → B, 11 → C, 0 → A, giving AABCA . The code table, or the frequencies, must be stored or agreed on so the receiver can decode.

Why the prefix rule matters. Suppose the codes were A = 0, B = 01, and C = 1 instead. The bits 01 could mean B, or A followed by C, so the message is ambiguous. In a prefix code , no codeword is the beginning of another codeword. The decoder reads bits from left to right and emits a symbol the moment the bits read so far match a codeword, with no separators needed.

Dictionary methods

Lempel–Ziv methods replace repeated sequences with references to earlier occurrences or to dictionary entries. LZW is used in GIF images. DEFLATE , which combines LZ77 with Huffman coding, is used in ZIP, gzip, and PNG.

Lossless formats: ZIP and gzip archives, PNG and GIF images, FLAC audio.

Lossy compression

Lossy compression gets much higher ratios by permanently discarding information that people are unlikely to notice.

Medium Technique Formats

Photos Keep brightness detail, reduce color detail, and discard fine high-frequency detail JPEG, WebP (lossy mode)

Music and speech Psychoacoustic models drop sounds masked by louder nearby sounds, and frequencies that are hard to hear MP3, AAC, Opus

Video Compress each frame like a photo, and store only the changes between frames, using motion prediction H.264, H.265, AV1

Typical results: photos at 10:1 or better, and music at around 128–256 kbps instead of CD's 1,411 kbps. Video compression often exceeds 100:1.

Video codecs get those ratios by storing occasional key frames (I-frames), each compressed like a standalone photo, and between them predicted frames (P-frames and B-frames) that record only motion and differences. A lecture recording with a still slide compresses far better than confetti or fast sports action, where almost every pixel changes from frame to frame.

Costs:

Lost data cannot be recovered .

Artifacts appear at high compression: blocky images, smeared edges, "swishy" audio.

Generation loss: decompressing, editing, and recompressing a lossy file again and again compounds the damage. Editors keep a lossless master.

Calculating ratios and savings

Space savings = 1 − (compressed size ÷ original size). A 2:1 ratio saves 50%, a 4:1 ratio saves 75%, and a 10:1 ratio saves 90%. The uncompressed sizes below come from the formulas in Section 13.2. The JPEG and ZIP sizes are illustrative.

  • Item Uncompressed Compressed Ratio Savings
  • 1920 × 1080 photo, 24-bit color 6,220,800 bytes 600,000-byte JPEG About 10.4:1 About 90%

4-minute CD-quality stereo song 42,336,000 bytes 128 kbps MP3: 128,000 × 240 ÷ 8 = 3,840,000 bytes About 11:1 About 91%

50,000-byte text file 50,000 bytes 20,000-byte ZIP 2.5:1 60%

For audio at a constant bit rate, the ratio is simply the ratio of bit rates: 1,411.2 kbps ÷ 128 kbps ≈ 11.

Why no lossless method shrinks every file

A counting argument, the pigeonhole principle , shows the limit. There are 2ⁿ different files of n bits, but only 2ⁿ − 1 files shorter than n bits (1 + 2 + 4 + … + 2ⁿ⁻¹). If a lossless compressor made every n-bit file shorter, at least two different files would have to share the same compressed output, and decompression could not tell them apart. So every lossless method leaves some inputs the same size or larger, as run-length encoding did with ABCD . In practice, random data and files that are already compressed (JPEG, MP3, ZIP) barely shrink when they are zipped again. Compressing a second time does not keep helping.

Choosing lossless or lossy

  • Data Choice Why
  • Source code, executables, spreadsheets, documents Lossless Any changed bit is an error
  • Medical and scientific images Usually lossless Fine detail can matter for diagnosis or measurement
  • Logos, screenshots, line art Lossless (PNG) Sharp edges; lossy creates visible artifacts
  • Photos for the web Lossy (JPEG, WebP) Much smaller files with little visible difference
  • Music streaming Lossy (AAC, Opus) Bandwidth matters more than perfect fidelity
  • Archival master recordings Lossless (FLAC) Preserves quality for future edits
  • Video calls Lossy Real-time bandwidth limits
  • Compression is not encryption

Compression makes data smaller . It does not make it secret . Anyone with the decompression method can read the data. Protecting data requires encryption (Section 13.4). Compressed data is often encrypted afterward, because encrypted data looks random and does not compress well.