Also, a hashtable has the requirement that word
boundaries are identified separately, while a trie does not require this.
That makes the mechanism a lot simpler.

Soundfolding is useful when someone knows how the words sounds but doesn't
know how it is spelled.  For example, the word "dictionary" might be written
as "daktonerie".  The number of changes that the first method would need to
try is very big, it's hard to find the good word that way.  After soundfolding
the words become "tktnr" and "tkxnry", these differ by only two letters.

To find words by their soundfolded equivalent (soundalike word) we need a list
of all soundfolded words.  A few experiments have been done to find out what
the best method is.  Alternatives:
1. Do the sound folding on the fly when looking for suggestions.  This means
   walking through the trie of good words, soundfolding each word and
   checking how different it is from the bad word.  This is very efficient for
   memory use, but takes a long time.  On a fast PC it takes a couple of
   seconds for English, which can be acceptable for interactive use.  But for
   some languages it takes more than ten seconds (e.g., German, Catalan),
   which is unacceptable slow.  For batch processing (automatic corrections)
   it's too slow for all languages.
2. Use a trie for the soundfolded words, so that searching can be done just
   like how it works without soundfolding.  This requires remembering a list
   of good words for each soundfolded word.  This makes finding matches very
   fast but requires quite a lot of memory, in the order of 1 to 10 Mbyte.
   For some languages more than the original word list.
3. Like the second alternative, but reduce the amount of memory by using affix
   compression and store only the soundfolded basic word.  This is what Aspell
   does.  Disadvantage is that affixes need to be stripped from the bad word
   before soundfolding it, which means that mistakes at the start and/or end
   of the word will cause the mechanism to fail.  Also, this becomes slow when
   the bad word is quite different from the good word.

The choice made is to use the second mechanism and use a separate file.  This
way a user with sufficient memory can get very good suggestions while a user
who is short of memory or just wants the spell checking and no suggestions
doesn't use so much memory.


Word frequency

For sorting suggestions it helps to know which words are common.  In theory we
could store a word frequency with the word in the dictionary.  However, this
requires storing a count per word.  That degrades word tree compression a lot.
And maintaining the word frequency for all languages will be a heavy task.
Also, it would be nice to prefer words that are already in the text.  This way
the words that appear in the specific text are preferred for suggestions.

What has been implemented is to count words that have been seen during
displaying.  A hashtable is used to quickly find the word count.  The count is
initialized from words listed in COMMON items in the affix file, so that it
also works when starting a new file.

This isn't ideal, because the longer Vim is running the higher the counts
become.  But in practice it is a noticeable improvement over not using the word
count.

 vim:tw=78:sw=4:ts=8:noet:ft=help:norl: