spell

[Doug McIlroy]

>I've bee wondering what the program "spell" does...

>All these words [utomsrr ...] are caught as misspelled by the HP-UX version

For the secrets of spell, see chapter 13 in J. Bentley, Programming
Pearls, Addison-Wesley, 1986.  The curious results of feeding
random strings to spell arise from hashing, which is the
key to spell's speed and compactness (fewer than 15 bits per
dictionary entry!).  The expected rate of hashing errors
is 1 in 2000 misspellings.  Differing outcomes in different 
implementations are accounted for by evolution in dictionaries, 
hashing functions and affix-stripping rules.

Doug McIlroy
AT&T Bell Labs
doug at research.att.com
research!doug