Frequency-Ordered Tokenization for Better Text Compression
| Authors | Maximilian Kalcher |
| Year | 2026 |
| Field | AI / ML |
| arXiv | 2602.22958 |
| Download | |
| Categories | cs.IT, cs.CL |
Abstract
We present frequency-ordered tokenization, a simple preprocessing technique that improves lossless text compression by exploiting the power-law frequency distribution of natural language tokens (Zipf's law). The method tokenizes text with Byte Pair Encoding (BPE), reorders the vocabulary so that frequent tokens receive small integer identifiers, and encodes the result with variable-length integers before passing it to any standard compressor. On enwik8 (100 MB Wikipedia), this yields improvements of 7.08 percentage points (pp) for zlib, 1.69 pp for LZMA, and 0.76 pp for zstd (all including vocabulary overhead), outperforming the classical Word Replacing Transform. Gains are consistent at 1 GB scale (enwik9) and across Chinese and Arabic text. We further show that preprocessing accelerates compression for computationally expensive algorithms: the total wall-clock time including preprocessing is 3.1x faster than raw zstd-22 and 2.4x faster than raw LZMA, because the preprocessed input is substantially smaller. The method can be implemented in under 50 lines of code.
Engineering Breakdown
Plain English
This paper introduces frequency-ordered tokenization, a preprocessing technique that improves text compression by reordering token vocabularies according to natural language frequency distributions. The approach tokenizes text with Byte Pair Encoding (BPE), assigns small integer IDs to frequent tokens, encodes with variable-length integers, then compresses with standard tools like zlib or LZMA. On the enwik8 benchmark (100 MB Wikipedia), it achieves 7.08 percentage point improvements for zlib, 1.69 pp for LZMA, and 0.76 pp for zstd, with consistent gains on larger datasets and non-English text. The method is simple, general-purpose, and compatible with any downstream compressor.
Core Technical Contribution
The core novelty is exploiting Zipf's law—the power-law distribution of token frequencies in natural language—to optimize entropy encoding during compression preprocessing. Rather than using arbitrary token IDs from BPE, the authors reorder the vocabulary so frequent tokens map to small integers, reducing bit-width in variable-length encoding schemes. This differs from the classical Word Replacing Transform by explicitly leveraging frequency ordering before compression, rather than relying on the compressor to discover token frequency patterns. The technique is remarkably simple (essentially a post-processing sort of the BPE vocabulary) yet yields measurable and consistent gains across multiple compression algorithms and languages.
How It Works
The pipeline operates in four sequential stages. First, input text is tokenized using standard Byte Pair Encoding, producing a sequence of token IDs. Second, the token vocabulary is sorted by frequency (descending), with the most frequent tokens assigned the smallest integer identifiers (0, 1, 2, etc.). Third, the token sequence is re-encoded using variable-length integer encoding (e.g., varint32 or similar), where small integers require fewer bytes than large integers. Finally, the compressed output is passed to a standard compressor (zlib, LZMA, zstd, etc.). The vocabulary ordering must be stored as overhead in the compressed file so the decoder can reconstruct the original token IDs, but this overhead is typically small relative to the file size. The technique leverages the fact that variable-length encoders and entropy coders work best when symbols have already been sorted by probability, reducing redundancy.
Production Impact
For engineers implementing compression pipelines, this technique is a low-cost preprocessing win that stacks with existing compressors without modification. In production systems handling large text datasets (logs, documents, training corpora), adding frequency-ordered tokenization could reduce storage by 1-7% depending on the downstream compressor—meaningful at petabyte scale. Integration is straightforward: add a tokenization and reordering step before compression, and a reordering reversal after decompression; no changes to the compressor itself are needed. The trade-off is minimal: vocabulary overhead is small, and the sorting and variable-length encoding add negligible CPU cost compared to compression time. However, the gains are most pronounced with simpler compressors (zlib) and diminish with modern entropy coders (zstd), so ROI depends on your compression stack.
Limitations and When Not to Use This
The paper shows diminishing returns as compressors become more sophisticated—zstd only gains 0.76 pp, suggesting advanced compressors already optimize token frequency implicitly. The approach assumes BPE tokenization; performance with subword or character-level encodings is unclear. Vocabulary overhead, though small on large files, may be unfavorable for very short texts or streaming scenarios where file headers dominate. The paper does not address dynamic or adaptive tokenization for domain-specific corpora, where frequency distributions may differ significantly from Wikipedia. Additionally, the method does not improve the decompression speed or address the sequential nature of variable-length decoding, which may be I/O bound in practice.
Research Context
This work builds on decades of compression research, most directly extending the Word Replacing Transform (WRT) and byte-pair encoding by applying a simple frequency-ordering optimization that classical information theory suggests should help but was apparently never systematized for modern BPE pipelines. It validates empirically that Zipf's law, while widely observed, can still be exploited at the preprocessing stage before entropy coding. The paper uses standard benchmarks (enwik8, enwik9) familiar to the compression community and extends findings to multilingual text, showing broad applicability. It opens a research direction on the interaction between tokenization strategies and compression algorithms, and may inspire similar frequency-aware preprocessing for other domains (e.g., neural compression, learned codecs).
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::