Exploring gzip as a Language Model

In a previous discussion on language modeling without neural networks, the author generated Shakespeare using an unbounded n-gram model, relying solely on counting rather than training. This exploration led to the discovery of the paper 'Language Modeling is Compression,' which posits that every prediction model functions as a compressor, and all compression algorithms serve as prediction models. This raises the question of whether gzip, a standard compressor included with operating systems, can perform language modeling without neural networks or learned parameters. By priming gzip with a corpus and providing a text prompt, it attempts to continue the prompt by identifying byte sequences that compress effectively. The results indicate that while the output is not entirely coherent, gzip demonstrates a surprising level of understanding of the text. The mechanism behind this lies in the way compressors operate, utilizing fewer bytes for expected data and more for unexpected data. The core principle of information theory states that the number of bits required to encode a symbol is inversely related to the probability assigned to it. Gzip employs the DEFLATE algorithm, which compresses data by finding matches within a 32 KiB sliding window. A continuation that matches existing text in the window compresses more efficiently, allowing for a scoring system where smaller compressed lengths indicate better predictions. However, generating text presents challenges, as the naive method of selecting the next byte based on compression length can lead to poor results due to quantization noise. To address this, a beam search method is employed, evaluating multiple byte sequences to improve generation quality. The implementation is available on GitHub for further exploration.