---
title: "Zstandard dictionary training"
url: https://recursiveai.org/onearchive/docs/zstd-dictionary-training/
description: "ZstdDictionary.Train(samples, options) turns a set of sample payloads into a dictionary in the Zstandard dictionary format (RFC 8878 §5). The pieces are…"
version: "0.7.0-preview.1"
source: https://github.com/recursive-ai-oss/onearchive-csharp/blob/3fa11f22dbe4e13c90ae9c63f393e945a0c09bba/docs/zstd-dictionary-training.md
---

# Zstandard dictionary training

`ZstdDictionary.Train(samples, options)` turns a set of sample payloads into a dictionary in the Zstandard dictionary format
(RFC 8878 §5). The pieces are public so that they can be composed: `ZstdCoverTrainer` (content selection, parameter search, and the
whole pipeline), `ZstdDictionaryBuilder` (content and samples to a complete dictionary) and `ZstdDictionaryTrainingOptions`.

The output depends only on the samples and the options: not on the platform, vector width, runtime, or the number of threads the
parameter search uses. All scoring is integer arithmetic. This page is normative: a port must produce the same bytes from it.

## Samples

- Empty samples are dropped. The samples are laid end to end in the order given.
- If their total exceeds `MaxTrainingBytes` (default 64 MiB), every `n`-th sample is kept (sample indexes `0, n, 2n, ...`) where
  `n = ceil(total / MaxTrainingBytes)`, and what is still over the limit is cut off at the limit (the sample that crosses it is
  truncated, later ones are dropped).
- Fewer than 8 bytes in total is a `CompressionDictionaryException`.

## Content selection (COVER)

Source: Liao, Petri, Moffat and Wirth, "Effective Construction of Relative Lempel-Ziv Dictionaries", WWW 2016, §3 (local
segments chosen per epoch by the frequencies of their k-mers, covered k-mers set to zero, ℓ0.5 scoring). Parameters: `k`
(segment size), `d` (d-mer size, the paper's k-mer), `D` (the content budget).

1. **d-mers.** A d-mer is the `d` bytes starting at a position, wholly inside one sample. Its key is the little-endian value of its
   bytes (`d <= 8`), or for `d` of 9 to 16 the mix `(a * 0xC2B2AE3D27D4EB4F) xor rotl(b * 0x165667B19E3779F9, 31)` of the first and
   last eight bytes read as little-endian 64-bit values (`a`, `b`), computed modulo 2^64.
   - *Cover* gives each distinct key its own id (exact).
   - *FastCover* has `2^b` ids with `b = clamp(floor(log2(N)) + 3, 12, HashBits)` for `N` total sample bytes (a table much larger
     than the data only costs time; `b` comes from the whole sample set, whichever part of it is trained on),
     `id = (key * 0x9E3779B97F4A7C15 mod 2^64) >> (64 - b)` (collisions share an id), and only positions whose offset within their
     sample is a multiple of `Acceleration` start a d-mer.
2. **Frequency.** The frequency of an id is the number of samples that contain a d-mer with that id (a sample counts once). It is
   counted per *group* of samples (see "Held-out parts") and saturates at 65535 in each group; the frequency over a part of the
   samples is the sum over its groups, capped at 65535 (so a d-mer found in 65535 or more samples counts as exactly that many).
3. **Weight.** A frequency below 2 has weight 0 (a d-mer in one sample only cannot help any other). Otherwise `Frequency` score:
   the frequency. `SquareRoot` score: `isqrt(frequency << 16)`, the floor of the integer square root (the paper's ℓ0.5 norm up to
   the final monotone square, with 8 fractional bits). Weights are 16 bits.
4. **Epochs.** `E = clamp(ceil(D / k), 1, max(1, N / k))` where `N` is the number of bytes trained on (all the samples, or all
   but a held-out part); epoch `e` covers positions `[e * (N / E), (e + 1) * (N / E))` of those bytes laid end to end, the last
   one up to `N`.
5. **Segment.** In epoch `e` with room `R` left of the budget, the window is `w = min(k, R, epoch length)`; epochs with `w < d` are
   skipped. The score of a window placement is the sum of the weights of the *distinct* ids of the d-mers starting inside it
   (positions `s .. s + w - d`). The best-scoring placement wins; among equal scores the earliest. A best score of 0 adds nothing.
   The window is `w` bytes from the winning start. The weights of all ids of its d-mers are then set to 0 for later epochs.
6. **Order.** The chosen segments are written by increasing score, ties by increasing epoch, so the most useful content ends up
   last, nearest the data it serves and with the smallest offsets. If nothing scored, the content is the first
   `min(D, N)` bytes of the samples.

## Parameter search

With `Optimize` (the default), `ZstdCoverTrainer.Optimize` looks for the combination of `DmerSizeCandidates`, `ScoreCandidates` and
`SegmentSizeCandidates` (distinct values, `k >= d`) with the smallest total. Candidates are numbered in the order d ascending, then
score (`SquareRoot` before `Frequency`, when both are given), then k ascending; a *variant* is one pair of d and score and its
candidates differ in k. A candidate is scored by the total size of the held-out samples compressed at `ScoringLevel` by this
library's encoder with the dictionary the candidate's content makes (a raw-content dictionary: the content only, no entropy tables,
so that only the content is judged); a held-out sample is a frame of its own. **The smallest total wins, and the first of equal
totals** (lowest candidate number). Scoring runs on `MaxDegreeOfParallelism` threads (0: the processor count, at most 8); each total
is independent of the others, so the choice does not depend on scheduling.

- **`SearchMode.Exhaustive`** scores every candidate.
- **`SearchMode.Guided`** (the default) scores a subset, chosen from totals only (the same totals whatever the thread count):
  1. If there are more than 6 candidates and the samples exceed 4 MiB, only the first variant is searched (below).
  2. The *first variant* is the one with the largest d up to 8 (else the first variant). Its segment sizes `k_0 < ... < k_(m-1)`
     are scored at positions `(m-1)/6`, `3(m-1)/6` and `5(m-1)/6` (integer division) of the list.
  3. From the best candidate so far, its two neighbours in the list (previous and next k) are scored, unless already scored. If a
     neighbour beat the best by more than a quarter of a percent (`(best - new) * 400 >= best`), this repeats from it; otherwise
     it stops. The smallest total scored so far stays the best.
  4. Each other variant is scored at the segment size nearest the best one (the smaller on a tie).
  5. With 6 or fewer candidates all are scored.
- **Held-out parts.** `TrainingPercent` (default 75) gives `F = ceil(100 / (100 - TrainingPercent))` folds (4 for 75; 1 and
  train = test when 100). The samples are cut into blocks of `max(1, count / 16)` consecutive samples; block `j` belongs to *group*
  `j mod F`, and fold `f` holds out group `f` and trains on the rest. Blocks, not single samples, are held out because neighbouring
  samples (ticks of one game, pieces of one file) are alike. If a group would be empty or the other groups hold fewer than 8 bytes
  (very few samples), there is one fold that trains and is scored on everything. The training samples of a fold are a few stretches
  of the original data and are never copied; the d-mers are counted once for all folds.
- **Folds scored.** Sample sets up to 1 MiB score the first `min(F, 4)` folds and add their totals; up to 4 MiB the first
  `min(F, 2)`; larger ones the first fold only. A fold is scored on at most `MaxScoringSamples` (default 2000) of its held-out samples
  and 1 MiB of them: every n-th, where `n = max(ceil(samples / MaxScoringSamples), ceil(bytes / 1 MiB))`.

Defaults: `d` in {6, 8}; `k` in {32, 48, 64, 96, 128, 192, 256, 384, 512, 768, 1024, 1536, 2048}; the `SquareRoot` score only (26
combinations; a guided search scores about 6 to 9 of them). Without `Optimize`, `SegmentSize` (256), `DmerSize` (8) and `Score`
(`SquareRoot`) are used.

## The dictionary file

`ZstdDictionaryBuilder.Build(content, samples, id)` writes: magic `0xEC30A437`, the ID, the Huffman table for literals, the FSE
tables for offsets, match lengths and literal lengths, three repeat offsets (1, 4, 8) and the content (RFC 8878 §5). Total size
is at most `DictionarySize`: content for the held-out parts is chosen with 350 bytes reserved for the tables, the tables are
measured, and the content from all the samples is then chosen with the real size of the tables (a whole-set choice of the same
length as the held-out content is kept as it is); if the final tables are bigger, the oldest (first) content bytes are dropped.

- **Statistics.** The tables are measured on held-out frames. With one fold (see "Held-out parts"), the content chosen from all
  the samples is used and every sample is parsed. Otherwise, for each fold `f` of the first `min(F, 4)` (all of them when the
  samples total at most 24 MiB, else the first only), content of the reserved size is chosen from the samples outside the fold with
  the final `k`, `d` and score, and the fold's samples (every n-th when more than 20000 or 8 MiB, as for scoring) are parsed
  against it. The histograms are added. Measuring against the final content itself would parse samples that the content was cut
  from, so almost every sample would be one long match and the tables would describe nothing like new data; the effect grows as
  the dictionary approaches the size of the samples. Each sample is parsed by the level-3 fast match finder with the content as
  history (one sample is one frame; blocks of 128 KiB). Every sequence is counted in the literal length code, match length code and
  offset code histograms (offset *value*: 1 to 3 for repeat offsets as the decoder resolves them, otherwise offset + 3; code =
  floor(log2 value)), starting each sample from the repeat offsets 1, 4, 8. All literals, including those after the last match, go
  into the byte histogram. The header is as large as the first fold's content and these histograms need.
- **Huffman.** Every byte gets a code: weight counts are `max(count, 1)`, built with the library's length-limited builder (11
  bits). If that cannot be described (no samples; a perfectly even spread) a text-like prior replaces the counts: space 64,
  `a`-`z` 32, `A`-`Z` and digits 16, other printable 8, control bytes 2, others 1.
- **FSE.** Counts are `max(count, 1)` for every symbol of the range: literal lengths 0..35, match lengths 0..52, offsets 0..max(17,
  floor(log2(content + 3))) (at most 31). The accuracy log is `OptimalAccuracyLog` (max 9; offsets 8), counts are normalized
  (counts at or below `total >> accuracyLog` become probability -1). With no sequences at all the format's default
  distributions are written.
- **ID.** The given `DictionaryId`, or if 0 the xxHash64 (seed 0) of the whole dictionary written with ID 0, folded as
  `32768 + hash mod (2^31 - 32768)`. IDs 1 to 32767 and 2^31 and up are refused (RFC 8878 §5).
- Passing a whole dictionary (magic first) as the content keeps its content and ID and replaces its tables: this is how
  dictionaries made by another tool get tables measured on your samples.

## Limits and errors

`DictionarySize` 256 to 2^30; `d` 2 to 16 and `k >= d` (at most 16 MiB); `HashBits` 8 to 24; `Acceleration` 1 to 10;
`TrainingPercent` 1 to 100; `ScoringLevel` 1 to 22 (a level above the encoder's highest is scored at its highest). Bad options throw `ArgumentException`; samples that cannot give a dictionary throw
`CompressionDictionaryException`; cancellation throws `OperationCanceledException`.

## Time and memory

The d-mers of the samples are counted once per d-mer size, in one pass that keeps the counts of each group apart; a fold's
weights are the sum of the other groups' counts, so holding out a part costs no second pass. Working arrays come from a pool and are
reused by the next candidate; none of this affects the output, which does not depend on what the arrays held before.
`tools/zstd-train-bench/timing.sh` measures time and peak memory against `zstd --train`, and `bench/Managed` against the fastest
managed implementation; method and figures are in the changelog and `docs/bench-method.md`.

## Measured against `zstd --train`

`tools/zstd-train-bench/quality.sh` compresses held-back payloads with zstd's own compressor and a dictionary from each trainer, so
only the dictionary differs. On game snapshot data (trained on one run, judged on another) the total over all kinds and dictionary
sizes is within 0.3% of `zstd --train` (smaller), with most rows within 1%.
Known gaps, left for later tuning: sample sets of a few hundred small payloads against a dictionary larger than the data (the
reference writes a dictionary smaller than the data; ours keeps nearly all of it), and heterogeneous bulk data cut into 4 KiB
chunks with dictionaries of 64 KiB and up (about 2% larger totals; the entropy tables are not the cause, the chosen content is).