Luísa: um método de compressão baseado em PPM

Abstract

Throughout the decades, many compression methods were proposed to transform symbols into binary codes that occupy less space. One method in particular is called PPM (Prediction by Partial Matching). This method uses context information to find the probability of each symbol, and uses entropy encoding to transform the probabilities into binary code. One characteristic of PPM is the coupling between the symbol search within a context and the actual coding. This coupling leads to a tight architecture that limits the way the compression is performed. This work proposes LUISA, a novel compression method based on PPM. The method innovates in separating the symbol search and the coding, turning these two stages into independent modules. This separation allows many strategies to be used in different aspects of the compression. This text presents some of these strategies, emphasizing scenarios where their usage is relevant. The experimental evaluation expands this analyzes, showing cases where the proposed method presents better compression ration when compared to PPM and GZip.