LZB: Data Compression with Bounded References

In this paper, we propose a new compression/decompression algorithm called LZB which belongs to a class of algorithms related to Lempel-Ziv (LZ). The distinguishing characteristic of LZB is that it allows decompression from arbitrary points in compressed data and decompressing a portion of compressed data does not require decompressing from the beginning. This is accomplished by setting a limit on how far back a reference in compressed data can directly or indirectly point to. This limit is defined as a sliding gate. In the well-known LZ77 algorithm, every match may be (directly or indirectly) referenced back to its first detected occurrence in the input. Hence, in order to decompress any part of the data we need to decompress from the beginning of compressed data. However, in LZB each match is only traced within the confinement of the designated gate size. This eliminates the need to decompress from the beginning. An example is illustrated in Figure 1. In order to take advantage of LZB and decompress data from any arbitrary location in the stream, the decoder needs to know where to start. During the compression, LZB stores a list of markers which specify distinct positions in the compressed version and their corresponding positions in the uncompressed version. LZB starts the decompression from the closest marker preceding the gate of the beginning of the data of interest.