4 ms·

While doing a bunch of research on exactly this problem space recently for a project, I stumbled onto this improvement on the Norvig corrector idea http://blog.

While doing a bunch of research on exactly this problem space recently for a project, I stumbled onto this improvement on the Norvig corrector idea http://blog.faroo.com/2012/06/07/improved-edit-distance-based-spelling-correction/ http://blog.faroo.com/2012/06/07/improved-edit-distance-base... that's one of those things that's so deceptively simple you kick yourself for not thinking of it: it turns out you can model the same "generate all the variations" effect but generating only the deletes, rather than also the insertions and substitutions, if you symmetrically apply the same transformation to the lookup side. So if your dictionary contains "cat" and you want to match queries for "cast," rather than adding "cast" to the corpus, you drop the s (and every other single letter) on the lookup side instead, and still match. Turns out it's much faster and, requires a much smaller index, and as a bonus, doesn't tie you to a specific alphabet like Norvig's approach does.

nmstoker 8y ago
The latest version of SymSpell (by the author of that blog post) handles compound words too, so it's pretty capable along with speed. https://github.com/wolfgarbe/SymSpellCompound/blob/master/README.md https://github.com/wolfgarbe/SymSpellCompound/blob/master/RE... I'm certainly not knocking that achievement, but the two issues I ran into fairly quickly were: 1. It (currently) doesn't handle words that are genuine words but which are contextually wrong 2. You need a high quality dictionary that's also well aligned with your domain or you'll have poor corrections (this last point is merely a matter of effort, so less of a concern)
wolfgarbe 8y ago
Here is the link to the SymSpell Github repository: https://github.com/wolfgarbe/SymSpell https://github.com/wolfgarbe/SymSpell An here a benchmark between Norvig's spelling corrector, BK-tree and SymSpell: https://towardsdatascience.com/symspell-vs-bk-tree-100x-faster-fuzzy-string-search-spell-checking-c4f10d80a078 https://towardsdatascience.com/symspell-vs-bk-tree-100x-fast...
- apendleton 8y ago
  Ah should have shared the repo, and thanks for publishing it! We're experimenting now with adapting this idea but using a directed acyclic FSA to store the index-time variations instead of a hashtable like in your version, with the idea that we might be able to search for all of the query-time variations in a single pass rather than one at a time (as for obvious reasons they'll be textually similar to one another so there should be some shared work between the lookups).

nmstoker 8y ago

The latest version of SymSpell (by the author of that blog post) handles compound words too, so it's pretty capable along with speed. https://github.com/wolfgarbe/SymSpellCompound/blob/master/README.md https://github.com/wolfgarbe/SymSpellCompound/blob/master/RE... I'm certainly not knocking that achievement, but the two issues I ran into fairly quickly were: 1. It (currently) doesn't handle words that are genuine words but which are contextually wrong 2. You need a high quality dictionary that's also well aligned with your domain or you'll have poor corrections (this last point is merely a matter of effort, so less of a concern)

wolfgarbe 8y ago

Here is the link to the SymSpell Github repository: https://github.com/wolfgarbe/SymSpell https://github.com/wolfgarbe/SymSpell An here a benchmark between Norvig's spelling corrector, BK-tree and SymSpell: https://towardsdatascience.com/symspell-vs-bk-tree-100x-faster-fuzzy-string-search-spell-checking-c4f10d80a078 https://towardsdatascience.com/symspell-vs-bk-tree-100x-fast...

apendleton 8y ago
Ah should have shared the repo, and thanks for publishing it! We're experimenting now with adapting this idea but using a directed acyclic FSA to store the index-time variations instead of a hashtable like in your version, with the idea that we might be able to search for all of the query-time variations in a single pass rather than one at a time (as for obvious reasons they'll be textually similar to one another so there should be some shared work between the lookups).