[
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)
