Many computer users are familiar with compressed formats such as zip, gzip, or gif images. These are based on a method called Ziv-Lempel coding, which turns out to be an interesting exercise in finding patterns in text.

Children's rhymes and stories are good examples for text compression, because they often involve repeated words and sequences.

Other Resources

• Wikipedia: LZ77 and LZ78 algorithms
• Howstuffworks.com article on file compression
• The Mathmaniacs web site has a similar activity (lesson 2).

Curriculum Links

This activity is great for cross-curricular programmes. As a focused worksheet activity it demonstrates an algorithm in common use, but it also encourages students to think about the text they're compressing. Why do children's rhymes have so much repetition? Does poetry tend to compress better than prose?

New Zealand Curriculum Achievement Objectives

• Technology Level 1:Technological systems
  • Understand that technological systems have inputs, controlled transformations, and outputs.
• Technology Level 3: Technological systems
  • Understand that technological systems are represented by symbolic language tools and understand the role played by the “black box” in technological systems.

ACM K12 Model Curriculum

• Level I (Grades 3–5) Topic 11: develop a simple understanding of an algorithm

Great Principles of Computer Science

• Communication
• Recollection