Dictionary (substitution) compression

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. Which statement describes dictionary compression correctly?

A Each repeated phrase is deleted and the file just gets smaller

B Each repeated phrase gets a short code, and the code table is stored once

2. A text repeats the phrase "good morning" 6 times. What is the best thing to put in the code table?

A 1 = morning

B 1 = good morning

3. The code table says 1 = the cat. Which is the correct compressed version of "the cat ran. the cat slept."?

A 1 ran. 1 slept.

B 1 1 ran. slept.

4. Why is the code table stored only once?

A It lets us decode every code back to its phrase without repeating the phrase

B It makes every code longer so it is easier to read

5. The phrase "go team" (7 characters) appears 5 times and is replaced by the code 1 (1 character). How many characters are saved by the replacements alone?

A 30 characters

B 35 characters

Match the Pairs

Draw a line connecting each item on the left to its match on the right.

Left column		Right column
11=go to the		A2 Sam, 2 Alex
21 shop, 1 park, 1 beach		BA code table entry: the short code 1 stands for the repeated phrase 'go to the'
3Build the code table by giving the repeated phrase 'good morning' the short code 2		CThe compressed text, where every repeat of the phrase has been replaced by its short code
4Replace both repeats of 'good morning' in 'good morning Sam, good morning Alex' using code 2		DThe second 'the cat' was not replaced with code 1, so a repeat was left in full and no extra space was saved
5Table: 1=the cat Text: 1 sat, the cat ran		EThe code table is missing, so nobody can tell that 3 stands for a phrase
6Text: 3 is fun, 3 is easy (no code table stored)		F2=good morning

Definitions

dictionary compression

Fill in the Blanks

Complete each line of code by filling in the missing parts.

TABLE: # = "the cat" TEXT: "the cat sat, the cat ran" SMALL: "_ sat, # ran"

original ← 30 compressed ← 12 saved ← original _ compressed

phrase ← "the cat" code ← "#" saved ← ______(phrase) - LENGTH(code)

text ← "the cat sat, the cat ran" small ← _______(text, "the cat", "#")

code ← "#" phrase ← "the cat" table[____] ← phrase

Spot the Error

Shade in the letter of the line that contains an error.

Question 1

A s ← "go go go home"

B table: 1 = "go"

C out ← "1 1 go home"

Question 2

A table: Z = "cat"

B s ← "the cat and the dog"

C out ← "Z cat and Z dog"

Question 3

A s ← "I like pie, we like tea"

B table: 1 = "I like"

C out ← "1 pie, 1 tea"

Question 4

A s ← "go go go go"

B table: go = "1"

C out ← "1 1 1 1"

D saved ← 11 - 7

Question 5

A s ← "red red red blue"

B table: R = "red"

C out ← "R R R blue"

D saved ← 10 - 16

Answer Key

Dictionary (substitution) compression

Section A: Quick Questions

B — Each repeated phrase gets a short code, and the code table is stored once

B — 1 = good morning

A — 1 ran. 1 slept.

A — It lets us decode every code back to its phrase without repeating the phrase

A — 30 characters

Section B: Match the Pairs

1=go to the → A code table entry: the short code 1 stands for the repeated phrase 'go to the'

1 shop, 1 park, 1 beach → The compressed text, where every repeat of the phrase has been replaced by its short code

Build the code table by giving the repeated phrase 'good morning' the short code 2 → 2=good morning

Replace both repeats of 'good morning' in 'good morning Sam, good morning Alex' using code 2 → 2 Sam, 2 Alex

Table: 1=the cat Text: 1 sat, the cat ran → The second 'the cat' was not replaced with code 1, so a repeat was left in full and no extra space was saved

Text: 3 is fun, 3 is easy (no code table stored) → The code table is missing, so nobody can tell that 3 stands for a phrase

Section C: Definitions

dictionary compression — Give each repeated word or phrase a short code, store the code table once, then replace every repeat with its code so the data takes up fewer characters.

Section D: Fill in the Blanks

TABLE: # = "the cat"
TEXT: "the cat sat, the cat ran"
SMALL: "# sat, # ran"

original ← 30
compressed ← 12
saved ← original - compressed

phrase ← "the cat"
code ← "#"
saved ← LENGTH(phrase) - LENGTH(code)

text ← "the cat sat, the cat ran"
small ← REPLACE(text, "the cat", "#")

code ← "#"
phrase ← "the cat"
table[code] ← phrase

Section E: Spot the Error

C — Every repeat of "go" must be replaced with its code. The third "go" was left in, so the line should be out ← "1 1 1 home".

A — The code Z replaces "the" in the packed text, so the table must say Z = "the". With "cat" in the table the message would decode wrongly.

A — Dictionary compression only works on a phrase that really repeats. "we like" is not the same as "I like", so the original should be s ← "I like pie, I like tea".

B — The table must list the short code first, then the phrase it stands for. It should be table: 1 = "go".

D — Characters saved = original length minus compressed length. The original is 16 characters and the packed text is 10, so it should be saved ← 16 - 10 (6 saved).