Z-Characters
Zork had to fit on a floppy and run on a pile of home computers that agreed on almost nothing. The second problem was solved with a virtual machine. The first was solved by deciding that a capital letter is a luxury.
New to compression? Start here
Only patterns can be spent
A file gets smaller for one of three reasons. Something in it repeats, so the second copy can be a note saying where the first one was. Or some symbols are commoner than others, so the common ones can be given shorter codes and the rare ones longer. Those two keep every bit, and are called lossless. The third is to throw information away on purpose, which works only where something can be relied on not to miss it: an eye, an ear, or an application that never needed it.
The first two are spending a pattern, and a pattern can only be spent once. Compress an already compressed file and you usually get nothing, or a little worse, because the first pass took what was there. Not always: a different method can find structure the first one was not looking for, which is why some formats chain two. What is certain is the counting argument underneath, and it is about all inputs rather than about yours: no lossless method can shorten every possible input, because shortening some must lengthen others. The machines here are choosing which inputs to be good at.
The machine for this idea on its own is Huffman, if you would rather press it than read about it.
A computer only has numbers
There are no letters in a computer, no colours and no sound. There are numbers, and an agreement about what a given number means. The letter A is a particular number because a committee said so, and for no other reason.
That agreement is an encoding, and the interesting part is never the table. It is what the table costs: how many bits each symbol takes, which symbols were favoured, what happens to the ones nobody thought of, and whether you can start reading in the middle. Every machine in this topic is an argument about that cost, settled differently.
The machine for this idea on its own is ASCII, if you would rather press it than read about it.
The encoder
1 Letters: a lowercase letter costs one Z-character, and nothing else does
2 Shift: uppercase and punctuation live in two more alphabets, reached one character at a time
3 Pack: three five-bit characters to a sixteen-bit word, with one bit spare
4 End: that spare bit, on the last word, is how a string knows where it stops
26 bytes stored against 37 as plain characters, so 30% smaller. It decodes back to exactly what you typed.
Checked when this page loaded: all 76 characters in the three alphabets encode at the advertised cost and decode back to themselves, with 0 exception(s). The opening line costs 38 Z-characters in lowercase and 66 shouted, which is 174% of it.
A floppy, and a room full of machines that agreed on nothing
A game that sold well at the turn of the eighties had to run on the Apple II, the TRS-80, the Atari 800, the PET and whatever arrived next month, and none of them agreed about anything. Infocom shipped its first Zork in November 1980, on the TRS-80 that December and the Apple II the following February, which is the world this answer was built for. Infocom's answer was to stop writing games for computers. They wrote one imaginary computer, the Z-machine, and then wrote a small interpreter for it per platform. The game shipped as a file.
That solved portability and created a second problem. The story file had to hold the whole game, and the whole game is almost entirely prose.
Five bits, and the arithmetic that follows
A Z-character is five bits, which is 32 values. English needs a good deal more than 32, so the scheme keeps three alphabets of 26 and spends a Z-character to move between them for exactly one character. Lowercase lives in the first, so it is free. A capital is a shift and then a letter. So is a comma.
Six of the 32 values are spent before any letter gets one: zero is a space, three point into an abbreviation table, and two are the shifts. That is why the letters start at six rather than at zero, and why every calculation on this page begins by adding six.
Three Z-characters make fifteen bits, and a word is sixteen. The bit left over is not padding. Set on the last word of a string, it is the terminator, which means the length of a string is stored nowhere at all: a reader takes words until one of them says stop.
What it actually saved
Less than you would guess, and the standards document says so plainly: the compression factor "is not really very good". The figure it offers is a hundred and fifty-five thousand characters of text becoming ninety-nine thousand bytes.
That figure cannot be this scheme alone, and the arithmetic says so. Ninety-nine thousand bytes is 49,500 words, which is 148,500 slots at three to a word. The cheapest a character can possibly be is one slot. So 155,000 characters need at least 155,000 slots, and the figure is 6,500 short of the floor before a single capital letter is charged for.
What closes the gap is the part this page does not model. Three of the thirty-two Z-characters point into a table of ninety-six strings that the compiler assembles from the finished game, and a single pair of Z-characters can stand for a whole repeated phrase. The standards document quotes both numbers without saying that one contains the other; the arithmetic is what says it must.
Even so, two thirds of a byte per character is not remarkable, and it was not the point. Any scheme here had to be undone by an interpreter running on a machine with almost nothing in it, and this one costs a shift, a mask and an add. What made the Z-machine matter was that the file was the same everywhere, and Zork still runs today for the same reason.
Five bits had run out once before. Baudot hit the same wall in the 1870s and answered with a shift character that changed what every code after it meant, which is exactly the move on this page, a hundred years later, on a machine with sixteen-bit words to fill.
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| all 8 samples encode, pack into words, unpack and decode back to themselves | yes | including a capital, a comma and a character in no alphabet, which take four Z-characters between them |
| a lowercase letter costs 1 Z-character, a capital 2, a comma 2, and a character in no alphabet 4 | yes | lowercase is free because prose is made of it; everything else spends a Z-character moving between alphabets |
| 13 Z-characters pack into 5 sixteen-bit words, 3 to a word with 2 of filler | yes | 3 times 5 is 15, and the sixteenth bit marks the last word, which is how a string ends without a length |
| a shift applies to one character only: "Ab" comes back as "Ab" and not as "AB" | yes | the alphabet resets after every character that is not itself a shift, which is why a capital costs two and a word of capitals costs double throughout |
| 55 characters of lowercase prose fit in 19 words, or 38 bytes against ASCII's 55 | yes | about 31% saved, and only on prose; the same length in capitals would not fit at all |
What is real here, and what is not
The abbreviations are missing, and they are worth about ten per cent
Z-characters 1, 2 and 3 select an entry from a table of 96 strings, and the compiler builds that table by looking at the finished game and finding what it repeats. That is not something this page can derive from a sentence you typed a second ago, so it does not pretend to. Every byte count here is therefore about ten per cent higher than a real story file would manage on the same text.
This is version 3, and the earlier versions shifted differently
In versions 1 and 2 there were shift-lock characters as well, so a run of capitals could be entered once and left on. Version 3 dropped the locks and made every shift last exactly one character, and that is what is modelled here.
Saying it is “what Zork I shipped as” would be too tidy, and this page said it until a reader pointed at the date. Zork I reached the TRS-80 in December 1980, before version 3 existed; the early releases are versions 1 and 2, and the copies in circulation now are mostly the later version 3 ones. The encoding above is the version 3 rule.
It is the text, not the Z-machine
No opcodes, no object tree, no dictionary, no parser, no save format. The Z-machine is a whole virtual computer and this is one thing it does with strings.
ZSCII is not ASCII, and this page cheats on the escape
A character in none of the three alphabets is written as a shift, an escape, and then a ten-bit code split across two more Z-characters: four Z-characters for one letter, which is worse than storing it plainly. The cost shown here is right.
The code is not. The standard says those ten bits carry a ZSCII character code, and ZSCII agrees with ASCII only up to 126; above that it has its own table, so an accented letter has a ZSCII number that is nothing to do with its Unicode one. This page sends the Unicode value, because the alternative is shipping a translation table to make a point about arithmetic. So for anything above plain ASCII, believe the four Z-characters and do not believe the two numbers inside them.
The round trip is checked, and the check could be wrong too
Everything typed is encoded, packed, unpacked and decoded, and the result is compared against what you typed. If they differ the page says so rather than showing you a number. That catches an encoder that disagrees with its own decoder; it would not catch both of them being wrong in the same direction, which is what the tests beside this page are for.