Here’s a problem: say you’re ingesting roughly 4 million Reddit comments per day, and you need to detect the presence of 10,000 specific keywords in near real time. The naive answer is obvious - loop through each comment and keyword. Done. for comment in reddit_comments:
    for keyword in keywords:
        if keyword in comment:
            # alert user for comment in reddit_comments:
    for keyword in keywords:
        if keyword in comment:
            # alert user It’s simple. Also visibly slow. Even if you ignore the math, it’s (easily) doing billions of string comparisons. The complexity is quadratic, and there’s no way you’d be  able to run it on a tiny VPS. That’s the problem Lewis Van Winkle came across when building F5Bot  (a free Reddit scraping service). And he ran it on a tiny VPS with an  anemic CPU, not some beefy cluster. The solution? An algorithm from 1975 called Aho-Corasick. It lets you search for patterns in a single pass. Aho-Corasick The $600 bibliographer problem The problem surfaced at Bell Labs (1975) when Margaret Corasick was  working on a tool to search for keywords on government-provided tapes. A  bibliographer hit $600 usage limits while searching for hundreds of keywords at once (and the program hadn’t finished). The kind of problem you hit when your algorithm doesn’t scale. Corasick attended a seminar on algorithm design by Alfred Aho, and they came up with what we know as the Aho-Corasick algorithm. She implemented it. The bibliographer’s search now ran for $25. 24x speedup. Why care The Aho-corasick is actually a very popular algorithm. The original implementation of fgrep was Aho-Corasick. Virus scanners use it to scan for thousands of malware signatures. F5Bot uses it to monitor comments from Reddit and Hacker  News. fgrep was Just look at the benchmark from F5Bot. Loaded 3000 keywords to search on a text of 19377 chars

searching with strpos (naive):  0.384 seconds
searching with aho-corasick:    0.055 seconds (7x faster) Loaded 3000 keywords to search on a text of 19377 chars

searching with strpos (naive):  0.384 seconds
searching with aho-corasick:    0.055 seconds (7x faster) That’s a flex I’d be happy to have any day. How it works The basic idea is - if you’re searching for multiple keywords, you’re doing redundant work. Let’s say you’re searching for : "art", "cart", "ted". Using the naive approach, you’d scan through your text three times - once for each keyword. "art" "cart" "ted" If you’ve already searched for "art"  and you know it’s there, you can start there. Just build a finite state  machine and exploit shared suffixes. Basically, a tree (of strings)  where each node represents a prefix of one of your keywords. As you scan  through your text character by character, you move through this graph.  Sounds eerily similar to a trie? That’s because it’s a trie! "art" What’s clever is that the algorithm builds “failure links” between  nodes. In English, that’s - “if the next character doesn’t match, don’t  start from the root. Jump to this other node in the tree that shares the  longest suffix.” Let me show you a simple example. If you’re searching for {a, ab, b, bc, bca, c, ca, caa}, the algorithm builds a trie (prefix tree) and adds the extra links you see in blue/green: {a, ab, b, bc, bca, c, ca, caa} If you’re familiar with a trie, it just adds a failure link.  That way, you can instantly jump to the longest matching suffix instead  of scanning the word from root again. Let’s say you’re searching "abccab",  you walk through this trie (automaton) once, character by character.  The text is only scanned once - so you end up with a time complexity of  O(n); where n is the length of the text. trie failure link "abccab" A naive approach would have you scanning the word again and again; O(n *  m * k) where m is the number of keywords and k is their average length.  Aho-Corasick is O(n+m+z), where z is the number of matches. Even if you  searched for millions of keywords, Aho-Corasick handles it linearly. Implementation You can find a simple implementation in my recent project, where I adapted it for searching 9 mutations (patterns) in a genome file (basically 4M characters), and it searched  the whole thing in 0.75s. Sure, the patterns I’m using are tiny, but  it’s pretty fast! simple implementation I’m showing a simple example so you get how it works. # naive approach
for comment in reddit_comments:
    for keyword in keywords:
        if keyword in comment:
            # alert user
 
# with aho-corasick
step 1: build an automaton (trie) using patterns
step 2: add failure links (with bfs)
step 3: search automaton by following failure links, and return patterns that matched # naive approach
for comment in reddit_comments:
    for keyword in keywords:
        if keyword in comment:
            # alert user
 
# with aho-corasick
step 1: build an automaton (trie) using patterns
step 2: add failure links (with bfs)
step 3: search automaton by following failure links, and return patterns that matched I think the implementation is about 60 lines of actual code. There’s also a recent library - pyahocorasick; it’s super easy to use. pyahocorasick Use this when You don’t have to spam ahocorasick when searching for three keywords in a paragraph. Use it when: ahocorasick you’re searching for thousands of keywords that don’t change often (F5Bot usecase)
it needs to run often (think streams) you’re searching for thousands of keywords that don’t change often (F5Bot usecase) it needs to run often (think streams) Closing thoughts The Aho-Corasick was invented by Margaret with a pen and paper 50  years ago, without any AI. Still, the core ideas hasn’t changed much in  multi-pattern string matching. Computers today are millions of times faster, and the $600 search  problem would be trivial today. But if you’re processing millions of  Reddit comments per day on a tiny VPS, you can’t just throw hardware at  the problem. Food for thought, there’s probably a 50-year-old algorithm that  solves your problem better than whatever you’re about to implement. If you read this far, let me know if you know what algorithms you find exciting! Footnotes: Footnotes: The original 1975 paper Efficient string matching: An aid to bibliographic search is surprisingly readable.
Margaret J. Corasick’s PhD dissertation (1974) was “securing proprietary data within open systems” - early information security. Sad that she doesn’t have her own Wikipedia page, despite her algorithm and Alfred Aho (he’s the ‘A’ in AWK - Aho, Weinberger, Kernighan) both having their own Wikipedia pages.
There’s a Python library called pyahocorasick  that’s implemented in C for production use. I’m sure it’s way faster than my version, but the principles are identical. I’ll run a benchmark soon.
KMP (Knuth-Morris-Pratt) uses a similar approach for compiling patterns into a finite automata. Basically ahocorasick for a single pattern. Both precompute a structure and exploit prefixes that show up.
The Aho-Corasick automaton can become massive - O(total characters in all keywords). If you have millions of patterns, it might need significant memory. The original 1975 paper Efficient string matching: An aid to bibliographic search is surprisingly readable. Efficient string matching: An aid to bibliographic search Margaret J. Corasick’s PhD dissertation (1974) was “securing proprietary data within open systems” - early information security. Sad that she doesn’t have her own Wikipedia page, despite her algorithm and Alfred Aho (he’s the ‘A’ in AWK - Aho, Weinberger, Kernighan) both having their own Wikipedia pages. There’s a Python library called pyahocorasick  that’s implemented in C for production use. I’m sure it’s way faster than my version, but the principles are identical. I’ll run a benchmark soon. Python library pyahocorasick KMP (Knuth-Morris-Pratt) uses a similar approach for compiling patterns into a finite automata. Basically ahocorasick for a single pattern. Both precompute a structure and exploit prefixes that show up. ahocorasick The Aho-Corasick automaton can become massive - O(total characters in all keywords). If you have millions of patterns, it might need significant memory.

This story contains new, firsthand information uncovered by the writer.

Walkthroughs, tutorials, guides, and tips. This story will teach you how to do something new or how to do something better.

A 1975 Algorithm Still Beats Brute Force in Modern Keyword Search

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Deep learning through the lens of Felix Klein's Erlangen's

Explore The Power of Bounded Adaptivity Through Equivalence Testing

Understand The Distributions Used In Equivalence Testing

EquivTester Samples In Equivalence Testing Algorithm

Technical Analysis Of The Correctness And Complexity Of EquivTester

How to Obtain A Fully Adaptive Algorithm With Sample Complexity O˜(log log n)

Deep learning through the lens of Felix Klein's Erlangen's

Explore The Power of Bounded Adaptivity Through Equivalence Testing

Understand The Distributions Used In Equivalence Testing

EquivTester Samples In Equivalence Testing Algorithm

Technical Analysis Of The Correctness And Complexity Of EquivTester

How to Obtain A Fully Adaptive Algorithm With Sample Complexity O˜(log log n)

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps