Aho-Corasick Algorithm
In computer science, the Aho-Corasick Algorithm is a string searching algorithm that efficiently finds multiple patterns in a given text. It constructs a finite-state machine in the form of a trie (prefix tree) with failure links, allowing it to search for all patterns simultaneously in linear time.
Overview
The Aho-Corasick Algorithm is a classical string matching algorithm used for efficiently finding multiple patterns within a given text. It constructs a finite-state machine in the form of a trie (prefix tree) with failure links, which allows it to search for all patterns simultaneously in linear time.
Video Explanation
Time Complexity:
- Construction Time: O(m), where
mis the total number of characters in all patterns. - Search Time: O(n), where
nis the length of the text.
How It Works
- Trie Construction: All patterns are inserted into a trie where each node represents a character in the patterns.
- Failure Links: Failure links are added to each node, pointing to the longest suffix which is also a prefix. This allows the algorithm to efficiently transition between nodes when a mismatch occurs.
- Pattern Search: The text is processed one character at a time, following the trie structure to match the patterns. If a mismatch occurs, failure links are used to skip unnecessary comparisons.
Example
Given patterns ["he", "she", "his", "hers"] and the text "ushers", the Aho-Corasick algorithm constructs a trie with failure links to search for these patterns. The algorithm finds matches for "he", "she", and "hers".
Code Implementation
Python
from collections import deque, defaultdict
class AhoCorasick:
def __init__(self, patterns):
"""Initialize the Aho-Corasick automaton for the given patterns."""
self.trie = {}
self.output = defaultdict(list)
self.fail = {}
# Build the trie
self._build_trie(patterns)
# Add failure links
self._build_failure_links()
def _build_trie(self, patterns):
"""Insert patterns into the trie."""
self.trie = {'root': {}}
new_node = 0
for idx, pattern in enumerate(patterns):
node = 'root'
for char in pattern:
if char not in self.trie[node]:
new_node += 1
self.trie[node][char] = str(new_node)
self.trie[str(new_node)] = {}
node = self.trie[node][char]
self.output[node].append(pattern)
def _build_failure_links(self):
"""Construct the failure links for Aho-Corasick."""
queue = deque()
self.fail['root'] = 'root'
# Initialize failure links for the first level of the trie
for char, node in self.trie['root'].items():
self.fail[node] = 'root'
queue.append(node)
# BFS for setting failure links
while queue:
curr_node = queue.popleft()
for char, next_node in self.trie[curr_node].items():
queue.append(next_node)
# Find failure link for current node
fail_node = self.fail[curr_node]
while fail_node != 'root' and char not in self.trie[fail_node]:
fail_node = self.fail[fail_node]
if char in self.trie[fail_node]:
self.fail[next_node] = self.trie[fail_node][char]
else:
self.fail[next_node] = 'root'
# Combine output of fail state
self.output[next_node].extend(self.output[self.fail[next_node]])
def search(self, text):
"""Search for patterns in the given text."""
node = 'root'
results = []
for i, char in enumerate(text):
while node != 'root' and char not in self.trie[node]:
node = self.fail[node]
if char in self.trie[node]:
node = self.trie[node]
else:
node = 'root'
# Check if any pattern ends at this character
if self.output[node]:
for pattern in self.output[node]:
results.append((i - len(pattern) + 1, pattern))
return results
# Example usage
patterns = ["he", "she", "his", "hers"]
text = "ushers"
ac = AhoCorasick(patterns)
matches = ac.search(text)
print("Matches found:", matches)
C++
#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
class AhoCorasick {
struct Node {
map<char, int> children;
int fail;
vector<int> output;
};
vector<Node> trie;
vector<string> patterns;
public:
AhoCorasick(const vector<string>& patterns) {
trie.push_back(Node()); // Root node
this->patterns = patterns;
build_trie();
build_failure_links();
}
void build_trie() {
for (int idx = 0; idx < patterns.size(); ++idx) {
string pattern = patterns[idx];
int node = 0;
for (char ch : pattern) {
if (!trie[node].children.count(ch)) {
trie[node].children[ch] = trie.size();
trie.push_back(Node());
}
node = trie[node].children[ch];
}
trie[node].output.push_back(idx);
}
}
void build_failure_links() {
queue<int> q;
for (auto& [ch, next_node] : trie[0].children) {
trie[next_node].fail = 0;
q.push(next_node);
}
while (!q.empty()) {
int curr_node = q.front();
q.pop();
for (auto& [ch, next_node] : trie[curr_node].children) {
int fail = trie[curr_node].fail;
while (fail != 0 && !trie[fail].children.count(ch)) {
fail = trie[fail].fail;
}
if (trie[fail].children.count(ch)) {
trie[next_node].fail = trie[fail].children[ch];
} else {
trie[next_node].fail = 0;
}
trie[next_node].output.insert(trie[next_node].output.end(),
trie[trie[next_node].fail].output.begin(),
trie[trie[next_node].fail].output.end());
q.push(next_node);
}
}
}
vector<pair<int, string>> search(const string& text) {
int node = 0;
vector<pair<int, string>> results;
for (int i = 0; i < text.size(); ++i) {
char ch = text[i];
while (node != 0 && !trie[node].children.count(ch)) {
node = trie[node].fail;
}
if (trie[node].children.count(ch)) {
node = trie[node].children[ch];
} else {
node = 0;
}
for (int pattern_idx : trie[node].output) {
results.emplace_back(i - patterns[pattern_idx].size() + 1, patterns[pattern_idx]);
}
}
return results;
}
};
int main() {
vector<string> patterns = {"he", "she", "his", "hers"};
string text = "ushers";
AhoCorasick ac(patterns);
vector<pair<int, string>> matches = ac.search(text);
cout << "Matches found:\n";
for (const auto& [idx, pattern] : matches) {
cout << "Pattern \"" << pattern << "\" found at index " << idx << endl;
}
return 0;
}
Advantages
- Multiple Pattern Search: Efficiently searches for multiple patterns in a single pass through the text.
- Linear Time Complexity: After preprocessing the patterns, the search runs in linear time relative to the length of the text.
- Failure Links: These allow the algorithm to efficiently backtrack and reuse previously computed results when mismatches occur.
Applications
- Text Search: Useful in applications such as search engines, text editors, and data mining where multiple patterns need to be searched.
- Intrusion Detection Systems: Often used to detect multiple predefined patterns in network traffic.
- DNA Sequence Analysis: Helps in finding multiple patterns within genetic sequences.
Conclusion
The Aho-Corasick Algorithm is an optimal solution for problems involving multiple pattern matching. Its combination of a trie and failure links ensures that it can handle large datasets and multiple queries efficiently.
Related Topics
- KMP Algorithm: Single-pattern foundation that Aho-Corasick generalizes for multi-pattern matching.
- Trie Data Structure: Aho-Corasick is built on a Trie with failure links ( build time).
- Rabin-Karp Algorithm: Alternative multi-pattern matching approach using rolling hashes.
🧠 Quick Quiz
Test Your Understanding
Answer these 3 questions to check what you have learned.
Q1
What is the main topic of this documentation page?
Q2
What should be identified before implementing aho corasick algorithm?
Q3
How is understanding of aho corasick algorithm best checked?
Track Your Progress
Done with this topic? Mark it as complete to track your progress.
💬 Discuss this page
Have a question or spot something confusing in "Aho-Corasick Algorithm"? Ask below — it's backed by GitHub Discussions, so maintainers get notified like any other GitHub activity.