Assignment 1: text compression

This video illustrates the algorithm on paper. I apologize that the resolution and audio quality aren’t great, but it should be understandable. The final encoding and tree are also pictured below.

   5|  10|  15|  20|  25|  30|  35|  40|  45|  50|  55|

010110011011000011001110100101100101100011011101001110   ← 54 bits
W    E  _ M    U    S  T   _ B    U    I    L    D
5    3  2 5    5    3  4   2 5    5    5    5    5

1001111111100110111011100100000100011011101111000001110  ← 55 bits
_ A    S  _ I    F    _ T   H    E  _ S  A    N   D
2 5    3  2 5    5    2 4   5    3  2 3  5    4   5

100101100100011001101110100010100000001                  ← 39 bits
_ W    E  R    E  _ S  T   O    N   E
2 5    3  5    3  2 3  4   5    4   3

The total size of the encoding is 54+55+39 = 148 bits.

1. How many distinct characters does your phrase contain?
2. If we were using a fixed-width encoding, how many bits per character would you need to represent just those characters?
3. What is the most frequent character in your phrase, and how many times did it appear?
4. How many bits are used to represent the most frequent character in your phrase?
5. What is the most number of bits used to encode any character in your phrase?
6. Use the tree you produced to encode the entire phrase you were given. How many bits are used, in total?

So that everyone’s solutions are a bit different, you should use the phrase provided beside your student ID and initials. If you are not in this list, contact me to obtain your phrase.

You will submit two things electronically: a photo of the tree you drew, and a text containing the answers to the 6 questions. Here is how:

1. Register for an account at gitlab.liu.edu. (You must use an liu.edu email address.)
2. Once you are logged in, click the green New Project button. On the subsequent screen,
   • Type cs101 (lower-case, no spaces) as the Project name.
   • Click the Initialize repository with a README option.
   • Then hit Create project.

   

3. On the cs101 project sidebar, select Settings » Members.
4. Under Select members to invite, type league. My account should pop up. Choose it. Set Choose a role permission to Developer and hit Add to project.

   

5. On the cs101 project sidebar, select Wiki. Push the green button to Create your first page.
6. Change the Title to exactly A1 (capital A, the number 1, no spaces). Write or paste your answers to the six questions into the big box.

   

7. While writing, you may use the “Add numbered list” button on the format toolbar. It will number all answers with 1., but when you preview they’ll be numbered 1,2,3.
8. With the cursor on a blank line at the end of the text, use Attach a file to upload the photo of your tree. You can use the Preview tab to make sure it shows up correctly. (Sometimes a new upload can take a few moments to appear.)
9. When you’re satisfied (or whenever you want to save), hit the Create page button. You will then be able to Edit the page if you like, but I’ll use the last time the page is updated as the submission time for your assignment.
10. The next time you return to the Wiki feature, it will display Home · Create Page again. But you will see a link to the page titled A1 in the right sidebar.

Congratulations, you’re done!