📘 treestore — compressed annotated articles with random access

treestore keeps annotated articles (JSON records whose text fields hold Markdown, sentence rows, CoNLL-U trees, frames and pragmatics labels — the layout of wikicorpus records) in typed columns, codes typical tree structure with a meta-dictionary, compresses each column with a trained zstd dictionary or a primed context-model coder, and gives every record back byte for byte. One article is read with one seek and one group decompression.

It is generic over records: any compact JSON object works; the fields text_md, sentences_tsv, conllu, frames_tsv and prag_tsv are coded when present and well formed, everything else stays in the envelope.

Format

Fields → columns (src/codec.rs). Each coded field is decoded back at write time; a field whose decoding differs in any byte stays in the envelope as written, so the round trip is lossless by construction.

Meta-dictionary (src/frag.rs). Frequent runs of token shapes learned by pair merging (BPE; Re-Pair). Heads are relative offsets, so a run whose heads point inside it is a tree fragment; a sentence is coded as fragments plus the residue of single shapes.

Columns → frames (src/store.rs, src/cm.rs). Articles are grouped up to a raw size (default 2 MB of JSON); each of the 16 streams of a group is one frame: zstd with the stream's trained dictionary, zstd without, the context coder (PPM orders 2/1/0 with a range coder, primed from the sample), or stored — whichever is smallest (the Grand Spider's dictionary levels, per stream).

Files. A store directory holds model.bin (tables, split exceptions, fragments, dictionaries, primed context models; named by its SHA-256 prefix), one .mts file per source shard, and index.tsv (title, file, number; sorted by the title's bytes):

.mts = "MOVATS01" model-id  group…  zstd(footer)  footer-length(u64 LE) "MOVATSF1"
group = n  n × 16 raw stream lengths  16 × (method, length, bytes)
footer = groups (offset, length, first article); articles (info line, JSON length, SHA-256 prefix, group, slot)

Every read checks the article's length and SHA-256 prefix, so a damaged column fails instead of returning wrong bytes.

Run

cargo build --release -p treestore
treestore train SRC_DIR SHARDS STEP OUT_DIR [--mode split|shape|frag] [--merges 1024] [--dict 114688] [--prime 1]
treestore pack OUT_DIR SRC_DIR SHARD… [--level 19] [--group 2000000] [--cm 1] [--resume]
treestore verify OUT_DIR SRC_DIR SHARD…        # every record byte for byte against the source; fails on any difference
treestore index OUT_DIR
treestore get OUT_DIR TITLE                     # the record's JSON
treestore sent OUT_DIR TITLE N                  # one sentence: row, CoNLL-U block, frames row, pragmatics row
treestore bench OUT_DIR SHARD [N]

SRC_DIR/SHARD is a wikicorpus shard (<k>.zst listed by <k>.tsv) or a directory of per-article .zst records. From Rust: dir::Store::open(dir)?.get(title) or .sentence(title, n), store::Shard::each to iterate a file, store::sentences(&fields) for sentence views.

Writing from a pass. store::Writer::create(path, &model, &model_id, &pack), then add(info, json) per article (a group is coded and appended whenever it reaches the group size), then finish(); the file appears only complete. The streaming and the batch writer give identical bytes.

Measured (2026-11-06)

Model: 250 articles from 10 tier-1 shards (every 20th), 2.97 MB, trained in 28 s (peak 825 MB). Level 19, 2 MB groups, context coder on. "Source" is the current wikicorpus shard (one zstd 9 frame per article); "one frame" is the whole shard's JSON as one zstd 19 --long=27 frame (no random access).

Every field of every record in these sets was taken by its codec (none kept raw), and verify found 0 differing records. Two packings of shard 00050 are byte-identical.

Tier 1, all of it (50 000 articles, 12.09 M sentences, 283.5 M tokens, 26.45 GB of JSON): 3 496.7 MB as wikicorpus shards → 1 209.8 MB as a store (2.89×; 4.27 bytes per token). Every field of every record coded; verify of all 100 files: 0 differing records. Packing took about 70 min on 6 threads at nice 10 on a box at load 15–20 (peak 789 MB); verification 17–39 MB of JSON per second per process (4 in parallel). get of «Estonia» (1.44 MB of JSON) from a fresh process, model load included: 136 ms; a random article of shard 00099: 57 ms.

Projection to all of English Wikipedia (6 786 209 ranked articles, disambiguation pages out). The 1 272 cached articles are a uniform draw over the ranked articles (the quality check's sampler): 657 ± 33 tokens per article (standard error), 3.25 KB each in a store. Non-tier-1 articles: 6 736 209 × 3.25 KB ≈ 21.9 GB (95 %: 19.7–24.1 GB), about 4.4 G tokens; with tier 1, ≈ 23 GB (21–25 GB) for trees, frames and pragmatics of every article — under a tenth of the 250 GB budget. The same articles as wikicorpus records would take ≈ 73 GB. Trees alone (no frames or pragmatics; 72 % of the bytes on shard 00050) ≈ 17 GB.

Where the bytes are (shard 00050, 2.82 M tokens, 120 812 sentences): Markdown text 4.61 MB, structure 2.0 MB (≈5.7 bits/token), frames 2.04 MB, confidences 1.20 MB (≈13 bits per value: near-uniform hundredths), envelope (links, categories, infobox, metadata) 1.05 MB, lemmas 0.49 MB (1.4 bits/token), sentence offsets 0.17 MB, literals 0.15 MB, splits 0.06 MB, the rest under 0.05 MB.

Structure coding (shard 00050, structure stream plus escapes): three columns 3.50 MB (zstd) / 3.23 MB (context coder); one shape id per token 2.49 / 2.04 MB; fragments of the meta-dictionary 2.44 / 2.01 MB (1 024 fragments; 4 096: 2.12 MB, 16 384: 2.30 MB with the context coder). The joint shape symbol gives the gain (−37 %); fragments on top add 1.5–2 %.

Coders (shard 00050): zstd only 12.92 MB; with the context coder 11.98 MB (−7 %: structure, frames, lemmas). Group size hardly matters with trained dictionaries (0.5 MB: 11.90, 2 MB: 11.88, 8 MB: 11.86 MB); level 22 = level 19.

Speed (shared box, load 15–20): packing a 500-article shard 4–17 s on 6 threads, peak 0.4–0.7 GB; decoding 26–32 MB of JSON per second per thread (zstd only: 56 MB/s); a random article of shard 00050 (mean 530 KB of JSON) 25 ms with 0.5 MB groups, 60 ms with 2 MB groups; iterating a shard 13 000–16 000 sentences per second with sentence views; reading uses 50–300 MB.

Writing an all-Wikipedia pass directly

A pass that already parses every sentence (the Elephant's wikigraph, which reads each article into Markdown, sentence rows and en trees and keeps only counts) can keep the trees at the cost of one encoder per unit: open store::Writer::create(<pass>/trees/<unit>.mts, &model, &id, &pack) with the unit's part, build per article the JSON record with title, page_id, rev_id, dump, stream_offset, model, text_md (wikischool::text::text_md), sentences_tsv and conllu in wikicorpus's formats (frames and pragmatics optional), add it, and finish when the unit's part is renamed into place, so a resumed pass resumes the store too. Train the store model once from a sample of the pass's own output (another parser model changes the tag and lemma statistics; misses stay lossless as literals). At the pass's ~7 000 sentences/s the encoder sees ~15 MB of JSON per second: level 19 with the context coder needs about one or two extra cores; writing at a low level and re-packing later (as the Grand Spider repacks its blocks) is the cheaper alternative, not yet a command here.

Sources

Library ids are folders of the paper library; works marked «outside» have no card yet (docs/usage.tsv).

• Context-model coder: PPM, Cleary & Witten 1984 (outside), escape method C, Moffat 1990 (outside); range coder, Martin 1979 (outside).
• Meta-dictionary of tree fragments: byte-pair encoding, Gage 1994 (outside); Re-Pair, Larsson & Moffat 2000 (outside); subword BPE use sennrich-2016, kudo-2018.
• Per-stream zstd with trained dictionaries: Collet & Kucherawy 2021, RFC 8878 (outside).
• Column streams: columnar formats, zeng-2023.

Limits

• One model per store directory; a store is readable only with its model.bin.
• No in-place update: a changed article means rewriting its file or writing a new file.
• Sentence access decodes the whole article (no index inside a group).
• Confidences are kept exactly; quantising them to one decimal would save about a quarter of their 1.2 MB per shard, but is lossy and not implemented. Frames and pragmatics are derivable from the trees with the frame reader and the pragmatics model; storing only trees would save about 3.7 of 11.85 MB per shard, at the cost of tying the store to those programs' versions — not done.
• The split rule and the lemma script grammar are part of the format: changing them changes how stores decode.
• Licence of the data: what it stores from Wikipedia stays CC BY-SA and stays out of the repository (Data and model licences).

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/tools/treestore/