24

Infocom's Z-Machine, designed in 1979, compresses text using a basic 5 bit code which is not very efficient in practice, achieving maybe a 1.5:1 compression ratio.

Huffman coding would be far more efficient, although more complex to decode, possibly putting it beyond what 8bit machines could realistically handle. By 1979 it was already 27 years old. LZ77 and LZ78 were published just before then, but are not always used with Huffman coding. The earliest compression application I've found is Pack, which compresses just using Huffman coding, dating from 1982 or before.

So how well known was Huffman coding at that time? Had compression formats or applications been written that used it?

Improve this question
7
  • 6
    I recall covering Huffman coding in a computer science course in 1980. Simplicity to decompress would have been far more important than somewhat better compression (having played Zork in that timeframe as well).
    – Jon Custer
    Jun 21, 2019 at 0:04
  • 9
    I think this question contains some unreliable statements that lead people answering astray. For example, "Huffman coding would be far more efficient" is manifestly incorrect. Storing text as 5-bit codes would give you compression ratio of 1.6:1. I had a student last year who implemented straightforward Huffman algorithm for her project; for English texts she was seeing compression about 1.7:1. So, you seem to overestimate (and overstate) benefits of Huffman coding, whereas in the context of English text compression it is simply not that great.
    – introspec
    Jun 21, 2019 at 11:37
  • 1
    @introspec Thanks for the info there - I didn't know that pure Huffman coding would give such a modest improvement over fixed bit codes. The reason why it's not 1.6:1 is because while lower case letters are 5 bit, upper case letters, numbers, and punctuation are 10.
    – curiousdannii
    Jun 21, 2019 at 12:43
  • 3
    Not directly a file format, but the Fax Group 3 One-Dimensional Encoding was standardized in 1980. This uses a "variation of the Huffman keyed compression scheme". The coding table was statistically determined based on "the average frequency of black-and-white runs [of pixels] occurring in typical typed and handwritten documents".
    – TripeHound
    Jun 21, 2019 at 13:15
  • 4
    Huffman coding is not great for text if done at the byte (character) level. The "zero order" entropy of English is about 4.76, which gives a compression ratio about 1.7:1., not very far from the 5-bit code. To improve this you should consider intra-characters statistics, which is not so easy to implement in Huffman coding. LZ coding capture some of this dependence is a quite efficient way.
    – leonbloy
    Jun 22, 2019 at 14:18

5 Answers 5

Reset to default
25

Well, in fact, a closely related question has been asked (and answered) few years ago: What is the history of data compression tools on personal computers?

From that question, and its answer, it transpires that several implementations of Huffman algorithms were in use by the early 1980s. Specifically,

  • Unix "pack" command implements a standard Huffman algorithm. The earliest implementation of this command that I could find browsing unix sources is in AUSAM released in November 1979. The source for the compressor can be read here; it contains no mention of the author or original version date. However, the manual page for the command mentions author "Steve Zucker" and date "12/12/75", which suggests earlier use is not unlikely.

  • Unix "compact" command implements an adaptive Huffman algorithm. The earliest version of it that I could find browsing unix sources was in 4BSD released in November 1980. The source of the compressor contains text "Written by Colin L. Mc Master (UCB) February 28, 1979". Given that adaptive Huffman algorithm was first described in Gallager, R. (1978) Variations on a theme by Huffman, IEEE Transactions on Information Theory, 24(6), 668-674, I am pretty sure that this implementation is about the earliest it could have been.

  • Interestingly, and a bit illogically, Leo B. from the related question seems to remember that "compact" predates "pack". I guess this is likely to have something to do with how widely AUSAM was used at the time (I am guessing not very widely). A more likely candidate for a commonly used implementation of "pack" is System III released in 1982. The source of the compressor can be read here; it contains string "Adapted April 1979, from a program by T.G. Szymanski, March 1978".

If you add to this the fact that the first commonly used compressor for CP/M used static Huffman compression (see answer to the question that I already mentioned, as well as comments here), I am guessing the best way to answer your question would be:

  • If you are thinking to write a data compressor for text in the late 1970s / early 1980s, you are probably automatically thinking about using Huffman algorithm. The only well-known alternative at the time is probably RLE, which is irrelevant for texts.

  • LZW was invented in 1984 and became popular from about 1985, thanks to unix "compress" utility, see Welch, T. A. (1984) Technique for high-performance data compression, Computer, (52). I am not aware of any commonly used implementations of vanilla LZ78.

  • Perhaps surprisingly from the modern point of view, LZ77 was not recognized as a viable algorithm before the second half of 1980s. Taken literally, LZ77 does not compress well unless it is converted into LZSS (first described in 1982, see Storer, J. A., & Szymanski, T. G. (1982) Data compression via textural substitution, Journal of the ACM, 29(4), 928-951) or, possibly, processed on top by arithmetic or Huffman encoder (this is definitely second half of the 1980s - LZARI, LZHUF were first introduced in 1988, DEFLATE is later than this). This may also have something to do with the impenetrability of the original papers; maybe no-one tried to read these papers seriously before LZW patents came to light?

Improve this answer
28

According to Google Scholar, Huffman’s 1952 paper had 326 citations by 1979, which given the volume of publication at the time means it was well-known, as far as can be determined now. Most compression-related papers published around that time refer to Huffman’s paper, either because they use Huffman coding in some way, or to explain why they don’t! Given the Infocom’s staff’s background, it’s quite certain they knew of it.

Looking through those citations leads to some concrete implementations. For example, Tanenbaum’s paper on efficient instruction encoding cites the use of Huffman coding on Burroughs B1700 S-machines; this is described in Wilner’s 1972 paper on Burroughs B1700 memory utilization.

Improve this answer
13

If you actually look at how the Z-Machine compresses texts, it does the following (from memory, it's been a while):

  • There's a list of frequently appearing words (like "the", "and") which are directly encoded by an index.
  • It uses "shift" codes like in the teletypes to switch between different modes.

This makes it simple to write a fast decoding routine that can be used for output. More importantly, no extra memory is needed for output.

For the purposes of compressing the text enough that it would fit on a disk together with the code for (the part of) Zork they were going to ship this was sufficient, so I don't even think they'd investigate more complex compression schemes.

More complex compression schemes would have several disadvantages:

  • The decompressor would have to be written in 6502, as a resident routine, taking up more space in the "resident code" part of the RAM than the rather simple decoding routine outlined above.

  • The decompressor would have needed extra RAM for tables for something like Huffman decoding

  • Text was paged in using a virtual memory mechanism, so decoding would have been needed to apply to random parts; which complicates things.

So the answer to "why didn't they use Huffman encoding" isn't necessarily "it wasn't known" but more "it would have been much more complicated than the simpler compression scheme, which was good enough".

Yes, I have read "I specifically want to know when it was first used in compression formats", but to answer that you have to take the circumstances into account, and the premise "Huffman code is so much better, they could have just used it" doesn't apply to this circumstances.

So Huffman encoding would have been used when there was enough CPU power and enough RAM available to have a good trade-off between resources spent and compression gained. If it wasn't used, it doesn't follow that "it wasn't known".

Improve this answer
8
  • 1
    This doesn't really address the question. (Neither does Raffzahn's answer, to be fair.) It's a frame challenge, which is acceptable, but it might be a good idea to edit it to be clearer in that regard.
    – wizzwizz4 ♦
    Jun 21, 2019 at 7:21
  • 6
    The point is not "aren't all that complicated to implement". When you start with a code base on a mainframe, with uncompressed text, and want to port it to a micro, you do the simplest thing that possible works (as often in developing code). So you end up with something that's just good enough. OTOH, when you are trying to code a tool to compress single files, with enough RAM available to do use any algorithm you want, you end up with LZ77, LZ78 and pack. That's what drives "how commonly used" something is. As for "how well was it known", that's really difficult to determine.
    – dirkt
    Jun 21, 2019 at 7:45
  • 8
    @curiousdannii The table for ZSCII decode is less than 100 bytes plus about 50-80 bytes code for decode/encode. Even the most modest decoders for Huffman need between 2 and 5 KiB of RAM for code and tables - static RAM, not virtual. That's a lot on systems with 48 KiB or less - and several magnitudes past what the Zorkmachine needed.
    – Raffzahn
    Jun 21, 2019 at 11:17
  • 1
    @Raffzahn - Indeed.As I recall, the original IBM PC I first used Zork on had 32 kilobytes of memory.
    – Jon Custer
    Jun 21, 2019 at 13:32
  • 1
    @Jon IIRC the published requirements were 48K on the booter version, the DOS version would require more, but it does remain an impressive feat. Marc Blank and Stu Galley even wrote a paper on how they fit everything in the small amount of RAM available on micros. I still have HGTTG for 8-bit Ataris, which also requires 48K.
    – Stephen Kitt
    Jun 21, 2019 at 13:56
6

(This is not really a great question, as it's asking for speculation about knowledgeand decisions of people long ago, something rarely supportable by referencee)

It might be helpful to look into several factors to be included.

  • Huffman coding was of course well known.

  • Basic Huffman coding relies on variable length data words, something hard to handle on 8 bit chips

  • Implementing a generic Huffman decoding function on 8 bit CPUs may cost several KiB of code - all to be taken from the memory otherwise able to store (virtual) game content.

  • Working with fixed 16 bit words and according two-to-three can be done in just a few instructions, leaving more space for the game.

  • 5 bit encoding works quite well on straight 7 bit text.

  • In real life not the best encoding is right but the one good enough to do the job.

Improve this answer
13
  • 2
    @curiousdannii If you not want to know about infocom, then why asking about? If you want to ask something else, then do so - Try something like " was huffman coding in practical use by 1980" - simple and without any need to argue, isn't it - and the answer will simply be yes, quite a lot. But you also my want to specify to ask for the area of application you have in mind, as you may be focused on applications like working with distinct files, not compression in general.
    – Raffzahn
    Jun 21, 2019 at 0:50
  • 3
    This is anecdotal, but I believe a ~1970 OS I used (Eldon2 on KDF9) whose file system natively used 8 bits to store each algol basic symbol, at one point was considering using a variable-length Huffman encoding to give more space on its 30-million character disc. Since that didn't happen, I suppose the conclusion was that it wasn't worthwhile. I'll see if I can find a reference.
    – another-dave
    Jun 21, 2019 at 1:07
  • 4
    @curiousdannii I think your best bet is probably to edit this question to fit the answers (something like "Why didn't Z-Machine use Huffman coding?") and re-ask this one. None of the answers really address what you want to ask.
    – wizzwizz4 ♦
    Jun 21, 2019 at 7:18
  • 2
    @wizzwizz4 That seems rather unfair... especially for the second answer which was asked after even my clarifications (and I don't think it really needed much clarification to start with.) And if I did edit it like that, then I would be completely unsatisfied with these answers because they're unsubstantiated speculation. I'd prefer to just completely remove any mention of Infocom from the question if you think that would help.
    – curiousdannii
    Jun 21, 2019 at 7:27
  • 4
    @curiousdannii The fact that two independent answers came up with similar points should be telling that the wording of the question is asking for them - after all it doesn't count what question you intend, but rather what question is asked. In addition, it's not exactly polite to attest that people who spend their time for you answering the question you asked as 'they never really tried'. We can do better, can't we?
    – Raffzahn
    Jun 21, 2019 at 11:30
6

In 1971 I took an information theory freshman seminar at MIT which included Huffman coding. Huffman coding was well known and casually taught as something that was widely used, but as it was one of several topics, we didn't go deeply into existing applications.

Improve this answer
2
  • In the context of information theory, Huffman would be very well known. But the question is about software developers, not information theory. And even if software developers were widely aware of Huffman (which isn't guaranteed), there might have been reasons that they weren't using it in real-world software.
    – David Richerby
    Jun 22, 2019 at 12:14
  • The question itself was about how well Huffman coding was known. At the time, I was also a software developer. If Huffman coding was a good tool, it would have been used. The LZ compressions are not based on traditional Huffman coding because the symbol priorities are not pre-known.
    – cmm
    Jun 22, 2019 at 13:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .