steeldb/

emergent.rs

//! **Emergent ontology from prose** — discover facets from unlabelled natural language, with no model and
//! no planted hints.
//!
//! Field sensing (`vocabulary::candidate_fields`) reads `- **Field:** value` markers. That works, but those
//! markers are a schema someone already wrote into the document: sensing them is reading an answer key, not
//! discovering structure. Real corpora are prose, and on prose field sensing returns nothing at all.
//!
//! This module discovers the vocabulary the hard way:
//!
//! 1. **Salience** — score every term by TF-IDF across the corpus. A term in every document distinguishes
//!    nothing; a term in one document is noise. What survives is the vocabulary that carves the corpus up.
//! 2. **Co-occurrence** — represent each term by the set of documents it appears in, and measure terms by
//!    how much those sets overlap. Terms naming the same *kind* of thing occur in the same places.
//! 3. **Agglomeration** — merge the closest clusters until the requested number remain, so the taxonomy is
//!    built bottom-up out of the corpus rather than imposed on it.
//! 4. **Labelling** — name each cluster by its most distinctive term, again by TF-IDF.
//!
//! Every step is deterministic and dependency-free, which is what lets it run in the browser. An
//! embedding-based clusterer would be sharper, but it needs a tokenizer that cannot target wasm32 — and a
//! demo that cannot run the real thing is worth less than a slightly blunter one that can.

use std::collections::{HashMap, HashSet};

/// A discovered group of co-occurring terms — a candidate facet before the MECE gate has ruled on it.
#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
pub struct TermCluster {
    /// most distinctive term in the cluster, used as the facet name
    pub label: String,
    /// members, most salient first
    pub terms: Vec<String>,
    /// fraction of the corpus in which at least one member appears
    pub coverage: f64,
    /// mean pairwise co-occurrence similarity — how tightly the group holds together
    pub cohesion: f64,
}

/// Terms that appear capitalised mid-sentence are proper nouns: names of individuals, not names of kinds.
///
/// They belong in a facet's MEMBERS (they are the instances it collects) but make poor LABELS — labelling
/// the battle cluster `gale` after a trainer's surname describes one competitor, not the category. A term is
/// treated as a common noun when the corpus writes it in lowercase at least sometimes.
pub fn common_nouns(docs: &[String]) -> HashSet<String> {
    let mut lower_seen: HashSet<String> = HashSet::new();
    for doc in docs {
        for raw in doc.split(|c: char| !c.is_alphanumeric() && c != '-' && c != '\'') {
            let t = raw.trim_matches('-');
            if t.len() < 3 {
                continue;
            }
            // first character lowercase in the source text
            if t.chars().next().map(|c| c.is_lowercase()).unwrap_or(false) {
                lower_seen.insert(t.to_lowercase());
            }
        }
    }
    lower_seen
}

/// Remove URL runs before tokenising. A URL splits into `https`, the host, and path fragments; the path
/// fragments are unique per link and fall to the document-frequency floor, but `https` (and `http`, `www`)
/// recur across every link in the corpus and rose to the top of the salient terms — the records corpus, where
/// 3423 of 7077 documents carry a link, discovered a category literally named `https`. The reference strips
/// `https?://\S+` for the same reason; this does the same without a regex dependency, replacing each URL run
/// with a space so it cannot contribute a token.
fn scrub_urls(s: &str) -> String {
    // URL schemes are ASCII, so a case-insensitive byte-prefix test needs no separate lowercased copy — which
    // is what a first version got wrong, indexing `s` with offsets from a lowercased string of a different byte
    // length. Work on `s` directly, one character at a time.
    fn starts_url(rest: &str) -> bool {
        // byte-slice comparison, so a multi-byte character straddling the prefix length cannot panic a string
        // slice; schemes are ASCII, so this is exact
        let b = rest.as_bytes();
        (b.len() >= 8 && b[..8].eq_ignore_ascii_case(b"https://"))
            || (b.len() >= 7 && b[..7].eq_ignore_ascii_case(b"http://"))
            || (b.len() >= 4 && b[..4].eq_ignore_ascii_case(b"www."))
    }
    let mut out = String::with_capacity(s.len());
    let mut rest = s;
    while !rest.is_empty() {
        if starts_url(rest) {
            // a URL runs until the next whitespace
            match rest.find(char::is_whitespace) {
                Some(ws) => {
                    out.push(' ');
                    rest = &rest[ws..];
                }
                None => break,
            }
        } else {
            let ch = rest.chars().next().unwrap();
            out.push(ch);
            rest = &rest[ch.len_utf8()..];
        }
    }
    out
}

fn tokenize(s: &str) -> Vec<String> {
    scrub_urls(s)
        .split(|c: char| !c.is_alphanumeric() && c != '-' && c != '\'')
        .map(|w| w.trim_matches('-').to_lowercase())
        .filter(|w| {
            w.len() >= 3
                && w.len() <= 28
                && w.chars().next().map(|c| c.is_alphabetic()).unwrap_or(false)
                // a bare number is a value, not a name for a kind of thing
                && !w.chars().all(|c| c.is_ascii_digit())
        })
        .collect()
}

const STOP: &[&str] = &[
    "the", "and", "for", "with", "was", "were", "this", "that", "from", "into", "are", "has", "had", "his",
    "her", "its", "not", "but", "all", "any", "may", "can", "will", "each", "than", "then", "during",
    "under", "over", "also", "which", "while", "their", "there", "been", "being", "who", "when", "what",
    "how", "why", "per", "via", "such", "more", "most", "less", "other", "some", "one", "two", "three",
    "against", "after", "before", "between", "both", "out", "off", "own", "same", "too", "very", "just",
    "him", "she", "they", "them", "these", "those", "have", "does", "did", "doing", "would", "could",
    "should", "must", "shall", "about", "above", "below", "again", "further", "once", "here", "only",
    "remains", "stands", "recorded", "reported", "held", "took", "made", "including", "included",
];

/// Select the candidate mentions to cluster — the members of the reified situations.
///
/// This step deliberately does **no TF-IDF**. TF-IDF measures how well a term distinguishes one group from
/// others, so it can only be applied once groups exist; using it to pick the input would be scoring terms
/// against a partition that has not been computed yet. Selection is therefore a plain document-frequency
/// window: a mention in nearly every situation separates nothing, and one appearing once cannot be a
/// dimension. TF-IDF enters later, in [`name_cluster`], where it replaces an LLM naming call.
fn salient_terms(docs: &[String], n_terms: usize) -> Vec<(String, HashSet<usize>)> {
    let mut incidence: HashMap<String, HashSet<usize>> = HashMap::new();
    let mut tf: HashMap<String, usize> = HashMap::new();
    for (i, doc) in docs.iter().enumerate() {
        for w in tokenize(doc) {
            if STOP.contains(&w.as_str()) || GENERIC.contains(&w.as_str()) || LOCATIVES.contains(&w.as_str()) {
                continue;
            }
            *tf.entry(w.clone()).or_default() += 1;
            incidence.entry(w).or_default().insert(i);
        }
    }

    let n = docs.len().max(1) as f64;
    let min_df = 2usize;
    let max_df = ((n * 0.85).ceil() as usize).max(min_df + 1);

    // rank only by how often the mention occurs, inside the frequency window; no relevance weighting here
    let mut scored: Vec<(String, f64)> = incidence
        .iter()
        .filter(|(_, docs_in)| docs_in.len() >= min_df && docs_in.len() <= max_df)
        .map(|(term, _)| (term.clone(), *tf.get(term).unwrap_or(&1) as f64))
        .collect();
    scored.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal).then(a.0.cmp(&b.0)));
    scored.truncate(n_terms);

    scored
        .into_iter()
        .map(|(term, _)| {
            let docs_in = incidence.remove(&term).unwrap_or_default();
            (term, docs_in)
        })
        .collect()
}

/// Latent motifs: themes a situation can join through terms that travel together, with no keyword in common.
///
/// This is the paper's sixth dimension. The reference implementation gets motifs from SPLADE activations, which
/// need a trained model; the paper permits optimal transport over the co-occurrence geometry as the alternative,
/// and that is what this does — the same solver as [`discover`], at a lower epsilon so each term commits to one
/// theme rather than hedging across all of them.
///
/// Returns `(name, member terms)`. A motif is named by its first member that is a corpus common noun, because a
/// theme should read as a kind of thing rather than as a proper name.
pub fn discover_motifs(docs: &[String], n_terms: usize, k: usize) -> Vec<(String, Vec<String>)> {
    let (terms, vecs) = term_vectors(docs, n_terms);
    if terms.len() < 2 || k == 0 {
        return Vec::new();
    }
    let (_protos, assign, _cost) = crate::text::ot::codebook(&vecs, k, MOTIF_EPS);
    let groups = assign.iter().copied().max().map_or(0, |m| m + 1);
    let mut members: Vec<Vec<String>> = vec![Vec::new(); groups];
    for (i, &a) in assign.iter().enumerate() {
        members[a].push(terms[i].clone());
    }
    let commons = common_nouns(docs);
    members
        .into_iter()
        .filter(|g| !g.is_empty())
        .filter_map(|g| {
            let name = g.iter().find(|t| commons.contains(*t)).or_else(|| g.first())?.clone();
            (!name.is_empty()).then_some((name, g))
        })
        .collect()
}

/// Entropy regularisation for motifs, below [`DISCOVER_EPS`] so a term commits to a single theme.
const MOTIF_EPS: f32 = 0.03;

/// Entropy regularisation for discovery, from the reference implementation's `--eps` default. Lower makes
/// each term commit to one facet; higher spreads it across several.
pub const DISCOVER_EPS: f32 = 0.05;

/// L2-normalised document-incidence vectors for the top salient terms, plus the terms themselves.
///
/// This is what lets optimal transport run with no embedding model. A term's "position" is simply the set of
/// documents it appears in, written as a vector of 0s and 1s and normalised — so cosine similarity between
/// two terms is exactly their co-occurrence. The Sinkhorn core takes a cost matrix and does not care where
/// the geometry came from, and this geometry needs no tokenizer, which is what makes it run in a browser.
pub fn term_vectors(docs: &[String], n_terms: usize) -> (Vec<String>, Vec<Vec<f32>>) {
    let picked = salient_terms(docs, n_terms);
    let n = docs.len().max(1);
    let mut names = Vec::with_capacity(picked.len());
    let mut vecs = Vec::with_capacity(picked.len());
    for (term, docs_in) in picked {
        let mut v = vec![0f32; n];
        for i in &docs_in {
            if *i < n {
                v[*i] = 1.0;
            }
        }
        let norm = v.iter().map(|x| x * x).sum::<f32>().sqrt() + 1e-9;
        vecs.push(v.into_iter().map(|x| x / norm).collect());
        names.push(term);
    }
    (names, vecs)
}

/// Quantities: a number followed by a unit, returned as `(start, end, canonical field)` byte ranges.
///
/// The paper treats quantities as their own dimension, and the reference pipeline routes them away from the
/// semantic codebook entirely — a measurement is not a kind of thing, it is a value with a scale. Extracting
/// them separately is also the only way a numeric range predicate has anything to range over: without this,
/// "1082 m" is three unremarkable characters and a unit nobody recorded.
pub fn quantity_spans(doc: &str) -> Vec<(usize, usize, String)> {
    const UNITS: &[(&str, &str)] = &[
        ("mm", "length_mm"), ("cm", "length_cm"), ("km", "length_km"), ("m", "length_m"),
        ("kg", "mass_kg"), ("g", "mass_g"), ("t", "mass_t"),
        ("°c", "temp_c"), ("°f", "temp_f"), ("c", "temp_c"),
        ("minutes", "minutes"), ("minute", "minutes"), ("min", "minutes"),
        ("hours", "hours"), ("hour", "hours"), ("seconds", "seconds"),
        ("mm/yr", "rainfall_mm"), ("%", "percent"),
    ];
    let b = doc.as_bytes();
    let mut out = Vec::new();
    let mut i = 0usize;
    while i < b.len() {
        // start of a number, not mid-word
        if b[i].is_ascii_digit() && (i == 0 || !(b[i - 1] as char).is_alphanumeric()) {
            // A leading minus belongs to the number. Dropping it turned "-7 °C" into 7 °C, so a sub-zero
            // reading indexed as above zero — a wrong answer, not a missing one. Only counts when the sign
            // directly precedes the digits and itself follows a boundary, so the hyphen in "11-minute" and
            // ranges like "5-10" are not mistaken for a sign.
            let mut start = i;
            if i > 0 && b[i - 1] == b'-' {
                let before_sign = i >= 2 && !(b[i - 2] as char).is_alphanumeric() && b[i - 2] != b'-';
                if i == 1 || before_sign {
                    start = i - 1;
                }
            }
            let mut j = i;
            while j < b.len() && (b[j].is_ascii_digit() || b[j] == b'.' || b[j] == b',') {
                j += 1;
            }
            let num_end = j;
            // optional separators (space, hyphen, non-breaking space) then the unit
            let mut k = j;
            while k < b.len() && (b[k] == b' ' || b[k] == b'-') {
                k += 1;
            }
            if k < b.len() && doc.is_char_boundary(k) {
                let rest = &doc[k..];
                let unit_len = rest
                    .char_indices()
                    .take_while(|(_, c)| c.is_alphabetic() || *c == '°' || *c == '%' || *c == '/')
                    .map(|(bi, c)| bi + c.len_utf8())
                    .last()
                    .unwrap_or(0);
                if unit_len > 0 {
                    let unit = rest[..unit_len].to_lowercase();
                    // longest unit match wins, so "km" is not read as "m"
                    let mut best: Option<(&str, usize)> = None;
                    for (u, field) in UNITS {
                        if unit == *u && best.map(|(_, l)| u.len() > l).unwrap_or(true) {
                            best = Some((field, u.len()));
                        }
                    }
                    if let Some((field, ulen)) = best {
                        let end = k + ulen;
                        if doc.is_char_boundary(start) && doc.is_char_boundary(end) {
                            out.push((start, end, field.to_string()));
                            i = end;
                            continue;
                        }
                    }
                }
            }
            i = num_end.max(i + 1);
            continue;
        }
        i += 1;
    }
    out
}

/// Whole-word containment test, for checking whether a document participates in a term group.
pub fn contains_term(hay: &str, needle: &str) -> bool {
    !word_spans(hay, needle).is_empty()
}

/// The whole words of a document, lowercased — the cheap key for deciding which phrases could occur in it.
pub fn word_set(doc: &str) -> std::collections::HashSet<String> {
    doc.split(|c: char| !c.is_alphanumeric())
        .filter(|w| !w.is_empty())
        .map(|w| w.chars().flat_map(|c| c.to_lowercase()).collect())
        .collect()
}

/// A gazetteer compiled for one-pass matching.
///
/// Scanning a document once per phrase is O(document × phrases), and on a large corpus the gazetteer grows into
/// the thousands, so projection was quadratic in corpus size — the reference implementation avoids this only by
/// having a neural tagger read each document once, which the model-free build has no equivalent for. An
/// Aho-Corasick automaton is that equivalent: built once from every phrase, it finds all of them in a single
/// pass over the text, independent of how many phrases there are.
///
/// The automaton is a prefilter. It finds substring occurrences; [`word_spans`] then confirms word boundaries
/// on the few phrases that occurred, so the result is exactly `mentions.iter().filter(|m| contains_term(doc,
/// m))` would give — a word-boundary match is necessarily a substring match — at a fraction of the cost.
pub struct MentionMatcher {
    ac: aho_corasick::AhoCorasick,
    surfaces: Vec<String>,
}

impl MentionMatcher {
    pub fn new(mentions: &[String]) -> MentionMatcher {
        let surfaces: Vec<String> = mentions.to_vec();
        // lowercase the patterns and match against lowercased text, mirroring `word_spans`, whose
        // case-folding is full Unicode `to_lowercase` rather than ASCII-only.
        let lowered: Vec<String> = surfaces.iter().map(|s| s.to_lowercase()).collect();
        let ac = aho_corasick::AhoCorasick::builder()
            .match_kind(aho_corasick::MatchKind::Standard)
            .build(&lowered)
            .expect("gazetteer automaton");
        MentionMatcher { ac, surfaces }
    }

    /// Which registered surfaces occur in `doc` as whole words, in registration order, deduplicated.
    pub fn present<'a>(&'a self, doc: &str) -> Vec<&'a String> {
        let lower = doc.to_lowercase();
        let mut seen = vec![false; self.surfaces.len()];
        // one pass finds every candidate; overlapping matches are wanted, since a prefix and the phrase
        // containing it can both be registered surfaces
        for m in self.ac.find_overlapping_iter(&lower) {
            let id = m.pattern().as_usize();
            if seen[id] {
                continue;
            }
            if contains_term(doc, &self.surfaces[id]) {
                seen[id] = true;
            }
        }
        self.surfaces.iter().enumerate().filter(|(i, _)| seen[*i]).map(|(_, s)| s).collect()
    }
}

/// Which of `mentions` occur in `doc`, as whole words, in input order. Convenience for a single document; when
/// projecting many, build one [`MentionMatcher`] and reuse it rather than rebuilding the automaton each call.
pub fn mentions_present<'a>(doc: &str, mentions: &'a [String]) -> Vec<&'a String> {
    // borrow-preserving: match on a matcher built from the same slice, then map ids back to the caller's refs
    let matcher = MentionMatcher::new(mentions);
    let present: std::collections::HashSet<&str> =
        matcher.present(doc).into_iter().map(|s| s.as_str()).collect();
    mentions.iter().filter(|m| present.contains(m.as_str())).collect()
}

/// Relation verbs worth binding a role to. A curated list rather than a morphological guess: "-ed" also ends
/// plenty of adjectives ("distinctive", "detailed"), and a false relation is worse than a missing one because
/// it asserts a direction that was never stated.
const REL_VERBS: &[(&str, &str)] = &[
    ("defeated", "defeated"), ("beat", "defeated"), ("faced", "faced"), ("met", "faced"),
    ("documented", "documented"), ("recorded", "recorded"), ("measured", "measured"),
    ("observed", "observed"), ("found", "observed"), ("held", "held_at"), ("hosted", "held_at"),
    ("used", "used"), ("led", "used"), ("answered", "answered_with"), ("commanded", "commanded"),
    ("permitted", "permitted"), ("banned", "banned"), ("restricted", "restricted"),
    ("competed", "competed_in"), ("entered", "competed_in"), ("won", "won"), ("secured", "secured"),
    ("contributes", "contributes_to"), ("supplies", "supplies"), ("operates", "operates"),
];

/// One directional relation read out of a sentence.
#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
pub struct Relation {
    /// canonical predicate name
    pub verb: String,
    /// the mention on the acting side
    pub actor: String,
    /// the mention on the receiving side
    pub target: String,
}

/// Extract directional relations from prose by pattern: mention, relation verb, mention.
///
/// This is deliberately not a model. The span tagger produces better relations, but it cannot run in a
/// browser, and leaving the dimension empty misrepresents the system more than a conservative extractor does.
///
/// Direction is the whole point. The mention on the left of the verb becomes the actor (`+`), the one on the
/// right the target (`-`). Storing them as separate tags is what makes a reversed relation
/// *unrepresentable* rather than merely wrong: there is no tag that means "supplied by" hiding inside
/// `rel/supplies/+`.
///
/// Only the nearest mention on each side is taken, and only within a single sentence, because a relation
/// inferred across a sentence boundary is a guess about coreference rather than something the text states.
pub fn relation_spans(doc: &str, mentions: &[String]) -> Vec<Relation> {
    relation_spans_with(doc, &MentionMatcher::new(mentions))
}

/// As [`relation_spans`], but reusing a [`MentionMatcher`] built once for the whole corpus.
///
/// Building the automaton is O(total gazetteer text); doing it per document would put the quadratic back. When
/// projecting many documents, build the matcher once and pass it here.
pub fn relation_spans_with(doc: &str, matcher: &MentionMatcher) -> Vec<Relation> {
    let mut out: Vec<Relation> = Vec::new();
    for sentence in doc.split(['.', ';', '!', '?', '\n']) {
        if sentence.trim().is_empty() {
            continue;
        }
        // locate every mention in this sentence, longest first so a full name beats its prefix. The matcher
        // returns exactly the surfaces present as whole words, in registration order (which is longest-first),
        // so the containment dedup below behaves as it did when this looped over the entire gazetteer.
        let mut found: Vec<(usize, usize, String)> = Vec::new();
        for m in matcher.present(sentence) {
            for (s, e) in word_spans(sentence, m) {
                if !found.iter().any(|(fs, fe, _)| s >= *fs && e <= *fe) {
                    found.push((s, e, m.clone()));
                }
            }
        }
        // The corpus gazetteer only keeps mentions that RECUR, which is right for building vocabulary and
        // wrong for reading a relation: "Juan Tide defeated Cynthia Ward" states a fact about two people
        // whether or not either name appears twice. So names found in this sentence count too.
        for (s, e, name) in local_mentions(sentence) {
            if !found.iter().any(|(fs, fe, _)| s < *fe && e > *fs) {
                found.push((s, e, name));
            }
        }
        if found.len() < 2 {
            continue;
        }
        found.sort_by_key(|(s, _, _)| *s);

        for (raw, canon) in REL_VERBS {
            for (vs, ve) in word_spans(sentence, raw) {
                // nearest mention ending before the verb, and nearest starting after it
                let actor = found.iter().filter(|(_, e, _)| *e <= vs).next_back();
                let target = found.iter().find(|(s, _, _)| *s >= ve);
                if let (Some((_, _, a)), Some((_, _, t))) = (actor, target) {
                    if a != t {
                        out.push(Relation { verb: canon.to_string(), actor: a.clone(), target: t.clone() });
                    }
                }
            }
        }
    }
    out.dedup_by(|a, b| a.verb == b.verb && a.actor == b.actor && a.target == b.target);
    out
}

/// Capitalised runs inside a single sentence — mentions that need no corpus-wide support to be real.
///
/// Used for relation extraction, where a one-off name is still a participant. Deliberately not used to build
/// the vocabulary, because a mention seen once cannot define a retrieval dimension.
///
/// The first word of a sentence is skipped: its capital is grammar, not a name.
pub fn local_mentions(sentence: &str) -> Vec<(usize, usize, String)> {
    // Iterate CHARACTERS, not bytes. Casting a raw byte to char treats a UTF-8 continuation byte as a
    // Latin-1 character, so word boundaries land mid-character and slicing panics — "Pokémon" and "28 °C"
    // both trigger it.
    let is_word = |c: char| c.is_alphanumeric() || c == '\'' || c == '-';

    let mut words: Vec<(usize, usize, &str)> = Vec::new();
    let mut cur: Option<usize> = None;
    for (i, c) in sentence.char_indices() {
        if is_word(c) {
            if cur.is_none() {
                cur = Some(i);
            }
        } else if let Some(st) = cur.take() {
            words.push((st, i, &sentence[st..i]));
        }
    }
    if let Some(st) = cur {
        words.push((st, sentence.len(), &sentence[st..]));
    }

    // Runs are collected as word-index ranges first, so the sentence-opening word can be reconsidered once we
    // know how long its run turned out to be.
    let mut runs: Vec<(usize, usize)> = Vec::new();
    let mut run: Option<(usize, usize)> = None;
    let mut prev_end: Option<usize> = None;
    for (wi, (st, en, w)) in words.iter().enumerate() {
        let capped = w.chars().next().map(|c| c.is_uppercase()).unwrap_or(false) && w.chars().count() > 1;
        // Punctuation ends a run even between two capitals. Without this, "in Violet City, Johto, Juan Tide
        // defeated ..." reads as one seven-word name, and the relation gets an actor that is three separate
        // things joined by commas.
        let punctuated = prev_end
            .map(|pe| sentence[pe..*st].chars().any(|c| !c.is_whitespace()))
            .unwrap_or(false);
        if punctuated {
            if let Some(r) = run.take() {
                runs.push(r);
            }
        }
        if capped {
            run = Some(match run {
                Some((rs, _)) => (rs, wi),
                None => (wi, wi),
            });
        } else if let Some(r) = run.take() {
            runs.push(r);
        }
        prev_end = Some(*en);
    }
    if let Some(r) = run {
        runs.push(r);
    }

    // Determiners that open a sentence are capitalised by grammar. Previously the whole first word was skipped,
    // which cost "Morty Shade defeated Wallace Gale" its actor: "Morty" was dropped and the relation recorded
    // `shade`. A sentence-initial capital now joins its run, and only a leading determiner is removed — so
    // "Milotic is not permitted" still yields Milotic, which is genuinely the subject.
    const DETERMINERS: &[&str] = &[
        "the", "a", "an", "this", "that", "these", "those", "their", "its", "his", "her", "our", "your", "my",
        "it", "they", "we", "he", "she", "there", "then", "when", "where", "what", "which", "who",
    ];
    let mut out: Vec<(usize, usize, String)> = Vec::new();
    for (first, last) in runs {
        let mut first = first;
        if first == 0 && DETERMINERS.contains(&words[0].2.to_lowercase().as_str()) {
            // "The Indigo Invitational" is a name wearing an article; "The survey" is not a name at all
            first += 1;
        }
        if first > last {
            continue;
        }
        let (rs, re) = (words[first].0, words[last].1);
        out.push((rs, re, sentence[rs..re].to_string()));
    }
    out
}

/// Temporal loci: years and quarters, as `(start, end, bucket token)` byte ranges.
///
/// Dates are the one dimension that needs neither a model nor a gazetteer — a four-digit year is
/// unambiguous. They are bucketed rather than stored as exact instants, because the engine matches sets: a
/// query asks for `time/2026/q3`, not for an interval comparison. Bucketing is what turns a continuous axis
/// into something a bitmap can intersect.
pub fn temporal_spans(doc: &str) -> Vec<(usize, usize, String)> {
    let b = doc.as_bytes();
    let mut out: Vec<(usize, usize, String)> = Vec::new();

    // quarters: Q1..Q4, optionally followed by a year
    let mut i = 0usize;
    while i + 1 < b.len() {
        if (b[i] == b'Q' || b[i] == b'q') && b[i + 1].is_ascii_digit() {
            let q = (b[i + 1] - b'0') as u32;
            let starts_word = i == 0 || !(b[i - 1] as char).is_alphanumeric();
            if (1..=4).contains(&q) && starts_word {
                let end = i + 2;
                // look ahead for a year so the bucket can be fully qualified
                let tail = &doc[end..].trim_start();
                let year: Option<u32> = tail
                    .split(|c: char| !c.is_ascii_digit())
                    .next()
                    .filter(|t| t.len() == 4)
                    .and_then(|t| t.parse().ok())
                    .filter(|y| (1900..2200).contains(y));
                let token = match year {
                    Some(y) => format!("time/{y}/q{q}"),
                    None => format!("time/q{q}"),
                };
                if doc.is_char_boundary(i) && doc.is_char_boundary(end) {
                    out.push((i, end, token));
                }
                i = end;
                continue;
            }
        }
        i += 1;
    }

    // bare years
    let mut j = 0usize;
    while j + 3 < b.len() {
        if b[j].is_ascii_digit() {
            let before_ok = j == 0 || !(b[j - 1] as char).is_alphanumeric();
            let end = j + 4;
            let after_ok = end >= b.len() || !(b[end] as char).is_alphanumeric();
            if before_ok && after_ok && b[j..end].iter().all(|c| c.is_ascii_digit()) {
                if let Ok(y) = doc[j..end].parse::<u32>() {
                    if (1900..2200).contains(&y) && !out.iter().any(|(s, e, _)| j >= *s && end <= *e) {
                        out.push((j, end, format!("time/{y}")));
                    }
                }
                j = end;
                continue;
            }
        }
        j += 1;
    }
    out.sort_by_key(|(s, _, _)| *s);
    out
}

/// Mine multi-word proper-noun mentions — a **gazetteer** grown from the corpus itself.
///
/// Word-level matching shatters real entities: "Sootopolis City" becomes "Sootopolis" plus "City", and the
/// engine then believes it saw two unrelated things. A mention is a run of capitalised words, so the longest
/// run wins and the parts are never emitted separately.
///
/// A run is kept only if it appears at least `min_count` times across the corpus. That threshold is what
/// stops an ordinary sentence-initial word from being promoted to an entity: "The" starts many sentences but
/// never forms a repeated multi-word run with what follows.
pub fn mine_gazetteer(docs: &[String], min_count: usize) -> Vec<String> {
    let mut counts: HashMap<String, usize> = HashMap::new();
    for doc in docs {
        for sentence in doc.split(['.', '\n', ';', '!', '?']) {
            let words: Vec<&str> = sentence.split_whitespace().collect();
            let mut run: Vec<&str> = Vec::new();
            let mut first = true;
            for w in words {
                let clean = w.trim_matches(|c: char| !c.is_alphanumeric() && c != '\'' && c != '-');
                let cap = clean
                    .chars()
                    .next()
                    .map(|c| c.is_uppercase())
                    .unwrap_or(false)
                    && clean.len() > 1;
                // a sentence-initial capital carries no information, so it cannot start a run
                if cap && !(first && run.is_empty()) {
                    run.push(clean);
                } else {
                    if run.len() >= 2 {
                        *counts.entry(run.join(" ")).or_default() += 1;
                    }
                    run.clear();
                }
                first = false;
            }
            if run.len() >= 2 {
                *counts.entry(run.join(" ")).or_default() += 1;
            }
        }
    }
    let mut kept: Vec<String> =
        counts.into_iter().filter(|(_, n)| *n >= min_count).map(|(s, _)| s).collect();
    // longest first, so matching prefers the full mention over any prefix of it
    kept.sort_by(|a, b| b.len().cmp(&a.len()).then(a.cmp(b)));
    kept
}

/// Generic vocabulary that looks like a category but names no kind of thing. The reference pipeline routes
/// this class away from the codebook rather than clustering it.
/// Prepositions and locatives. These belong with `STOP`: a function word is not a kind of thing, so it can
/// neither name a category nor usefully join one, and one that occurs in most documents adds only noise to the
/// co-occurrence geometry. The list already held `during`, `under`, `over` and `between`; the omissions showed
/// up as a corpus whose discovered category was `near/*`.
pub const LOCATIVES: &[&str] = &[
    "near", "nearby", "across", "along", "around", "through", "throughout", "toward", "towards",
    "beside", "behind", "beyond", "upon", "onto", "inside", "outside", "amid", "among", "amongst",
    "beneath", "underneath", "alongside", "opposite", "past", "since", "until", "till", "unto",
];

pub const GENERIC: &[&str] = &[
    "within", "presence", "data", "contributes", "distribution", "environmental", "understanding",
    "preferences", "observation", "site", "location", "conditions", "period", "mean", "documented",
    "recorded", "measured", "reported", "described", "including", "various", "distinctive", "populations",
    "ecological", "information", "details", "features", "aspects", "elements", "factors", "values",
    "results", "analysis", "summary", "overview", "context", "purposes", "requirements",
];

/// Find every whole-word occurrence of `needle` in `hay`, as byte ranges.
///
/// Whole-word only: a substring match would highlight "it" inside "submitted".
pub fn word_spans(hay: &str, needle: &str) -> Vec<(usize, usize)> {
    let mut out = Vec::new();
    if needle.is_empty() {
        return out;
    }
    let lower = hay.to_lowercase();
    let pat = needle.to_lowercase();
    let bytes = lower.as_bytes();
    let mut from = 0usize;
    while let Some(rel) = lower[from..].find(&pat) {
        let s = from + rel;
        let e = s + pat.len();
        let before_ok = s == 0 || !(bytes[s - 1] as char).is_alphanumeric();
        let after_ok = e >= bytes.len() || !(bytes[e] as char).is_alphanumeric();
        // only keep it if the byte range is also a char boundary in the ORIGINAL string
        if before_ok && after_ok && hay.is_char_boundary(s) && hay.is_char_boundary(e) {
            out.push((s, e));
        }
        from = s + pat.len().max(1);
        if from >= lower.len() {
            break;
        }
    }
    out
}

/// The salience ranking on its own, for callers that want to show the intermediate step: `(term, score,
/// document frequency)`, most salient first.
pub fn salient(docs: &[String], n_terms: usize) -> Vec<(String, f64, usize)> {
    let picked = salient_terms(docs, n_terms);
    let n = docs.len().max(1) as f64;
    picked
        .into_iter()
        .map(|(term, docs_in)| {
            let d = docs_in.len();
            let idf = ((n + 1.0) / (d as f64 + 1.0)).ln() + 1.0;
            (term, idf, d)
        })
        .collect()
}

/// Name a cluster by the member term most exclusive to it — TF-IDF where a "document" is a CLUSTER.
///
/// This is the step that replaces an LLM naming call. The reference pipeline asked a model to invent a facet
/// name; here the corpus decides. A term scores highly when it is frequent inside this cluster and rare in
/// the other clusters, which is exactly what makes it a usable label for the group.
///
/// Running TF-IDF against the raw documents instead would answer a different question — "which words are
/// unusual in this corpus" — and can hand back a term that several clusters share.
///
/// Proper nouns are demoted: a facet names a KIND, and an always-capitalised term is an instance inside the
/// kind, not the name of it.
pub fn name_cluster(
    members: &[String],
    tf_in_cluster: &HashMap<String, usize>,
    clusters_containing: &HashMap<String, usize>,
    n_clusters: usize,
    cluster_size: usize,
    commons: &HashSet<String>,
    exclusivity: &HashMap<String, f64>,
) -> String {
    let n = n_clusters.max(1) as f64;
    let size = cluster_size.max(1) as f64;

    // A label has to be specific to its own group. `city` occurred in every battle document AND every survey
    // document ("Ecruteak City", "Sootopolis City"), so ranking by frequency alone named the battle category
    // `city/*` — a label that describes the corpus rather than the category, and the worst kind of wrong
    // because it reads as meaningful. Terms whose documents mostly sit in OTHER groups are therefore not
    // eligible to name this one. If that leaves nothing, every member is eligible again, since a group with no
    // specific term still needs a name.
    const MIN_EXCLUSIVITY: f64 = 0.8;
    let confined: Vec<String> = members
        .iter()
        .filter(|t| exclusivity.get(*t).copied().unwrap_or(1.0) >= MIN_EXCLUSIVITY)
        .cloned()
        .collect();
    let pool: &[String] = if confined.is_empty() { members } else { &confined };

    let mut scored: Vec<(String, f64)> = pool
        .iter()
        .map(|t| {
            let tf = *tf_in_cluster.get(t).unwrap_or(&1) as f64;
            let dfc = *clusters_containing.get(t).unwrap_or(&1) as f64;
            let idf = ((n + 1.0) / (dfc + 1.0)).ln() + 1.0;
            // A label must describe MOST of its group. Ranking by raw frequency first picked `city` for the
            // survey cluster: a frequent sub-part rather than the kind. Coverage of the cluster's own
            // situations leads, and exclusivity across clusters only breaks ties.
            let coverage = (tf / size).min(1.0);
            let common_bonus = if commons.contains(t) { 1.3 } else { 1.0 };
            (t.clone(), coverage * common_bonus + 0.12 * idf)
        })
        .collect();
    scored.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal).then(a.0.cmp(&b.0)));
    scored.first().map(|(t, _)| t.clone()).unwrap_or_default()
}

/// Cosine similarity of two document-incidence sets.
fn cosine(a: &HashSet<usize>, b: &HashSet<usize>) -> f64 {
    if a.is_empty() || b.is_empty() {
        return 0.0;
    }
    let inter = a.intersection(b).count() as f64;
    inter / ((a.len() as f64).sqrt() * (b.len() as f64).sqrt())
}

/// One node of the discovered taxonomy. Leaves are the clusters that survived the cut; internal nodes are
/// the merges that built them, so the shape is the corpus's own hierarchy rather than an imposed one.
#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
pub struct TreeNode {
    /// cluster label for a leaf; empty for an internal merge node
    pub label: String,
    /// average-linkage similarity at which this merge happened (0 for leaves)
    pub height: f64,
    /// number of member terms beneath this node
    pub size: usize,
    pub children: Vec<TreeNode>,
}

/// Build the full dendrogram, continuing past the requested cut all the way to a single root.
///
/// The cut at `n_clusters` marks which nodes become facets; everything above it is the super-structure the
/// corpus implies. Returning the whole tree lets a viewer show both the accepted categories and how they
/// would have combined, which is the picture agglomerative clustering actually produces.
pub fn discover_hierarchy(docs: &[String], n_terms: usize, n_clusters: usize) -> Option<TreeNode> {
    let terms = salient_terms(docs, n_terms.clamp(2, 400));
    if terms.len() < 2 {
        return None;
    }
    let cut = n_clusters.clamp(1, terms.len());
    let commons = common_nouns(docs);

    // active[i] = (members, doc incidence, node)
    let mut active: Vec<(Vec<usize>, HashSet<usize>, TreeNode)> = terms
        .iter()
        .enumerate()
        .map(|(i, (t, d))| {
            (vec![i], d.clone(), TreeNode { label: t.clone(), height: 0.0, size: 1, children: Vec::new() })
        })
        .collect();

    let avg_linkage = |a: &[usize], b: &[usize]| -> f64 {
        let mut sum = 0.0;
        for x in a {
            for y in b {
                sum += cosine(&terms[*x].1, &terms[*y].1);
            }
        }
        sum / (a.len() * b.len()) as f64
    };

    // when the count reaches the cut, label the surviving groups — these are the facets
    let mut labelled = false;
    while active.len() > 1 {
        if active.len() == cut && !labelled {
            labelled = true;
            let n_c = active.len();
            let mut tf: HashMap<String, usize> = HashMap::new();
            let mut containing: HashMap<String, usize> = HashMap::new();
            for (members, docs_in, _) in &active {
                let mut seen = HashSet::new();
                for m in members {
                    let t = &terms[*m].0;
                    let c = docs_in.iter().filter_map(|i| docs.get(*i)).filter(|d| !word_spans(d, t).is_empty()).count();
                    *tf.entry(t.clone()).or_default() += c.max(1);
                    seen.insert(t.clone());
                }
                for t in seen {
                    *containing.entry(t).or_default() += 1;
                }
            }
            // the same specificity rule the flat discovery uses, computed before the mutable pass
            let excl: Vec<HashMap<String, f64>> = (0..active.len())
                .map(|ci| {
                    let others: HashSet<usize> = active
                        .iter()
                        .enumerate()
                        .filter(|(cj, _)| *cj != ci)
                        .flat_map(|(_, (_, docs_j, _))| docs_j.iter().copied())
                        .collect();
                    active[ci]
                        .0
                        .iter()
                        .map(|m| {
                            let (term, term_docs) = &terms[*m];
                            let own = term_docs.iter().filter(|d| !others.contains(d)).count() as f64;
                            (term.clone(), own / term_docs.len().max(1) as f64)
                        })
                        .collect()
                })
                .collect();
            for (ci, (members, docs_in, node)) in active.iter_mut().enumerate() {
                let names: Vec<String> = members.iter().map(|m| terms[*m].0.clone()).collect();
                node.label =
                    name_cluster(&names, &tf, &containing, n_c, docs_in.len(), &commons, &excl[ci]);
            }
        }

        let mut best: Option<(usize, usize, f64)> = None;
        for i in 0..active.len() {
            for j in (i + 1)..active.len() {
                let s = avg_linkage(&active[i].0, &active[j].0);
                if best.map(|(_, _, bs)| s > bs).unwrap_or(true) {
                    best = Some((i, j, s));
                }
            }
        }
        let Some((i, j, sim)) = best else { break };
        let (mj, dj, nj) = active.remove(j);
        let (_, _, ni) = &active[i];
        let merged = TreeNode {
            label: String::new(),
            height: sim,
            size: ni.size + nj.size,
            children: vec![active[i].2.clone(), nj],
        };
        active[i].0.extend(mj);
        active[i].1.extend(dj);
        active[i].2 = merged;
    }

    active.into_iter().next().map(|(_, _, n)| n)
}

/// Discover `n_clusters` candidate facets from prose.
///
/// `n_terms` caps how much vocabulary is considered; agglomeration is O(n_terms^3) in the worst case, so the
/// cap is what keeps this interactive in a browser.
pub fn discover(docs: &[String], n_terms: usize, n_clusters: usize) -> Vec<TermCluster> {
    let terms = salient_terms(docs, n_terms.clamp(2, 400));
    if terms.len() < 2 || n_clusters == 0 {
        return Vec::new();
    }

    // L2-normalised document-incidence vectors. A term's position is the set of documents it appears in, so
    // cosine between two terms is exactly their co-occurrence — the geometry the transport plan runs over, and
    // it needs no embedding model, which is what lets this run in a browser.
    let n_docs = docs.len().max(1);
    let vecs: Vec<Vec<f32>> = terms
        .iter()
        .map(|(_, docs_in)| {
            let mut v = vec![0f32; n_docs];
            for i in docs_in {
                if *i < n_docs {
                    v[*i] = 1.0;
                }
            }
            let norm = v.iter().map(|x| x * x).sum::<f32>().sqrt() + 1e-9;
            v.into_iter().map(|x| x / norm).collect()
        })
        .collect();

    // k-means++ prototypes, then entropy-regularised optimal transport onto them, then argmax over the plan.
    // This is the reference pipeline's `cluster()` (python/splade/spo_sinkhorn.py): eps 0.05, 200 Sinkhorn
    // iterations, 60 k-means iterations, cost `1 - cosine`, uniform marginals on both sides.
    //
    // It replaced average-linkage agglomerative clustering, which was never the paper's method. Linkage was
    // adopted here to stop one group chaining through weak similarities and swallowing the corpus, but the
    // uniform TARGET marginal rules that out structurally: no prototype can absorb more than its 1/k share of
    // the mass, so collapse is prevented by the solver rather than patched by a linkage floor.
    let (_protos, assign, _cost) = crate::text::ot::codebook(&vecs, n_clusters, DISCOVER_EPS);

    // group the terms by the target each was transported to; a prototype that won nothing is not a facet
    let k = assign.iter().copied().max().map_or(0, |m| m + 1);
    let mut clusters: Vec<(Vec<usize>, HashSet<usize>)> = vec![(Vec::new(), HashSet::new()); k];
    for (i, &a) in assign.iter().enumerate() {
        clusters[a].0.push(i);
        clusters[a].1.extend(terms[i].1.iter().copied());
    }
    clusters.retain(|(members, _)| !members.is_empty());

    let commons = common_nouns(docs);
    let n = docs.len().max(1) as f64;

    // Cluster-level statistics for naming: how often each term occurs inside its own cluster, and how many
    // clusters mention it at all. Both are needed before any cluster can be named, which is precisely why
    // naming cannot happen during selection.
    let n_clusters_final = clusters.len();
    let mut tf_in_cluster: HashMap<String, usize> = HashMap::new();
    let mut clusters_containing: HashMap<String, usize> = HashMap::new();
    for (members, docs_in) in &clusters {
        let mut seen: HashSet<String> = HashSet::new();
        for m in members {
            let term = &terms[*m].0;
            // occurrences of this member inside the cluster's own situations
            let count = docs_in
                .iter()
                .filter_map(|i| docs.get(*i))
                .filter(|d| word_spans(d, term).len() > 0)
                .count();
            *tf_in_cluster.entry(term.clone()).or_default() += count.max(1);
            seen.insert(term.clone());
        }
        for t in seen {
            *clusters_containing.entry(t).or_default() += 1;
        }
    }
    // For each cluster, how specific each member term is to it: the share of the term's own documents that no
    // OTHER cluster claims. Measuring against the cluster's own union would be vacuous, because that union is
    // built from its members' documents and every member would score 1.0.
    let exclusivity: Vec<HashMap<String, f64>> = (0..clusters.len())
        .map(|ci| {
            let others: HashSet<usize> = clusters
                .iter()
                .enumerate()
                .filter(|(cj, _)| *cj != ci)
                .flat_map(|(_, (_, docs_j))| docs_j.iter().copied())
                .collect();
            clusters[ci]
                .0
                .iter()
                .map(|m| {
                    let (term, term_docs) = &terms[*m];
                    let own = term_docs.iter().filter(|d| !others.contains(d)).count() as f64;
                    (term.clone(), own / term_docs.len().max(1) as f64)
                })
                .collect()
        })
        .collect();

    let mut out: Vec<TermCluster> = clusters
        .iter()
        .cloned()
        .enumerate()
        .map(|(ci, (members, docs_in))| {
            // members are already in salience order, since `terms` was sorted
            let mut member_terms: Vec<String> = members.iter().map(|m| terms[*m].0.clone()).collect();

            // cohesion: mean pairwise similarity among members
            let mut sum = 0.0;
            let mut pairs = 0usize;
            for a in 0..members.len() {
                for b in (a + 1)..members.len() {
                    sum += cosine(&terms[members[a]].1, &terms[members[b]].1);
                    pairs += 1;
                }
            }
            let cohesion = if pairs == 0 { 1.0 } else { sum / pairs as f64 };

            // label by the most distinctive term: the cluster's own documents against the whole corpus
            let label = name_cluster(
                &member_terms,
                &tf_in_cluster,
                &clusters_containing,
                n_clusters_final,
                docs_in.len(),
                &commons,
                &exclusivity[ci],
            );

            member_terms.retain(|t| *t != label);
            member_terms.insert(0, label.clone());

            TermCluster { label, terms: member_terms, coverage: docs_in.len() as f64 / n, cohesion }
        })
        .filter(|c| !c.label.is_empty() && c.terms.len() > 1)
        .collect();

    out.sort_by(|a, b| b.coverage.partial_cmp(&a.coverage).unwrap_or(std::cmp::Ordering::Equal));
    out
}

#[cfg(test)]
mod tests {
    use super::*;

    fn corpus() -> Vec<String> {
        // two clearly separate domains, stated only in prose — no field markers to read
        let battles = [
            "Morty Shade defeated Wallace Gale in a battle at the tournament venue",
            "Bea Strike defeated Falkner Gale in a battle at the tournament venue",
            "Iris Draco defeated Nessa Reef in a battle at the tournament venue",
            "Marnie Dusk defeated Juan Tide in a battle at the tournament venue",
        ];
        let surveys = [
            "The survey recorded elevation and rainfall across the habitat region",
            "The survey recorded elevation and temperature across the habitat region",
            "A survey measured rainfall and elevation within the habitat region",
            "A survey measured temperature and elevation within the habitat region",
        ];
        battles.iter().chain(surveys.iter()).map(|s| s.to_string()).collect()
    }

    #[test]
    fn discovers_the_two_domains_without_any_field_markers() {
        let docs = corpus();
        let clusters = discover(&docs, 60, 2);
        assert_eq!(clusters.len(), 2, "{clusters:#?}");

        let joined: Vec<String> = clusters.iter().map(|c| c.terms.join(" ")).collect();
        let battle_cluster = joined.iter().find(|t| t.contains("battle")).expect(&format!("{joined:?}"));
        let survey_cluster = joined.iter().find(|t| t.contains("survey")).expect(&format!("{joined:?}"));

        // the domains must not be mixed together
        assert!(!battle_cluster.contains("survey"), "battle cluster leaked survey terms: {battle_cluster}");
        assert!(!survey_cluster.contains("battle"), "survey cluster leaked battle terms: {survey_cluster}");
        assert!(survey_cluster.contains("elevation"), "{survey_cluster}");
    }

    #[test]
    fn labels_are_drawn_from_the_cluster_and_are_distinctive() {
        let docs = corpus();
        for c in discover(&docs, 60, 2) {
            assert!(c.terms.contains(&c.label), "label must be a member: {c:?}");
            assert_eq!(c.terms[0], c.label, "label should lead the member list");
            assert!(!STOP.contains(&c.label.as_str()), "label is a stopword: {c:?}");
            assert!(c.coverage > 0.0 && c.coverage <= 1.0, "{c:?}");
        }
    }

    #[test]
    fn prose_with_no_shared_vocabulary_yields_nothing_rather_than_noise() {
        // no term appears in two documents, so there is no co-occurrence to discover
        let docs: Vec<String> = ["alpha beta", "gamma delta", "epsilon zeta"].iter().map(|s| s.to_string()).collect();
        assert!(discover(&docs, 40, 3).is_empty());
    }

    #[test]
    fn is_deterministic() {
        let docs = corpus();
        let a = discover(&docs, 60, 3);
        let b = discover(&docs, 60, 3);
        assert_eq!(
            a.iter().map(|c| c.terms.join(",")).collect::<Vec<_>>(),
            b.iter().map(|c| c.terms.join(",")).collect::<Vec<_>>()
        );
    }

    #[test]
    fn quantities_are_extracted_with_their_units() {
        let doc = "recorded at an elevation of 1082 m. The mean temperature was 28 °C and it ran 7 minutes.";
        let q = quantity_spans(doc);
        let got: Vec<(&str, &str)> = q.iter().map(|(s, e, f)| (&doc[*s..*e], f.as_str())).collect();
        assert!(got.contains(&("1082 m", "length_m")), "{got:?}");
        assert!(got.contains(&("28 °C", "temp_c")), "{got:?}");
        assert!(got.contains(&("7 minutes", "minutes")), "{got:?}");
    }

    #[test]
    fn km_is_not_read_as_m() {
        let doc = "a range of 500 km across";
        let q = quantity_spans(doc);
        assert_eq!(q.len(), 1, "{q:?}");
        assert_eq!(q[0].2, "length_km");
        assert_eq!(&doc[q[0].0..q[0].1], "500 km");
    }

    #[test]
    fn gazetteer_keeps_whole_mentions_not_their_parts() {
        let docs: Vec<String> = [
            "A survey in Sootopolis City recorded Aggron near the crater",
            "Another survey in Sootopolis City found more Aggron there",
            "The Indigo Invitational was held in Sootopolis City again",
        ].iter().map(|s| s.to_string()).collect();
        let g = mine_gazetteer(&docs, 2);
        assert!(g.contains(&"Sootopolis City".to_string()), "{g:?}");
        // the parts must not be promoted on their own
        assert!(!g.contains(&"Sootopolis".to_string()), "{g:?}");
        assert!(!g.contains(&"City".to_string()), "{g:?}");
        // longest-first ordering so matching prefers the full mention
        assert!(g.iter().all(|x| x.split_whitespace().count() >= 2), "{g:?}");
    }

    #[test]
    fn sentence_initial_capitals_do_not_become_entities() {
        let docs: Vec<String> = [
            "The survey found nothing. The survey ended early",
            "The survey found nothing. The survey ended early",
        ].iter().map(|s| s.to_string()).collect();
        let g = mine_gazetteer(&docs, 2);
        assert!(!g.iter().any(|x| x.starts_with("The ")), "{g:?}");
    }

    #[test]
    fn generic_words_are_not_selected_as_vocabulary() {
        let docs: Vec<String> = (0..4)
            .map(|i| format!("survey {i} recorded data within the location and the distribution of species"))
            .collect();
        let picked: Vec<String> = salient(&docs, 40).into_iter().map(|(t, _, _)| t).collect();
        for g in ["data", "within", "location", "distribution"] {
            assert!(!picked.contains(&g.to_string()), "generic term leaked: {g} in {picked:?}");
        }
        assert!(picked.contains(&"survey".to_string()) || picked.contains(&"species".to_string()), "{picked:?}");
    }

    #[test]
    fn temporal_buckets_are_extracted_and_qualified() {
        let doc = "held in Q3 2026 at the venue, following the 2025 season";
        let t = temporal_spans(doc);
        let toks: Vec<&str> = t.iter().map(|(_, _, x)| x.as_str()).collect();
        assert!(toks.contains(&"time/2026/q3"), "{toks:?}");
        assert!(toks.contains(&"time/2025"), "{toks:?}");
        // spans must index the original text
        for (s, e, _) in &t {
            assert!(doc.get(*s..*e).is_some(), "bad span {s}..{e}");
        }
    }

    #[test]
    fn a_four_digit_number_that_is_not_a_year_is_ignored() {
        // an elevation, not a date
        let t = temporal_spans("an elevation of 2369 m");
        assert!(t.iter().all(|(_, _, x)| x != "time/2369"), "{t:?}");
    }

    #[test]
    fn relations_carry_direction_from_word_order() {
        let mentions: Vec<String> = ["Morty Shade", "Wallace Gale"].iter().map(|s| s.to_string()).collect();
        let r = relation_spans("Morty Shade defeated Wallace Gale at the venue", &mentions);
        assert_eq!(r.len(), 1, "{r:?}");
        assert_eq!(r[0].verb, "defeated");
        assert_eq!(r[0].actor, "Morty Shade");
        assert_eq!(r[0].target, "Wallace Gale");

        // reversing the sentence must reverse the roles, not merely relabel them
        let rev = relation_spans("Wallace Gale defeated Morty Shade at the venue", &mentions);
        assert_eq!(rev[0].actor, "Wallace Gale");
        assert_eq!(rev[0].target, "Morty Shade");
    }

    #[test]
    fn no_relation_is_invented_across_a_sentence_boundary() {
        let mentions: Vec<String> = ["Morty Shade", "Wallace Gale"].iter().map(|s| s.to_string()).collect();
        // the verb and the second mention are in different sentences
        let r = relation_spans("Morty Shade defeated someone. Wallace Gale watched", &mentions);
        assert!(r.is_empty(), "should not link across sentences: {r:?}");
    }

    #[test]
    fn a_single_mention_yields_no_relation() {
        let mentions: Vec<String> = vec!["Morty Shade".to_string()];
        assert!(relation_spans("Morty Shade defeated everyone", &mentions).is_empty());
    }

    #[test]
    fn a_one_off_name_can_still_be_a_relation_participant() {
        // neither name recurs, so neither is in the corpus gazetteer
        let r = relation_spans("At the tournament, Juan Tide defeated Cynthia Ward in a close battle", &[]);
        assert!(!r.is_empty(), "should read the relation from local names: {r:?}");
        let d = r.iter().find(|x| x.verb == "defeated").expect("a defeated relation");
        assert_eq!(d.actor, "Juan Tide");
        assert_eq!(d.target, "Cynthia Ward");
    }

    #[test]
    fn local_mentions_skip_the_sentence_initial_capital() {
        let m = local_mentions("Juan Tide defeated Cynthia Ward");
        let names: Vec<&str> = m.iter().map(|(_, _, n)| n.as_str()).collect();
        // "Juan" opens the sentence, so the run starts at "Tide"
        assert!(names.iter().any(|n| n.contains("Cynthia Ward")), "{names:?}");
        assert!(!names.iter().any(|n| n.starts_with("Juan Tide defeated")), "{names:?}");
    }

    #[test]
    fn local_mentions_survive_multibyte_text() {
        // é and ° are multi-byte; a byte-wise scan panicked here with a slice boundary error
        for text in [
            "A Pokémon named Aggron was recorded at 28 °C by Cynthia Ward",
            "Café Ecruteak hosted Juan Tide and Bea Strike",
            "28 °C — Sootopolis City",
        ] {
            let m = local_mentions(text);
            for (s, e, name) in &m {
                assert_eq!(&text[*s..*e], name, "offsets must slice cleanly");
            }
        }
    }

    #[test]
    fn relations_survive_multibyte_text() {
        let r = relation_spans("At the venue, Juan Tide defeated Cynthia Ward and a Pokémon at 28 °C", &[]);
        assert!(r.iter().any(|x| x.actor == "Juan Tide"), "{r:?}");
    }

    #[test]
    fn punctuation_breaks_a_capitalised_run() {
        // three separate names, not one seven-word name
        let m = local_mentions("held in Violet City, Johto, Juan Tide defeated Cynthia Ward");
        let names: Vec<&str> = m.iter().map(|(_, _, n)| n.as_str()).collect();
        assert!(names.contains(&"Violet City"), "{names:?}");
        assert!(names.contains(&"Juan Tide"), "{names:?}");
        assert!(!names.iter().any(|n| n.contains(',')), "a name must not span punctuation: {names:?}");

        let r = relation_spans("held in Violet City, Johto, Juan Tide defeated Cynthia Ward", &[]);
        let d = r.iter().find(|x| x.verb == "defeated").expect("a defeated relation");
        assert_eq!(d.actor, "Juan Tide", "nearest clean name, not a comma-joined run");
        assert_eq!(d.target, "Cynthia Ward");
    }

    #[test]
    fn a_negative_quantity_keeps_its_sign() {
        let doc = "the mean temperature was -7 °C that winter";
        let q = quantity_spans(doc);
        let (s, e, f) = q.first().expect("a quantity").clone();
        assert_eq!(f, "temp_c");
        assert_eq!(&doc[s..e], "-7 °C", "the sign is part of the number");
    }

    #[test]
    fn a_hyphen_between_words_is_not_a_minus_sign() {
        // "11-minute" is a compound, not negative eleven
        let doc = "an 11-minute battle";
        let q = quantity_spans(doc);
        let (s, e, _) = q.first().expect("a quantity").clone();
        assert_eq!(&doc[s..e], "11-minute".split('-').next().unwrap().to_owned() + "-minute");
        assert!(!doc[s..e].starts_with('-'), "must not read the compound hyphen as a sign: {:?}", &doc[s..e]);
    }

    #[test]
    fn a_range_hyphen_is_not_a_minus_sign() {
        let doc = "between 5-10 m of clearance";
        for (s, e, _) in quantity_spans(doc) {
            assert!(!doc[s..e].starts_with('-'), "range hyphen read as a sign: {:?}", &doc[s..e]);
        }
    }

    #[test]
    fn a_term_spanning_two_domains_cannot_name_either() {
        // "city" occurs in every battle document AND every survey document, so it is the most frequent term in
        // whichever group transport puts it in — and naming by frequency alone labelled the battle category
        // `city/*`. A label has to be specific to its own group, or it describes the corpus instead.
        let docs: Vec<String> = [
            "Morty Shade defeated Wallace Gale in a battle at Ecruteak City",
            "Bea Strike defeated Falkner Gale in a battle at Ecruteak City",
            "Iris Draco defeated Nessa Reef in a battle at Ecruteak City",
            "The survey recorded elevation across the habitat near Sootopolis City",
            "The survey recorded rainfall across the habitat near Sootopolis City",
            "A survey measured elevation within the habitat near Sootopolis City",
        ]
        .iter()
        .map(|s| s.to_string())
        .collect();

        let clusters = discover(&docs, 60, 2);
        assert!(!clusters.is_empty(), "the two domains should still be found");
        for c in &clusters {
            assert_ne!(c.label, "city", "a term common to both domains named one of them: {c:?}");
        }
        // it may still be a MEMBER — it genuinely co-occurs — it just cannot be the name
        assert!(clusters.iter().any(|c| c.terms.iter().any(|t| t == "city")), "{clusters:#?}");
    }

    #[test]
    fn discovery_transports_every_salient_term_to_some_facet() {
        // Sinkhorn assigns each term to exactly one target, so nothing salient is silently dropped — which is
        // what the agglomerative version did when a merge fell below its linkage floor.
        let docs = corpus();
        let clusters = discover(&docs, 60, 2);
        let placed: usize = clusters.iter().map(|c| c.terms.len()).sum();
        assert!(placed >= 6, "expected the salient terms to be placed, got {placed}: {clusters:#?}");
    }

    #[test]
    fn urls_do_not_become_vocabulary() {
        // `https` recurred in thousands of documents and became a discovered category. It must not survive
        // tokenisation, nor may the host or path fragments.
        let toks = tokenize("See https://odin.army.mil/WEG/Asset/d2cf and http://EN.Example.COM/x for detail");
        for junk in ["https", "http", "odin", "army", "example", "asset", "weg"] {
            assert!(!toks.iter().any(|t| t == junk), "URL fragment {junk:?} leaked into tokens: {toks:?}");
        }
        assert!(toks.contains(&"see".to_string()) && toks.contains(&"detail".to_string()), "{toks:?}");
    }

    #[test]
    fn scrubbing_a_url_next_to_non_ascii_text_does_not_panic() {
        // A first version indexed a lowercased copy of the string with the original's byte offsets, and a later
        // one sliced a string at a non-char-boundary; both panicked on real corpora where a link abuts an
        // accented or CJK word. This is that case.
        for s in [
            "Aggron https://例え.jp/経路 café near Sootopolis",
            "Pokémon https://a.b/münchen–straße done",
            "https://x.y/z",
            "wwwnoturl actually a word",
            "trailing https://only.at.end",
        ] {
            let _ = scrub_urls(s);
            let _ = tokenize(s);
        }
        // "wwwnoturl" is not a URL (no dot right after www), so it survives as a token
        assert!(tokenize("wwwnoturl actually a word").contains(&"wwwnoturl".to_string()));
    }

    #[test]
    fn the_matcher_matches_the_naive_scan_exactly() {
        // The Aho-Corasick prefilter is only sound if it returns EXACTLY what scanning each phrase would. It
        // finds substrings; word boundaries are confirmed after, so a word-boundary match — which is always a
        // substring match — is never missed, and a substring that is not a whole word is never kept.
        let docs = corpus();
        let gaz = mine_gazetteer(&docs, 2);
        let matcher = MentionMatcher::new(&gaz);
        for d in &docs {
            let naive: Vec<&String> = gaz.iter().filter(|m| contains_term(d, m)).collect();
            let fast = matcher.present(d);
            assert_eq!(naive, fast, "matcher disagreed with the naive scan on: {d}");

            let key = |v: &[Relation]| {
                v.iter().map(|r| format!("{}|{}|{}", r.verb, r.actor, r.target)).collect::<Vec<_>>()
            };
            assert_eq!(
                key(&relation_spans_with(d, &matcher)),
                key(&relation_spans(d, &gaz)),
                "relation extraction diverged via the matcher"
            );
        }

        // a phrase present only as a non-word-boundary substring must NOT be reported
        let m = MentionMatcher::new(&["cat".to_string()]);
        assert!(m.present("the category expanded").is_empty(), "matched inside 'category'");
        assert_eq!(m.present("the cat sat"), vec![&"cat".to_string()]);
    }

    #[test]
    fn a_function_word_cannot_become_a_category() {
        // A corpus of these eight documents discovered `near/*`. A preposition is not a kind of thing, so it
        // can neither name a category nor usefully join one, and one that appears in most documents adds noise
        // to the co-occurrence geometry that the transport plan then has to spend mass on.
        let docs: Vec<String> = [
            "Morty Shade defeated Wallace Gale at Ecruteak City in 2025.",
            "Bea Strike defeated Iris Draco at Ecruteak City in 2025.",
            "Lance Wing defeated Karen Dusk at Ecruteak City in 2025.",
            "A survey recorded Aggron near Sootopolis City at 28 degrees.",
            "A survey recorded Salamence near Sootopolis City at 31 degrees.",
            "A survey recorded Metagross near Sootopolis City at 19 degrees.",
            "Milotic is not permitted in Series 1 play for the 2025 season.",
            "Registeel is not permitted in Series 1 play for the 2025 season.",
        ]
        .iter()
        .map(|s| s.to_string())
        .collect();

        for c in discover(&docs, 60, 4) {
            assert!(
                !LOCATIVES.contains(&c.label.as_str()) && !STOP.contains(&c.label.as_str()),
                "a function word named a category: {c:?}"
            );
            assert!(
                !c.terms.iter().any(|t| LOCATIVES.contains(&t.as_str())),
                "a function word was clustered as a signal word: {c:?}"
            );
        }
    }

    #[test]
    fn the_word_lists_do_not_overlap() {
        // Duplicated entries are harmless but mean one list is being maintained in two places.
        for w in LOCATIVES {
            assert!(!STOP.contains(w), "{w} is in both STOP and LOCATIVES");
            assert!(!GENERIC.contains(w), "{w} is in both GENERIC and LOCATIVES");
        }
    }
}