Now that we’ve got a working little ASCII compressor it’s time to talk about how “real” compression algorithms work.

Now honestly I should probably just drop a couple wiki links to Huffman_Coding and DEFLATE but presumably you’re here on my blog because you specifically want to hear me talk about computer science so here we go!

Let’s start by refreshing our memories on how we approached the problem of compression.

We started by discovering that normal ASCII text assigns a full 8-bits to every possible letter. We then did some research and found that some ASCII letters are much more common than others. That let us invent a new standard that squished common letters into 4-bits while expanding less common letters into 9-bits. This overall resulted in files that were 20-30% smaller than their plan ASCII equivalents.

So how would a professional approach the same problem?

Believe it or not they would do more or less the same thing. Professional tools achieve their impressive 80%+ compression standards using the same basic approach we did: Find unusually common data patterns and then replace them with much smaller compressed place holders. The professional tools are just much much smarter about how they find and compress these patterns than we were.

How much smarter? Let’s find out by comparing and contrasting what we did against what better compression tools do.

Our OK Idea: We designed our compression patterns based around our knowledge of average letter frequencies in the English language. While this worked OK there was the problem that not every text file follows the average English pattern. A report about zigzagging zebras is going to have a ton of z’s and g’s while a C++ code file is going to have lots of brackets and semi-colons. Our average English compression strategy won’t work very well on files like that.

Their Better Idea: Professional tools don’t use a single universal encoding scheme but instead create a unique encoding for every file based on their individual symbol frequency. So if a particular text file has a ton of “z”s or parenthesis or brackets it will get its own custom code that compresses those letters. This lack of a universal standard does mean that each compressed file has to start with a dictionary explaining the specific compression pattern used for that file but the space saved by using an optimized compression pattern for each file more than makes up for the space taken up by the dictionary.

Our OK Idea: We not only used the same compression codes for every single file, we used the same compression codes throughout every file. This was easy to program but could be sub-optimal on longer files. If a book starts out talking about zigzagging zebras but later focuses on electric eels then one half of the book might compress better than the other.

Their Better Idea: Many compressional algorithms split files into multiple segments and then compress them individually before gluing them together into an output file. This way each segment can have its own optimized compression pattern. So if one half of a file had a lot of “z”s but no “l”s it could get a compression pattern focused on “z”s. If the second half of the file switched things around and had lots of “l”s but almost no “z”s the algorithm could then switch to a new compression pattern that shrunk down the “l”s and did nothing with “z”s. Of course this means each compressed file has to have multiple dictionaries explaining the specific compression pattern and length of each file segment but once again the space you save in better compression outweighs the space you lose from the extra dictionaries.

Our OK Idea: Our compression code focused only on ASCII text files. This made it easy to design and test our project but also severely limits it’s utility.

Their Better Idea: Admittedly some professional tools also only focus on one file type. For example, PNG only compresses image files. But many other professional compression tools work by looking for repeated bit patterns of any sort and length. This lets them compress any file made of bits which is, well, all of them. Sure, not every file compresses particularly well but at least there are no files you plain can’t run the algorithm on.

Our OK Idea: Our compression code worked by replacing common 8-bit letter patterns with smaller 4-bit patterns. This means that even in a best case scenario (a file containing only our eight compressible common letters) we could only shrink a file down to 50%.

Their Better Idea: Professional tools don’t restrict themselves to only looking for common 8-bit patterns but can instead find repeated patterns of any length. This can lead to massive compression by finding things like commonly used 256-bit patterns that can be replaced with two or three bit placeholders for 99% compression. Of course not every file is going to have conveniently repeated large bit sequences but being able to recognize these opportunities when they do happen opens up a lot of possibilities.

So there you have it. The main difference between professional compression algorithms and our toy is that professional programs spend a lot more time upfront analyzing their target files in order to figure out an ideal compression strategy for that specific file. This obviously is going to lead to better results than our naive “one size fits all” approach.

But figuring out the ideal compression strategy for a specific file or type of file is often easier said than done! To go much deeper into that we’d have to start seriously digging into information theory and various bits of complex math and that’s way beyond the scope of this blog. But if this little project piqued your interest I’d definitely encourage you to take some time and study up on it a bit yourself.

BONUS PROJECT FOR ENTERPRISING PROGRAMMERS

Hopefully this article has given you a few ideas on how our little toy compressor could be improved. And while you probably don’t want to try anything as drastic as implementing a full Huffman style algorithm I think there are a lot of relatively simple improvements you could experiment with.

For example, what if you got rid the hard coded set of “English’s eight most common symbols” and instead had your algorithm begin compression by doing a simple ASCII letter count to figure out the eight most common symbols for your specific target file? You could then have your algorithm assign compression short codes to those eight symbols which should probably lead to results at least a few percentage points smaller than our one size fits all prototypes

Of course, in order to decompress these files you’ll have to start your file with a list of which short codes map to which letters. You could do this with some sort of pair syntax (ex: {0000:z,0001:l,0010:p}) or maybe just have the first eight bytes in a compressed file always be the eight symbols from your compression map.

And with that we’re pretty much done talking about compression, but speaking of improvements reminds me that my Lisp code is still slow as cold tar. So if you have any interest in Lisp at all I’d like to encourage you to tune in again next week as we analyze and speed up our code and maybe even talk a little about that “functional programming”.

Last time we invented and tested a super-simple compression algorithm that revolves around replacing the eight most common symbols in the English language with tiny 4-bit codes instead of their normal 8-bit representations (at the cost of replacing everything else with bigger 9-bit versions). We even did some examples by hand.

But this is a coding blog, so it’s time to write some actual code. When it comes to language choice our only real requirement is that the language be capable or working directly with bits and bytes and files and since pretty much every language ever has no problem doing that we’re open to choose whatever we want.

I’m personally going to choose Lisp and be keeping all my code in a file named “wrc.lisp” for “White Rabbit Compression”. You, of course, can follow along in whatever language you want. In fact, that would probably be the most educational approach to this series.

Anyways, like we talked about in the design phase, this project will mostly focus on processing lists of bits in batches of 8, 4 and 9. That means we’re going to need a convenient data structure for holding these lists.

Fortunately Lisp is built entirely around list processing and has some very powerful built in tools for creating and managing lists of numbers, so I will be representing our binary fragments as a plain old list of integers which will just so happen to always be either a 0 or a 1.

For those of you not in Lisp I bet your language has it’s own list structures. Could be a vector, a queue, a linked list, whatever. Anything that lets you add new stuff to the end and pull old stuff off the front will be fine.

Now the efficiency buffs in the audience might have noticed that we’re wasting space by using entire integers to keep track of mere bits. Shouldn’t we be using something else, like a bit vector?

Probably! But this is just the proof of concept first pass so doing things the easy way is more important than doing things the best way. If it turns out the program is too slow or memory hungry then we’ll revisit this decision.

With that in mind our first attempt at letter bit lists is going to look something like this:

; An 8-bit ASCII letter
(list 0 1 0 0 0 0 0 1)

;One of our 4 bit compressed letters
(list 0 0 1 1)

;One of our 9 bit labeled ASCII letters
(list 1 0 1 0 0 0 0 0 1)

Next up let’s write some helper functions that can turn real 8-bit bytes into our custom bit lists or turn our bit lists back into bytes.

(defun 8-bit-list-to-byte (bitlist)
    (+     (* 128 (first bitlist))
        (* 64 (second bitlist))
        (* 32 (third bitlist))
        (* 16 (fourth bitlist))
        (* 8 (fifth bitlist))
        (* 4 (sixth bitlist))
        (* 2 (seventh bitlist))
        (* 1 (eighth bitlist))))
        
(defun byte-to-8-bit-list (byte)
    (let ((bitlist nil))
        (if (>= byte 128)
            (progn
                (push 1 bitlist)
                (setf byte (- byte 128)))
            (push 0 bitlist))
        (if (>= byte 64)
            (progn
                (push 1 bitlist)
                (setf byte (- byte 64)))
            (push 0 bitlist))
        (if (>= byte 32)
            (progn
                (push 1 bitlist)
                (setf byte (- byte 32)))
            (push 0 bitlist))
        (if (>= byte 16)
            (progn
                (push 1 bitlist)
                (setf byte (- byte 16)))
            (push 0 bitlist))
        (if (>= byte 8)
            (progn
                (push 1 bitlist)
                (setf byte (- byte 8)))
            (push 0 bitlist))
        (if (>= byte 4)
            (progn
                (push 1 bitlist)
                (setf byte (- byte 4)))
            (push 0 bitlist))
        (if (>= byte 2)
            (progn
                (push 1 bitlist)
                (setf byte (- byte 2)))
            (push 0 bitlist))
        (if (>= byte 1)
            (progn
                (push 1 bitlist)
                (setf byte (- byte 1)))
            (push 0 bitlist))
        (nreverse bitlist)))

The logic here is pretty simple although the Lisp syntax can be a bit weird. I think 8-bit-list-to-byte is self-explanatory but byte-to-8-bit-list might need some explaining. The basic idea is that every bit in a byte has a specific value: 128, 64, 32, 16, 8, 4, 2 or 1. Because of how binary works any number greater than 128 must have the first bit set, any number smaller than 128 but larger than 64 must have the second bit set and so on.

So we can turn a byte into a list by first checking if the number is bigger than 128. If not we put a 0 into our list and move on. But if it is we put a 1 into our list and then subtract 128 before working with the remainder of the number. Then the next if statement checks if the numbe ris bigger than 64 and so on. The only Lispy trick here is that Lisp if statements by default can only contain two lines of logic: the first for when the if is true and the second when the if is false. Since we want to run two lines of logic when things are true we wrap them in a progn, which just lumps multiple lines of code into one unit.

Clear as mud? Let’s move on then.

With those generic helpers out of the way let’s move on to writing the core of our compressor: A function that can accept a byte and then transform it into either a 4-bit short code or a 9-bit extended code.

The first thing we’ll want is a single place in the code where we can keep the “official” list of which letters translate to which short codes. It’s important we have only one copy of this list because later on we might find out we need to change it and updating one list is a lot easier than hunting through our code for half a dozen different lists.

(defparameter *compression-map*
   '((160 (0 0 0 0)) 
     (101 (0 0 0 1))
     (116 (0 0 1 0))
     (97  (0 0 1 1))
     (111 (0 1 0 0))
     (105 (0 1 0 1))
     (110 (0 1 1 0))
     (115 (0 1 1 1))))

Here I’m using the ‘ shortcut to create a list of lists since (list (list 160 (list 0 0 0 0))…) would get really tiring to type really fast. Syntax aside the first item in each of the eight items in our list is the ASCII code for the letter we want to compress and the second item is the bit list we want it to compress to.

Now that we’ve gor our compression map in whatever format you prefer all we need is an easy way to get the data we need out of that map. During compression we want to be able to take a byte and find out it’s short code and during decompression we want to take a short-code and find out which byte it used to be.

Off the top of my head there are a few ways to do this. One would be to just loop through the entire list every time we want to do a lookup, stopping when we find an item that starts with the byte we want or ends with the list we want (or returning false if we don’t find anything). The whole list is only eight items long so this isn’t as wasteful as it might sound.

An easier solution (depending on your language) might be to use our master list to create a pair of hash tables or dictionaries. As you probably know these are one way lookup structures that link “keys” to “values”. Give the hash a key and it will very efficiently tell you whether or not it has stored a value for it and what that value is; perfect for our needs. The only trick is that since they are only one way and we want to both compress and decompress our data we’ll actually need two hashes that mirror each other. One would use the bytes as keys and reference the bit-lists. The other would use the bit-lists as keys and reference the bytes.

I think I’ll go with the hash approach since they are a more universal language feature than Lisp’s particular approach to list parsing.

Hash tables seem pretty weird until you understand how they work internally.

To translate my universal compression mapping into a pair of usable hash tables I’m going to first create the hash tables as global variables and then I’m going to use a simple Lisp loop to step through every pair in the compression map. During each step of the loop we will insert the data from one pair into each hash.

(defparameter *byte-to-list-compression-hash* (make-hash-table))
(defparameter *list-to-byte-compression-hash* (make-hash-table :test 'equal))

(loop
    for compression-pair in *compression-map*
    do    (setf 
            (gethash (car compression-pair) *byte-to-list-compression-hash*) 
            (cadr compression-pair))
        (setf 
            (gethash (cadr compression-pair) *list-to-byte-compression-hash*) 
            (car compression-pair)))

A little Lisp trivia here for anybody following along in my language of choice:

1) The :test keyword lets you tell a hash how to compare keys. The default value works great with bytes but not so great with lists so I use :test ‘equal to give the *list-to-byte-compression-hash* a more list friendly compartor.

2) To pull data out of or put data into a hash you use the gethash function. The fist argument is a key value, the second argument is the hash you want to use. I tend to get this backwards a lot :-(

3) “car” and “cdr” and combinitions like “cadar” are all old fashioned keywords for grabbing different parts of lists. I could have just as easily used chains of “first” and “second” but what’s the fun in that?

Lisp aside, we now have an official compression map and two easy to search hashes for doing compression lookups and decompression reverse lookups. Let’s put them to good use by actually writing a compression function!

The compression function should take an ASCII byte and check if it’s in the compression map. If it is it will return the proper 4-bit short code. If it isn’t in the map it should transform it to an 8-bit list, glue on a leading 1 and then return the new 9-bit list.

(defun compress-byte (byte-to-compress)
    (let ((short-code (gethash byte-to-compress *byte-to-list-compression-hash*)))
        (if short-code 
            short-code 
            (append '(1) (byte-to-8-bit-list byte-to-compress)))))

Nothing all that clever here. We take the byte-to-compress and lookup whatever value it has in the *byte-to-list-compression-hash*. We then use let to store that result in a local short-code variable. We then us a simple if statment to see whether short-code has an actual value (meaning we found a compression) or if it is empty (meaning that byte doesn’t compress). If it has a compressed value we just return it. Otherwise we take the original byte-to-compress, turn it into a bit list, glue a 1 to the front and return it.

Let’s see it all in action:

[1]> (load “wrc.lisp”)

;; Loading file wrc.lisp …

;; Loaded file wrc.lisp

T

[2]> (compress-byte 111)

(0 1 0 0)

[3]> (compress-byte 82)

(1 0 1 0 1 0 0 1 0)

Cool. It successfully found 111 (“o”) in our compression map and shrunk it from eight bytes down to four. It also noticed that 82 (“R”) was not in our map and so returned the full 8-bits with a ninth “1” marker glued to the front.

Next time we’ll start looking into how to use this function to compress and save an actual file.

Last time we talked about Alice in Wonderland and the deep cruelty of stores that play the same handful of movie trailers on endless loop.

More importantly we also talked about how computers use compression to shrink files down for easier storage and faster transfer. Without good compression algorithms the Internet would crawl to a halt and half the electronics you use on a daily basis wouldn’t exist. For instance, without compression a 2 hour HD movie would be over 300 GB; good luck fitting that all on one disc!

To better understand this vital computer science breakthrough we’re going to be writing our own ASCII text compression program.

Disclaimer: It’s not going to be a very good compression program. Like all of my let’s programs the goal here is education and not the creation of usable code. We’re going to be skipping out on all the security and error checking issues a professional compressor would include and our end goal is a modest 20% reduction in file size compared to the 75%+ reduction well known tools like Zip can pull off.

Now that your expectations have been properly lowered let’s talk about the structure of text files. After all, we can’t compress them if we don’t know what they’re supposed to look like or how they work.

The ASCII text standard is a set of 256 symbols that includes all 26 letters of the English language in both upper and lower case as well as all standard punctuation, some useful computer symbols (like newline) and a bunch of random symbols and proto-emoticons that seem like they were included mostly to fill up space.

The fact that there are 256 symbols is very important because 256 is exactly how high you can count using a single 8-bit computer byte. That means you can store one letter in one byte by simply using binary counting to mark down where the letter is in the ASCII chart.

For example, the capital letter “A” is in spot 65 of the ASCII chart. 65 in binary is 01000001. So to store the letter “A” in our computer we would grab a byte worth of space on our hard drive and fill it with the electronic pattern 01000001.

An ASCII text file is just a bunch of these 8-bit character bytes all in a row. If you want to save a 120 character long text you need a 120-byte long ASCII file. If you want to save a 5,000 character short story you need a roughly 5 kilobyte ASCII file.

Ok, cool. Now we know what an ASCII file’s guts look like. Time to start looking for patterns we can use for compression.

Patterns… patterns… here’s one!

The ASCII files we’ll be working with are all based on the English alphabet, and in English not all letters are used evenly. Things like “s”, “e”, and “a” get used all the time while poor little letters like “x” and “z” hardly ever see the light of day. And don’t forget “ ”! You might not think of the blank space as a letter but just imagine tryingtowritewithoutit.

So some letters are much more common than others but ASCII stores them all in identical 8-bit bytes anyways. What if we were to change that? What if we stored the most common letters in smaller spaces, like 4-bit nibbles*?

The biggest challenge here is figuring out a way to let the computer know when it should expect a nibble instead of a byte. In normal ASCII every letter is eight bits long which makes it easy for the computer to figure out where one letter ends and the next begins.

But since we’re going to have letters of different lengths we need some way to point out to the computer what to expect. A sort of virtual name-tag to say “I’m a 4-bit letter” or “I’m a normal 8-bit letter”.

Here’s a simple idea: Our short 4-bit letters will always start with a 0, on the other hand our 8-bit ASCII letters will always start with a 1.

This solution does have some drawbacks. If the first bit of our 4-bit letters is always 0 that means we only have three bits left for encoding the actual letter. Three bits is only enough to count up to eight so that means we will only be able to compress eight letters.

A bigger problem comes from the 8-bit ASCII letters. They need their full 8-bits to work properly so the only way to mark them with a leading 1 is by gluing it to the front and turning them into 9-bit letters. So while our common letters had their size cut in half our uncommon letters are actually getting bigger. Hopefully we’ll still come out ahead but it might be close.

It’s amazing how many problems are caused by people trying to apply averages to things that ought not be averaged

Anyways, it sounds like we’re going to have eight different shortcut codes to work with. What letters should we use them for? Well, according to Wikipedia the eight most common letters in the English language are, in order: E, T, A, O, I, N, S, H. So that’s probably a good bet if we want as much compression as possible.

But Wikipedia doesn’t count the blank space as a letter. However because it’s so common in text it’s definitely something we want to compress. Let’s add it to the front of the list and drop “H”. That means the letters we will be compressing are “ ”, E, T, A, O, I, N, S.

Or more accurately “ ”, e, t, a, o , i, n, s. Remember that in ASCII upper and lower case letters are coded differently so we have to choose which we want. Since lowercase letters are more common than uppercase it makes sense to focus on them.

Now that we have our eight compression targets all we have to do is assign them one of our short codes, all of which are just the number 0 followed by some binary. Let’s go with this:

“ ” = 0000

“e” = 0001

“t” = 0010

“a” = 0011

“o” = 0100

“i” = 0101

“n” = 0110

“s” = 0111

Also remember that any letter not on this list will actually be expanded by putting a “1” in front of it’s binary representation.

One Makes You Smaller

Whew! That was a lot of abstract thinking but believe it or not we now have a complete compression algorithm. And just to prove it we’re going to do a compression by hand.

But what should we practice on? Well, our theme is “Wonderland” and I seem to recall that Alice was able to shrink herself by fooling around with a bottle labeled “drink me”. In ASCII that looks like this:

Eight bits times eight letter means 64 bits total. But if we replace the space, ‘i’, ‘e’, and ‘n’ with our 4-bit shortcuts while adding a 1 flag in front of the remaining 8-bit (soon to be 9-bit) letters we get

Which is 9*4 + 4*4 bits long for a total of only 52 bits. So we saved ourselves 12 bits, which is almost 20% less space than the original. Not bad.

One Makes You Grow Taller

Of course, taking text and compressing it is pretty useless unless we also know how to take compressed text and expand it back into normal readable ASCII. So please take a look at the following bit sequence and see if you can figure out what it used to say:

0001001111111010000001011011010001

I don’t want anybody accidentally looking ahead so let’s push the answer down a page or so with some another random comic.

Information theory jokes are funny, right?

So the first thing to do here is to take that big messy data stream and split it into individual letters. Remember that according to our rules the length of each letter is determined by whether it starts with a 0 or a 1. The 0s are 4-bit letters and the 1s are 9-bit letters.

So here we go. 0001001111111010000001011011010001 starts with 0 so the first letter must be four bits long: 0001

After removing those four bits we’re left with 001111111010000001011011010001, which also starts with a 0 meaning our next letter is also four bits long: 0011

Removing those four letters leaves us with 11111010000001011011010001. Since that starts with a 1 that means our next letter is 9 bits long: 111110100

By doing this again and again we finally get these six letters:

Now that we have our individual letters it’s time to turn them into, well, letters. But the kind of letters people can read.

For the four bit letters we just reference the list of short codes we made up. Scroll up in the likely event that you neglected to commit them to long term memory.

For the nine bit letters we need to remove the leading 1 and then look up the remaining eight bit code in the official ASCII chart. For instance 111110100 becomes 11110100 which is the code for “t”.

And there we go, the compressed binary has successfully been turned back into human readable data.

I Don’t Like Pretending To Be A Compression Algorithm

Doing these examples by hand was a great way to prove our proposed compression algorithm actually works but I don’t think any of us want to to try and compress an entire book or even an entire email by hand. It would be much better to teach the computer how to do this all for us. Which is exactly what we’re going to start working on next time.

After all, this is a Let’s Program, not a Let’s Spend A Small Eternity Doing Mathematical Busywork.

* Yes, nibble is the actual official term for half a byte. Programmers are weird like that.