Hacktoberfest 2026: le issue che i maintainer hanno segnato per ottobre, aperte e adatte ai principianti. Sfoglia le issue Hacktoberfest

HermitCrab analysis: subsequence fallback and insertion classes for the root prune (v2)

Aperta
  • Qualcosa non va?
#568 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
5/5
Tempo stimato
Più di una settimana
Idoneità per principianti
25/100
Tipo di issue
Funzionalità
Chiarezza
Specificata chiaramente
Stato di attività
Attiva
Stack tecnologico
csharp
Ambito
search

Direzione di ricerca

Read #562 and its shadow harness first, then inspect the root tries and the strata rules that determine infixation, reduplication, and inserted segment classes. Run the proposed shadow measurements across Mbugwe, Indonesian, Aweti, and Amharic, including the #562 stress fixture plus the stated rule cases. Done means zero violations, identical verdicts to PR #480’s conformance suite, and savings and probe counts meeting the kill criteria.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

enhancement Hermit Crab

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:

  1. 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.
  2. 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

  • #562 (hard dependency), #561 (overlap on Mbugwe and Aweti), #485 and #512 (related search and memory issues).
  • PR #490: research record, ledger row 27. PR #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

Lingua principale
C#
Stelle
29
Fork
16
Merge medio
6g 13h
PR unite (30g)
12

Preparare l'ambiente

  • Nessun Dockerfile né file Docker Compose
  • Ha un modello di pull request
  • Nessuna guida per i contributori

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di sillsdev/machine

Tutte le issue di sillsdev/machine

Issue simili

Altre issue su C#

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.