compression and TLS

This is not a proposal for the TLS 3.1 specification, but here is some
information for those that would like to look forward past this year. I
mentioned an unpatented compression algorithm at the IETF meeting and
here (finally) is a pointer to it.

I am forwarding the following from somebody who wishes to be protected
from sending to a large list. :-)



Mike Burrows [of DEC] gave me the following recent reference for the
compression algorithm that you had in mind:

This is a paper by a third party (Mark Nelson). It includes source 
code and a link to the original paper by Burrows and Wheeler. Neither 
this paper nor the original paper are detailed enough to constitute 
a specification. Someone would need to put in some work to fix
parameters, etc., and in particular to fix a Huffman coder. This could
be a drawback.

There are several other implementation of this algorithm. Mark Nelson's 
is good but not great; it is apparently reasonably clean. Mike Burrows's 
is better, Mike says, but Digital is not distributing it. (It is 
being used in some products, but has never been licensed on its own. 
As far as we know, there are no patents on this algorithm.) In Mike's 
implementation, this algorithm is a bit slower but compresses better 
than gzip. 

Mike recommended considering another compression algorithm, to which 
he refers as Wheeler hashing because Wheeler discovered it in 1983. 
When Wheeler hashing is combined with a suitable Huffman back-end, 
it performs better than Unix compress in all dimensions. The algorithm 
was first described in: 

    Raita, T. and Teuhola, J. (1987), "Predictive text compression
    by hashing", ACM Conference on Information Retrieval

This algorithm has been patented (5,229,768) by K. Thomas in 1993, 
but given the dates the patent should probably not hold. The algorithm 
is used in the Internet Draft "PPP Predictor Compression Protocol" 
This might be an advantage.

Received on Friday, 2 August 1996 23:23:39 UTC