Introduction

Welcome to the crypt...

This web contains a record of most of my work in text data compression during the late 1980s and early 1990s. I created this web because the email I receive has shown that there is continued interest in these algorithms from students, academics and practitioners, and I thought it was about time I consolidated all my compression work into one well-organized resource.

The algorithms I have created reside at opposite ends of the speed/compression tradeoff scale. From 1986 to 1989, while working towards my Ph.D., I researched text compression at the high-compression end of the scale and produced the SAKDC algorithm which was, to my knowledge, the highest-compression text compression algorithm in the world at the time. If you're interested in this high-compression algorithm, you may wish to take a look at my Ph.D. Thesis which was published as a book (which you can purchase online).

Upon graduating, I decided to explore the other end of the scale and from 1990 to 1992 produced the LZRW series of algorithms which provided reasonable compression at very high speed. The LZRW1 algorithm is still one of the fastest known text compression algorithms.

The high-compression (SAKDC, MMDC) algorithms were implemented in Ada under VAX/VMS using all sorts of obscure libraries and interfaces. This made their implementations appropriate for research experimentation only. In contrast most of the algorithms in the high-speed LZRW series were implemented in short sections of C code and, for a while, they became quite popular.

Unfortunately, during this happy rollout, some patents popped out of the US patent system that cast a shadow over the LZRW series algorithms, and they became effectively unuseable in any practical application. If you want to use them in any product (whether free or commercial), you will have to do some in-depth patent homework and algorithm development/modification so as to avoid infringement. If you think that's easy, then you should be aware that Microsoft tried to use an LZ77/LZRW1/etc variant, specifically designed not to infringe existing patents, in its MS-DOS V6 operating system, and ended up having to pay Stac about $80m in the resulting patent lawsuit. For this reason, I would like to take this opportunity to state that the code provided in this web (and FTP site) is provided with the intention that it be used for educational and recreational use only.

This web was created in a hurry in May 1996, but was not finished and placed online until August 1997. Future additions and changes to the web are likely to be just as sporadic. I will be creating a mailing list to which to post notice of such updates, but until then, the best thing you can do to stay up to date is to either check for changes every few months in the personalized change list on the RossNet Home Web, or register at The Registry. I will email all registrees when I get the mailing list web going.

I hope that you enjoy the compression crypt. To get started take a look at the crypt Policy or surf the links at the top of this page.

Ross N. Williams
ross@ross.net
30 August 1997.