Day 6: Lossless Data Compression

Learning Objectives

• DAT-1.D: Compare data compression algorithms to determine which is best in a particular context.

Essential Questions

• How can we reduce the size of data without losing information?
• What are the principles behind lossless compression?
• When is lossless compression most appropriate?

Materials Needed

• Presentation slides on lossless compression
• Handouts with compression examples
• Worksheet for run-length encoding practice
• Sample text files for compression activities
• Computers with compression tools (optional)

Vocabulary

• Lossless compression
• Run-length encoding (RLE)
• Dictionary-based compression
• Huffman coding
• Compression ratio
• Redundancy
• Entropy
• Decompression

Procedure (50 minutes)

Opening (8 minutes)

1. Review and Connection (3 minutes)

   • Review file formats from previous lesson
   • Connect to today's focus on reducing file sizes through compression

2. Warm-up Activity (5 minutes)

   • Display a repetitive pattern (e.g., "AAABBBCCCAAABBBCCC")
   • Ask students: "How could we write this more efficiently?"
   • Collect student ideas on the board

Main Activities (32 minutes)

3. Lecture: Principles of Lossless Compression (12 minutes)

   • Define lossless compression: reducing file size while preserving all original information
   • Explain that lossless compression works by eliminating redundancy
   • Discuss key properties:
     • Original data can be perfectly reconstructed
     • Effectiveness depends on data redundancy
     • Some data compresses better than others
   • Introduce compression ratio as a measure of effectiveness
   • Explain when lossless compression is most appropriate (text, spreadsheets, program files, etc.)

4. Demo: Run-length Encoding and Dictionary-based Compression (10 minutes)

   • Explain run-length encoding (RLE):
     • Replace sequences of repeated data with a count and the data item
     • Example: "AAABBBCCC" → "3A3B3C"
     • Show examples with text and simple images
   • Introduce dictionary-based compression:
     • Replace common patterns with shorter references
     • Example: "the the the" → Dictionary: {1:"the"} → "1 1 1"
     • Briefly explain how LZW and other algorithms work
   • Demonstrate compression and decompression with examples

5. Activity: Manually Compress and Decompress Data (10 minutes)

   • Provide students with sample data (text strings, simple bitmap patterns)
   • Students work in pairs to:
     • Apply run-length encoding to compress the data
     • Exchange their compressed data with another pair
     • Decompress their peers' data to recover the original
     • Calculate the compression ratio achieved
   • Discuss which samples compressed well and which didn't

Closing (10 minutes)

6. Discussion and Analysis (5 minutes)

   • What types of data are most suitable for RLE? Why?
   • What are the limitations of the compression techniques we explored?
   • How might compression algorithms be optimized for different types of data?
   • Real-world applications of lossless compression

7. Worksheet and Preview (5 minutes)

   • Students complete a worksheet on lossless compression techniques
   • Preview that next class will focus on lossy compression techniques

Assessment

• Formative: Quality of manual compression/decompression activity
• Worksheet: Accuracy of compression technique application and understanding

Differentiation

For Advanced Students

• Explore more complex compression algorithms like Huffman coding
• Analyze the time complexity of compression/decompression algorithms
• Create a simple program to perform run-length encoding

For Struggling Students

• Focus on simpler examples with obvious patterns
• Provide step-by-step guides for compression techniques
• Use visual aids to illustrate the compression process

Homework/Extension

• Complete additional compression exercises
• Research a real-world application of lossless compression
• Compare file sizes of compressed vs. uncompressed versions of the same file

Teacher Notes

• Have diverse examples ready to show varying compression effectiveness
• Make connections to students' experiences with ZIP files and other compressed formats
• Emphasize that lossless compression is essential for data that must remain exact
• Consider demonstrating actual compression tools if time allows