[arXiv 2026] Frequency-Ordered Tokenization: Boosting Classical Compression via Zipf’s Law

TL;DR

Frequency-Ordered Tokenization is a simple yet powerful preprocessing pipeline that transforms text into a format optimized for classical compressors (like gzip or zstd). By reordering BPE tokens so that frequent words use fewer bits (Zipf's Law), it improves compression ratios by up to 7% and, surprisingly, accelerates heavy compressors like LZMA by over 2x by reducing the volume of data they need to process.

Background Positioning: This is a high-impact "plug-and-play" utility. It doesn't replace zstd or LZMA but acts as an "adapter" that makes them significantly more effective on natural language text.

The "Broken" Intuition of Modern Compressors

Most production-grade compressors belong to the LZ77 family. They work by looking back in a sliding window to find repeated strings. While efficient, they have a blind spot: they treat all bytes equally and don't "know" that in English (or any language), the word "the" appears thousands of times more often than "aardvark."

Previous attempts like the Word Replacing Transform (WRT) tried to fix this by replacing words with short codes. However, these methods break down when they encounter rare words, Different capitalizations, or non-Latin scripts like Chinese.

Methodology: Harnessing the Power of Subwords

The author's insight is to borrow Byte Pair Encoding (BPE)—the backbone of LLMs like GPT-4—to tokenize text. BPE naturally handles any character sequence. The magic happens in three steps:

1. Tokenization: Break text into BPE subwords.
2. Frequency Reordering: Sort the vocabulary. The most common token gets ID 0, the next 1, and so on.
3. Varint Encoding: Use LEB128 (variable-length integers) to save these IDs. This ensures ID 0 takes only 1 byte, while rare IDs take more.

Figure 1: The Zipfian distribution of tokens. Frequency reordering maps the "Head" of the distribution to the shortest possible byte representations.

Why does this work? (The Logic)

Without reordering, BPE IDs are assigned in the order they are "merged" during training—which is essentially random relative to frequency. By reordering, 45.7% of all tokens in a typical Wikipedia dump are compressed into a single byte before the actual compressor even starts its work.

Experimental Results: The Pareto Improvement

The results on the enwik8 (100MB Wikipedia) benchmark show consistent gains across the board:

The Speed Paradox

Usually, better compression means slower speeds. Here, the opposite happens for heavy-duty algorithms. Because the preprocessing reduces 100MB of text into a ~41MB "varint stream," the downstream compressor has much less data to analyze.

• zstd-22 becomes 3.1x faster.
• LZMA becomes 2.4x faster.

Figure 2: The speed-ratio tradeoff. Preprocessing (solid lines) moves the performance to the "bottom-left" (better and faster) than raw compression.

Critical Insight & Limitations

Why doesn't it help statistical compressors like PPMd? PPMd already builds an internal probability model of the data. The tokenization process "scrambles" the byte-level context that PPMd relies on, leading to a slight performance decrease (-0.44 pp). This proves the method is best suited as a companion to Dictionary-based (LZ) methods.

Limitations:

• Latency: Decompression is currently slower (5-7s vs <1s) due to the Python implementation of the varint decoder.
• Non-Streaming: You need to see the whole file to count frequencies before you can reorder the IDs.

Final Takeaway

Frequency-Ordered Tokenization is a masterclass in applying "Old School" Information Theory (Zipf's Law) to "New School" NLP tools (BPE). For anyone managing large-scale text archives or data lakes, this 50-line-of-code trick provides a significant boost in both storage density and processing speed.