An Educational Java Applet That Assists in Teaching Students The

INFSCI 2470 Final Project:

An educational java applet that assists in teaching students the

LZW Compression Algorithm

Philip Cwynar

Jeffrey Gennari

Qingzi Sang

Peter Sutovsky

TABLE OF CONTENT

Project overview 3

LZW Algorithm 3

Client 3

Requirements 3

System Development Life Cycle 4

Initial Requirements Analysis 4

Prototype Design 5

First User Evaluation of Prototype 5

Second Design Iteration 6

Third Design Iteration 7

Second User Evaluation of Prototype 7

Final Design 8

Design Features 8

Compression Process Panel 8

Decompression Process Panel 10

Transmission Stream 10

Transmission Compression Statistics 11

Evaluation 12

User Study: 12

LZW applet Questionnaire 12

User Study findings: 13

Usability Aspect Reports 15

Future work 15

Responsibilities 15

FIGURES

Figure 1 Work Sheet 5

Figure 2 Design Phase I 6

Figure 3 Design Phase II 7

Figure 4 Design Phase III 8

Figure 5 Design Phase IV 9

Figure 6 Compression Instructions 10

Figure 7 Stop Compression Button 10

Figure 8 Pause Demo Button 11

Figure 9 Resume Demo Button 11

Figure 10 Compression Pseudo Code 11

Figure 11 Transmission Panel 12

Figure 12 Statistics Result 12

Figure 13 Usability Aspect Reports 20

Project overview

LZW Algorithm

LZW is named after Abraham Lempel, Jakob Ziv and Terry Welch, the scientists who developed this compression algorithm. LZW belongs to a class of algorithms known as dictionary based compression algorithms. A dictionary based algorithm operates by scanning a file for sequences of data that occur multiple times and storing these sequences in a dictionary. LZW compression replaces strings of characters with single codes. It does not analyze the incoming text. Instead, it just adds every new string of characters it sees to a table of strings. Compression occurs when a single code is output instead of a string of characters.

There are advantages and disadvantages when using the LZW algorithm. One advantage is that LZW compression is fast. LZW compression works best for files containing many repetitive data. One disadvantage is that files that are compressed but that do not contain any repetitive information at all can grow larger than the original message.

Client

Dr. Michael Spring

Professor

Department of Information Science and Telecommunications

School of Information Sciences
727 SIS Building
University of Pittsburgh
Pittsburgh, PA 15260
Voice: (412) 624-9429 Fax: (412) 624-2788
E-Mail: or

Requirements

The goal of this project was to develop an interactive educational java applet to help information science students to gain a better understanding of the LZW compression algorithm. In particular we hope to give students the ability to:

1. Learn the LZW algorithm at ones own pace.

Step through the algorithm to see what each step does
Demonstrate the algorithm in its entirety through the use of animation

2. Provide students with statistics to help evaluate the algorithm

System Development Life Cycle

Initial Requirements Analysis

Dr. Spring already had a model that he used to teach students the LZW compression algorithm. It was on a sheet of paper in which he would transfer it into a transparency to use with the overhead projector in class. While in his office he demonstrated how he made use of the transparency (Figure 1) to teach a class. He would show students what and when values were changed by stepping through the algorithm incrementally and penciling in values. After Dr. Spring demonstrated his method to us we concluded that we could improve this process by emulating it in software and provide students with a personal tool they can consult when they need to.

Figure 1 Work Sheet

Prototype Design

Based on the model Dr. Spring used, we built a prototype using Microsoft’s Visual Basic. The prototype possessed no real functionality. Instead, the prototype was meant to serve as a visual starting point to show are client and confirm that his vision concurred with ours.

Figure 2 Design Phase I

First User Evaluation of Prototype

Upon showing our prototype to the Dr. Spring, he critiqued our design and assigned us additional requirements which include:

The generation of randomized input so as to mimic many of the common uses of LZW (such as the compression of GIF images).
The ability to quickly step through the compression process.

Second Design Iteration

At this stage, we had developed a working prototype, shown it to our client, and redesigned it to their specifications. At this point we began to work on an operational prototype. We created our first non-functional java applet in this phase. This was a critical step in the design as java has a much different programming model, look, and feel than Visual Basic applications. Initially we were worried some constructs would be hard to migrate from Visual Basic to java. However, the migration went smoothly (Figure 3).

Figure 3 Design Phase II

The interface is made of four components based on the design in the first stage. They are Compression Process Panel, Compression Message Panel, Control Panel, and Decompression Process Panel. The Compression and Decompression Process panels contain pixel matrix of the images, dictionaries, text areas for variables, and buttons of Start, Pause, Next Step, and Stop. The Compressed Message Panel contains the table of compression result. The Control Panel contains a combo-box for speed controlling and three buttons: Run Demonstration, Pause Demonstration, and Stop Demonstration.

Finally, in this iteration we began to implement the applet’s functionality. We started by making some important design decisions. First, we decided to restrict the core alphabet to capital A-E. This abbreviated alphabet used to compress/decompress messages simplifies the algorithm thus making the algorithm easier to follow. Next, we implemented step-by-step compression. Step-by-step compression allows the user to step through the algorithm manually and observe each step. The automated demonstration of compression was then added to the compression process and speed controls were implemented. Once we were satisfied with compression we moved on to decompression. As with compression we first implemented a step-by-step algorithm and then the automated demonstration. As this iteration drew to a close we had produced the first fully functional version of our applet from this point we began to shift our focus from development to improvement.

Third Design Iteration

In this stage, we refined the applet’s functionality and began to evaluate our design. Innovations added in this iteration include:

1. The addition of compression statistics.

2. The reallocation of demonstration controls to the Compression and Decompression panels.

3. The Control Panel was replaced by Compression Statistics panel.

4. Control buttons were separated and embedded into each Process Panel.

5. Reset Message button was added to reset compressed message.

6. We choose to highlight each step in the pseudo code instead of generating new code in text area.

Figure 4 illustrates the major changes to the interface, please note the “Compression Statistics” section which was added to show the power of the applet.

Figure 4 Design Phase III

Second User Evaluation of Prototype

On demonstrating our prototype to the Dr. Spring, we felt that some of the terminology used on labels needed to be clarified. For instance, Dr. Spring’s model uses terminology like OCode and CCode to describe decompression variables in the algorithm. After discussing this issue with him he instructed us to replace the OCode label with DCode which stands for dictionary code, the CCode label with TScode which stand for current code and transmission code respectively. Replacing the ambiguous labels helped us to understand the decompression sequence more and we felt it would help other students too. At the conclusion of this evaluation Dr. Spring stated he was very pleased.

Final Design

1. After our last meeting with Dr. Spring we added an instructional button to provide the user with the necessary information to successfully operate the applet.

2. We updated the ambiguous labels with more meaningful ones.

3. Decompression process was implemented and the whole program was tested in this phase.

Figure 5 Design Phase IV

Design Features

Compression Process Panel

The Compression Process Panel contains:

1. Input Stream --- A 5x5 matrix containing the original input.

2. Encode dictionary --- A table with two columns: Code and String. The program will generate the rest of the dictionary automatically.

3. String, Suffix, and String + Suffix --- Three text areas holding variables, whose values change along the process.

4. Instruction --- When the button is clicked, a message will pop up the instruction of LZW Applet. (See Figure 6)

Figure 6 Compression Instructions

5. Start Compression --- When the button is clicked, compression process will start, and the Start Compression button will change into the Stop Compression button and now be used to stop the compression process. (See Figure 7)

Figure 7 Stop Compression Button

6. Next Step --- When the button is clicked, the program will step through the compression.

7. Demo Compression --- When the button is clicked, compression will run automatically. A Demo Speed slide bar will show up. Demo Compression button will change into Pause Demo. When the Pause Demo button is clicked, demonstration will stop and the Pause Demo button will change into Resume Demo button. When the Resume Demo button is clicked, the demonstration will continue. (See Figure 8, Figure 9)

Figure 8 Pause Demo Button

Figure 9 Resume Demo Button

8. Demo Speed --- A slide bar for controlling demonstration speed. (See figure 8)

9. Pseudo Code --- Each step will be highlighted during the compressing. (See
Figure 10)

Figure 10 Compression Pseudo Code

Decompression Process Panel

The Decompression Process Panel contains:

1. Output Stream (table)

2. Decode dictionary (table)

3. Decode, Decode String, TSCode, TSCode String, and Prefix (text area)

4. Instruction (button)

5. Start Decompression (button)

6. Next Step (button)

7. Demo Decompression (button)

8. Demo Speed (slide bar)

9. Pseudo Code

All widgets have the same functions as those in the Compression Process Panel.

Transmission Stream

1. Transmission Stream --- A table shows the compression result. The current character being used is highlighted. (See Figure 11)

Figure 11 Transmission Panel

2. Clear Message --- When the button is clicked, the content in Transmission Stream is cleared.

Transmission Compression Statistics

1. Original Message Size

2. Compressed Message Size

3. Compression Ratio

All above show the statistic result of compression on the fly.

Figure 12 Statistics Result

Evaluation

User Study:

Upon successfully satisfying our client’s requirements, we decided to perform a user study. The study which used the below questionnaire was conducted by briefing an information science student on the LZW algorithm and letting them operate the applet themselves. The questionnaire would make it clear if students found the applet to be useful or not.

LZW applet Questionnaire

Please answer the following questions by placing a checkmark next to the answer that best describes your experience:

How many programming courses have you taken?

· None ______

· 1-2 courses ______

· 3 or more courses ______

What academic program are you currently enrolled in?

· BSIS ______

· MSIS ______

· TELECOM ______

· MLIS ______

· Other ______

* If other, please enter the name of the program: ______

What was your understanding of LZW compression algorithm before using applet?

· I had never heard of the LZW compression algorithm ______

· I had a heard of it before but did not understand it ______

· I had a basic understanding of the algorithm ______

· I had a very good understanding of the algorithm ______

The LZW compression applet helped me learn LZW compression

· Strongly agree ______

· Agree ______

· Disagree ______

· Strongly Disagree ______

I think the LZW applet should be used to teach other student’s LZW compression

· Strongly agree ______

· Agree ______

· Disagree ______

· Strongly Disagree ______

I found the use of automated demonstrations a helpful tool for learning the LZW algorithm.

· Strongly agree ______

· Agree ______

· Disagree ______

· Strongly Disagree ______

I found the LZW applet easy to use

· Strongly agree ______

· Agree ______

· Disagree ______

· Strongly Disagree ______

I found the LZW applet easy to understand

· Strongly agree ______

· Agree ______

· Disagree ______

· Strongly Disagree ______

On a scale of 1 to 10, with 1 being very poor and 10 being very good I would rate the LZW applet as ______.

Thank you for answering out questions.

User Study findings:

We conducted our study on 10 undergraduate and graduate Information Science students. Below is a summary of their responses:

· Question 1:

§ No Courses: 0 students

§ 1 – 2 Courses: 1 student

§ 3 or more Courses: 9 students

· Question 2:

§ BSIS: 2 students

§ MSIS: 7 students

§ TELECOM: 0 Students

§ MLIS: 0 Students

§ Other:

o IS-PhD: 1 student

· Question 3:

§ I had never heard of the LZW compression algorithm: 1 students

§ I had a heard of it before but did not understand it: 8 students

§ I had a basic understanding of the algorithm: 0 students

§ I had a very good understanding of the algorithm: 1 student

· Question 4:

§ Strongly agree: 2 Students

§ Agree: 8 student

§ Disagree: 0 Students

§ Strongly Disagree: 0 Students

· Question 5:

§ Strongly agree: 1 student

§ Agree: 9 students

§ Disagree: 0 Students

§ Strongly Disagree: 0 Students

· Question 6:

§ Strongly agree: 1 student

§ Agree: 9 students

§ Disagree: 0 Students

§ Strongly Disagree: 0 Students

· Question 7: