Dr Peter Fenwick

1. Use a BW transform to derive all contexts of some fixed order, say 4, and use these to drive an escape-free PPM compressor/decompressor. This is the main substance of the report and presentation; it worked, but not nearly as well as hoped.

2. "Break open" the reverse BW transform to generate partial contexts during both compression and decompression, so aiding the operation of the coder and decoder.
   The report starts by developing analogies between the Fourier Transform and its associated spectra, autocorrelations, etc, on the one hand and the the Burrows Wheeler transform and PPM on the other. Invoking ideas of symmetry leads to a significant new understanding of the Burrows Wheeler operation.
   (I have long thought that we did not really understand the Burrows-Wheeler Transform. But the forward transform is essentially simple, at least in concept, and showed little scope for improvement. With these ideas the reverse transform looks the more likely for further study and deeper understanding. At least I hope so.)

3. Is there some relation between data compression and error correction codes? Compression can be thought of as a very noisy channel (encoding a single symbol into a range of possible symbols) and then generation of the codes to select the correct symbol from the "noise" codes; the encoder and decoder track each other and the "corrections" are what the compressor emits. (The ideas follow most readily from my earlier work on "Symbol Ranking" compression which uses an explicit symbol predictor/corrector mechanism).
   This third idea may provide a useful starting point for somebody with more imagination than me. It leads to two other ideas relating to the possible relationship between Error Correction and compression.

4. Can we omit some symbols (giving an erasure code) and then use a Viterbi-like trellis to recover feasible decodings. (Whew!)

5. The relatively new error-correcting "turbo-codes" use two interacting but complementary error-correcting codes to give superlative performance. Can something similar be done for compression? (It also ties in with the previous point.)
   But do we have suitably different compressors? The two compressors must work with the same symbol order, probably precluding a BW and PPM combination. But of those which retain the original "text" order, PPM and LZ-77 were shown to be equivalent by Bell, Cleary & Witten (in their book "Text Compression"). So until somebody invents say a symbol-by-symbol compressor which does not depend on contexts, there may be no suitable complementary candidates!
   If you have ideas, please try them!

Return to top

Some recent papers.

(The links for the electronic journal J.UCS, the "Journal for Universal Computer Science" are to the J.UCS Page for the appropriate month. The journal contains compressed Postscript files which may be copied and printed.)

Most of my papers and reports are available by anonymous ftp from ftp.cs.auckland.ac.nz/pub/staff/peter-f

• “Burrows–Wheeler compression : Principles and reflections” Theoretical Computer Science Vol 387(2007) pp 200–219
  Abstract After a general description of the Burrows Wheeler Transform and a brief survey of recent work on processing its output, the paper examines the coding of the zero-runs from the MTF recoding stage, an aspect with little prior treatment. It is concluded that the original scheme proposed by Wheeler is extremely efficient and unlikely to be much improved.
  The paper then proposes some new interpretations and uses of the Burrows Wheeler transform, with new insights and approaches to lossless compression, perhaps including techniques from error correction.
  A preprint of this paper is available from here

• "Burrows Wheeler -- Alternatives to Move to Front",
  Authors - Dr Peter Fenwick, Dr Mark Titchener, Michelle Lorenz. Presented at Data Compression Conference DCC-2003.
  Abstract The Burrows Wheeler Transform, first published in 1994, is a relatively new approach to text compression and has already proven to produce excellent results. However, there has been much research directed towards improving the efficiency of the Move to Front algorithm with varying degrees of complexity. This paper examines a relatively simple technique using a cached modeling system proposed by Fenwick and achieves very promising results.
  Information loss during the Burrows Wheeler Transform is also examined using Deterministic Information Theory measuring techniques developed by Titchener. This provides an interesting insight into what is actually occurring during the complete Burrows Wheeler Transform and can confirm whether manipulating the MTF algorithm is the correct approach to refining an already successful compression scheme.
  Full papers in PDF and in PostScript. (Please tell me if you have problems with these files. On my computer the Acrobat Reader has some trouble with fonts, but the hard-copy print is fine.)

• "Burrows Wheeler Compression with Variable Length Integer Codes", Software - Practice and Experience, Vol 32, No 13, Nov 2002, pp 1307 - 1316.
  Abstract The final coder in Burrows-Wheeler compression is usually either an adaptive Huffman coder (for speed) or a complex of arithmetic coders for better compression. This article describes the use of conventional pre-defined variable length codes or universal codes and shows that they too can give excellent compression. The paper also describes a "sticky Move-to-Front" modification which gives a useful improvement in compression for most files.

• "Variable-Length Integer Codes Based on the Goldbach Conjecture, and Other Additive Codes", IEEE Trans. Inform. Theory, Vol 48, No 8, pp 2412 - 2417,Aug 2002.
  Abstract This paper introduces a new family of variable length codes for the integers, initially based on the Goldbach conjecture that every even integer is the sum of two primes. For an even integer we decompose the value into its two constituent primes and encode the ordinal numbers of those primes with an Elias gamma code. The method is then elaborated to handle odd integers. The paper then develops a more general method of encoding any integer as the sum of two integers and developing suitable basis sets of integers. Although the codes which are generated by these methods are characterised by widely-varying and unpredictable lengths, they are over some ranges shorter than most other variable length codes.

• "Zeckendorf Integer Arithmetic", Fibonacci Quarterly Nov 2003, pp 405 - 413.
  For something quite different.... Fibonacci numbers are the basis of the "Zeckendorf" number representation which looks like a binary number but has no consecutive 1 bits. (By sending the Zeckendorf representation least-significant bit first and following its most significant 1-bit with another 1-bit the illegal pair 11 acts as terminator. The result is a very good variable-length code for integers.)
  However, can we perform arithmetic on these Zeckendorf representations? This paper shows that we can, giving procedures for addition, subtraction (and complementing), multiplication and division. "(preprint in PDF format)"

• "Some Perils of Performance Prediction : a case study on Pattern Matching", Software - Practice and Experience, Vol 31, pp 835-843 April 2001.
  Abstract Recent experience with string searching or pattern matching algorithms revealed wide discrepancies between predicted and observed performance. Further observations on a variety of computers revealed even greater variations between those algorithms on different computers. These observations are collected here as an example of problems in real-world comparison of algorithms.
  This is a companion to the following paper.

• "Fast string matching for multiple searches", Software - Practice and Experience, Vol 31, pp 815-833 April 2001.
  Abstract We present a string matching or pattern matching method which is especially useful when a single block of text must be searched repeatedly for different patterns. The method combines linking the text according to digrams, searching on the least-frequent digram, and probing selected characters as a preliminary filter before full pattern comparison. Tests on real alphabetic data show that the number of character comparisons may be decreased by two orders of magnitude compared with Knuth-Morris-Pratt and similar searching, but with an initialisation overhead comparable to 5 to 10 conventional searches.
  But see also the previous paper..

• "Symbol Ranking Text Compressors: Review and Implementation", Software - Practice and Experience Vol 28 No 5 pp 547-559 April 1998.
  This paper reviews several previous text compressors with 'symbol ranking' as a unifying theme. It includes the compressor described in Tech Rep 145.

• "Compression of Unicode Files", DCC-98 Data Compression Conference, Snowbird, Utah, March 1998.
  [A poster was presented at DCC-98 on the compression of Unicode files, showing that they can behave rather differently from conventional byte-oriented data. Experiments with a compressor using 16-bit data show that it often works better than standard byte compressors for Unicode data.] A pdf version of the paper is also available.

• "Symbol Ranking Text Compression with Shannon Recodings", J.UCS Vol 3, No 2 pp 70 85 Feb 1997.
  [A general introduction to "symbol ranking" text compression and a description of a proof-of-concept compressor. An extended version of Tech Rep 132]

• "The Burrows-Wheeler Transform for Block Sorting Text Compression -- Principles and Improvements", The Computer Journal, Vol 39, No 9, pp 731-740, 1996.
  [This is the paper which was written as the definitive summary of my experience with block sorting compression.]

• " Queue Prediction: an efficient scheduler for fast ATM cell transmission ", ACSC'97, Sydney, Australia Feb 1997.
  [This paper describes a new technique for controlling ATM cell transmission.]

• "Block Sorting Text Compression", ACSC'96, Melbourne, Australia Jan 1996.
  [This paper is the general overview of block sorting compression.]

• "Differential Ziv-Lempel Text Compression", J.UCS Vol 1, No 8 pp 587 598 Aug 1995.
  [ An account of an attempt to combine Ziv-Lempel (lossless) compression with Vector Quamtisation (lossy) compression. It includes some predictions on the limits of LZ compression.]

• "Huffman code efficiencies for extensions of sources", IEEE Trans. Comm., Vol 43 No 2 pp163 165, Feb 1995.
  [Athough coding the extensions of sources is a fundamental concept in Information Theory, there seems to be no work describing what actually happens in practice. This paper arose from a student assignment which showed that increasing the code extension can lead to a poorer code! Also available as Tech Rep 89.]

• "High-radix Division with Approximate Quotient-digit Estimation", Journal for Universal Computer Science (J.UCS) Vol 1, No 1, pp 2 22 Jan 1995.
  [A major problem in high-radix division is estimating the correct digit (and divisor multiple). While it is easy to get the right answer most of the time, it is much harder to get it right all of the time. This paper shows that allowing a bad estimate to be corrected can lead to much simpler control logic, with very little speed penalty.]

• "A new data structure for cumulative frequency tables", Software Practice and Experience, Vol 24, No 3, pp 327 336 Mar 1994.
  [This paper describes a new data structure which is especially designed to handle the cumulative frequency tables of arithmetic compression. See also Tech Rep 88 & 110.]