[
https://issues.apache.org/jira/browse/OPENNLP-1906?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Martin Wiesner reopened OPENNLP-1906:
-------------------------------------
> Sentence detector abbreviation veto is quadratic in document length
> -------------------------------------------------------------------
>
> Key: OPENNLP-1906
> URL: https://issues.apache.org/jira/browse/OPENNLP-1906
> Project: OpenNLP
> Issue Type: Bug
> Reporter: Kristian Rickert
> Assignee: Kristian Rickert
> Priority: Major
> Fix For: 3.0.0-M6
>
> Time Spent: 1h 10m
> Remaining Estimate: 0h
>
> h2. Summary
> {{SentenceDetectorME.isAcceptableBreak}} is quadratic in document length
> whenever an
> abbreviation dictionary is configured. Measured at 8.2 seconds for a single
> {{sentPosDetect}} on a 400 KB document with a 200-entry dictionary, against
> 6.8 ms
> after the fix.
> h2. Why this has never been reported
> The expensive path is *gated on a dictionary being configured, and no
> published
> sentence model ships one*. With stock models the branch is never entered,
> which is the
> {{noDictionary}} column below at roughly 0.9 ms per 100 KB.
> The absence of reports is therefore evidence of the gate, not of low impact.
> Supplying
> a dictionary is the first thing a serious user does, and they then hit the
> quadratic
> behaviour at full force on their largest documents.
> Supporting data from a downstream user, offered as their measurement rather
> than one
> taken here: a 222-entry corpus-derived abbreviation list moved
> sentence-detector
> failures among short chunks from 44.5% to 0.0% on legal prose. So doing the
> right thing
> is what triggers the pathology.
> One half of the gate *was* verified directly here: all 25 shipped
> {{abb_*.xml}}
> dictionaries declare {{case_sensitive="false"}}, so the whole-document
> lower-casing
> described below was always active for anyone using one.
> h2. The accept condition, and why the old code was quadratic
> {{isAcceptableBreak(s, fromIndex, candidateIndex)}} vetoes if any dictionary
> entry of
> length {{L}} occurs at a position {{p}} with {{fromIndex <= p <=
> candidateIndex}} such
> that either
> * *A:* {{p == fromIndex}} and {{p + L == candidateIndex + 1}}, or
> * *B:* {{p + L >= candidateIndex}} and the character at {{(p == fromIndex ? p
> : p - 1)}}
> is whitespace, an apostrophe ({{'}} {{`}} {{´}}) or {{(}}.
> Both clauses require {{p + L >= candidateIndex}}. So the only positions that
> can matter
> are {{max(fromIndex, candidateIndex - L) <= p <= candidateIndex}}, at most
> {{L + 1}} of
> them. The old implementation did not exploit that: per candidate it ran
> {{searchText.indexOf(entry, fromIndex)}} for every entry, and {{indexOf}} on
> an absent
> entry, which is the overwhelming case, scans to end of document before
> returning -1.
> Cost is candidates x entries x document length.
> Two additional amplifiers, neither previously noted:
> * It called {{s.toString()}} *and* {{StringUtil.toLowerCase(text)}} over the
> whole
> document on *every* call, before the entry loop. A non-null but *empty*
> dictionary was
> therefore enough to make sentence detection quadratic.
> * Combined with all 25 shipped dictionaries being case-insensitive, that
> whole-document
> fold was always live in practice.
> h2. The fix
> The dictionary is read once at construction into an immutable veto structure
> (folded
> entry set, sorted distinct entry lengths, max length). {{isAcceptableBreak}}
> enumerates
> the bounded window per distinct entry length and does a hash-set lookup,
> folding only
> the window.
> Window folding is code-point-wise, matching {{StringUtil.toLowerCase}}, with
> window
> bounds snapped off surrogate-pair halves so the folded characters are
> byte-identical to
> a slice of the whole-text fold. {{Character.toLowerCase(int)}} was verified
> to preserve
> {{charCount}} for all 1,114,112 code points, which is what makes the original
> index-alignment assumption valid in the first place.
> Snapshotting the dictionary at construction matches what
> {{SentenceDetectorFactory.getSDContextGenerator()}} already does, and the
> class is
> {{@ThreadSafe}}, so mutating a live dictionary was never safe.
> h2. Measurements
> JMH, Linux, JDK 25 GraalVM CE, 8 pinned cores of a 32-core box, 2 forks x 10
> iterations
> x 3 s. One op is one {{sentPosDetect}}. Milliseconds per op.
> || entries || chars || noDictionary || legacy || bounded window ||
> | 10 | 12,500 | 0.120 | 5.045 | 0.163 |
> | 10 | 100,000 | 0.902 | 278.811 | 1.263 |
> | 200 | 12,500 | 0.114 | 10.582 | 0.212 |
> | 200 | 50,000 | 0.453 | 145.631 | 0.821 |
> | 200 | 100,000 | 0.930 | 546.487 | 1.611 |
> | 200 | 200,000 | | 2,066.219 | 3.513 |
> | 200 | 400,000 | | 8,221.748 | 6.800 |
> Growth per doubling of input: legacy *3.68x to 3.98x* (quadratic), bounded
> window
> *1.88x to 2.09x*, no-dictionary floor *1.89x to 2.06x*. The fix tracks the
> floor.
> The benchmark document is deliberately EOS-dense (five short sentences per
> ~280
> characters), since candidate count is the first factor of the cost product.
> h2. Equivalence
> The pre-fix algorithm is retained verbatim as
> {{LegacyAbbreviationSentenceDetectorME}}
> and used as an oracle.
> *1,933,465* {{(fromIndex, candidateIndex)}} decisions compared across the
> full contract
> domain of every fixture text: *zero in-contract disagreements*.
> Edge cases each carry a guard asserting the oracle actually vetoes, so no
> case can pass
> vacuously: abbreviation at document start, at document end, reaching past the
> end;
> overlapping candidates ({{U.S.S.R.}}, {{...}}); empty dictionary; null
> dictionary; entry
> absent from text; entry longer than the text; multi-character and Unicode
> entries;
> supplementary code points and unpaired surrogates in both text and
> dictionary; repeated
> abbreviations; case-insensitive dictionary including {{İ}} versus {{i̇}};
> empty-string
> entry (which really can veto, pinned separately); multi-token entries;
> apostrophe,
> backtick, acute and {{(}} prefixes; segment start inside an abbreviation.
> Plus 250 seeded random texts across 3 dictionaries, and
> whole-{{sentPosDetect}} runs
> over a ~25 KB corpus asserting identical {{Span[]}} *and* identical
> {{probs()}} for the
> shipped EN and DE dictionaries and a case-sensitive dictionary.
> A no-dictionary equivalence test is included specifically because that is the
> path every
> current user is on, and the one most at risk from an optimization aimed at the
> dictionary path. It asserts identical spans, identical probs, and a veto
> count of
> exactly 0.
> h2. Behaviour changes, all outside the documented contract
> # {{candidateIndex}} not an index into {{s}}: the old code threw
> {{IndexOutOfBoundsException}} from {{substring(p, candidateIndex + 1)}}; the
> new code
> accepts the break. Pinned and documented in the method javadoc.
> # Negative {{fromIndex}}: both still throw when a match sits at index 0. When
> the only
> match is too far left to be relevant, the old code read {{charAt(-1)}} and
> threw, while
> the new code returns a decision. Pinned.
> # Mutating the {{Dictionary}} after constructing the detector no longer
> affects it.
> Documented in the constructor javadoc.
> Item 3 is the one a reviewer could reasonably want changed. It can be
> reverted to a
> per-call read at the cost of building a {{HashSet}} per candidate, which is
> still linear.
> h2. Test fixture note
> The shipped {{Sentences.txt}} and {{Sentences_DE.txt}} contain almost none of
> the EN
> dictionary's entries, so a corpus equivalence test over them would have been
> vacuous.
> The veto-count guard caught this; abbreviation-bearing sentences were added
> to the
> corpus rather than lowering the assertion.
> h2. Build
> Full project {{./mvnw -o clean test}}: *3,410 tests, 0 failures, 0 errors, 2
> skipped,
> 23 of 23 modules SUCCESS*, with checkstyle, forbiddenapis and rat enabled.
> {{opennlp-runtime}} alone: 1,646 tests green. The new equivalence test is 22
> tests in
> about 5 seconds (two model trainings plus the oracle sweep); if that is
> judged too slow
> for {{mvn test}}, the seeded sweep size is a single constant.
> h2. Files
> {{opennlp-core/opennlp-runtime/src/main/java/opennlp/tools/sentdetect/SentenceDetectorME.java}},
> {{BENCHMARKS.md}},
> {{src/jmh/java/opennlp/tools/sentdetect/SentenceDetectorMEAbbreviationBenchmark.java}},
> {{src/test/java/opennlp/tools/sentdetect/SentenceDetectorMEAbbreviationEquivalenceTest.java}},
> {{src/test/java/opennlp/tools/sentdetect/LegacyAbbreviationSentenceDetectorME.java}}.
> ----
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
