Introduction

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.

Try It

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">A Bloom filter stores the dictionary as a 32-bit array using 3 hash functions. Type a word and press Check to see which bits are probed. A word is <b>flagged</b> only if at least one probed bit is OFF — that is a definite miss. If all bits are ON the word is <b>probably correct</b>, but it might be a false positive.</p>
<div class="dict-display" id="dict-display"></div>
<div class="bits-row">
  <span class="bits-label">Filter bits (32):</span>
  <div class="bits" id="bits"></div>
</div>
<div class="input-row">
  <input id="word-input" type="text" placeholder="Type a word…" autocomplete="off" spellcheck="false" />
  <button id="check-btn" type="button">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">Reset</button>

/* General layout styles. */
* { 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; }
/* Bit array display styles. */
.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; }
/* Input row and button styles. */
.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; }
/* Status message styles. */
.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; }
/* Hash detail row styles. */
.hash-row { font-size: .78rem; color: #666; min-height: 1.2em; margin-bottom: .5rem; }

/* Bloom filter spellchecker: encodes a dictionary into a compact bit array. */
/* No false negatives: if a bit is OFF the word is definitely absent. */
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

/* The fixed dictionary of known words. */
const DICT = ['apple','banana','cherry','dragon','example','filter','grape','honey','island','jungle'];

/* Filter parameters. */
const M = 32; // number of bits in the filter
const K = 3;  // number of independent hash functions

/* Deterministic hash using a seed; maps a word to one of M bit positions. */
function hashFn(word, seed) {
  let h = seed;
  for (let i = 0; i < word.length; i++) {
    h = Math.imul(31, h) ^ word.charCodeAt(i);
    h |= 0;
  }
  return ((h >>> 0) % M);
}

function bloomBits(word) {
  /* Returns the K bit positions this word maps to. */
  const positions = [];
  for (let s = 1; s <= K; s++) positions.push(hashFn(word, s * 0x9e3779b9 | 0));
  return positions;
}

/* Build the filter by setting bits for every dictionary word. */
const filter = new Uint8Array(M);
DICT.forEach(w => { bloomBits(w).forEach(p => { filter[p] = 1; }); });

function check(word) {
  /* Returns bit positions, whether all are set, and whether the word is truly in the dict. */
  const positions = bloomBits(word);
  const allSet = positions.every(p => filter[p] === 1);
  const inDict = DICT.includes(word.toLowerCase());
  return { positions, allSet, inDict };
}

/* Render the dictionary label. */
function renderDict() {
  const el = document.getElementById('dict-display');
  el.innerHTML = 'Dictionary (10 words): ' + DICT.map(w => `<b>${w}</b>`).join(', ');
}

function renderBits(highlighted) {
  /* Render the bit array; highlight probed positions in red. */
  const el = document.getElementById('bits');
  el.innerHTML = '';
  for (let i = 0; i < M; i++) {
    const d = document.createElement('div');
    d.className = 'bit' + (highlighted && highlighted.includes(i) ? ' hit' : (filter[i] ? ' on' : ''));
    d.title = i;
    el.appendChild(d);
  }
}

function setStatus(text, cls) {
  const s = document.getElementById('status');
  s.textContent = text; s.className = 'status ' + cls;
}

function setHashRow(text) {
  document.getElementById('hash-row').textContent = text;
}

function doCheck() {
  const raw = document.getElementById('word-input').value.trim();
  if (!raw) return;
  const word = raw.toLowerCase();
  const { positions, allSet, inDict } = check(word);
  renderBits(positions);
  const posStr = positions.join(', ');
  setHashRow(i18nFmt('%k% hash positions probed: %positions%', { k: K, positions: posStr }));
  if (!allSet) {
    /* At least one bit is off — definite miss. */
    setStatus(i18nFmt('✗ '%word%' is NOT in the dictionary — at least one bit was off.', { word: raw }), 'bad');
  } else if (inDict) {
    /* All bits on and word is truly in the dictionary. */
    setStatus(i18nFmt('✓ '%word%' is in the dictionary — all bits are on.', { word: raw }), 'ok');
  } else {
    /* All bits on but word is NOT in dictionary — false positive. */
    setStatus(i18nFmt('⚠ '%word%' is NOT in the dictionary — but all bits are on. This is a false positive!', { word: raw }), 'warn');
  }
}

document.getElementById('check-btn').addEventListener('click', doCheck);
document.getElementById('word-input').addEventListener('keydown', e => {
  if (e.key === 'Enter') doCheck();
});
document.getElementById('reset-btn').addEventListener('click', () => {
  document.getElementById('word-input').value = '';
  renderBits(null);
  setStatus('', '');
  setHashRow('');
});

renderDict();
renderBits(null);
Result
Console

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 Real Complexity

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

  • Bit array size mm: the larger the array, the fewer collisions between different words' hash patterns and the lower the false-positive rate.
  • Number of hash functions kk: 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 nn words inserted into an mm-bit array with kk hash functions, the expected false-positive rate is approximately:

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

The optimal number of hash functions is k=mnln⁡2k = \frac{m}{n} \ln 2, and at that optimum the false-positive rate is roughly (12)k\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)O(k) time regardless of dictionary size, and kk 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.

Where It Matters

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.

Conclusion

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 mm and kk.

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)O(k) time, making a probabilistic bet that almost always wins.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/bloom-filter-spellcheck/Content licensed under CC BY-NC 4.0.