9

Before the advent of Lempel-Ziv family compression algorithms, there was an algorithm for "Information compression by factorising common strings" by A. Mayne and E. B. James (1975), based on Mayne's dissertation "Data Base Compression and Retrieval on Significant Substrings" (1972).

Were there any known compression programs based on that algorithm, or on a similar two-pass algorithm based on the same idea of deriving a dictionary for a file during the first pass, then applying it during the second pass, whether part of commercial OS packages, or distributed as freeware, given that the algorithm preceded Lempel-Ziv by several years?

A toy attempt to implement this algorithm (in XPL, of all languages) can be found in the book "Etudes for Programmers" by Charles Wetherell. The digital version is here.

(The printed book, if judged by the price, is a rarity; apparently it has a nostalgic value for many.)

Improve this question

1 Answer 1

Reset to default
10

After browsing the paper, it looks like the idea is to extract common sequences of letters from a given text into a table of a certain size, and then replace those substrings with references to the tables in the text.

That is how text in the Infocom text adventures is encoded when using the Z-Machine (together with some other tricks, e.g. "shift" codes for uppercase/lowercase similar to telex).

But I have no idea if the tables were created with that particular algorithm, or with a different algorithm. OTOH, the algorithm is straight-forward, so once you hit on the idea (even independently) you'd probably come up with a similar algorithm.

Edit (more details): As described in the reverse-engineered [Z-Machine standard], text is packed into three 5-bit codes per two bytes. There are "shift characters" that switch between lowercase, uppercase and punctuation alphabets (similar to shift codes in the Baudot telex encoding). There are also three special characters which together with the next 5-bit code form a reference into the dictionary, so the dictionary has a fixed maximum size of 3*32=96 entries. The dictionary entries I have seen can be frequent English words, game specific expressions, and are even used inside words.

This is literally the decoding algorithm from the paper, with three "special coding symbols" instead of the single @ used in the paper:

The decoding is performed by examining the compressed data for special coding symbols. When a special coding symbol is found the code is used to index to the appropriate string in the decoding dictionary. The string may then be substituted for the code.

To be useful, the Mayne-James algorithm needs (1) a fairly large amount of text, (2) text that has enough common substrings, (3) the need to compress text because space is more important than time, or the circumstances where decompression is needed are simple.

So text adventures are probably one of the few use-cases where this algorithm is really of use, given that the Infocom team had to port games like Zork from a PDP-10 mainframe to home-computers with limited floppy storage (which caused Zork to get split into three parts).

As Mark Williams mentioned in the comments, the Company Level 9 also used a dictionary based compression scheme in the A-Code virtual machine for their text adventures, confirming that text adventures are a prominent use case for compression. However, they use (at least in later versions) multiple dictionaries hashed on the first two letters of the word, with a "keep some letter from the previous dictionary entry" scheme, and any byte larger 0x5d seems to be an index into the "current bank" dictionary.

So that's sufficiently different from the Mayne-James decoding scheme that I would assume it was invented independently.

given that the algorithm was the state of the art for several years

Any proof for that? If you don't even know that it has been used in practice?

There have been quite a few compression schemes around well before Lempel-Ziv, which have been used frequently in many places, e.g. run-length encoding. And Huffman encoding is from 1952.

The printed book, if judged by the price, is a rarity

Some offers on Amazon for rare items have a price based on some sort of funny machine-learning algorithm; don't draw any conclusions from the price to the real value of the book.

Improve this answer
9
  • There is a distinction between various entropy encodings and dictionary-based algorithms. By "state of the art" I meant among the latter, and I'm basing that on the fact that it was selected as the theme for a non-trivial programming exercise in the book. If you can find another pre-LZ dictionary-based algorithm, I'd welcome the reference.
    – Leo B.
    Apr 30, 2022 at 7:28
  • Of course there's somewhat of a distinction, but e.g. run-length encoding is not entropy-based, and one could argue that "find the most common subsequences" is related to entropy. But I am objecting to the "state of the art" claim - for me, "state of the art" means the majority of programmers would have that algorithm in their toolbox, because it was widely known. Which I don't think it was, though it's easily recoverable once you hit on the idea. OTOH, you can still find Huffmann encoding on the syllabus of many university courses.
    – dirkt
    Apr 30, 2022 at 8:10
  • Shouldn't it be "the majority of programmers in the field of data compression"? If so, they would be familiar with it if they kept up with relevant publications. To prevent people from reading the question too narrowly, I'm going to update it.
    – Leo B.
    Apr 30, 2022 at 8:22
  • 1
    @LeoB., isn't that the abbreviations part of the standard? Paraphrased: In Versions 3 and later, Z-characters 1, 2 and 3 (z) represent abbreviations, sometimes also called 'synonyms' (for traditional reasons): the next Z-character (x) indicates which abbreviation string to print ... the interpreter must look up entry 32(z-1)+x in the abbreviations table and print the string at that word address.
    – paxdiablo
    Apr 30, 2022 at 10:47
  • 3
    @LeoB. I have seen the list of abbreviations for Zork, and it's not something I'd have chosen manually (though of course I don't know how it was chosen), so I suspect they ran some kind of algorithm on it to decide table entries. Whatever this algorithm was. If it was not based on the Mayne-James paper, they probably re-invented something very similar.
    – dirkt
    Apr 30, 2022 at 16:43

You must log in to answer this question.

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