Optimal alphabet for single text compression
A text written using symbols from a given alphabet can be compressed using the Huffman code, which minimizes the length of the encoded text. It is necessary, however, to employ a text-specific codebook, i.e. the symbol-codeword dictionary, to decode the original text. Thus, the compression performance should be evaluated by the full code length, i.e. the length of the encoded text plus the length of the codebook. We studied several alphabets for compressing texts -- letters, n-grams of letters, syllables, words, and phrases. If only sufficiently short texts are retained, an alphabet of letters or two-grams of letters is optimal. For the majority of Project Gutenberg texts, the best alphabet (the one that minimizes the full code length) is given by syllables or words, depending on the representation of the codebook. Letter 3 and 4-grams, having on average comparable length to syllables/words, perform noticeably worse than syllables or words. Word 2-grams also are never the best alphabet, on the account of having a very large codebook. We also show that the codebook representation is important -- switching from a naive representation to a compact one significantly improves the matters for alphabets with large number of symbols, most notably the words. Thus, meaning-expressing elements of the language (syllables or words) provide the best compression alphabet.
Code (0)
등록된 구현이 없습니다.
Tasks
Text CompressionSimilar Papers 제목 키워드 기반
Compressing Multisets with Large Alphabets using Bits-Back Coding
Current methods which compress multisets at an optimal rate have computational complexity that scales linearly with alphabet size, making them too slow to be practical in many real-world settings. We show how to convert …
Support sufficiency as action-sufficient compression: a single-cycle rate-regret formulation
Robust decision-making requires compression. A system that forms a rich support state cannot usually preserve its full structure at the point of action. It must retain only those distinctions needed to act, verify, absta…
Almost-lossless compression of a low-rank random tensor
In this work, we establish an asymptotic limit of almost-lossless compression of a random, finite alphabet tensor which admits a low-rank canonical polyadic decomposition.
Channel Simulation and Distributed Compression with Ensemble Rejection Sampling
We study channel simulation and distributed matching, two fundamental problems with several applications to machine learning, using a recently introduced generalization of the standard rejection sampling (RS) algorithm k…
Image CompressionDZip: improved general-purpose lossless compression based on novel neural network modeling
We consider lossless compression based on statistical data modeling followed by prediction-based encoding, where an accurate statistical model for the input data leads to substantial improvements in compression. We propo…