HermitCrab: affix-process matching enumerates every choice over runs of optional segments

Đang mở
  • Có gì không ổn?
#635 2 bình luận 0 reaction 0 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 1 ngày

Chưa có ai nhận issue này.

Đánh giá

Độ khó
4/5
Thời gian dự kiến
3-5 ngày
Mức phù hợp với người mới
51/100
Loại issue
Lỗi
Độ rõ ràng
Đặc tả rõ ràng
Mức độ hoạt động
Sôi nổi
Công nghệ
csharp
Lĩnh vực
performance

Hướng nghiên cứu

Start with NarrowAnalysisRewriteRuleSpec.cs:87 to see how unapplying deletion rules creates optional nodes, then trace the affix-process pattern traversal that enumerates choices. Prototype feasibility pruning or canonical choices for equivalent optional nodes and measure it on the toy grammar. Done means the candidate paths shrink while all parses remain identical.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

Hermit Crab performance

Matching an affix-process analysis pattern against a shape that contains long runs of optional segments enumerates every choice of nodes from those runs, with no feasibility check and no merging of equivalent choices, so a handful of distinct outputs can cost hundreds of times the work of the same grammar without the rule. Results are correct; this is efficiency only.

Mechanism: unapplying a deletion rule with several subrules restores each deleted segment as an optional node (NarrowAnalysisRewriteRuleSpec.cs:87), and every subrule sees the earlier insertions. With DeletionReapplications at 0 the optional runs still grow, 2, 6, 14, 30 optional nodes per run in the toy grammar below. A pattern such as C V V C V V (the shape CVV copied twice) then picks its vowel slots out of those runs: the traversal spawns a skip instance for every optional annotation, and instances differ by registers so they never merge. The restored nodes carry no place features, so almost any choice unifies. On a run of 15 and a run of 31 that is about C(15,2) x C(31,2) = 48,825 candidate paths for a few distinct outputs.

Toy grammar, same rule, three shapes (C# elapsed time against the grammar without the rule): CVV 3.8x, CVCV 16x, CVCCV 353x. Cost depends on shape, not only length: shapes with consonant slots die early on the vowel-only runs.

On a real FieldWorks Cebuano project, one word (Pintahag) went from 35.7M to 217.8M parser work steps in a port of this algorithm (6x) for 59 outputs; about 99% of the rise is inside the CVV allomorph's own matching.

Proposed directions, either of which should leave every parse unchanged: (a) feasibility pruning in the traversal, so that before spawning a skip instance the remaining required nodes must still fit the remaining pattern slots; (b) one canonical choice per run of value-identical optional nodes, since interchangeable optional nodes give the same output.

Next: a prototype of (a) or (b) measured on the toy grammar, with identical outputs required; the PanGloss side is tracked separately and will link here.

Repro (synthetic toy grammar and word)

Master at 74ee09bf. Grammar: segments p t k s h n q l g a i u plus an archi-nasal N with only a place value; q has no voc value; natural classes C (cons +) and V (voc +). Stems Nt tuu piNtqa piNtaha tahaa kapa hapa tipa pitaq. One phonological rule, simultaneous, input V (voc +), output empty, with four subrules, each C _ C:

<PhonologicalRule id="prSync" multipleApplicationOrder="simultaneous"><Name>syncope</Name>
 <PhoneticInput><PhoneticSequence><SimpleContext naturalClass="ncV"/></PhoneticSequence></PhoneticInput>
 <PhonologicalSubrules>
  <PhonologicalSubrule><PhoneticOutput><PhoneticSequence/></PhoneticOutput><Environment>
   <LeftEnvironment><PhoneticTemplate><PhoneticSequence><SimpleContext naturalClass="ncC"/></PhoneticSequence></PhoneticTemplate></LeftEnvironment>
   <RightEnvironment><PhoneticTemplate><PhoneticSequence><SimpleContext naturalClass="ncC"/></PhoneticSequence></PhoneticTemplate></RightEnvironment>
  </Environment></PhonologicalSubrule>
  <!-- the same subrule three more times -->
 </PhonologicalSubrules></PhonologicalRule>

Three same-category reduplication rules (N, V, A), each with one subrule whose input is the shape as separate single-class parts and whose output is the parts copied twice. For shape CVV:

<MorphologicalInput>
 <PhoneticSequence id="r0"><SimpleContext naturalClass="ncC"/></PhoneticSequence>
 <PhoneticSequence id="r1"><SimpleContext naturalClass="ncV"/></PhoneticSequence>
 <PhoneticSequence id="r2"><SimpleContext naturalClass="ncV"/></PhoneticSequence>
</MorphologicalInput>
<MorphologicalOutput><CopyFromInput index="r0"/><CopyFromInput index="r1"/><CopyFromInput index="r2"/><CopyFromInput index="r0"/><CopyFromInput index="r1"/><CopyFromInput index="r2"/></MorphologicalOutput>

Also a suffix rule -hag and a prefix rule pa- (input (Any){1,-1}) so the word is analysed through the phonological rule first. Word: piNtqa. Compare the grammar with no reduplication rule against the same grammar with the CVV, CVCV and CVCCV shapes in turn. Observed optional nodes per phonological unapplication: 2, 6, 14, 30, then a plateau.

Numbers and limits
  • C# toy, elapsed per pass: none 11.4 ms; CVV 42.9 ms (3.8x); CVCV 179 ms (16x); CVCCV 4,028 ms (353x). These are elapsed times, untraced, on a loaded machine; read them as an ordering.
  • The same toy in a port of the algorithm, parser work: none 9,821; CVV 36,494 (3.7x); CVCV 484,006 (49x); CVCCV 5,848,882 (595x).
  • Real grammar, port only (the C# loader for FieldWorks projects needs the FieldWorks stack, so C# was not run on the real grammar): before 35,722,913 work steps, after 217.8M, 162.0M of it in the three CVV allomorph rows (about 560k steps per call, about 31 input nodes). Stacking is bounded at one application per rule (MaxApplicationCount 1), so the three rows are the three possible levels.
  • Dropping the CVV allomorph is not an option on the real grammar: four attested words have no reading without it.
  • The copy-agreement prune does not help here: it runs after the enumeration, and single-node optional vowel captures align under the existing alignment. Related: #519, and the empty-copy leak filed separately.
  • The CVV model of the path count is an inference (a simulation), not a trace; the elapsed ordering is observed.
Ngôn ngữ chính
C#
Star
29
Fork
16
Merge trung bình
4 ngày 11 giờ
Pull request đã merge (30 ngày)
14

Chuẩn bị môi trường

  • Không có Dockerfile hay tệp Docker Compose
  • Có mẫu pull request
  • Không có hướng dẫn đóng góp

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của sillsdev/machine

Tất cả issue của sillsdev/machine

Issue tương tự

Thêm issue về C#

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.