This seems very suspicious to me. They’re comparing performance to a tutorial blog post that is extremely inefficient.
How about comparing it to. Levenshtein automaton or another state of the art approach?
How about comparing it to. Levenshtein automaton or another state of the art approach?
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.