Re:SymSpell: 1M times faster spelling correction
by cb321 on Sunday March 06, 2022 @02:21PM
(#30580279)
You are absolutely right to be suspicious. https://news.ycombinator.com/item?id=30580011
The TL;DR is that on a "worst case" basis, it may be 10x faster or even 10x slower than a non-indexed linear scan depending upon latency of backing stores. Physical memories in computers are pretty big these days, but this technique would have been a total non-starter just 10 years before the 2007 article by Norvig. Meanwhile its linear scan competitor would have worked fine. It is also not a great approach if you have a big dictionary of long words and want truly large edit distances (>>5, say). I would say "mid-size edit distances of 2-4" are SymSpell's sweet spot.
How about comparing it to. Levenshtein automaton or another state of the art approach?