A Look at Compression
By Dan Weiss


	Compression is a hot topic everywhere today. Computer users want to compress the files on their hard drives to save space. Cable companies want to compress their signals so that they can send 500 channels over the cable they are currently sending 50 channels. Graphic programs have new and even more powerful tools of compression with the JPEG and MPEG standards. Soon, they tell us, we will be able to fit 72 minutes of full motion video and sound on a CD where today we can only fit 72 minutes of sound. Everywhere you look compression is in use. But what is it and how does it work? Lets take a look at compression, by looking at two popular methods used.

Put the squeeze on
	Compression in the computer sense is taking a file and from it creating a smaller second file that can be used to recreate the first file. There are many ways to do this. All methods come down to one simple idea: replace a large amount of information with a small amount of information by finding things that are common in the data. As an example the file consisting of 

?AAAAAAABBAAAAAAACCBABABBBBBBBBBBBBBBABABBBAAAAABBABBAAAA? 

could be compressed as :

7A2B7A2C1B1A1B1A14B1A1B1A3B5A2B1A2B4A

Where the number preceding the letter tells how many times that letter should be repeated.As you can see this works out pretty good, except when there is a single letter, then the code takes up more space than the original letter. In fact if you had a block of text that very few letters were next to a similar letter (like this article) then the ?compressed? file would be much bigger than the original. In compression ?lingo? this is know as the degenerate case, and most algorithms have some similar worse case situation. In this algorithm we ?let the air out? of the file by counting runs of information that are the same.
	Counting the runs of information is known as ?Run Length Encoding? or RLE for short. RLE is used in the IFF ILBM standard and is very good where there are long runs of the same value. For this reason a two color picture (black and white for instance) compresses very well where a 24 bit picture (approximately 16.8 million colors) does not. Of course if the whole 24 bit image was on a particular color then it would compress very well, but usually they are not.
	Another advantage of RLE is that it executes quickly and is easy to implement. The following is a block of pseudo code that implements an RLE compressor :

/* File compressor */
curRun = NULL;
curRunCount = 0;
while (not end-of-infile)
{
	curChar = fscanf(infile,?%c?);
	if (curChar != curRun)
	{
		if (curRunCount != 0)
		{
			fprintf(outfile,?%c%c?,curRunCount,curRun);
		}
		curRunCount = 1;
		curRun = curChar;
	}
	else
	{
		curRunCount ++;
	}
}

The only problem with this code is that it assumes that the program that decompresses the file can tell a number from a piece of data. In the previous example let?s replace the letter ?A? with 1, ?B? with 2 and ?C? with 3. The data then becomes :

?11111112211111113321212222222222222212122211111221221111? 

and the compressed version becomes :

7122712312111211142111211325122112241

This is clearly a problem since you can?t tell the numbers from the data. We can get around this with the following convention. The first byte of the file will always be a count byte. The second byte will always be a data byte. This means that we can only do runs of at most 255 characters before we must define a second run of the same character. This way, the odd bytes in the file are count bytes and the even are data bytes. 
	Modifying the above code we get :

/* File compressor */
curRun = NULL;
curRunCount = 0;
while (not end-of-infile)
{
	curChar = fscanf(infile,?%c?);
	if (curChar != curRun)
	{
		if (curRunCount != 0)
		{
			fprintf(outfile,?%c%c?,curRunCount,curRun);
		}
		curRunCount = 1;
		curRun = curChar;
	}
	else
	{
		curRunCount ++;
		if (curRunCount > 255)
		{
			fprintf(outfile,?%c%c?,curRunCount,curRun);
			curRunCount = 1;
		}
	}
}

Now we can write the decompressor. The pseudo code would be:

/* File de-compressor */
while (not end-of-infile)
{
	fscanf(infile,?%c,%c?,runCount,runChar);
	for (i = 0; i < runCount; i++)
	{
		fprintf(outfile,?%c?,runChar);
	}
}

	As you can see the decompressor is trivial, which is a desirable attribute. In most cases it is more important to be able to decompress quickly than to be able to compress quickly. In the case of high speed animation (30 frames per second) compression is used as a way to get the image in from the hard drove (or CD-ROM) quickly (by having less data to load). Once the data is loaded it must be expanded quickly. This algorithm does that.
	But it needs a better ability to handle data that is nearly random. As mentioned in the beginning the case of every character being different than the last one would result in a doubling of the file. What we need is a way to block out these runs of randomness. Taking a page from the IFF ILBM implementation of RLE we will do the following :

If the high bit is set in a count byte then clear the bit and copy the number of bytes indicated directly from the file.

If the high bit is not set on a count byte then copy the next byte the number of times indicated.

This reduces the maximum run to 127 but handles random cases much better. The modified compressor pseudo code looks like this :

/* File compressor with random support */
curRun = NULL;
curRunCount = 0;
randomString = NULL;
randomCount = 0;
while (not end-of-infile)
{
	curChar = fscanf(infile,?%c?);
	if (curChar != curRun)
	{
		if (curRunCount != 0) /* ending a run */
		{
			fprintf(outfile,?%c%c?,curRunCount,curRun);
			curRunCount = 1;
			curRun = curChar;
		}
		else /* just beginning or in a random block */
		{
			if (randomCount != 0)
			{
				if (randomString[randomCount] == curChar)
				{
					/* second char in run */
					curRunCount = 2;
					curRun = curChar;
					randomString[randomCount-1] = 0;
					randomCount += 128; /* set high bit */
					fprintf(outfile,?%c%s?,randomCount,randomString);
					randomCount = 0; /* no random data now */
				}
				else
				{
					/* just another random character */
					if (randomCount == 127)
					{
						randomString[randomCount+1] = 0;
						randomCount += 128; /* set high bit */
						fprintf(outfile,?%c%s?,randomCount,randomString);
						randomCount = 0;
					}
					randomString[randomCount] = curChar;
					randomCount ++;
					curRun = curChar;
				{
			}
			else /* just starting out, treat as random */
			{
				randomString[randomCount] = curChar;
				randomCount ++;
				curRun = curChar;
			}
		}
	}
	else
	{
		curRunCount ++;
		if (curRunCount > 127)
		{
			fprintf(outfile,?%c%c?,curRunCount,curRun);
			curRunCount = 1;
			curRun = curChar;
		}
	}
}

	The code has gown a bit, but we now handle random runs of up to 127 characters at a time. In the example string this change the string from :

7A2B7A2C1B1A1B1A14B1A1B1A3B5A2B1A2B4A

to:

7A2B7A2C132BABA14B131ABA3B5A2B129A2B4A

	Which doesn?t look smaller because we are writing out the numbers, but actually uses 5 bytes less. If the data were more random the savings would be greater. Looking at the degenerate case of total randomness we only add one byte for every 127 characters. If the file has only one run of four characters out of every 127 then we end up with no net enlargement. Any more or larger runs result in some compression. The best case is when each run is 127 characters long resulting in a 63.5 to 1 compression ratio! This of course does not happen in the real world, but is fun to think about.
	The de-compressor does not get much more complicated with the new rules. The pseudo code becomes :

/* File de-compressor with random support */
while (not end-of-infile)
{
	fscanf(infile,?%c?,runCount);
	if (runCount > 128) /* random */
	{
		runCount -= 128; /* clear the top bit */
		fread(randomString,runCount,1,infile);
		randomString[runCount+1] = 0;
		fprintf(outfile,?%s?,randomString);
	}
	else /* a run */
	{
		fscanf(infile,?%c?,runChar);
		for (i = 0; i < runCount; i++)
		{
			fprintf(outfile,?%c?,runChar);
		}
	}
}


Look it up in a dictionary
	One of the advantages of RLE is that it can adapt to any data. This is because it is only worried about the data one byte at a time. This is also a disadvantage when the data tends to repeat itself over a range of more than one byte. For instance the string:

INOUTOUTINININOUTOUTOUTINOUTININOUTOUTOUTININOUT

would not compress at all under the RLE algorithm because every character is surrounded by different characters. On the other hand you can see that the string is simply the words ?IN? and ?OUT? repeated over and over. What would be great is if we could create a special compression scheme where ?IN? was replaced with 1 and ?OUT? with 2. Then the string would be :

1221112221211222112

A savings of 19 vs 48, better than 2.5 to 1 compression. If the string were longer, then the savings would be bigger. We could also apply the RLE algorithm to the compressed file and gain a little more. 
The approach of using short codes to replace chunks of the file is known as dictionary based compression (from the fact that the codes are looked up). Dictionary based compression can be very powerful since it can look at larger parts of the file. The problems with this method are two fold. First you must send a copy of the dictionary with the file which increases the size of the file losing some of the benefit of the compression, and secondly choosing and building a dictionary is not trivial and takes time.
	The first problem can be alleviated if you come up with a static dictionary that can be used for many files. When using a static dictionary it only needs to be built into the compressor and decompressor, not sent. This is the idea used by fax machines. When defining the Group 3 fax standard thousands of faxes were analyzed to find typical runs of white and black dots. When they were finished, a static dictionary was released, and built into every Group 3 fax machine. Because there is a very high chance that noise on the phone line could scramble the data, each line of the fax is treated as a separate ?file?. In a perfect world the whole fax would be one stream of data, but if a code gets changed then count bytes could be read as data and vice versa resulting in chaos. Treating each line separately limits the damage to a single line.
	It would seem that every fax is very different and that a simple RLE algorithm would be better but the dictionary based compression works very well, but only for faxes. If you try to apply the fax dictionary to regular data, the results are not as good. As you would expect this is typical of all dictionary based compression methods. An optimal dictionary for one file is not optimal for another. 
	How then do you build an optimal dictionary? In the case where there is a logical unit of information, like words in a sentence, a dictionary can be built from these units, much like in the ?IN/OUT? example. In situations where the data appears random what you choose for the entries in the dictionary don?t matter. Don?t matter? you say. No, it doesn?t really matter. Pioneering work by Abraham Lempel and Jacob Ziv (the L and Z of LZW compression) showed in the late seventies that you can create a useful dictionary on the fly by looking at the file. 

Lempel, Ziv and Welch
	LZW (Lempel - Ziv - Welch) compression is the backbone of much of the general purpose file compression today. The modem V42.bis compression method is based on LZW and the GIF and TIFF graphic formats use it as well. The idea is deceptively simple yet represents a major breakthrough. The basic algorithm works as follows:
	Create a dictionary array with some number of entries (2K to 4K entries is typical). Assume that the table starts with entry 256 because entries 0 to 255 are assumed to contain themselves (ie. entry 230 contains 230). Read the first two bytes in the file. Place the combination of the two bytes into the dictionary as the first entry. Since there was not a match for the pair in the dictionary originally, output the first byte and shift the second one down. Read the next byte. Does the buffer now hold a combination that is in the dictionary. If not, do as the first time. If it does match a combination in the dictionary, then keep reading data until you can no longer make a match. Then make a new code out of all the data and output the last code that was matched. Clear the buffer down to the last character read and start again.
	What this does is continue to build longer and longer codes based on what has come before. This is prefect for picking up runs of characters that repeat, like words. It may seem very inefficient to add a new code into the dictionary for every character or group of characters encoded but it has two advantages. The first is that you never know when a sequence of data will reoccur. By building a large table you stand a very good chance of catching the same sequence again. Using this method you can even catch longer sequences like repetitive phrases (such as ?I have a dream? from Martin Luther King Jr.?s famous speech). It also is very good at encoding long runs of the same data. The repeating string of XO (as in XOXOXOXOXOXOXO) would not be compressed by RLE encoding. But the LZW version would first save the X then the O then the codes for XO, XOX, OX, OXO and finally XO. All together the data would be reduced to seven codes,  a significant savings. 
	The second reason to encode all of the combinations is so that you do not have to send the dictionary along. Remember one of the disadvantages of dictionary based compression is having to send the dictionary. By using the a well defined method for creating the dictionary from the data you can create the dictionary from the compressed data and codes as well. Let?s look at how.

How?s it done?
	Going back to our first example we start with:

?AAAAAAABBAAAAAAACCBABABBBBBBBBBBBBBBABABBBAAAAABBABBAAAA? 

	The first two characters are read in. Since no codes exist yet, the first ?A? is output and the combination ?AA? is made entry number 256. Now the third ?A? is read in. Combined with the second ?A? it makes ?AA? which is code 256, so we read in another byte hoping to find an even longer match. We don?t so we output the code 256 in place of ?AA?, take the current buffer of ?AAA? and make it code 257. Then we remove the first two ?A??s since they have been output and read in the next character. Reading in the fifth character  we get ?AA? in the buffer. Since we have a match for ?AA? we read the next character hoping for a longer match. The sixth character is an ?A? so the buffer is now ?AAA?. This matches code 257 so we add another character. The seventh character is also an ?A?. There is no code for ?AAAA? so we output 257, create code 258 and remove the code ?AAA? from the buffer leaving ?A?. The next piece of data is ?B?. Combined with the ?A? we get ?AB?. There is no code for this so we have to output the ?A? by itself and create code 259. ?The next ?B? combines to make ?BB? there is no code for this either so the first ?B? is output and ?BB? becomes code 260. Next is an ?A? the ?B? in the buffer and the ?A? make ?BA? which has no code. Code 261 is created and the ?B? is output. Next is an ?A?. ?AA? is a code we know so we try for more. ?AAA? is known as well so we continue. ?AAAA? is also know so we try for five ?A??s. We don?t have a code for five ?A??s so we out put code 258 and create code 262 with first ?A?s. 
Let?s stop here a minute and make a table of what we have done.

Input	Output	Code Table
?AA?		?A?		256 = ?AA?
?AA?		256		257 = ?AAA?
?AAA?	257		258 = ?AAAA?
?B?		?A?		259 = ?AB?
?B?		?B?		260 = ?BB?
?A?		?B?		261 = ?BA?
?AAAA?	258		262 = ?AAAAA?

As you can see it paid off latter for creating the code 258 earlier. At this point any run of ?A??s from two to five characters can be encoded by a single code.
	But how does it look from the other end? How does the decompressor recreate the file? Working only from the data in the file we will recreate the dictionary and the file. The compressed file is :

?A{256}{257}ABB{258}?

The decompressor starts with an empty dictionary. Reading the first ?A? the decompressor places it in an empty buffer. The next code is {256}. This means that the compression program found a match on the second character. Since the first character is an ?A? and the second and third characters were the same as the first and second, the first two characters must be the same. The decompressor adds a second ?A? to the buffer and creates code 256, which it then outputs and leaves ?AA? in the buffer. The next piece of data is a code as well so again the new character must be an ?A?. Code 257 is created and output. The next piece of data is an ?A?. Since this is not a code, then we know we need to flush the buffer. The code 258 is created and the buffer is flushed except for the ?A? just read in. Finally the ?A? is output. The next character is a ?B?. Again since this is a character code, the code 259 is created and the buffer is flushed except for the ?B?, which is output.  The next ?B? repeats the process. The code 258 causes the buffer to be loaded with the first character from the code. Code 261 is created from the ?B? and the first ?A? in code 258. Now the entire entry for code 258 is loaded and output. 
	As you can see, the dictionary is recreated on the fly from the order of the data and the rules used to create it. While the explanations can get a bit lengthy it actually works out to be a straight forward algorithm. It is very good at compressing files that have repetitive data in them. Text files are loaded with repetitive data as are many graphics files. For example, a black and white file that has a gray pattern (every other bit is black) does not compress using an RLE algorithm. But as shown by the ?XOXOXO? example earlier, LZW will get better and better at compressing the file until it can take very large chunks at a time. This ability to adapt to the data is what makes it so powerful. 

What?s the difference
	When we first looked at dictionary compression we noted that the best results come when you understand the data you are compressing. LZW does well even when it knows nothing about the data. But if we look at the data, very often we can ?help? the LZW algorithm. The best case of this is called horizontal differencing. If you look at 24 bit pictures, they tend to feature gentle transitions from one color to another unlike Deluxe Paint pictures which offer sharp contrasts. If you think about it the transition from light to dark red is the same as from light to dark blue except for the color. To take advantage of this, we take the data and preprocess it. 
Take the value of the first pixel and subtract it from the second pixel. store the original first pixel and the difference between the first and second as the second pixel. Compute the third pixel by subtracting the original second pixel from the third pixel. Continuing through out the file you will notice some things. In places where there is a gentle even change, you will end up with long strings of the same value, which compress very well. Gradations of all colors now look the same (and compress with the same codes) because the change data instead of the color data is being recorded. In the case where the colors are random, then the data is random either way. In effect this becomes a win/win situation for very little effort. The file is easy to reconstitute after it has been uncompressed. Simply take the first pixel and add it to the second. Add the second to third and so on.

More later
	Well that concludes an overview of two of the more popular methods of data compression. There are many others, and there is even more to LZW than what we covered. In another issue of AC?s Tech we will look at implementing these and other compression algorithms on ?C?. Until then, keep in touch through this magazine or via internet at danw@slpc.com.