Learn AI Create the Future — with Pranay
Main site

Classical NLP That Still Works

Matching thousands of keywords at once

Dictionary matching finds every occurrence of thousands of keywords in one single pass over the text, instead of searching for each keyword separately.

Read these first

On this page 5
  1. Why it exists
  2. How it works
  3. Where you have already seen it
  4. Remember this
  5. What to learn next

One lesson, three depths. Pick the one that fits you today — you can switch any time.

Beginner — No maths. Plain English.

Dictionary matching finds every occurrence of thousands of words at once, in a single read through the text.

Think about proofreading a long letter for ten specific spelling mistakes. You could read the letter ten separate times, once per mistake, checking for one thing each time. Or you could read it once, alert for all ten at the same time.

Dictionary matching is that second approach, built into an algorithm. Instead of ten words though, it can watch for a hundred thousand — all in one single pass over the text.

Why it exists

Some real jobs need thousands of exact terms searched for at once. A pharmacy system checking a prescription against 60,000 drug names. A content moderation system checking a post against a list of banned terms. A resume screener looking for any of 2,000 possible skill names.

The naive approach — search for each word one at a time, using something like Python's .find() — technically works. But it reads through the entire text once per keyword. Search for 60,000 drug names that way, and you read the same document 60,000 times.

Dictionary matching algorithms read the text exactly once, no matter how many keywords you are searching for. The most well-known one, Aho-Corasick, was published in 1975. It is still the standard answer to this problem today.

How it works

The trick is to build all the keywords into one combined structure first. Think of a family tree, where words that start the same way share the same early branches.

   Keywords: "chai", "coffee", "tea"

   Combined structure (a shared "trie"):

        (start)
        /  |  \
       c   c   t
       |   |   |
       h   o   e
       |   |   |
       a   f   a  <- "tea" found here
       |   |
       i   f
       |   |
     "chai" e
            |
            e  <- "coffee" found here

Reading through a new piece of text, the algorithm walks through this structure one character at a time. Every time it lands on a spot marked as the end of a keyword, that keyword has been found. It never has to go back and re-read anything.

Because the structure is shared, this works whether you have 3 keywords or 300,000. The reading cost stays proportional to the length of the text you are scanning. It does not depend on how many keywords you are searching for.

Where you have already seen it

  • Content moderation. Flagging posts that contain any of a large banned-word list, instantly, at the moment you hit "post".
  • Antivirus software. Scanning a file for any of millions of known malware signatures in one pass.
  • Medical and pharmacy systems. Matching prescription text against huge drug name databases.
  • Bioinformatics. Searching a DNA sequence for thousands of known genetic markers at once.

Remember this

  • Dictionary matching finds thousands of keywords in one pass over the text, instead of one pass per keyword.
  • It works by combining all keywords into one shared structure before scanning even starts.
  • Aho-Corasick, from 1975, is still the standard algorithm for this job.

What to learn next

  • Tokenization — a related but different job: choosing what counts as a "word" in the first place.
  • Named entity recognition — a task that often layers dictionary matching underneath a smarter model.
  • BM25 — ranking documents by relevance, a different problem to dictionary matching's exact-match search.

Developer — Code and libraries.

Building Aho-Corasick from scratch, in about 40 lines, is the clearest way to see why it beats searching for each keyword separately.

Setup

Nothing to install — this uses only the standard library.

bash
python --version    # 3.9 or newer

Aho-Corasick, from scratch

dictionary_matching.py
from collections import deque

class AhoCorasick:
    """Finds every occurrence of many keywords in one pass over the text."""

    def __init__(self, keywords):
        # each trie node: {char: child_id}, plus a fail link and an output list
        self.goto = [{}]
        self.fail = [0]
        self.output = [[]]
        for kw in keywords:
            self._add(kw)
        self._build_fail_links()

    def _add(self, keyword):
        node = 0
        for ch in keyword:
            if ch not in self.goto[node]:
                self.goto.append({})
                self.fail.append(0)
                self.output.append([])
                self.goto[node][ch] = len(self.goto) - 1
            node = self.goto[node][ch]
        self.output[node].append(keyword)

    def _build_fail_links(self):
        q = deque()
        for ch, child in self.goto[0].items():
            self.fail[child] = 0        # root's direct children fail back to root
            q.append(child)
        while q:
            node = q.popleft()
            for ch, child in self.goto[node].items():
                q.append(child)
                f = self.fail[node]
                while f and ch not in self.goto[f]:
                    f = self.fail[f]
                self.fail[child] = self.goto[f].get(ch, 0) if (f or ch in self.goto[0]) else 0
                self.output[child] += self.output[self.fail[child]]

    def find_all(self, text):
        node = 0
        hits = []
        for i, ch in enumerate(text):
            while node and ch not in self.goto[node]:
                node = self.fail[node]
            node = self.goto[node].get(ch, 0)
            for kw in self.output[node]:
                hits.append((i - len(kw) + 1, kw))
        return hits

keywords = ["chai", "coffee", "tea", "hai"]
matcher = AhoCorasick(keywords)

text = "chai and coffee and tea, but no chaii today"
hits = matcher.find_all(text)
print(f"scanned {len(text)} characters once for {len(keywords)} keywords")
for pos, kw in hits:
    print(f"  position {pos:2}: {kw!r}   (context: ...{text[max(0,pos-3):pos+len(kw)+3]!r}...)")
Output
scanned 43 characters once for 4 keywords
  position  0: 'chai'   (context: ...'chai an'...)
  position  1: 'hai'   (context: ...'chai an'...)
  position  9: 'coffee'   (context: ...'nd coffee an'...)
  position 20: 'tea'   (context: ...'nd tea, b'...)
  position 32: 'chai'   (context: ...'no chaii t'...)
  position 33: 'hai'   (context: ...'o chaii t'...)

Line by line

goto is the trie — a tree of characters where every keyword traces a path from the root. Shared prefixes, like "chai" and its own substring "hai", walk through overlapping nodes.

fail links are what make this fast on a mismatch. When the current character does not continue matching, instead of restarting from the root and re-reading text, the algorithm jumps to the longest suffix of what it has matched so far that is also a prefix of some keyword. This is exactly what lets the scan touch each character of the text once, no backtracking.

output[child] += output[fail[child]] is the subtle part. It means a node inherits the matches of everything its fail link points to. That is how "hai" gets reported as found at position 1, even though the trie was walked looking for "chai" — "hai" is a suffix of "chai", reachable through a fail link.

Notice "chai" was found again at position 32, inside "chaii". Aho-Corasick matches substrings, not whole words — see the very next section for why that matters.

Common mistakes

Forgetting this finds substrings, not whole words. "chai" was correctly found inside "chaii" above, which is not the word "chai" at all. A drug-name matcher built this way could wrongly flag "hamster" as containing the drug "ham" as a drug fragment. Real systems check word boundaries — whitespace or punctuation on both sides — before accepting a match.

Rebuilding the trie and fail links for every document. The construction step, AhoCorasick(keywords), only needs to happen once per keyword list. Reuse the same matcher object across every document you scan; only find_all needs to run per document.

Using this for a handful of keywords. Building the trie and fail links has real setup cost. For 3 or 4 keywords, plain string search is simpler and fast enough. Aho-Corasick earns its cost at hundreds or thousands of keywords, not a handful.

Try it yourself

Add "i" to the keywords list and re-run. Because "i" is a single character, it will now match almost everywhere — a concrete demonstration of why the word-boundary problem above is not a rare edge case in real dictionaries with short entries.

What to learn next

  • Named entity recognition — the task this technique often quietly sits underneath.
  • BM25 — a very different kind of text matching, ranking rather than exact search.
  • Regex for text — the tool of choice for a handful of patterns, where Aho-Corasick would be overkill.

Researcher — Mathematics and papers.

The algorithm

Aho-Corasick (1975) generalizes single-pattern string matching to multi-pattern matching by combining two structures:

  • A trie over the keyword set, O(sum of keyword lengths) nodes.
  • Failure links, computed via BFS over the trie, where fail(v) points to the node representing the longest proper suffix of the string represented by v that is also a prefix of some keyword — the automaton-theoretic analogue of the KMP failure function, generalized from one pattern to many.

Construction time is O(sum of keyword lengths * |alphabet|) in the naive dictionary-per-node implementation shown in the developer block; a goto-function implemented as a fixed-size array per node instead of a hash map achieves O(sum of keyword lengths) construction at the cost of more memory.

Scanning complexity

For text of length n, keyword set of total length m, and z total matches reported, scanning is:

text
O(n + m + z)

This is the central theoretical result: scanning cost is independent of the number of keywords beyond the one-time O(m) construction. Searching for each of k keywords independently with a single-pattern matcher (e.g. KMP) costs O(k * n). Aho-Corasick amortizes the text-reading cost across all keywords simultaneously, which is why it wins decisively once k is large relative to n.

Output-inheritance and overlapping matches

The output[child] += output[fail[child]] step means a single position in the automaton can report multiple keyword matches — every keyword that is a suffix of the currently-matched string. This is why "chai" and "hai" both fire at overlapping positions in the developer example: Aho-Corasick reports all matches, including nested and overlapping ones, unlike a naive left-to-right single-pattern scanner which is typically implemented to find only non-overlapping matches.

Relationship to other exact-match structures

The Wu-Manber algorithm (1994) and shift-or / bitap techniques trade Aho-Corasick's guaranteed-linear scan for average-case speedups using multi-character shifts, and are preferred when the keyword set is very large but sparse relative to typical matches (few hits expected). Suffix automata and suffix trees solve a related but distinct problem — finding all occurrences of arbitrary substrings of a fixed text, rather than a fixed dictionary against arbitrary text — and are the right tool when the roles of "text" and "pattern" are reversed.

Approximate dictionary matching (allowing edit-distance-bounded matches, for typo tolerance) requires different machinery entirely — typically a BK-tree, a Levenshtein automaton, or an approximate variant of Aho-Corasick — since the exact automaton described here accepts only exact matches by construction.

Key references

  • Aho, A. V. & Corasick, M. J. (1975). Efficient String Matching: An Aid to Bibliographic Search. Communications of the ACM 18(6), 333–340. The original algorithm.
  • Knuth, D. E., Morris, J. H. & Pratt, V. R. (1977). Fast Pattern Matching in Strings. SIAM Journal on Computing 6(2), 323–350. The single-pattern predecessor whose failure-function idea Aho-Corasick generalizes.
  • Wu, S. & Manber, U. (1994). A Fast Algorithm for Multi-Pattern Searching. Technical Report, University of Arizona. The practical alternative for very large, sparse keyword sets.

Current state and open problems

For exact multi-pattern matching over a fixed dictionary, Aho-Corasick has not been meaningfully improved upon in asymptotic terms since 1975 — O(n + m + z) is already optimal in the sense that any correct algorithm must read the text and report the matches. Modern work in this space is almost entirely about constant-factor engineering: cache-friendly automaton layouts, SIMD-vectorized transition lookups, and GPU implementations for security and genomics workloads scanning terabytes of data against million-entry dictionaries. The open, harder problem sitting next to it is approximate and semantic matching — finding not the exact string "myocardial infarction" but its synonyms and misspellings too — which is the gap that named entity recognition and embedding-based matching exist to close.

What to learn next

  • Named entity recognition — the learned, generalizing counterpart to exact dictionary matching.
  • BM25 — ranked retrieval, built on different assumptions than exact matching.
  • Regex for text — pattern matching for structure rather than a fixed vocabulary.