Longest match string searching for Ziv-Lempel compression
T. Bell and D. Kulp
Department of Computer Science
University of Canterbury
Abstract
Ziv-Lempel coding is currently one of the more practical data compression schemes. It operates by replacing a substring of a text with a pointer to its longest previous occurrence in the input, for each coding step. Decoding a compressed file is very fast, but encoding involves searching at each coding step to find the longest match for the next few characters. This paper presents eight data structures that can be used to accelerate the searching, including adaptations of four methods normally used for exact match searching. The algorithms are evaluated analytically and empirically, indicating the trade-offs available between compression speed and memory consumption. Two of the algorithms are well-known methods of finding the longest match --- the time-consuming linear search, and the storage-intensive trie (digital search tree.) The trie is adapted along the lines of a PATRICIA tree to operate economically. Hashing, binary search trees, splay trees, and the Boyer-Moore searching algorithm are traditionally used to search for exact matches, but we show how these can be adapted to find longest matches. In addition, two data structures specifically designed for the application are presented.