Repository navigation
HermitCrab analysis: subsequence fallback and insertion classes for the root prune (v2) #568
Description
The root-substring prune (#562) turns itself off on strata with infixation, reduplication or segment-restoring rules, which are exactly Indonesian, Amharic, Mbugwe and Aweti. The trigger is any such stratum. The cost is that the census ceiling (Mbugwe 38.5%, Indonesian 29.6%, Aweti 14.8%, Amharic 13.6% of analysis events) stays unreached.
Depends on #562. Build only if #562 is sound in shadow and v1 pays on Sena or on its stress fixture; otherwise close this.
Problem (census, steps)
The H2 ceilings above come from the census, overlapped in part by required-slot look-ahead (#561) on Mbugwe and Aweti, so the net figure is lower and unmeasured. Expected value is uncertain: it depends on how weak the fallback predicates are, which only a shadow run shows.
Proposed change
Two weaker predicates for strata that fail #562's flag:
- Subsequence fallback for strata with order-preserving but non-contiguous removal (infixation, reduplication on Indonesian and Amharic): prune when no root allomorph is a subsequence of the shape's segments.
- Insertion classes for restoring rules (Mbugwe
n-1,n-2; Aweti's 30 slot subrules): treat each restorable segment class as a wildcard gap, so a root may match with gaps wherever a rule in or below the stratum can insert that class.
Soundness
(1) holds when every rule is order-preserving: any shape looked up below the node is a subsequence of the node's shape (a contiguous run is a special case). (2) holds when the set of segments any remaining rule can insert is known statically; each such class is allowed at any position, so the prune fires only when the root cannot be matched even with those gaps. Rules whose inserted material cannot be bounded statically turn the flag off. Re-argued in XML docs and checked in shadow (zero violations).
Memory bound
Per-stratum flags and per-stratum sets of insertable segment classes: grammar-sized, bytes to KB. Uses the existing root tries. No cache.
Measurement plan
Shadow first, reusing #562's harness mode. Report per grammar the share of analysis events below fired nodes for each predicate (contiguous, subsequence, gapped), violations (must be 0), and trie or subsequence probes beside the savings. Stress fixture: the #562 fixture plus infix, reduplication and nasal-substitution strata.
Kill criterion
Any shadow violation: stop. Close if the net saving after removing the overlap with #561 is under 5% on every one of Mbugwe, Indonesian, Aweti and Amharic, or if probes exceed events saved.
Related
- HermitCrab analysis: prune on root substring at rule outputs, gated by restoration flags #562 (hard dependency), HermitCrab analysis: skip template partials whose required slot material is absent #561 (overlap on Mbugwe and Aweti), Analysis search is nogood-dominated on a template-heavy Bantu grammar; memoization yields ~6%, and the HasReachableRoot prune is absent from all refs #485 and HermitCrab: cull analysis candidates at emission by stratum+shape lexical lookup (memory on truncation-heavy grammars) #512 (related search and memory issues).
- PR HermitCrab optimization round record: what was tried, and a faster package that is not mergeable #490: research record, ledger row 27. PR Add a conformance suite for HermitCrab, with its adequacy argument #480: conformance suite (its nasal-substitution and restoration fixtures are the violation class); verdicts must be identical.
- Units: deterministic steps, never ms. Owner constraint: no memo or cache.
🤖 Generated with Claude Code
Activity