2
$\begingroup$

I have completely understood how Aho Corasick works for finding one pattern in a text, and how to construct the automaton for a certain pattern. I have studied the CLRS book and watched this video. But the problem is that I cannot find any material on how to build an automaton for more than just one pattern. For example given the following words, how can I build an automaton with the required transition function?

P = {vine, vincent, cent, center}

Are there any topics on StackOverflow or any YouTube videos that teach this step-by-step?

$\endgroup$
6
$\begingroup$

At a high level, the process for building an Aho-Corasick automaton is:

  1. Build a trie for the pattern strings.
  2. Add suffix links (also called failure links) from each node to its longest proper suffix that's still in the trie.
  3. Add output links to any patterns that are reachable from each node via suffix links.

Build the trie

Create a root node, then go through each pattern character by character. Starting from the root, try and follow an edge for the current character. If one does not exist, create an edge to a new node for that character.

Using P = {vine, vincent, cent, center}, say we start with the pattern 'vine'. When we go and add the next pattern 'vincent', we first follow the existing edges for v-i-n, and then add in new edges for c-e-n-t: trie for {vine, vincent}

(I'm marking the ends of each pattern with a double circle). Continue this process until the whole trie is built: trie for {vine, vincent, cent, center}

Add suffix links

Now to add the suffix links, we perform a breadth first search of the tree, adding an edge for each node except the root. If a node is one hop away from the root, its suffix link goes to the root. Adding suffix links in blue, the suffix links for the nodes corresponding to 'v' and 'c' are: enter image description here

Otherwise, the node corresponds to some string wx, where x is the final character. For example, if we look at the string 'vi', w='v' and x='i'. Now follow w's suffix link and let the node you arrive at be called n. enter image description here

If this node has an edge for x, then set wx's suffix link to point at nx. Else if n is the root node, set wx's suffix link to point at n. Otherwise, follow n's suffix link, let this node be the new n, and repeat. In this case, the node for n does not have an edge for 'i'. Here's another example adding in the suffix link for 'vinc', where w='vin' and x='c': enter image description here

Add output links

As you are performing the BFS to fill in the suffix links, you can also fill in the output links (all initially null). Let the current node be n. Follow n's suffix link and let the node you arrive at be called m.

If m corresponds to one of the pattern strings (is marked with a double circle), set n's output link to point at m. Else set n's output link to point at the same node as m's output link, or null if m has no output link. In our example there is only one output link, shown here in green:

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.