Kristian Rickert created OPENNLP-1906:
-----------------------------------------
Summary: 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
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)
