We present frequency-ordered tokenization (FOT), a simple preprocessing technique that improves lossless text compression by exploiting the power-law frequency distribution of natural language (Zipf's law). FOT segments text into the vocabulary of a pretrained Byte Pair Encoding (BPE) tokenizer, renumbers tokens by frequency with a fixed table, and writes them with a short byte code before any standard compressor. Because the FOT stream is less than half the size of the text, compressors produce smaller output and run faster at the same time. On enwik8 (100 MB of Wikipedia), FOT reduces the compressed size by 7.96 percentage points (pp) for zlib, 2.24 pp for xz (LZMA), 1.96 pp for brotli and 1.44 pp for zstd, while making total compression, including the transform, 1.6x, 3.2x, 1.8x and 5.0x faster. Gains hold from 100 KB to 1 GB (enwik9) and across texts of diverse languages, and outperform the classical Word Replacing Transform. On enwik9, FOT with tuned xz sets a new state of the art among LZ-based compressors on the Large Text Compression Benchmark. The method can be implemented in under 50 lines of code.
Figures & tables
Fig. 1 : Zipf’s law on enwik8: frequency of the 100 most common (lowercased) words vs. rank. The top 10 words account for over 20% of all occurrences.
Compressor
Raw (%)
FOT (%)
Impr. (pp)
zlib-9
36.48
28.52
7.96
bz2-9
29.01
28.07
0.94
xz-6
26.38
24.14
2.24
xz-9e
24.83
23.46
1.37
zstd-22
25.33
23.89
1.44
brotli-11
25.74
23.78
1.96
TABLE I : Compression ratios on enwik8 (100 MB). Lower is better. FOT ratios include all headers and the 128-token hybrid list (0.3 KB).
Pipeline
zlib-9
xz-6
zstd-22
brotli-11
Raw UTF-8
36.48
26.38
25.33
25.74
BPE tokens, merge-order IDs, LEB128
32.68
26.01
25.49
25.29
+ adaptive frequency order (table sent)
29.38
24.62
24.48
24.08
+ static table (none sent)
29.23
24.50
24.32
23.97
+ prefix code instead of LEB128
28.85
24.39
24.12
24.02
+ minimum-cost segmentation
28.55
24.16
23.91
23.81
TABLE II : Ablation on enwik8 (100 MB), compression ratio (%). Each row adds one component; all per-file costs included.
Size
U
Table
Table (%)
Raw
Adaptive
Static
100 KB
4,830
10.8 KB
10.80
33.75
36.71
27.11
1 MB
21,222
49.8 KB
4.98
30.01
31.74
26.52
10 MB
50,500
121 KB
1.21
27.93
27.81
26.08
100 MB
71,161
172 KB
0.17
25.33
24.48
23.89
TABLE III : Adaptive rank-table overhead vs. file size (enwik8 prefixes, cl100k). zstd-22 ratios (%) for raw text, the adaptive table including its cost, and FOT with the static table.
Fig. 2 : (a) BPE token rank vs. frequency on enwik8 (cl100k, log-log), with a Zipf fit over the top 1000 ranks ( α=1.04 ). (b) Share of tokens needing 1, 2 or 3 LEB128 bytes with BPE’s merge-order IDs and with frequency-ordered IDs.
Fig. 3 : Compressed size vs. file size (enwik8 prefixes, enwik8, enwik9) for zstd-22, brotli-11 and zlib-9. Solid, filled: FOT; dashed, open: raw.
Vocabulary
∣V∣
zlib-9
xz-6
zstd-22
brotli-11
GPT-2
50k
28.68
24.19
23.88
23.78
cl100k
100k
28.52
24.14
23.89
23.78
o200k
200k
28.28
24.08
23.83
23.71
Raw (no preprocessing)
36.48
26.38
25.33
25.74
TABLE IV : Pretrained vocabularies on enwik8 (100 MB), compression ratio (%), each with its own static table.
Segmentation
MB/s
zlib-9
xz-6
zstd-22
brotli-11
Exact BPE (tiktoken)
14
28.84
24.39
24.11
24.02
Greedy longest match
140
29.29
24.68
24.36
24.29
Minimum cost (FOT)
60
28.52
24.14
23.89
23.78
TABLE V : Segmentation of enwik8 into the cl100k vocabulary (static table, prefix code). Speed is single-core transform throughput.
Dataset
Size
Improvement (pp)
zlib-9
xz-6
zstd-22
brotli-11
enwik8 (100 KB subset)
100 KB
8.91
6.14
6.64
2.44
enwik8 (10 MB subset)
10 MB
7.91
1.70
1.85
1.57
enwik9 (English)
1 GB
6.86
1.91
1.63
1.70
Shakespeare
5.4 MB
7.82
2.32
2.26
2.33
Python code
98 KB
3.15
1.88
1.79
0.27
TABLE VI : Cross-dataset generalization (cl100k, English static table). Improvement over raw in pp; all overheads included.
Method
zlib-9 (%)
zstd-22 (%)
xz-6 (%)
Raw
36.48
25.33
26.38
WRT [ 28 ]
31.74
25.35
25.51
FOT
28.52
23.89
24.14
TABLE VII : Comparison to Word Replacing Transform on enwik8 (100 MB). Ratios include all overheads. WRT was measured with the Python bindings of the same codecs, whose zstd-22 baseline is 25.27%; its improvement is relative to that baseline.
Method
Ratio (%)
Category
cmix v21 [ 18 ]
14.62
Neural/context mixing
NNCP v3.2 [ 19 ]
14.92
Transformer
PAQ8px
15.85
Context mixing
PPMd-16
22.83
Statistical
FOT + xz-9e
23.46
LZ + FOT
FOT + brotli-11
23.78
LZ + FOT
TABLE VIII : Comparison on enwik8 (100 MB). SOTA results from the Large Text Compression Benchmark [ 17 ] . FOT applies to the practical LZ-family compressors below the line.