LUISA: Decoupling the Frequency Model From the Context Model in Prediction-Based Compression. (7th July 2020)

• Record Type: Journal Article
• Authors: Fulber-Garcia, Vinicius; Sardi Mergen, Sérgio Luis
• Is Part Of: Computer journal. Volume 64:Number 9(2021)
• Page Start: 1437
• Page End: 1450
• Publication Date: 2020-07-07
• Subjects: data compression -- lossless compression -- prediction by partial matching -- prediction tree -- LUISA -- compression methodology; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxaa074
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: Prediction-based compression methods, like prediction by partial matching, achieve a remarkable compression ratio, especially for texts written in natural language. However, they are not efficient in terms of speed. Part of the problem concerns the usage of dynamic entropy encoding, which is considerably slower than the static alternatives. In this paper, we propose a prediction-based compression method that decouples the context model from the frequency model. The separation allows static entropy encoding to be used without a significant overhead in the meta-data embedded in the compressed data. The result is a reasonably efficient algorithm that is particularly suited for small textual files, as the experiments show. We also show it is relatively easy to built strategies designed to handle specific cases, like the compression of files whose symbols are only locally frequent.