[jira] [Resolved] (OPENNLP-1832) Add SymSpell-based spell correction component

["Martin Wiesner (Jira)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/OPENNLP-1832?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Martin Wiesner resolved OPENNLP-1832.
-------------------------------------
    Resolution: Delivered

> 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
>            Assignee: Richard Zowalla
>            Priority: Major
>             Fix For: 3.0.0-M4, 3.0.0
>
>          Time Spent: 2h
>  Remaining Estimate: 0h
>
> 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)