O algoritmo de Aho-Corasick resolve um dos problemas mais importantes em processamento de texto: buscar multiplos padroes simultaneamente em um texto. Enquanto executar KMP ou Rabin-Karp para cada padrao individualmente custaria O(n*k) (onde k e o numero de padroes), o Aho-Corasick encontra todas as ocorrencias de todos os padroes em uma unica passagem pelo texto em O(n + m + z), onde m e a soma dos comprimentos dos padroes e z e o numero total de ocorrencias encontradas.
O algoritmo constroi um automato finito baseado em uma Trie dos padroes, equipado com dois tipos especiais de links: links de falha (para onde ir quando um caractere nao corresponde) e links de dicionario (para encontrar padroes que sao sufixos de outros). Criado por Alfred Aho e Margaret Corasick em 1975, e usado em ferramentas como grep, sistemas de deteccao de intrusao e filtros de conteudo.
Como Funciona
Fase 1: Construir a Trie
Primeiro inserimos todos os padroes em uma Trie normal:
Padroes: "he", "she", "his", "hers"
(raiz)
/ \
h s
/ \ \
e* i h
| | |
r s* e*
|
s*
* = fim de padrao
Fase 2: Construir Links de Falha (BFS)
Os links de falha conectam cada no ao no que representa o maior sufixo proprio que tambem e prefixo de algum padrao. Construimos via BFS (busca em largura):
(raiz) <----+
/ \ |
h s |
/ \ \ |
raiz <-- e* i h --+ (falha -> h da raiz)
| | |
raiz <-- r s* e* ---> e* (falha -> "he" e sufixo de "she"!)
| (link de dicionario -> "he")
raiz <-- s*
Links de falha (->):
h -> raiz (nenhum sufixo de "h" e prefixo)
s -> raiz (nenhum sufixo de "s" e prefixo)
he -> raiz (sufixo "e" nao e prefixo de padrao)
hi -> raiz (sufixo "i" nao e prefixo)
sh -> h ("h" e sufixo de "sh" E prefixo de "he","his")
her -> raiz
his -> s ("s" e sufixo de "his" E prefixo de "she")
she -> he ("he" e sufixo de "she" E e um padrao!)
hers -> s ("s" e sufixo de "hers")
Fase 3: Busca no Texto
Percorremos o texto caractere a caractere, seguindo a Trie. Em mismatch, seguimos o link de falha.
Texto: "ahishers"
Estado: raiz
'a' -> nao tem filho 'a' -> fica na raiz
'h' -> vai para no 'h'
'i' -> vai para no 'hi'
's' -> vai para no 'his' >>> MATCH: "his" na posicao 1 <<<
link de falha -> 's' (no da Trie de "she")
'h' -> de 's', vai para 'sh'
'e' -> vai para 'she' >>> MATCH: "she" na posicao 3 <<<
link de dicionario -> 'he' >>> MATCH: "he" na posicao 4 <<<
'r' -> de 'she', falha -> 'he', filho 'r' -> 'her'
's' -> vai para 'hers' >>> MATCH: "hers" na posicao 4 <<<
Resultado: "his"@1, "she"@3, "he"@4, "hers"@4
Complexidade
| Fase | Tempo | Espaco |
|---|---|---|
| Construcao da Trie | O(m) | O(m*A) |
| Links de falha (BFS) | O(m*A) | O(m) |
| Busca no texto | O(n+z) | O(1) |
| Total | O(m*A+n+z) | O(m*A) |
Onde m = soma dos comprimentos dos padroes, n = comprimento do texto, z = numero de matches, A = tamanho do alfabeto. Na pratica, com HashMap para filhos, o fator A e substituido pelo numero medio de filhos por no.
Implementacao em Rust
use std::collections::{HashMap, VecDeque};
/// Representa um no do automato Aho-Corasick.
#[derive(Debug)]
struct NoAC {
filhos: HashMap<u8, usize>, // byte -> indice do no filho
link_falha: usize, // indice do no de falha
link_dicionario: Option<usize>, // proximo no que e fim de padrao (via falha)
padrao_idx: Option<usize>, // indice do padrao que termina aqui
profundidade: usize, // profundidade na Trie (= comprimento do prefixo)
}
impl NoAC {
fn novo(profundidade: usize) -> Self {
NoAC {
filhos: HashMap::new(),
link_falha: 0,
link_dicionario: None,
padrao_idx: None,
profundidade,
}
}
}
/// Resultado de uma busca: posicao no texto e indice do padrao.
#[derive(Debug)]
struct Ocorrencia {
posicao: usize, // posicao inicial no texto
padrao_idx: usize, // indice do padrao encontrado
}
/// Automato Aho-Corasick.
struct AhoCorasick {
nos: Vec<NoAC>,
padroes: Vec<String>,
}
impl AhoCorasick {
/// Constroi o automato a partir de uma lista de padroes.
fn construir(padroes: &[&str]) -> Self {
let mut ac = AhoCorasick {
nos: vec![NoAC::novo(0)], // no 0 = raiz
padroes: padroes.iter().map(|s| s.to_string()).collect(),
};
// Fase 1: Inserir padroes na Trie
for (idx, padrao) in padroes.iter().enumerate() {
ac.inserir_padrao(padrao, idx);
}
// Fase 2: Construir links de falha e dicionario via BFS
ac.construir_links();
ac
}
/// Insere um padrao na Trie.
fn inserir_padrao(&mut self, padrao: &str, idx: usize) {
let mut no_atual = 0; // comeca na raiz
for (profundidade, byte) in padrao.bytes().enumerate() {
if !self.nos[no_atual].filhos.contains_key(&byte) {
let novo_idx = self.nos.len();
self.nos.push(NoAC::novo(profundidade + 1));
self.nos[no_atual].filhos.insert(byte, novo_idx);
}
no_atual = self.nos[no_atual].filhos[&byte];
}
self.nos[no_atual].padrao_idx = Some(idx);
}
/// Constroi links de falha e links de dicionario usando BFS.
fn construir_links(&mut self) {
let mut fila: VecDeque<usize> = VecDeque::new();
// Filhos diretos da raiz tem link de falha para a raiz
let filhos_raiz: Vec<(u8, usize)> = self.nos[0].filhos.iter()
.map(|(&b, &idx)| (b, idx))
.collect();
for &(_byte, filho_idx) in &filhos_raiz {
self.nos[filho_idx].link_falha = 0;
fila.push_back(filho_idx);
}
// BFS para construir links de falha
while let Some(no_idx) = fila.pop_front() {
let filhos: Vec<(u8, usize)> = self.nos[no_idx].filhos.iter()
.map(|(&b, &idx)| (b, idx))
.collect();
for (byte, filho_idx) in filhos {
// Encontra o link de falha para o filho
let mut falha = self.nos[no_idx].link_falha;
// Sobe pelos links de falha ate encontrar um no com filho 'byte'
while falha != 0 && !self.nos[falha].filhos.contains_key(&byte) {
falha = self.nos[falha].link_falha;
}
let link_falha = if let Some(&destino) = self.nos[falha].filhos.get(&byte) {
if destino != filho_idx {
destino
} else {
0 // evita loop para si mesmo
}
} else {
0 // volta para a raiz
};
self.nos[filho_idx].link_falha = link_falha;
// Link de dicionario: proximo no que e fim de padrao via links de falha
self.nos[filho_idx].link_dicionario =
if self.nos[link_falha].padrao_idx.is_some() {
Some(link_falha)
} else {
self.nos[link_falha].link_dicionario
};
fila.push_back(filho_idx);
}
}
}
/// Busca todos os padroes no texto.
fn buscar(&self, texto: &str) -> Vec<Ocorrencia> {
let mut resultados = Vec::new();
let mut estado = 0; // comeca na raiz
for (i, byte) in texto.bytes().enumerate() {
// Segue links de falha ate encontrar transicao valida
while estado != 0 && !self.nos[estado].filhos.contains_key(&byte) {
estado = self.nos[estado].link_falha;
}
if let Some(&proximo) = self.nos[estado].filhos.get(&byte) {
estado = proximo;
}
// Se nenhuma transicao, fica na raiz (estado = 0)
// Verifica se o estado atual e fim de padrao
if let Some(idx) = self.nos[estado].padrao_idx {
let pos = i + 1 - self.padroes[idx].len();
resultados.push(Ocorrencia {
posicao: pos,
padrao_idx: idx,
});
}
// Segue links de dicionario para encontrar padroes menores
let mut dict_link = self.nos[estado].link_dicionario;
while let Some(dict_no) = dict_link {
if let Some(idx) = self.nos[dict_no].padrao_idx {
let pos = i + 1 - self.padroes[idx].len();
resultados.push(Ocorrencia {
posicao: pos,
padrao_idx: idx,
});
}
dict_link = self.nos[dict_no].link_dicionario;
}
}
resultados
}
}
fn main() {
let padroes = vec!["he", "she", "his", "hers"];
let texto = "ahishers";
println!("Padroes: {:?}", padroes);
println!("Texto: \"{}\"", texto);
println!();
let ac = AhoCorasick::construir(&padroes);
let resultados = ac.buscar(texto);
println!("Ocorrencias encontradas:");
for oc in &resultados {
let padrao = &ac.padroes[oc.padrao_idx];
println!(
" \"{}\" encontrado na posicao {} (texto[{}..{}])",
padrao,
oc.posicao,
oc.posicao,
oc.posicao + padrao.len()
);
}
// Visualizacao no texto
println!();
println!("Visualizacao:");
println!(" {}", texto);
for oc in &resultados {
let padrao = &ac.padroes[oc.padrao_idx];
let espacos = " ".repeat(oc.posicao + 2);
let sublinhado = "^".repeat(padrao.len());
println!("{}{} \"{}\"", espacos, sublinhado, padrao);
}
}
Exemplo de Execucao
Padroes: ["he", "she", "his", "hers"]
Texto: "ahishers"
Ocorrencias encontradas:
"his" encontrado na posicao 1 (texto[1..4])
"she" encontrado na posicao 3 (texto[3..6])
"he" encontrado na posicao 4 (texto[4..6])
"hers" encontrado na posicao 4 (texto[4..8])
Visualizacao:
ahishers
^^^ "his"
^^^ "she"
^^ "he"
^^^^ "hers"
Trace detalhado do automato:
Texto: a h i s h e r s
0 1 2 3 4 5 6 7
Estado apos cada caractere:
'a' (i=0): raiz nao tem 'a' -> estado=raiz
'h' (i=1): raiz tem 'h' -> estado=h
'i' (i=2): h tem 'i' -> estado=hi
's' (i=3): hi tem 's' -> estado=his (MATCH "his"@1)
falha(his) -> s -> segue para verificar dicionario
'h' (i=4): s tem 'h' -> estado=sh
'e' (i=5): sh tem 'e' -> estado=she (MATCH "she"@3)
dict(she) -> he -> MATCH "he"@4
'r' (i=6): she nao tem 'r'
falha(she) -> he, he tem 'r' -> estado=her
's' (i=7): her tem 's' -> estado=hers (MATCH "hers"@4)
Variacoes e Otimizacoes
1. Busca Case-Insensitive
/// Constroi o automato normalizando para minusculas.
fn construir_case_insensitive(padroes: &[&str]) -> AhoCorasick {
let normalizados: Vec<String> = padroes.iter()
.map(|p| p.to_lowercase())
.collect();
let refs: Vec<&str> = normalizados.iter().map(|s| s.as_str()).collect();
AhoCorasick::construir(&refs)
}
/// Busca normalizando o texto para minusculas.
fn buscar_case_insensitive(ac: &AhoCorasick, texto: &str) -> Vec<Ocorrencia> {
let texto_lower = texto.to_lowercase();
ac.buscar(&texto_lower)
}
2. Filtro de Conteudo com Substituicao
/// Substitui todas as ocorrencias dos padroes por asteriscos.
fn censurar_texto(texto: &str, padroes: &[&str]) -> String {
let ac = AhoCorasick::construir(padroes);
let resultados = ac.buscar(texto);
let mut chars: Vec<char> = texto.chars().collect();
// Marca posicoes que devem ser censuradas
let mut censurar = vec![false; chars.len()];
for oc in &resultados {
let padrao = &ac.padroes[oc.padrao_idx];
for j in oc.posicao..oc.posicao + padrao.len() {
if j < censurar.len() {
censurar[j] = true;
}
}
}
for (i, deve_censurar) in censurar.iter().enumerate() {
if *deve_censurar {
chars[i] = '*';
}
}
chars.into_iter().collect()
}
fn main() {
let texto = "Este texto contem palavras proibidas como spam e virus";
let proibidas = vec!["spam", "virus"];
let censurado = censurar_texto(texto, &proibidas);
println!("Original: {}", texto);
println!("Censurado: {}", censurado);
}
3. Contagem Eficiente de Padroes
/// Conta quantas vezes cada padrao aparece no texto.
fn contar_padroes(texto: &str, padroes: &[&str]) -> Vec<(String, usize)> {
let ac = AhoCorasick::construir(padroes);
let resultados = ac.buscar(texto);
let mut contagens = vec![0usize; padroes.len()];
for oc in &resultados {
contagens[oc.padrao_idx] += 1;
}
padroes.iter()
.enumerate()
.map(|(i, &p)| (p.to_string(), contagens[i]))
.filter(|(_, c)| *c > 0)
.collect()
}
Aplicacoes Praticas
Sistema de Deteccao de Intrusao (IDS)
/// Simula um IDS simplificado que verifica pacotes de rede
/// contra assinaturas conhecidas de ataques.
fn verificar_pacote(payload: &str, assinaturas: &AhoCorasick) -> Vec<String> {
let ocorrencias = assinaturas.buscar(payload);
let mut alertas = Vec::new();
for oc in &ocorrencias {
let padrao = &assinaturas.padroes[oc.padrao_idx];
alertas.push(format!(
"ALERTA: Assinatura \"{}\" detectada na posicao {}",
padrao, oc.posicao
));
}
alertas
}
fn main() {
let assinaturas_ataque = vec![
"DROP TABLE",
"UNION SELECT",
"<script>",
"../../../",
"cmd.exe",
];
let ac = AhoCorasick::construir(&assinaturas_ataque);
let pacotes = vec![
"SELECT * FROM users WHERE id=1",
"SELECT * FROM users UNION SELECT * FROM senhas",
"GET /page?q=<script>alert(1)</script>",
"GET /files/../../../etc/passwd",
];
for pacote in &pacotes {
let alertas = verificar_pacote(pacote, &ac);
if alertas.is_empty() {
println!("[OK] {}", pacote);
} else {
for alerta in &alertas {
println!("{}", alerta);
}
}
println!();
}
}
Extrator de Palavras-Chave para SEO
/// Extrai e conta palavras-chave relevantes em um texto.
fn analisar_palavras_chave(texto: &str, palavras_chave: &[&str]) -> Vec<(String, usize, f64)> {
let texto_lower = texto.to_lowercase();
let total_palavras = texto.split_whitespace().count();
let ac = AhoCorasick::construir(palavras_chave);
let resultados = ac.buscar(&texto_lower);
let mut contagens = vec![0usize; palavras_chave.len()];
for oc in &resultados {
contagens[oc.padrao_idx] += 1;
}
let mut analise: Vec<(String, usize, f64)> = palavras_chave.iter()
.enumerate()
.filter(|(i, _)| contagens[*i] > 0)
.map(|(i, &p)| {
let densidade = (contagens[i] as f64 / total_palavras as f64) * 100.0;
(p.to_string(), contagens[i], densidade)
})
.collect();
analise.sort_by(|a, b| b.1.cmp(&a.1));
analise
}
Comparacao com Outros Algoritmos
| Algoritmo | Padroes | Construcao | Busca | Espaco |
|---|---|---|---|---|
| KMP (por padrao) | 1 | O(m) | O(n) | O(m) |
| KMP (k padroes) | k | O(soma m) | O(n*k) | O(soma m) |
| Rabin-Karp multi | k | O(soma m) | O(nk) | O(k) |
| Aho-Corasick | k | O(m*A) | O(n+z) | O(m*A) |
| Regex (alternacao) | k | O(soma m) | O(n*soma m) | O(soma m) |
* Caso medio. m = soma dos comprimentos, A = tamanho do alfabeto, z = ocorrencias.
O Aho-Corasick e o algoritmo ideal quando voce precisa buscar muitos padroes simultaneamente. O tempo de busca O(n+z) e independente do numero de padroes, o que o torna imbativel para aplicacoes como filtros de conteudo e IDS.
Exercicios Praticos
Busca com wildcards: Estenda o Aho-Corasick para suportar o caractere ‘?’ que corresponde a qualquer byte. Dica: ao encontrar ‘?’, adicione transicoes para todos os bytes possiveis.
Streaming: Modifique a implementacao para processar texto em chunks (pedacos), mantendo o estado do automato entre chamadas. Isso e util para processar grandes arquivos sem carrega-los inteiramente em memoria.
Padroes com prioridade: Quando multiplos padroes se sobrepoem na mesma posicao, retorne apenas o mais longo (ou o de maior prioridade). Implemente uma versao que resolve conflitos.
Visualizador de automato: Crie uma funcao que imprime a estrutura do automato (nos, transicoes, links de falha) em formato legivel, como uma tabela.
Veja Tambem
- VecDeque na Biblioteca Padrao – fila dupla usada no BFS
- HashMap – mapa hash para transicoes dos nos
- String em Rust – manipulacao de strings
- Vec: Vetores Dinamicos – armazenamento dos nos e resultados
- Trie em Rust – estrutura base do automato Aho-Corasick
- Algoritmo KMP – busca de padrao unico