8. Membership Structures

In chapter 5 we studied data structures that support insertion, deletion, membership testing, and iteration. For some applications testing membership may be enough. Iteration and deletion may not be necessary. The classic example is that of a spell checker. Consider the job of a spell checker. A simple one may detect errors in spelling while a more advanced spell checker may suggest alternatives of correctly spelled words.

Clearly a spell checker is provided with a large dictionary of words. Using the list of words the spell checker determines whether a word you have is in the dictionary and therefore a correct word. If the word does not appear in the dictionary the word processor or editor may underline the word indicating it may be incorrectly spelled. In some cases the word processor may suggest an alternative, correctly spelled word. In some cases, the word processor may simply correct the mispelling. How do these spell checkers/correctors work? What kind of data structures do they use?

8.1. An English Dictionary

You can download an English dictionary of words by clicking this link.

8.2. Figures from Text

../_images/bloom1.png

Fig. 1: An Empty Bloom Filter

../_images/bloom2.png

Fig. 2: After Inserting cow into the Bloom Filter

../_images/bloom3.png

Fig. 3: After inserting cow, cat, dog into the Bloom Filter

../_images/trie.png

Fig. 4: After inserting cow, cat, dog into a Trie