An extremely fast Ziv-Lempel data compression algorithm

Abstract

A new, simple, extremely fast, locally adaptive data compression algorithm of the LZ77 class is presented. The algorithm, called LZRW1, almost halves the size of text files, uses 16 K of memory, and requires about 13 machine instructions to compress and about 4 instructions to decompress each byte. This results in speeds of about 77 K and 250 K bytes per second on a one-MIPS machine. The algorithm runs in linear time and has a good worst-case running time. It adapts quickly and has a negligible initialization overhead, making it fast and efficient for small as well as large blocks of data. >