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

Offen
  • Stimmt etwas nicht?
#634 1 Kommentar 0 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen

Maintainer antworten meist innerhalb von 1 Tag

Dieses Issue hat noch niemand übernommen.

Bewertung

Schwierigkeit
4/5
Geschätzter Aufwand
3-5 Tage
Anfängerfreundlichkeit
55/100
Issue-Typ
Bug
Klarheit
Klar beschrieben
Aktivitätsstatus
Aktiv
Tech-Stack
csharp
Bereich
backend, performance

Rechercherichtung

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.

Vom Indexierungsmodell aus dem Issue-Text verfasst.

Beschreibung

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).

Vorherrschende Sprache
C#
Sterne
29
Forks
16
Ø Merge
4 T. 11 Std.
Gemergte PRs (30 T.)
14

Entwicklungsumgebung

  • Kein Dockerfile und keine Docker-Compose-Datei
  • Hat eine Pull-Request-Vorlage
  • Kein Beitragsleitfaden

Erste Schritte

  1. Lesen Sie das ganze Issue und danach den Beitragsleitfaden des Projekts.
  2. Schreiben Sie ins Issue, dass Sie es übernehmen — das erspart doppelte Arbeit.
  3. Forken Sie das Repository und arbeiten Sie in einem Branch.
  4. Öffnen Sie einen Pull Request, der die Issue-Nummer nennt.

Mehr aus sillsdev/machine

Alle Issues in sillsdev/machine

Ähnliche Issues

Weitere Issues zu C#

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.