LZW

File compression and decompression using LZW algorithm

Introduction

The subject of the project is to implement a Lempel-Ziv-Welch (LZW) data compression and decompression algorithm using Java Programming Language.

LZW is a lossless algorithm which finds recurring patterns, saves them in a dictionary and replaces them with shorter codes. It starts with a dictionary of all the single byte values (0-255) and then keeps adding longer patterns to it as it reads through the data. Because the decoder is able to build the exact same dictionary while it reads, the codes do not have to be stored anywhere in the file. This algorithm can significantly decrease the size of files and is often used for data compression.

This version works on raw bytes instead of just text, so it can compress any type of file and not only plain text.

Tools

• Java (tested with JDK 17+)

How it works

To make the output smaller and to handle bigger files, a few things were added on top of the basic algorithm:

• Byte based: the input is read as raw bytes, so binary files work too.
• Variable width codes: instead of always using the same number of bits, the codes start at 9 bits and grow one bit at a time up to 16 bits as the dictionary fills up. This saves space early on when there are not many codes yet.
• Special codes: CLEAR (256) tells the decoder to reset the dictionary and EOF (257) marks the end of the data. New patterns get codes starting from 258.
• Dictionary reset: when the dictionary becomes full it is cleared and rebuilt so the algorithm keeps adapting to the file.
• Small header: the encoder writes the 4 letters LZW2 followed by one byte for the maximum code width, so the decoder knows how the file was made.

How to run

Compile the sources:

javac -d out src/*.java

Run the demo (compresses resources/input1 into resources/encoded and then decodes it back into resources/output):

java -cp out Main

Or give it your own files:

java -cp out Main encode <input file> <output file>
java -cp out Main decode <input file> <output file>

After running the demo the original file and resources/output should be exactly the same, which shows the compression is lossless.

Compression

Following is the pseudo code for the LZW compression algorithm:

STRING = get input character
WHILE there are still input characters DO
    CHARACTER = get input character
    IF STRING+CHARACTER is in the string table then
        STRING = STRING+CHARACTER
    ELSE
        output the code for STRING
        add STRING+CHARACTER to the string table
        STRING = CHARACTER
    END of IF
END of WHILE
output the code for STRING

In the actual code the codes are not kept in a list, they are packed straight into the output stream bit by bit using the current code width.

Decompression

Following is the pseudo code for the LZW decompression algorithm:

Read OLD
output OLD
CHARACTER = OLD
WHILE there are still input characters DO
    Read NEW
    IF NEW is not in the translation table THEN
        STRING = get translation of OLD
        STRING = STRING+CHARACTER
    ELSE
        STRING = get translation of NEW
    END of IF
    output STRING
    CHARACTER = first character in STRING
    add OLD + CHARACTER to the translation table
    OLD = NEW
END of WHILE

The special case where NEW is not in the table yet is the well known "KwKwK" case and is handled the same way as in the pseudo code above.

Results

To test the program properly I ran it on the Canterbury Corpus, which is a standard set of files people use to compare compression programs. Each file was compressed and then decompressed again and compared byte for byte with the original, so the "Round trip" column shows that nothing was lost. The gzip -9 column is only there as a reference to see how close a from scratch LZW gets to a well known tool.

File	Original	Compressed	Compressed %	gzip -9 %	Round trip
alice29.txt	152089	62254	40.9	35.6	OK
asyoulik.txt	125179	54996	43.9	39.0	OK
cp.html	24603	11322	46.0	32.3	OK
fields.c	11150	4970	44.6	28.0	OK
grammar.lsp	3721	1818	48.9	33.2	OK
kennedy.xls	1029744	309170	30.0	20.1	OK
lcet10.txt	426754	170025	39.8	33.8	OK
plrabn12.txt	481861	205184	42.6	40.3	OK
ptt5	513216	62222	12.1	10.2	OK
sum	38240	20108	52.6	33.6	OK
xargs.1	4227	2345	55.5	41.4	OK
Total	2810784	904414	32.2	25.9

So overall the files were compressed to about 32% of their original size with no data loss on any of them. gzip still does better (about 26%) because it also uses Huffman coding on top of the dictionary, but for a plain LZW the results are pretty close. The best result is ptt5 (a fax image) at 12.1% because it has a lot of repeating patterns, and the small files compress the least because the dictionary does not get much time to build up.