Sort order preserving data compression for extended alphabets

Abstract

The compression method is based on composing phrases from symbols. The authors extend the sort-order property to parsing models, i.e. to Variable-to-Fixed Length codes, or a static Ziv-Lempel algorithm, or alternatively a Tunstall algorithm for an adjoint source. The parsed phrases comprising the original storage data units have the same position in the sort ordering as the original units themselves. The VFL result may be further compressed by use of Variable-to-Variable Length techniques based on the relative frequencies of the parsed phrases. The sort-order property is facilitated by an 'end of record' symbol and requires a new zilch symbol.