Codelet parsing: quadratic-time, sequential, adaptive algorithms for lossy compression

Abstract

The codelet parsing algorithms were proposed for lossy compression. The algorithms sequentially parse a given source sequence into phrases, say, sourcelets, and map each sourcelet to a distorted phrase, say, a codelet, such that the pre-letter distortion between the two phrases does not exceed the desired distortion. The algorithms adaptively maintain a codebook, and do not require any a priori knowledge of the source statistics. The algorithms use approximate string matching and, at each epoch, carefully select one of the many approximately matching codewords to balance between the code rates in the current epoch versus the code rate from the resulting codebooks in future epochs. The algorithms are quadratic-time in the length of the source sequence and output a distorted sequence that can be naturally losslessly compressed using the Lempel-Ziv algorithm.