The Aho–Corasick algorithm

Who appears where in Part One of “War and Peace”? Twenty-six characters have 135 name forms in the Russian text: Russian nouns change their endings, so Pierre is «Пьер», «Пьера», «Пьеру», Anna Pavlovna is also «Анной Павловной», the little princess «маленькой княгини», and there are the French «Pierre» and «Lise». Searching for each form separately takes 135 passes over the text. The Aho–Corasick machine puts all the forms into one trie and goes over the 244,500 letters of the part once. Each row below is a character, each tick a mention. Click any of them to read the sentence around it.

The picture shows how the part is built. Chapters I–VI are Petersburg: Anna Pavlovna's salon, where Pierre and Prince Andrei first appear, and the night carousal at Anatole's with Dolokhov. Chapters VII–XVII are Moscow, the name day at the Rostovs': Natasha, Sonya, Boris, Vera, Marya Dmitrievna and Shinshin, and between them Anna Mikhailovna's first visit with Boris to the dying Count Bezukhov. In chapters XVIII–XXI the count dies, and around the inheritance are Prince Vasily, Anna Mikhailovna and Catiche. The last four chapters are Bald Hills: the old prince, Princess Marya, Mademoiselle Bourienne, the little princess and Prince Andrei again. Pierre is mentioned 251 times, more than anyone.

The machine found 1373 matches, 1184 of them whole words. The other 189 are forms inside other words: «Пьер» inside «Пьера», «Берг» inside «Бергом». The machine looks for substrings, not words, and this matters; we will come back to it in the section on traps. The 244,500 letters read took 25,956 steps along failure links, about one per ten letters.

The idea

Put all the words into a trie and walk along it while reading the text. While the letters continue some path, go down. When the next letter continues no word, do not start over but move to the node for the longest ending of what has been read that is still in the trie: that is the failure link. Like the prefix function, it is computed in advance. A word is found when we stand in the node where it ends, or in a node from which failure links lead to such a node.

The machine has three parts. Goto edges are the edges of the trie: a node is the beginning of some word, and an edge by a letter extends it. The failure link of a node leads to the node of the longest proper ending of its string that is also in the trie. The dictionary link leads along the chain of failures to the nearest node where some word ends: following them lists the words nested in the end of the current one.

The machine step by step

Below is the example from the 1975 paper by Alfred Aho and Margaret Corasick: the dictionary he, she, his, hers and the text ushers. The nodes are numbered in the order the words were inserted, as in the paper: he is nodes 1 and 2, she 3, 4 and 5, his 6 and 7, hers 8 and 9. Dashed lines are failure links, orange circles nodes where a word ends. Type your own words and text, or pick the example with nested words.

Having read “ush”, the machine stands in node 4, which is “sh”, the beginning of she. The letter e leads to node 5, and two words end there at once: she and, by the dictionary link, he. Next comes r: node 5 has no edge by r, and the machine falls back along the failure link to node 2, “he”, the longest ending of “she” still in the trie. From node 2 the letter r leads to 8, s to 9, and hers is found. No letter of the text is read twice. The listing below prints the same table of failure links as the 1975 paper: for nodes one to nine, 0 0 0 1 2 0 3 0 3.

How to build the failure links

The failure link of a node v = u + c (node u extended by the letter c) is found the same way as the next value of the prefix function. Take the failure link of the parent u and try to extend it by c; if it does not extend, take the link's link, and so on. The first node with an edge by c gives the answer; if there is none, the link leads to the root. All nodes on this way are shallower than v, so the nodes are visited breadth-first, level by level: by the time the queue reaches v, the links of all shallower nodes are ready. The dictionary link is computed along the way: if a word ends in the node of the failure link, it is that node, otherwise that node's own dictionary link.

The links need not be stored: the machine can be turned into a fully deterministic one by writing down in advance, for every node and every letter, where the search will land after all its fallbacks. This is proposed in section six of the same 1975 paper. The machine then makes exactly one step per letter, but the transition table takes nodes × alphabet size: a trifle for DNA, not for Unicode.

Code

The trie's edges are kept in a dictionary per node, the failure and dictionary links in arrays. search yields pairs “where it ended, which word” as it reads the text, so the text can be fed as a stream. The demo has the example from the 1975 paper, all the characters of Part One of the novel and the word filter from the section on traps.

What it costs

The term z can be huge, and it is honest: if the dictionary has the words a, aa, aaa, … , a⁴⁴⁶, then in a text of a hundred thousand letters a every position is the end of hundreds of words, and there are about 45 million occurrences. If you need not to list the occurrences but only to count them for each word, listing is not necessary: in every node count how many times the machine stood there, and add these numbers up along the failure links, from deep nodes to shallow ones. The problem below is built this way.

The pass itself hardly depends on the number of words. A measurement: fifty thousand letters of Part One of the novel and a dictionary of 10, 100, … , 10,000 words from “War and Peace”. Next to it is what people write most often: a regular expression of all the words joined by “or”.

In Python a regular expression of ten words is faster than a home-made machine: its engine is written in C. But the regex's time grows with the dictionary, since at every position it tries the words one by one, and with ten thousand words it runs 24 times longer than the machine. Over the same range the machine slowed down one and a half times, from extra failure steps and extra words found. In Go the regular expression engine factors out the common beginnings of words while parsing and so builds something like a trie itself, so it grows slowly, but with ten thousand words it still lags behind the machine 22 times. The comparison is not quite even: the regular expression finds non-overlapping occurrences, the machine all of them.

Where it breaks: a substring is not a word

The machine looks for substrings, and a banned-word filter built on it directly catches innocent words. In April 1996 AOL's filter would not let residents of the town of Scunthorpe open accounts: an obscene word hides in the town's name. Since then the error has been called the Scunthorpe problem. Try it on the dictionary of “War and Peace”: ban the Russian words «яд» (poison), «вор» (thief), «бес» (demon) and «лох» (sucker).

«Яд» sits in 97 of the novel's 14,871 words, among them «беспорядке» (disorder) and «взгляде» (glance). «Вор» is in 162, including «выговорил» (pronounced) and «говоре» (speech). «Бес» hides in «небесном» (heavenly) and «собеседнике» (interlocutor), and a filter on «лох» would not let through a single mention of Dolokhov. Switch to “as whole words”: the filter checks that there are no letters before and after the match, and all the false alarms disappear. The characters in the first scene are tagged the same way. But that is not the end either: the plurals «лохи» and «воры» no longer match «лох» and «вор» as whole words. Real filters add word forms, normalisation of characters that look like letters, and allow lists, while the machine stays inside as a fast search over that whole dictionary.

Where it is used

• fgrep. Alfred Aho personally implemented these search algorithms in the first versions of the Unix utilities egrep and fgrep. fgrep searches for a list of fixed strings at once, and its algorithm is Aho–Corasick.
• Antivirus software. In ClamAV signatures with wildcards are cut into fixed pieces, and all the pieces are found by one Aho–Corasick machine; simple signatures are found by a Boyer–Moore variant.
• Network security. Snort, an intrusion detection system, looks for thousands of patterns in every packet with an Aho–Corasick machine; the search-method setting chooses between variants that trade memory for speed differently.
• Texts and data. Tagging by a dictionary (names, terms, drug names), finding primers and probes in DNA, highlighting keywords in editors.

History

Alfred Aho and Margaret Corasick worked at Bell Laboratories. The technical libraries of Bell Labs issued a bulletin, “Current Technical Papers”, every two weeks with references to journal papers, and by the summer of 1973 about 150,000 references had piled up, about 10⁷ characters. A bibliographer posed a query, a logical formula of keywords, and a Fortran program looked for titles satisfying it, comparing each word in turn with each title. Aho and Corasick replaced this search with a machine. On a Honeywell 6070 a query of 15 words came to take 0.18 hours of processor time instead of 0.79, and a query of 24 words 0.21 instead of 1.27. The more words, the bigger the gain: the machine's time hardly depends on their number.

In the paper “Efficient string matching: an aid to bibliographic search” (Communications of the ACM, June 1975) the authors say plainly that their algorithm is modelled on the Knuth–Morris–Pratt algorithm, and that a similar scheme for finding the first occurrence had been proposed, but not published, by John Hopcroft and Richard Karp. Margaret Corasick later moved to the MITRE Corporation, and Alfred Aho received the Turing Award for 2020 together with Jeffrey Ullman, for the algorithms and theory that compilers rest on.

Problems

Count how many times each word of a dictionary occurs in a text; one of the tests has tens of millions of occurrences, so they cannot be listed one by one.