Richard Zowalla created OPENNLP-1832:
----------------------------------------
Summary: Add SymSpell-based spell correction component
Key: OPENNLP-1832
URL: https://issues.apache.org/jira/browse/OPENNLP-1832
Project: OpenNLP
Issue Type: New Feature
Reporter: Richard Zowalla
h3. Summary
OpenNLP currently lacks a first-class spell correction component. This issue
proposes adding a {{SpellChecker}} API backed by the *SymSpell* (Symmetric
Delete) algorithm by Wolf Garbe, which offers up to 1,000,000× faster lookups
than naive Norvig-style edit-distance enumeration while staying
memory-reasonable for typical NLP dictionaries.
h3. Motivation
Spell correction is a frequent preprocessing step for downstream OpenNLP
components (tokenization, NER, doc-cat, language detection on noisy
user-generated text). Today users have to wire in an external library
(LanguageTool, JamSpell, custom Lucene {{{}SpellChecker{}}}) or roll their own.
Bringing a native, well-tested, language-agnostic implementation into OpenNLP
would:
* Close a long-standing feature gap relative to spaCy / Stanza ecosystems.
* Provide a reusable building block for future components (e.g., normalization
filters, query correction in {{opennlp-tools}} CLI).
* Be trainable from the same corpora/dictionaries already produced by OpenNLP
training pipelines.
h3. Why SymSpell (and not BK-tree / Norvig / Levenshtein automaton)
||Approach||Lookup complexity||Notes||
|Norvig (1-edit enumeration)|O(n · alphabet · length)|Slow on long words / edit
distance > 2|
|BK-tree|O(log N) average, worse at high ED|Tree traversal overhead|
|Levenshtein automaton|Fast, complex to implement|Harder to maintain|
|*SymSpell*|*~O(1)* average|Precomputed delete dictionary; symmetric deletes on
query + dict|
SymSpell precomputes deletes (only deletes, not all edits) from the dictionary
at index time, and at query time generates deletes from the input term and
intersects. Edits up to distance _k_ are reduced to hash lookups.
Reference: [https://github.com/wolfgarbe/SymSpell]
Algorithm description:
[https://wolfgarbe.medium.com/1000x-faster-spelling-correction-algorithm-2012-8701fcd87a5f]
License is *MIT* for the reference implementation compatible with
porting/re-implementing in ASLv2.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
