using this formula it is possible to solve for given an and desired probabilitypof false positives the formula is as follows = ln (ln ) finallysolving for above results in the following formula ln these two formulas tell us how many bits are required in our filter to guarantee maximum specified rate of false positives we can also compute the required number of hash functions for instancefor an english dictionary containing , words and desired false postive percentage of no more than (expressed as in the formularequires bit array of , , bits and seven hashing functions the number of bits in this example may seem excessive howeverrecall that they are bits an efficient implementation requires roughly kb of storage the number of characters in the english dictionary used in these examples totals , assuming byte per characterstoring all these words would require minimum of kb the bloom filter represents quite savings in space in additionduring experiments the lookup time using the bloom filter never took longer than us the lookup time is bounded by the number and efficiency of the hash functions used to compute the desired values assuming that the hash functions are dependent on the length of the string being hashedthen the lookup time is (lkwhere is given by the length of the item being looked up and is the number of hash functions drawbacks of bloom filter besides the obvious false positive potentialthe bloom filter can only report yes or no it can' suggest alternatives for items that might be close to being spelled correctly bloom filter has no memory of which bits were set by which items so yes or no answer is the best we can get with even yes answer not being correct in some circumstances the next section presents trie data structure that will not report false positives and can be used to find alternatives for incorrectly spelled words the trie datatype trie is data structure that is designed for retrieval the data structure is pronounced like the word try trie is not meant to be used when deleting values from data structure is required it is meant only for retrieval of items based on key value this copy belongs to 'acha