membership structures in chap we covered data structures that support insertiondeletionmembership testingand iteration for some applications testing membership may be enough iteration and deletion may not be necessary the classic example is that of spell checker consider the job of spell checker simple one may detect errors in spelling while more advanced spell checker may suggest alternatives of correctly spelled words clearly spell checker is provided with large dictionary of words using the list of words the spell checker determines whether word you have is in the dictionary and therefore 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 alternativecorrectly spelled word in some casesthe word processor may simply correct the misspelling how do these spell checkers/correctors workwhat kind of data structures do they use goals at first glancea hash set ( python dictionarymight seem an appropriate data structure for spell checking lookup time within the set could be done in ( time howeverthe tradeoff is in the size of this hash map typical english dictionary might contain over , words the amount of space required to store that many words would be quite large in this we'll cover two data structures that are designed to test membership within set the firsta bloom filterhas significantly smaller space requirements and provides very fast membership test the other is trie (pronounced trydata structure which has features that would not be readily available to hash set implementation and may take up less space than hash set (cspringer international publishing switzerland lee and hubbarddata structures and algorithms with pythonundergraduate topics in computer sciencedoi -- this copy belongs to 'acha