ProjectsSpell Checker with a Bloom Filter
A command-line spell checker that builds a Bloom filter from a dictionary, saves it as a compact binary file, and loads it again to report the words that are probably misspelt. Building it teaches how a set can answer membership questions in a few bits per item by accepting rare false positives but never a false negative, how to size the filter for the error rate you can live with, and how to design a binary file format that another run of the program can trust.
From Coding Challenges #53 ↗ by John Crickett
No sign-up. You tell the mentor your language: Java, Python or Node.js.
What you'll learn · 7 concepts
In the order the steps use them. Each one links to the best places to learn it, and you explain it in your own words once its steps are built.
The dictionary is the set. No false negatives means a correct word is never reported as wrong, and a false positive means a typo occasionally passes, which you build in step 1 and see for yourself in step 5.
Covers: a set that keeps bits, not items · no false negatives · false positives from shared bits · why an item can't be removed · counting filters that allow deletion
Bloom filter (Wikipedia) ↗ · Bloom Filters by Example, an interactive tutorial ↗ · Bloom Filters, an interactive demonstration (Jason Davies) ↗
Step 1 asks you to derive the number of bits and hash functions from the expected item count and the rate you can accept, and step 2 applies that to the real dictionary.
Covers: items, bits and hash functions · the chance that a bit is still zero · the false-positive rate as the filter fills · the best number of hash functions · bits per item for a target rate · adding more items than planned
Bloom filter (Wikipedia): Optimal number of hash functions ↗ · Bloom filter calculator (Thomas Hurst) ↗ · Network Applications of Bloom Filters: A Survey (Broder and Mitzenmacher), section 2 ↗
Step 1 needs several positions per word, and the page suggests writing two FNV variants. Step 4 loads the filter in a new run, which only works if the hashes give exactly the positions they gave at build time.
Covers: spreading items evenly over the positions · many positions from two hashes, by double hashing · turning a hash into a position · fast hashes such as FNV that aren't cryptographic · the same positions on every run and every machine
Fowler-Noll-Vo hash function (Wikipedia) ↗ · Less Hashing, Same Performance: Building a Better Bloom Filter (Kirsch and Mitzenmacher) ↗ · LevelDB source: util/bloom.cc ↗
Step 3 writes the bit array after the header and step 4 reads it back. The page fixes the byte order of the header but not the order of bits inside each byte, so your format has to decide it.
Covers: one bit per position, eight per byte · finding the byte and the bit within it · setting and testing a bit with a mask · the order of bits inside a byte · rounding up to whole bytes
Bit array (Wikipedia) ↗ · Bit numbering (Wikipedia) ↗ · Mask (computing) (Wikipedia) ↗
Steps 3 and 4 write and read a fixed header in big-endian order. The header records how many hash functions and bits there are, but not which hash functions or bit order, so the version number has to stand for those.
Covers: a magic number to recognise the file · a version number for change · fixed-width fields and the ceilings they set · big-endian byte order · a header, then the payload, and the expected length · checking a file before trusting it
Endianness (Wikipedia) ↗ · PNG (Wikipedia): File header ↗ · List of file signatures (Wikipedia) ↗
Step 2 reads words from a file and step 5 reads them from the command line, so the same word arrives by two routes and has to become the same bytes both times.
Covers: a filter matches exact bytes · line endings and stray spaces in the word list · upper and lower case · Unicode normalisation · one rule for building and for checking · the word list as the only definition of correct
Unicode Standard Annex #15: Unicode Normalization Forms ↗ · Unicode equivalence (Wikipedia) ↗ · Newline (Wikipedia) ↗
The file from step 3 is much smaller than the dictionary it stands for, and step 5 shows the price, a rare typo that goes unreported. The optional step turns the trade-off around: a false positive rejects a good password, which is a small annoyance, while no listed password ever gets through.
Covers: bits per item, whatever the item's length · an exact set as the alternative · a cheap filter in front of a costly exact check · choosing the rate from the cost of a false positive · storage engines, caches and password lists · newer filters that allow deletion
Network Applications of Bloom Filters: A Survey (Broder and Mitzenmacher) ↗ · Apache Cassandra documentation: Bloom Filters ↗ · Cuckoo Filter: Practically Better Than Bloom (Fan, Andersen, Kaminsky and Mitzenmacher) ↗
What you'll build · 6 steps
Steps of 30 to 60 minutes, in your own editor and language. Each one has a check, so you know when it works.
Create the project and get a dictionary to build from, one word per line: the system word list on a Unix-like machine, or a downloaded English word list elsewhere.
Works whenThe dictionary file opens, it holds one word per line, and you know roughly how many words it has, since that count sizes the filter later.
From the number of items you expect and the false-positive rate you can accept, work out how many bits and how many hash functions the filter needs. Start with every bit at zero. Adding an item sets the bit each hash function picks, and a query answers definitely absent if any of those bits is zero and probably present if all are one. Write or choose the hash functions yourself, for example two variants of FNV.
Works whenYour tests show that every item you added is reported present, and that among many items you never added, the share reported present stays close to the rate you chose.
Concepts: probabilistic membership · sizing the filter from the item count and the error rate · hash functions for a filter
Given -build and a dictionary file, read every word, add it to a filter sized for that many words, and write the filter to a file.
Works whenRunning the build on the dictionary creates the filter file, and the filter reports every word of the dictionary as present.
Concepts: sizing the filter from the item count and the error rate · what counts as the same word
Write the filter as a 12-byte header followed by the bit array. The header holds, all in big-endian order, the four-letter identifier CCBF, a 2-byte version, a 2-byte count of hash functions and a 4-byte count of bits.
Works whenA hex dump of the start of the file (xxd or od) shows the identifier, the version, the hash count and the bit count as you wrote them, most significant byte first. Compared with du, the filter file is much smaller than the dictionary.
Concepts: designing a binary file format · bit arrays
Read a filter file back: check the identifier and the version before trusting anything else, then read the hash count, the bit count and the bit array.
Works whenA filter loaded in a fresh run reports every dictionary word present, as it did when it was built, and a file with the wrong identifier or an unknown version is rejected with a clear error instead of being used.
Concepts: designing a binary file format · hash functions for a filter
Take words from the command line, test each one against the loaded filter, and print one line listing the words that are probably misspelt.
Works whenWords from the dictionary are never listed, made-up words are, and across a large batch of made-up words only about the share you designed for slips through unreported.
Concepts: probabilistic membership · what counts as the same word · space versus accuracy, and where Bloom filters earn their place
Build a small filter of common passwords that a sign-up page can download, so the browser can turn down a common password before it is ever sent. Choose its size and error rate for a file that has to download quickly.
Works whenEvery password on the list is turned down, strong random passwords almost never are, and the filter file is small enough to download with the page.
Concepts: space versus accuracy, and where Bloom filters earn their place · sizing the filter from the item count and the error rate