HermitCrab: copy-agreement prune keeps matches with an empty copy, re-running the whole search

Aperta
  • Qualcosa non va?
#634 1 commento 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
4/5
Tempo stimato
3-5 giorni
Idoneità per principianti
55/100
Tipo di issue
Bug
Chiarezza
Specificata chiaramente
Stato di attività
Attiva
Stack tecnologico
csharp
Ambito
backend, performance

Direzione di ricerca

Start with AnalysisMorphologicalTransform.cs:91-93 and read GroupCapture.cs:15 to understand how empty captures are represented; then inspect the related matcher behavior in Matcher.cs:184-195. Add the proposed empty-copy handling and a trace-count regression test, checking that non-reduplicated words return to the no-rule baseline and the six probe words parse identically. The issue notes the test suites have not yet been run against this change.

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

Descrizione

Hermit Crab performance

The copy-agreement prune from #519 keeps a match in which one copy of a part is non-empty and another copy of the same part is empty, so every word gets a spurious whole-word candidate at each point of the unapplication search, and the whole remaining search runs again under it. Parses are unchanged; synthesis rejects the candidate. This is an efficiency defect, not a correctness one.

This is the shape FieldWorks exports for full reduplication, X => X X: a single zero-or-more variable part (minimum 0) copied twice. When the capture of the first copy is the whole word, the second capture is empty. An empty group becomes Range.Null, GroupCapture.Success is false, TryGetSegmentCopies returns false, and HasDisagreeingCopies does not report a disagreement, so the match is kept.

Measured on a synthetic grammar (39 non-reduplicated words, prune on):

C# trace count no reduplication rule rule with min 1 rule with min 0
rule unapplications 40 40 172
lexical lookups 79 79 211
word syntheses 43 43 128

Treating an empty capture as a zero-length copy returns all three counts to the no-rule baseline, and the six reduplication probe words parse identically. A real-grammar port of the same behaviour (PanGloss) pays about +84% parser work on a 4,279-word set from the same cause.

Proposed fix: in TryGetSegmentCopies, treat !capture.Success as a zero-length copy rather than "undecidable". Soundness: synthesis writes every copy from one input, so a non-empty copy cannot equal an empty one, unless the non-empty copy consists only of optional segments (the existing alignment already lets such a copy line up with nothing). Refuse the match otherwise.

Secondary point: every one of the n-1 splits of a shape is still enumerated before the Acceptable predicate runs, so the cost is quadratic in word length even when nothing leaks.

Next: a fix PR against this issue with a trace-count regression test; the PanGloss side is tracked separately and will link here.

Where it happens (source)
  • AnalysisMorphologicalTransform.cs:91-93: TryGetSegmentCopies returns false when !capture.Success; HasDisagreeingCopies (:69-72) then does not report disagreement, so the match is kept.
  • Matcher.cs:184-195: CreatePatternMatch turns an empty group range into Range.Null.
  • GroupCapture.cs:15: Success is Range != Range.Null.
  • FieldWorks side: HCLoader.cs:1389-1394 maps a phonological variable input part to new Pattern(i, AnyStar()); AnyStar (HCLoader.cs:2356-2359) is a quantifier with minimum 0 and no maximum. A repro with minimum 1 hides the leak.
  • The enumeration of all n-1 splits: AllSubmatches (Matcher.cs:313); Acceptable runs only at an accepting state (TraversalMethodBase.cs:166), after the whole path was walked.
Repro (synthetic grammar and words)

Master at 74ee09bf (3.9.6, contains #519), prune on (the default, Morpher.cs:60). Load a HermitCrabInput XML grammar with the XML language loader, parse the word list with a trace attached, and count rule unapplications, lexical lookups and word syntheses.

Grammar: one stratum, one part of speech V, ten segments p t k s m n l a i u each with a unique place value (so nothing unifies by accident), natural classes Any (no constraints), C (cons +), V (voc +). Fourteen stems, all V: salum patik nusak tilam sakin munat kalip patikus nusakil tilamas sakinun patikusal nusakilun tilamasip; only patik and salum carry the rule feature REDSYN. Two plain suffix rules (-an, -un) with input (Any){1,-1}, copy then insert the suffix. The reduplication rule:

<MorphologicalRule id="mrRedup" requiredPartsOfSpeech="posV" outputPartOfSpeech="posV"><Name>redup</Name>
 <MorphologicalSubrules><MorphologicalSubrule id="mrRedups">
  <MorphologicalInput requiredMPRFeatures="mprRedsyn">
   <PhoneticSequence id="rp"><OptionalSegmentSequence min="0" max="-1"><SimpleContext naturalClass="ncAny"/></OptionalSegmentSequence></PhoneticSequence>
  </MorphologicalInput>
  <MorphologicalOutput><CopyFromInput index="rp"/><CopyFromInput index="rp"/></MorphologicalOutput>
 </MorphologicalSubrule></MorphologicalSubrules><MorphemeId>REDUP</MorphemeId></MorphologicalRule>

Change min="0" to min="1" to see the control row. Words (45):

salum patik nusak tilam sakin munat kalip patikus nusakil tilamas sakinun patikusal nusakilun tilamasip
saluman patikan nusakan tilaman sakinan munatan kalipan patikusan nusakilan tilamasan sakinunan patikusalan nusakilunan tilamasipan
kalipanun patikusanun nusakilanun tilamasanun sakinunanun patikusalanun nusakilunanun tilamasipanun salumanun patikanun nusakanun
patikpatik patikpatikan nusaknusak salumsalm salumsalum salumsalumanun

The first 39 are non-reduplicated (the trace counts above); the last six are reduplication probes. Expected for patik: zero reduplication-rule unapplications (a non-empty copy cannot equal an empty one). Observed: one, and the full remaining search runs under it.

Method and limits

Tracing disables MergeEquivalentAnalyses (AnalysisStratumRule.cs:131), so trace counts are comparable only within one table. The fix was tried in a scratch copy only: with it, the six probes parse identically (1,1,0,0,1,1), and with an additional deletion rule also identically (1,1,0,1,0,0). Elapsed time per pass of the word list went 129.6 to 106.8 ms (noisy, loaded machine; the remaining gap is the split enumeration). The scratch change was not run against the SIL.Machine test suite or the conformance suite. No existing issue or comment in this repository covers the empty-copy case (searched #519, #599 to #611).

Lingua principale
C#
Stelle
29
Fork
16
Merge medio
4g 11h
PR unite (30g)
14

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.