A Block-sorting Lossless Data Compression AlgorithmAbstract: "We describe a block-sorting, lossless data compression algorithm, and our implementation of that algorithm. We compare the performance of our implementation with widely available data compressors running on the same hardware. The algorithm works by applying a reversible transformation to a block of input text. The tranformation does not itself compress the data, but reorders it to make it easy to compress with simple algorithms such as move-to-front coding. Our algorithm achieves speed comparable to algorithms based on the techniques of Lempel and Ziv, but obtains compression close to the best statistical modelling techniques. The size of the input block must be large (a few kilobytes) to achieve good compression." |
Common terms and phrases
aabrac abraca acaabr alphabet arithmetic coding Birrell block of text block size book1 bracaa Brown and Hershberger Burrows bytes C[ch caabra Calgary Compression Corpus Cardelli ch characters character L[i coder coding scheme comparisons compression programmes Computational Geometry Data Compression Algorithm decompress Dynamic Typing edited by Brown elements encodes example File System final character Glassman Guarino Reid Guibas gzip hash table Hector corpus Hisgen Huffman or arithmetic input block input character inverse operation Jerian Lamport last character Lempel and Ziv lexicographical order Lossless Data Compression matrix Modula-3 move-to-front coding Multiprocessor Nelson number of characters number of instances original string output Owicki performance personal computing Program radix sort reversible transformation rows Sept set R[i simple Simple Polygon sort the rotations sorted rotations sorts the suffixes starting with ch step C1 step M2 step Q6 suffix tree suffixes starting ch Swart vector Vesta Video Review Wobber