Dictionary compression

Deep dive

How it works

In: a set of sample messages (training), then single small messages · Out: a dictionary blob (training), then compressed frames that reference it · State: the shared dictionary, identical on both sides and tagged with an ID · Cost: training O(total sample size); per message the base codec's cost plus dictionary load unless prepared once

1. Collect samples: real messages, representative of current traffic (thousands, of the same type).
2. Train: zstd's COVER / fastCover selects the substrings (segments of size k, scored by frequent d-byte n-grams) that occur in the most samples, and packs the best ones into the dictionary, most useful at the end (closest = cheapest offsets). It also stores entropy tables and initial repeat offsets fitted to the samples.
3. Compress: load the dictionary as window history (ZSTD_CCtx_refCDict), compress the message; matches may point into the dictionary.
4. Decompress with the same dictionary (matched by dictionary ID).
5. Retrain periodically as data drifts; keep old dictionaries for old data.

window seen by encoder:  [ dictionary 110 KB ][ message 600 B ]
                                     ^---- back-reference from message into dictionary

Raw-content dictionaries also work: any byte string used as prefix history (DEFLATE deflateSetDictionary, LZ4 LZ4_loadDict, zstd raw content), just without tuned entropy tables.

Code

Train, prepare once, and compress small messages with minimal frame overhead (zstd crate with feature zdict_builder).

use std::io;
use zstd::bulk::{Compressor, Decompressor};
use zstd::dict::{DecoderDictionary, EncoderDictionary};
use zstd::zstd_safe::CParameter;

/// Train a dictionary; aim for total sample bytes ~100x `dict_size`.
pub fn train(samples: &[Vec<u8>], dict_size: usize) -> io::Result<Vec<u8>> {
    zstd::dict::from_samples(samples, dict_size)
}

pub struct DictCodec<'a> { c: Compressor<'a>, d: Decompressor<'a> }

impl<'a> DictCodec<'a> {
    /// Prepared dictionaries are digested once (tables built), then shared by any number of codecs.
    pub fn new(enc: &'a EncoderDictionary<'static>, dec: &'a DecoderDictionary<'static>) -> io::Result<Self> {
        let mut c = Compressor::with_prepared_dictionary(enc)?;
        // Small messages: every header byte counts. Store dict ID and size out of band instead.
        c.set_parameter(CParameter::DictIdFlag(false))?;
        c.set_parameter(CParameter::ContentSizeFlag(false))?;
        c.set_parameter(CParameter::ChecksumFlag(false))?;
        Ok(DictCodec { c, d: Decompressor::with_prepared_dictionary(dec)? })
    }
    pub fn compress(&mut self, msg: &[u8]) -> io::Result<Vec<u8>> { self.c.compress(msg) }
    pub fn decompress(&mut self, data: &[u8], max_len: usize) -> io::Result<Vec<u8>> {
        self.d.decompress(data, max_len)
    }
}

/// Compare plain vs dictionary compression on held-out messages (never test on training samples).
pub fn evaluate(train_set: &[Vec<u8>], test_set: &[Vec<u8>], level: i32) -> io::Result<(f64, f64)> {
    let dict = train(train_set, 110 * 1024)?;
    let enc = EncoderDictionary::copy(&dict, level);
    let dec = DecoderDictionary::copy(&dict);
    let mut codec = DictCodec::new(&enc, &dec)?;
    let (mut raw, mut plain, mut with_dict) = (0usize, 0usize, 0usize);
    for m in test_set {
        raw += m.len();
        plain += zstd::bulk::compress(m, level)?.len();
        let c = codec.compress(m)?;
        assert_eq!(&codec.decompress(&c, m.len())?, m);
        with_dict += c.len();
    }
    Ok((raw as f64 / plain as f64, raw as f64 / with_dict as f64))
}

Complexity and constants

• Training: seconds for tens of MB of samples (fastCover); the --train-cover parameter search (k, d) is order of 10-100× slower but finds better dictionaries.
• Dictionary sizes: 16-128 KB typical. Bigger helps until matches into it get expensive (longer offsets) and it stops fitting in L2.
• Per-message overhead without preparation: loading a 110 KB dictionary costs order of 10-100 µs (hashing it into tables), more than compressing a 1 KB message. Prepared CDicts reduce this to a table copy or reference.
• Frame overhead for tiny messages: magic (4) + header (2-14) + block header (3); disabling dict ID, content size and checksum saves up to 12 bytes. Raw zstd "magicless" format saves the 4-byte magic.

Efficiency

• Cost: training takes seconds for tens of MB of samples (fastCover). Per message, loading a 110 KB dictionary costs order of 10-100 µs (hashing it into tables), more than compressing a 1 KB message; a prepared dictionary reduces that to a table copy or reference. Measured here: zstd -3 on 180-byte JSON records, 1.15x without and 3.1x with a 110 KB dictionary. Bound: per-message setup, then match-finding compute.
• Levers:
  • prepare the dictionary once (ZSTD_CCtx_refCDict, EncoderDictionary) — removes the 10-100 µs load per message — any many-message path
  • one dictionary per message type — avoids a diluted mixed dictionary — several schemas or endpoints
  • 16-128 KB dictionary size — gains fade above that and it stops fitting in L2 — most workloads
  • drop magic, dictionary ID, content size and checksum — saves up to 12-16 bytes per frame — messages under 1 KB
  • batch records into 64 KB+ blocks — simpler than a dictionary — when per-record random access is not needed
• Naive → standard → state of the art:
  • new compressor and dictionary per message · more CPU than the compression itself
  • trained, prepared dictionary at a fixed level · 3.1x on the 180-byte JSON example above
  • versioned per-type dictionaries, retrained as data drifts, or the previous resource as dictionary (HTTP Compression Dictionary Transport) · tiny deltas for small edits to a large file

Implementation notes

• Store dictionaries like schema: versioned, immutable, referenced by ID next to the data (RocksDB stores the dictionary inside each SST file; others keep a dictionary registry).
• One dictionary per message type: a mixed dictionary dilutes; train separately for each schema/endpoint.
• Compression level: EncoderDictionary::copy(&dict, level) bakes the level in; higher levels exploit the dictionary better at modest cost for small inputs.
• Raw content prefix for streams with a known header or for diffs (zstd --patch-from=old.bin treats the old version as dictionary).
• HTTP: Compression Dictionary Transport lets a server name a previously downloaded resource (e.g., the last JS bundle version) as dictionary for the next with dcb (Brotli) / dcz (zstd) encodings; small edits to a large bundle then ship as tiny deltas.

Pitfalls

• Evaluating on the training samples: inflated ratios; hold out a test set.
• Dictionary drift: schema changes silently cut ratios; monitor compressed size per message type and retrain.
• Losing or overwriting a dictionary version makes existing data unreadable; never mutate a dictionary in place.
• Creating a new compressor/dictionary per message (the common naive API use) costs more CPU than the compression itself.
• Too few samples (zstd recommends thousands, totalling ~100× the dictionary size): training errors out or yields a weak dictionary.

Variants and alternatives

In production

Storage and services: zstd dictionaries at Meta for small objects, RocksDB per-SST dictionary compression (CompressionOptions::max_dict_bytes). Web and networking: Brotli's static dictionary in every browser (RFC 7932), HTTP Compression Dictionary Transport (RFC 9842, Chrome), DEFLATE preset dictionaries (zlib deflateSetDictionary, used by SPDY header compression). Large collections: relative Lempel-Ziv, which compresses a collection against a sampled dictionary built from it (Liao et al.).

Implementations

Sources

• K. Liao, M. Petri, A. Moffat, A. Wirth, Effective Construction of Relative Lempel-Ziv Dictionaries, WWW, 2016. paper
• Y. Collet, M. Kucherawy, RFC 8878: Zstandard Compression and the 'application/zstd' Media Type, 2021 (dictionary format, §5). RFC · code
• J. Alakuijala, Z. Szabadka, RFC 7932: Brotli Compressed Data Format, 2016. RFC · code
• RFC 9842: Compression Dictionary Transport, 2025. RFC