📐wordgraph-extract

The groupant beside wordgraph/src/extract.rs in the Mova repository: what the code computes, what it never does, how to go back from its outputs, its invariants, cost and checks.

Facts

Components

Obernants

The typed relations around the forward model: the behaviour complement (what the code never does), the reverse reconstruction (every input compatible with an output) and specialised views.

Model text

Descriptant

CoNLL-U sentence → typed word-pair events (head word, relation code, dependent word), each word an en lemma number or a caller-interned out-of-dictionary number (OOV_TAG | k) with its UPOS. Rules version VERSION = 2 (2026-11-06: version 2 drops pairs whose two ends are the same node, after «dog isa dog» showed up in the first 50 k build). Key packing (pack/unpack) gives the sort order used by passes and the build.

Approximant

For a well-formed block with tokens t (head h, deprel b[:s]), with content(u) = u ∈ {NOUN, PROPN, VERB, ADJ, ADV}: E = { (h, ρ(b, s, t), t) : content(h), content(t), word(h) ≠ word(t) } ∪ propagated arcs, where ρ maps nsubj → isa(t→h) if h has a cop child and is a NOUN, prop(t→h) if an ADJ (t nominal), else nsubj / nsubj:pass; obj, iobj; obl → agent (subtype agent) or obl:<first ADP case child of t>; nmod → poss or nmod:<case>; amod; compound (no subtype, both nominal); advmod (not a negator); xcomp; conj. A predicate with a negator child (not, never, n't, or an aux with Polarity=Neg) gives no nsubj/obj/isa/prop. Propagation: a nominal conj of an nsubj/obj/iobj token repeats that arc to the same head; a VERB conj of a VERB with no own nsubj and no cop inherits the first verb's first nsubj. Lemmas are lowercased except PROPN.

Invariant

unpack(pack(e)) = e for ids < 2^32, UPOS < 2^8, codes < 2^32; pack is monotone in the lexicographic order of (head id, head UPOS, rel, dep id, dep UPOS), which equals the derived Ord of Event. A malformed block (missing column, non-numeric head, head index > n) yields false and appends nothing. Dictionary ids are < OOV_TAG.

Cost

O(n) per sentence of n tokens (one scan for children, one for arcs), plus one dictionary probe per content token and one to_lowercase allocation for capitalised non-PROPN lemmas. Events per token measured 2026-11-06: 18.0 M events from 1.95 M sentences of Wikipedia tier-1 shards 0–9 (about 0.33 per token).

Composition

Called by pass::read_unit per sentence block; its intern callback is the part's OOV interner. Its codes come from rel.

Tests

subjects_objects_and_propagation, copula_gives_isa_and_negation_blocks (negated copula gives nothing; a word is not its own class), out_of_dictionary_words_are_interned_and_malformed_blocks_rejected, pack_preserves_order_and_round_trips.

Behavior complement

Does not: read enhanced dependencies (column 9), resolve pronouns, use multiword names beyond their head token, keep numbers, pronouns or function words, handle negation scope beyond direct children, propagate through more than one conj level, keep word order or sentence identity, or check the tree is acyclic (cycles do not matter: arcs are local). Empty nodes and multiword-token ranges are ignored.

Reverse reconstruction

Preimage of an event multiset: all trees whose content-word arcs, after the rules, give that multiset; word forms, function words, order, punctuation, negated or non-content arcs and sentence boundaries are unconstrained. The OOV string of OOV_TAG | k is recoverable only with the caller's interner.

This page in Markdown → https://md.groupants.elamur.ai/free/en/mova/wordgraph/src/extract.rs.groupant/