Yes, the entire dictionary is compared against each word. This can be fast by using a trie and an algorithm similar to Levenshtein's.
I have built my own spelling corrector that checks words against a dictionary of about 1 million words and 12.5 million word-pairs (for basic word usage checking). It takes about 0.7 milliseconds to check a single word and provide corrective suggestions based on these two dictionaries. I'm sure it could be significantly faster; I stopped optimizing once it became fast enough for my purposes, which was to check a few paragraphs in under 1 second.
Several of the other answers have hinted toward how spelling and grammar checkers/correctors work, but let's put all the pieces together and see how we could build our own fast spelling corrector.
Disclaimer: I don't know if this is how Microsoft and Google actually do it, but it works very well for my needs.
How to build a spelling corrector
I started from this excellent article by Peter Norvig. It's worth a read if you're serious about implementing your own spelling corrector, but the most important insight is the use of Bayes' Theorem to decompose the question into independent parts. Let's start by actually stating our goal.
Goal: given the user typed word $w$, find and rank the most likely possibilities for what the user actually meant to type, $c$ ("candidate"). In other words, for each $c$ in our list of 1 million candidates, we are looking for the probability that the user wanted to type each $c$ when they actually typed $w$. Norvig's insight is to use Bayes' theorem to turn this into manageable independent sub-problems:
$$
P(c|w) = \frac{P(c)P(w|c)}{P(w)}
$$
Where:
$P(c|w)$ = the probability the user meant $c$ when they actually typed $w$ (our goal)
$P(c)$ = the probability of typing $c$. This is simply a measure of the frequency of the candidate word in our language model. For example, in English, P("the") is larger than P("thaw").
$P(w|c)$ = The probability that the user would type $w$ when they meant $c$. This is our error model. For example, the probability the user would type "thew" when they meant "thaw" is probably higher than typing "thew" when they really meant "the".
$P(w)$ = The probability of typing $w$. We're simply not interested in any cases where $w$ was not typed, because we observe that it was. Therefore this value is basically 1 (or at least constant) for our purposes and we divide it out.
Since we're just trying to rank suggestions relative to each other, I'm not going to worry about making sure the probabilities actually add up to 1.
Levenshtein distance is an error model. We could say that that $P(w|c)$ = $Levenshtein(w,c)$ and we get a perfectly serviceable error model. It might even be the best we can do in some cases, e.g. if we're trying to reconstruct English text that was sent over a noisy line that caused essentially random insertion, deletion, and replacement errors. However, for a human typist, we can do better by taking into account common language-specific errors. For instance, accidentally replacing an "e" with an "a" is much more likely than with an "m". As gnasher729 pointed out, we could also take the user's keyboard layout into account.
Generating Candidate Words
Now we can get to the heart of your question: how do we generate candidates to check? Every word in our dictionary is a candidate! If we try to do this with a naïve brute-force approach, we can think of some obvious waste. For instance, we shouldn't need to fully evaluate the word "continuations" if we've already evaluated "continuation"; this hints that a Trie (or "prefix tree") might help us here. We also probably shouldn't be comparing the "s" in "continuations" against the "y" in "specificity"; surely we know by that point that neither is a good substitute for the other! This hints that we can significantly cull down our search for candidates if we keep track of compounding error while doing our search.
So our steps are:
Step 1. Organize your dictionary into a giant trie
Let's say our dictionary consists of the 12 words shown below. The corresponding trie is shown to the right. We also want to keep track of which nodes are word endings, which I've given a solid blue color:
Even with 1 million words, this data structure is only a few hundred megabytes and fits easily into memory. (The n-grams are the memory hogs!)
Step 2. Calculate compounding error while searching for suggestions
Let's say the user writes "saken", and we want to suggest corrections from this dictionary. We keep a list of 3-tuples containing the following information:
- Where we are in the word
- Where we are in the trie
- The total compounded error so far
This list starts with one entry: (first letter, root of trie, 0), as shown below.
Until we have an empty list, we loop over every element in the list. If it's a valid word (that is, the trie pointer is pointing to a node marked "end-of-word"), we return it as a possible suggestion, along with its error. Then (valid word or not) we remove it from our list and use it as a new seed to continue to populate the list.
Given a starting 3-tuple as a seed, we add new elements to the list differently for each type of error (insertion, deletion, and substitution). For instance, when checking for substitution errors, we add an element for every child of our current trie node, with additional error based on the letters being substituted (taking into account surrounding letters as well). This is illustrated below for the "a" node, but we do the same for every other child. Of course, substituting "s" for "s" gets an error value of 0.
We always have a single possible insertion error, which is the letter we're currently on. In that case, the word-pointer moves forward, but the trie-pointer stays where it is. Deletions are the opposite: the word-pointer stays where it is, while the trie-pointer moves forward (to every child).
Here's an example traversal with mixed errors. Here we are considering the possibility that the user accidentally typed "s" instead of "t", then correctly typed "a", then accidentally inserted a "k", then accidentally type "e" when they meant to type "k". In reality, only the last row would be left in our list, but the others are left for illustration.
If we're using a simple Levenshtein distance error model, then our total error so far is 3.
Of course it's more likely that the user actually did mean "ke" at this point, but our job right now is to simply enumerate and score all the possible ways $w$ could have been typed instead of $c$.
Step 3. Stop traversing your trie if the error gets too large
Now that we're calculating errors as we're generating suggestions, we can simply refuse to add a new 3-tuple to our list if the total error is too high (notice the error never decreases). That culls entire branches of the trie from future traversal and keeps our search narrowly focused.
In fact a rather small limit works well here if errors are reasonably independently distributed (an example where they're not is keyboard off-by-one errors like gnasher729 demonstrated, but you could make a custom error type with its own traversal logic for this). If I have a 5% chance of making a single typo in a 6-letter word, I probably have about a (5%)^2 = 0.25% chance of making two typos in that same word. Therefore an error limit of about 3 is good enough in practice (with Levenshtein distance; obviously this depends on your error model), and significantly reduces your search space.
Another way you can cull your search is by only ever considering the shortest path (error-wise) to a given suggestion. If you implement this, you'll find you get lots of cases where the same word is being suggested via many different paths, and you really only need to keep one as your next seed.
Once you have your list of suggestions, you already have $P(w|c)$ calculated for each, so you simply need to look up $P(w)$ and you're done! In my implementation, this all happens in about 0.7 milliseconds (700 microseconds) per word, including an additional step where I account for the frequency of the word appearing next to its neighbors. There are lots of parameters you can tune to your needs, and probably lots of other ways to make this faster.
