Elamur: **Mova** · [Parse](https://mova.elamur.ai/free/en/parse/) · [Dictionary](https://md.dictionary.elamur.ai/free/en/) · [Translate](https://md.translate.elamur.ai/free/en/) · [Research](https://md.research.elamur.ai/free/en/) · [MCP](https://mcp.elamur.ai/) · [Groupants](https://md.groupants.elamur.ai/free/en/)

[Mova](https://md.mova.elamur.ai/free/en/) · [this page in HTML](https://mova.elamur.ai/free/en/docs/tools/treestore/)

[home](https://md.mova.elamur.ai/free/en/) / [docs](https://md.mova.elamur.ai/free/en/docs/) / [tools](https://md.mova.elamur.ai/free/en/docs/tools/) / treestore — compressed annotated articles with random access

# 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.

| field | coded as |
| --- | --- |
| `text_md` | raw text: the one copy of the article's words |
| `sentences_tsv` | id = article prefix + `:n`, n by +1, section "same as before" or a table id, block as a delta, item as a bit, text as (offset, length) into the Markdown |
| `conllu` | `# sent_id` by row delta; `# text` by "same as the sentence row"; FORM by the split of the text's whitespace chunks (a frozen rule plus learned exceptions; only wrong predictions are stored); MISC `SpaceAfter=No` follows from the split; LEMMA as an edit script against the form (`=`, or strip k characters of the form or its lower case and append); (UPOS, XPOS, FEATS) as one tag id; DEPREL as an id; HEAD as a signed offset; (tag, relation, head) as one shape id or a fragment of shapes |
| `frames_tsv` | row delta, frame count, the shown text as pieces: table id, a reference to a lemma or form of the sentence's tree, or a literal |
| `prag_tsv` | row delta, the six labels as one tuple id, the confidences as hundredths (lossless; no quantisation) |

**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).

| set | articles | JSON | source | one frame | treestore | vs source | vs one frame |
| --- | --- | --- | --- | --- | --- | --- | --- |
| shard 00005 (held out) | 500 | 406.5 MB | 52.60 MB | 38.29 MB | 18.43 MB | 2.85× | 2.08× |
| shard 00050 (held out) | 500 | 264.6 MB | 34.29 MB | 24.8 MB | 11.85 MB | 2.89× | 2.09× |
| shard 00099 (held out) | 500 | 190.6 MB | 25.50 MB | 18.19 MB | 8.70 MB | 2.93× | 2.09× |
| 1 272 random articles (held out) | 1 272 | 81.5 MB | 13.05 MB | 8.23 MB | 4.13 MB | 3.16× | 1.99× |

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](https://md.mova.elamur.ai/free/en/docs/licence/DATA/)).
- [← previous treebanks — UD treebank facts and their papers](https://md.mova.elamur.ai/free/en/docs/tools/treebanks/)
- [next → Sea Turtle — mova-turtle](https://md.mova.elamur.ai/free/en/docs/tools/turtle/)
- [↑ back to tools](https://md.mova.elamur.ai/free/en/docs/tools/)