Wolf, thank you for these additional points. I agree that Peter Norvig’s post, while very educational, is a starting point to learn about spelling correction but hardly an end point — either in terms of performance or applicability to non-alphabetic languages.

And I’ve always been intrigued by symmetric deletion, which I’ve used in offline analysis but never seen it used in a production setting. It does seem a bit limited by design, but it’s hard to argue with the raw speed.

As for combining spelling correction with autocomplete, I agree that they should work together. I’ve seen several approaches to combine them, including Solr’s use of weighted FSTs. But yes, the goal here is a shared one: help users express their intent in a way that the search engine understands it.