Bloom-Filter Spellcheck

Every time you type on a phone or a computer, something in the software decides whether each word looks right. A naive spellchecker would keep the entire dictionary in memory and look each word up. That works — but a standard English dictionary has hundreds of thousands of entries, and on early hardware (or on a microcontroller today) even that lookup table is a luxury.

In 1970, Burton Howard Bloom published a two-page paper that made the tradeoff explicit: you can check membership in a set using a tiny fraction of the memory, as long as you accept a small probability of a false positive — calling a valid word incorrect when it isn't.

The data structure he proposed, now called a Bloom filter, works by hashing each dictionary word through several independent hash functions and turning on the corresponding bits in a compact array. Checking a query word runs the same hashes; if any bit is off, the word is definitely not in the dictionary. If all bits are on, the word is probably in the dictionary — but it might be a false positive, a word whose hash pattern happens to overlap with dictionary entries.

The crucial property is that false negatives are impossible: a word that is in the dictionary will always pass. The filter may occasionally flag a valid word as a typo, but it will never let a genuine typo slip through undetected. That asymmetry makes Bloom filters ideal for spellchecking.

Below is a tiny Bloom filter built from a dictionary of ten common words. It uses three independent hash functions and a 32-bit array. Type any word and press Check to see whether it passes, gets flagged, or triggers a false positive.

<p class="hint">{{hint_para}}</p>
<div class="dict-display" id="dict-display"></div>
<div class="bits-row">
  <span class="bits-label">{{bits_label}}</span>
  <div class="bits" id="bits"></div>
</div>
<div class="input-row">
  <input id="word-input" type="text" placeholder="{{placeholder_word}}" autocomplete="off" spellcheck="false" />
  <button id="check-btn" type="button">{{btn_check}}</button>
</div>
<div class="status" id="status"></div>
<div class="hash-row" id="hash-row"></div>
<button id="reset-btn" type="button" class="ghost">{{btn_reset}}</button>

/* {{c_layout}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.5; }
.dict-display { font-size: .8rem; color: #555; margin-bottom: .55rem; }
.dict-display b { color: #1d3557; }
/* {{c_bits_style}} */
.bits-row { display: flex; align-items: center; gap: .5rem; margin-bottom: .6rem; flex-wrap: wrap; }
.bits-label { font-size: .78rem; color: #555; white-space: nowrap; }
.bits { display: flex; gap: 3px; flex-wrap: wrap; }
.bit { width: 18px; height: 18px; border-radius: 4px; background: #d0d5dc; font-size: .65rem;
       display: flex; align-items: center; justify-content: center; color: #888;
       transition: background .15s; }
.bit.on { background: #1d3557; color: #fff; }
.bit.hit { background: #e63946; color: #fff; }
/* {{c_input_style}} */
.input-row { display: flex; gap: .5rem; margin-bottom: .55rem; }
input { flex: 1; padding: .42rem .7rem; border: 1px solid #ccc; border-radius: 8px;
        font: 400 15px system-ui; outline: none; }
input:focus { border-color: #1d3557; }
button { font: 600 14px system-ui; padding: .42rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; font-size: .85rem; padding: .32rem .7rem; }
/* {{c_status_style}} */
.status { font-size: .98rem; font-weight: 600; min-height: 1.4em; margin-bottom: .35rem; }
.status.ok  { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.warn { color: #b06e00; }
/* {{c_hash_style}} */
.hash-row { font-size: .78rem; color: #666; min-height: 1.2em; margin-bottom: .5rem; }

// Code not found

Notice what happens when you type a word that is not in the dictionary but whose bits all happen to be set anyway — the filter reports it as probably correct. That is a false positive: the filter is wrong, but only in the safe direction. It will never tell you a real dictionary word is a typo.

The elegance of a Bloom filter is that its error rate is precisely controlled by two parameters.

• Bit array size $m$: the larger the array, the fewer collisions between different words' hash patterns and the lower the false-positive rate.
• Number of hash functions $k$: each additional hash function sets more bits per word, making false matches less likely — up to a point. Too many hashes fill the array quickly and raise the collision rate again.

For a dictionary of $n$ words inserted into an $m$-bit array with $k$ hash functions, the expected false-positive rate is approximately:

$$p \approx \left(1 - e^{-kn/m}\right)^k$$

The optimal number of hash functions is $k = \frac{m}{n} \ln 2$, and at that optimum the false-positive rate is roughly $\left(\frac{1}{2}\right)^k$.

In practice, 10 bits per word with 7 hash functions gives a false-positive rate below 1 %. A 100 000-word dictionary needs only about 125 KB — versus several megabytes for a compressed trie or hash table.

Lookups run in $O(k)$ time regardless of dictionary size, and $k$ is typically small (3–10). Insertions are equally fast. The only operation a Bloom filter cannot do is deletion: turning a bit off might unset a bit shared with another word.

This structure sits at the boundary between probabilistic algorithms and classical data structures — it achieves near-perfect recall (no false negatives) while deliberately sacrificing perfect precision in exchange for dramatic space savings.

The spellchecker is just the most intuitive use case. Bloom filters appear wherever you need a fast, memory-efficient membership test and can tolerate a small false-positive rate:

• Web browsers: Google Chrome's Safe Browsing list is a Bloom filter. Your browser checks a URL against a local filter before sending anything to Google's servers — protecting your privacy while still catching most malicious URLs.
• Database engines: Apache Cassandra and RocksDB use Bloom filters to avoid disk reads. Before opening an SSTable file on disk, the engine checks the filter; if the key is absent, the disk access is skipped entirely.
• Blockchain: Bitcoin's simplified payment verification uses a variant called a Golomb-coded set (a compressed Bloom filter) so light clients can ask full nodes for relevant transactions without revealing which addresses they own.
• Spell- and grammar-checkers: the original application — a 1 MB filter can represent a million-word corpus with a false-positive rate under 1 %.
• Networking: routers use Bloom filters to track which packets have already been forwarded, preventing loops without storing full packet headers.

Everywhere you need "is this item in a huge set?" answered in microseconds and with minimal memory, a Bloom filter trades a little correctness for a lot of efficiency. Compare this with the exact membership test needed in pattern matching, where no false positives are acceptable.

Burton Bloom's insight was to accept imperfection deliberately and on your own terms. A Bloom filter never misses a real member of the set — that guarantee is absolute. What it gives up is the promise that every item it reports as present actually is: a small fraction of false alarms is baked in, and the exact rate is yours to tune by choosing $m$ and $k$.

That trade — absolute recall for reduced precision — turns out to be exactly the right deal for spellchecking, safe-browsing, and dozens of other membership-test problems. The next time your browser silently decides a URL is safe without phoning home, or a database skips a disk read because a word isn't in the index, there is probably a Bloom filter quietly running in $O(k)$ time, making a probabilistic bet that almost always wins.