Conquiste a pesquisa de strings com o algoritmo Aho-Corasick

Manipular strings e buscar padrões nelas são tarefas fundamentais em ciência de dados e uma tarefa típica de qualquer programador.

Algoritmos de string eficientes desempenham um papel importante em muitos processos de ciência de dados. Muitas vezes são eles que tornam tais processos viáveis ​​o suficiente para uso prático.

Neste artigo, você conhecerá um dos algoritmos mais poderosos para pesquisar padrões em uma grande quantidade de texto: o algoritmo Aho-Corasick. Esse algoritmo usa uma estrutura de dados trie (pronuncia-se “try”) para acompanhar os padrões de pesquisa e usa um método simples para encontrar com eficiência todas as ocorrências de um determinado conjunto de padrões em qualquer blob de texto.

Um artigo anterior no Toptal Engineering Blog demonstrou um algoritmo de busca de strings para o mesmo problema. A abordagem adotada neste artigo oferece maior complexidade computacional.

O algoritmo Knuth-Morris-Pratt (KMP)

Para entender como podemos procurar vários padrões em um texto com eficiência, precisamos primeiro resolver um problema mais fácil: procurar um único padrão em um determinado texto.

Suponha que tenhamos um grande blob de texto de comprimento N e um padrão (que queremos procurar no texto) de comprimento M . Quer queiramos procurar uma única ocorrência deste padrão, ou todas as ocorrências, podemos alcançar uma complexidade computacional de O(N + M) usando o algoritmo KMP.

Função de prefixo

O algoritmo KMP funciona calculando uma função de prefixo do padrão que estamos procurando. A função prefix pré-calcula uma posição de fallback para cada prefixo do padrão.

Vamos definir nosso padrão de pesquisa como uma string, rotulada S . Para cada substring S[0..i] , onde i >= 1 , encontraremos o prefixo máximo dessa string que também é o sufixo dessa string. Vamos rotular o comprimento desse prefixo P[i] .

Para o padrão “abracadabra”, a função de prefixo produziria as seguintes posições de fallback:

A função prefix identifica uma característica interessante do padrão.

Vamos pegar um prefixo específico do padrão como exemplo: “abracadab”. O valor da função de prefixo para este prefixo é dois. Isso indica que para este prefixo “abracadab”, existe um sufixo de comprimento dois que combina exatamente com o prefixo de comprimento dois (ou seja, o padrão começa com “ab” e o prefixo termina com “ab.”). a correspondência mais longa para esse prefixo.

Implementação

Aqui está uma função C# que pode ser usada para calcular a função de prefixo para qualquer string:

 public int[] CalcPrefixFunction(String s) { int[] result = new int[s.Length]; // array with prefix function values result[0] = 0; // the prefix function is always zero for the first symbol (its degenerate case) int k = 0; // current prefix function value for (int i = 1; i < s.Length; i++) { // We're jumping by prefix function values to try smaller prefixes // Jumping stops when we find a match, or reach zero // Case 2 if we stop at a zero-length prefix // Case 3 if we stop at a match while (k > 0 && s[i] != s[k]) k = result[k - 1]; if (s[k] == s[i]) k++; // we've found the longest prefix - case 1 result[i] = k; // store this result in the array } return result; }

Executar esta função em um padrão um pouco mais longo “abcdabcabcdabcdab” produz isso:

Complexidade computacional

Apesar de existirem dois laços aninhados, a complexidade da função prefixo é apenas O(M) , onde M é o comprimento do padrão S .

Isso pode ser explicado facilmente observando como os loops funcionam.

Todas as iterações do loop externo através de i podem ser divididas em três casos:

1. Aumenta k em um. O loop completa uma iteração.

2. Não altera o valor zero de k . O loop completa uma iteração.

3. Não altera ou diminui um valor positivo de k .

Os dois primeiros casos podem ser executados no máximo M vezes.

Para o terceiro caso, vamos definir P(s, i) = k1 e P(s, i + 1) = k2, k2 <= k1 . Cada um desses casos deve ser precedido por k1 - k2 ocorrências do primeiro caso. A contagem de diminuições não excede k1 - k2 + 1 . E no total não temos mais do que 2 * M iterações.

Explicação do Segundo Exemplo

Vejamos o segundo padrão de exemplo “abcdabcabcdabcdab”. Aqui está como a função de prefixo o processa, passo a passo:

1. Para uma substring vazia e a substring “a” de comprimento um, o valor da função prefix é definido como zero. ( k = 0 )

2. Olhe para a substring “ab”. O valor atual de k é zero e o caractere “b” não é igual ao caractere “a”. Aqui, temos o segundo caso da seção anterior. O valor de k permanece em zero e o valor da função de prefixo para a substring “ab” também é zero.

3. É o mesmo caso para as substrings “abc” e “abcd”. Não há prefixos que também sejam os sufixos dessas substrings. O valor para eles permanece em zero.

4. Agora vamos ver um caso interessante, a substring “abcda”. O valor atual de k ainda é zero, mas o último caractere de nossa substring corresponde ao seu primeiro caractere. Isso aciona a condição de s[k] == s[i] , onde k == 0 i == 4 . A matriz é indexada a zero e k é o índice do próximo caractere para o prefixo de comprimento máximo. Isso significa que encontramos o prefixo de comprimento máximo para nossa substring que também é um sufixo. Temos o primeiro caso, onde o novo valor de k é um, e assim o valor da função prefixo P(“abcda”) é um.

5. O mesmo caso também acontece para as próximas duas substrings, P(“abcdab”) = 2 e P(“abcdabc”) = 3 . Aqui, estamos procurando nosso padrão no texto, comparando strings caractere por caractere. Digamos que os primeiros sete caracteres do padrão correspondam a cerca de sete caracteres consecutivos de texto processado, mas no oitavo caractere não corresponde. O que deve acontecer a seguir? No caso de correspondência de string ingênua, devemos retornar sete caracteres e iniciar o processo de comparação novamente a partir do primeiro caractere do nosso padrão. Com o valor da função de prefixo (aqui P(“abcdabc”) = 3 ), sabemos que nosso sufixo de três caracteres já corresponde a três caracteres de texto. E se o próximo caractere no texto for “d”, o comprimento da substring correspondente de nosso padrão e substring no texto será aumentado para quatro (“abcd”). Caso contrário, P(“abc”) = 0 e iniciaremos o processo de comparação a partir do primeiro caractere do padrão. Mas o importante é que não retornemos durante o processamento do texto.

6. A próxima substring é “abcdabca”. Na substring anterior, a função de prefixo era igual a três. Isso significa que k = 3 é maior que zero e, ao mesmo tempo, temos uma incompatibilidade entre o próximo caractere no prefixo ( s[k] = s[3] = "d" ) e o próximo caractere no sufixo ( s[i] = s[7] = "a" ). Isso significa que acionamos a condição de s[k] != s[i] , e que o prefixo “abcd” não pode ser o sufixo da nossa string. Devemos diminuir o valor de k e usar o prefixo anterior para comparação, sempre que possível. Como descrevemos acima, a matriz é indexada a zero e k é o índice do próximo caractere que verificamos no prefixo. O último índice do prefixo atualmente correspondido é k - 1 . Tomamos o valor da função de prefixo para o prefixo correspondente k = result[k - 1] . No nosso caso (o terceiro caso) o comprimento do prefixo máximo será reduzido para zero e então na próxima linha será aumentado para um, pois “a” é o prefixo máximo que também é o sufixo da nossa substring.

7. (Aqui continuamos nosso processo de cálculo até chegarmos a um caso mais interessante.)

8. Começamos a processar a seguinte substring: “abcdabcabcdabcd”. O valor atual de k é sete. Assim como com “abcdabca” acima, encontramos uma não correspondência: Como o caractere “a” (o sétimo caractere) não é igual ao caractere “d”, a substring “abcdabca” não pode ser o sufixo de nossa string. Agora obtemos o valor já calculado da função de prefixo para “abcdabc” (três) e agora temos uma correspondência: O prefixo “abcd” também é o sufixo da nossa string. Seu prefixo máximo e o valor da função prefix para nossa substring é quatro, porque foi assim que o valor atual de k se tornou.

9. Continuamos esse processo até o final do padrão.

Resumindo: Ambos os ciclos não levam mais de 3 M iterações, o que prova que a complexidade é O(M). O uso de memória também é O(M).

Implementação do algoritmo KMP

 public int KMP(String text, String s) { int[] p = CalcPrefixFunction(s); // Calculate prefix function for a pattern string // The idea is the same as in the prefix function described above, but now // we're comparing prefixes of text and pattern. // The value of maximum-length prefix of the pattern string that was found // in the text: int maxPrefixLength = 0; for (int i = 0; i < text.Length; i++) { // As in the prefix function, we're jumping by prefixes until k is // greater than 0 or we find a prefix that has matches in the text. while (maxPrefixLength > 0 && text[i] != s[maxPrefixLength]) maxPrefixLength = p[maxPrefixLength - 1]; // If a match happened, increase the length of the maximum-length // prefix. if (s[maxPrefixLength] == text[i]) maxPrefixLength++; // If the prefix length is the same length as the pattern string, it // means that we have found a matching substring in the text. if (maxPrefixLength == s.Length) { // We can return this value or perform this operation. int idx = i - s.Length + 1; // Get the previous maximum-length prefix and continue search. maxPrefixLength = p[maxPrefixLength - 1]; } } return -1; }

O algoritmo acima itera pelo texto, caractere por caractere, e tenta aumentar o prefixo máximo tanto para nosso padrão quanto para alguma sequência de caracteres consecutivos no texto. Em caso de reprovação, não retornaremos nossa posição anterior no texto. Sabemos o prefixo máximo da substring encontrada do padrão; este prefixo também é o sufixo desta substring encontrada e podemos simplesmente continuar a busca.

A complexidade desta função é a mesma da função prefixo, tornando a complexidade computacional geral O(N + M) com memória O(M) .

Curiosidades: Os métodos String.IndexOf() e String.Contains() no framework .NET possuem um algoritmo com a mesma complexidade sob o capô.

O Algoritmo Aho-Corasick

Agora queremos fazer o mesmo para vários padrões.

Suponha que existam M padrões de comprimentos L1 , L2 , …, Lm . Precisamos encontrar todas as correspondências de padrões de um dicionário em um texto de comprimento N .

Uma solução trivial seria pegar qualquer algoritmo da primeira parte e executá-lo M vezes. Temos complexidade de O(N + L1 + N + L2 + … + N + Lm) , ou seja, O(M * N + L) .

Qualquer teste sério o suficiente mata esse algoritmo.

Pegar um dicionário com as 1.000 palavras inglesas mais comuns como padrões e usá-lo para pesquisar a versão em inglês de “Guerra e Paz” de Tolstoi levaria um bom tempo. O livro tem mais de três milhões de caracteres.

Se pegarmos as 10.000 palavras mais comuns em inglês, o algoritmo funcionará cerca de 10 vezes mais devagar. Obviamente em entradas maiores que esta, o tempo de execução também aumentará.

É aqui que o algoritmo Aho-Corasick faz sua mágica.

A complexidade do algoritmo Aho-Corasick é O(N + L + Z) , onde Z é a contagem de correspondências. Este algoritmo foi inventado por Alfred V. Aho e Margaret J. Corasick em 1975.

Implementação

Aqui, precisamos de um trie e adicionamos ao nosso algoritmo uma ideia semelhante às funções de prefixo descritas acima. Calcularemos os valores da função de prefixo para todo o dicionário.

Cada vértice na trie armazenará as seguintes informações:

 public class Vertex { public Vertex() { Children = new Hashtable(); Leaf = false; Parent = -1; SuffixLink = -1; WordID = -1; EndWordLink= -1; } // Links to the child vertexes in the trie: // Key: A single character // Value: The ID of vertex public Hashtable Children; // Flag that some word from the dictionary ends in this vertex public bool Leaf; // Link to the parent vertex public int Parent; // Char which moves us from the parent vertex to the current vertex public char ParentChar; // Suffix link from current vertex (the equivalent of P[i] from the KMP algorithm) public int SuffixLink; // Link to the leaf vertex of the maximum-length word we can make from the current prefix public int EndWordLink; // If the vertex is the leaf, we store the ID of the word public int WordID; }

Existem várias maneiras de implementar links filho. O algoritmo terá uma complexidade de O(N + L + Z) no caso de uma matriz, mas isso terá um requisito de memória adicional de O(L * q) , onde q é o comprimento do alfabeto, já que é o número máximo de filhos que um nó pode ter.

Se usarmos alguma estrutura com acesso O(log(q)) aos seus elementos, teremos um requisito de memória adicional de O(L) , mas a complexidade de todo o algoritmo será O((N + L) * log(q) + Z) .

No caso de uma tabela de hash, temos memória adicional O(L) , e a complexidade de todo o algoritmo será O(N + L + Z) .

Este tutorial usa uma tabela de hash porque também funcionará com diferentes conjuntos de caracteres, por exemplo, caracteres chineses.

Já temos uma estrutura para um vértice. Em seguida, vamos definir uma lista de vértices e inicializar o nó raiz da trie.

 public class Aho { List<Vertex> Trie; List<int> WordsLength; int size = 0; int root = 0; public Aho() { Trie = new List<Vertex>(); WordsLength = new List<int>(); Init(); } private void Init() { Trie.Add(new Vertex()) size++; } }

Em seguida, adicionamos todos os padrões ao trie. Para isso, precisamos de um método para adicionar palavras ao trie:

 public void AddString(String s, int wordID) { int curVertex = root; for (int i = 0; i < s.Length; ++i) // Iterating over the string's characters { char c = s[i]; // Checking if a vertex with this edge exists in the trie: if (!Trie[curVertex].Children.ContainsKey(c)) { Trie.Add(new Vertex()); Trie[size].SuffixLink = -1; // If not - add vertex Trie[size].Parent = curVertex; Trie[size].ParentChar = c; Trie[curVertex].Children[c] = size; size++; } curVertex = (int)Trie[curVertex].Children[c]; // Move to the new vertex in the trie } // Mark the end of the word and store its ID Trie[curVertex].Leaf = true; Trie[curVertex].WordID = wordID; WordsLength.Add(s.Length); }

Neste ponto, todas as palavras padrão estão na estrutura de dados. Isso requer uma memória adicional de O(L) .

Em seguida, precisamos calcular todos os links de sufixo e links de entrada de dicionário.

Para deixar claro e simples de entender, vou percorrer nosso trie da raiz até as folhas e fazer cálculos semelhantes aos que fizemos para o algoritmo KMP, mas em contraste com o algoritmo KMP, onde encontramos o comprimento máximo prefixo que também era o sufixo da mesma substring, agora encontraremos o sufixo de comprimento máximo da substring atual que também é o prefixo de algum padrão na trie. O valor desta função não será o comprimento do sufixo encontrado; será o link para o último caractere do sufixo máximo da substring atual. Isso é o que quero dizer com o link de sufixo de um vértice.

Vou processar vértices por níveis. Para isso, usarei um algoritmo de busca em largura (BFS):

E abaixo está a implementação desta travessia:

 public void PrepareAho() { Queue<int> vertexQueue = new Queue<int>(); vertexQueue.Enqueue(root); while (vertexQueue.Count > 0) { int curVertex = vertexQueue.Dequeue(); CalcSuffLink(curVertex); foreach (char key in Trie[curVertex].Children.Keys) { vertexQueue.Enqueue((int)Trie[curVertex].Children[key]); } } }

E abaixo está o método CalcSuffLink para calcular o link do sufixo para cada vértice (ou seja, o valor da função de prefixo para cada substring na trie):

 public void CalcSuffLink(int vertex) { // Processing root (empty string) if (vertex == root) { Trie[vertex].SuffixLink = root; Trie[vertex].EndWordLink = root; return; } // Processing children of the root (one character substrings) if (Trie[vertex].Parent == root) { Trie[vertex].SuffixLink = root; if (Trie[vertex].Leaf) Trie[vertex].EndWordLink = vertex; else Trie[vertex].EndWordLink = Trie[Trie[vertex].SuffixLink].EndWordLink; return; } // Cases above are degenerate cases as for prefix function calculation; the // value is always 0 and links to the root vertex. // To calculate the suffix link for the current vertex, we need the suffix // link for the parent of the vertex and the character that moved us to the // current vertex. int curBetterVertex = Trie[Trie[vertex].Parent].SuffixLink; char chVertex = Trie[vertex].ParentChar; // From this vertex and its substring we will start to look for the maximum // prefix for the current vertex and its substring. while (true) { // If there is an edge with the needed char, we update our suffix link // and leave the cycle if (Trie[curBetterVertex].Children.ContainsKey(chVertex)) { Trie[vertex].SuffixLink = (int)Trie[curBetterVertex].Children[chVertex]; break; } // Otherwise, we are jumping by suffix links until we reach the root // (equivalent of k == 0 in prefix function calculation) or we find a // better prefix for the current substring. if (curBetterVertex == root) { Trie[vertex].SuffixLink = root; break; } curBetterVertex = Trie[curBetterVertex].SuffixLink; // Go back by sufflink } // When we complete the calculation of the suffix link for the current // vertex, we should update the link to the end of the maximum length word // that can be produced from the current substring. if (Trie[vertex].Leaf) Trie[vertex].EndWordLink = vertex; else Trie[vertex].EndWordLink = Trie[Trie[vertex].SuffixLink].EndWordLink; }

A complexidade deste método é O(L) ; dependendo da implementação da coleção filha, a complexidade pode ser O(L * log(q)) .

A prova de complexidade é semelhante à função de prefixo de prova de complexidade no algoritmo KMP.

Vejamos a imagem a seguir. Esta é uma visualização do trie para o dicionário { abba, cab, baba, caab, ac, abac, bac } com todas as informações calculadas:

As bordas do Trie são azuis profundas, os links de sufixo são azuis claros e os links de sufixo do dicionário são verdes. Os nós correspondentes às entradas do dicionário são destacados em azul.

E agora precisamos apenas de mais um método - processar um bloco de texto que pretendemos pesquisar:

 public int ProcessString(String text) { // Current state value int currentState = root; // Targeted result value int result = 0; for (int j = 0; j < text.Length; j++) { // Calculating new state in the trie while (true) { // If we have the edge, then use it if (Trie[currentState].Children.ContainsKey(text[j])) { currentState = (int)Trie[currentState].Children[text[j]]; break; } // Otherwise, jump by suffix links and try to find the edge with // this char // If there aren't any possible edges we will eventually ascend to // the root, and at this point we stop checking. if (currentState == root) break; currentState = Trie[currentState].SuffixLink; } int checkState = currentState; // Trying to find all possible words from this prefix while (true) { // Checking all words that we can get from the current prefix checkState = Trie[checkState].EndWordLink; // If we are in the root vertex, there are no more matches if (checkState == root) break; // If the algorithm arrived at this row, it means we have found a // pattern match. And we can make additional calculations like find // the index of the found match in the text. Or check that the found // pattern is a separate word and not just, eg, a substring. result++; int indexOfMatch = j + 1 - WordsLength[Trie[checkState].WordID]; // Trying to find all matched patterns of smaller length checkState = Trie[checkState].SuffixLink; } } return result; }

E, agora, isso está pronto para uso:

Na entrada, temos uma lista de padrões:

 List<string> patterns;

E pesquise o texto:

 string text;

E aqui está como colá-lo juntos:

 // Init the trie structure. As an optional parameter we can put the approximate // size of the trie to allocate memory just once for all nodes. Aho ahoAlg = new Aho(); for (int i = 0; i < patterns.Count; i++) { ahoAlg.AddString(patterns[i], i); // Add all patterns to the structure } // Prepare algorithm for work (calculates all links in the structure): ahoAlg.PrepareAho(); // Process the text. Output might be different; in my case, it's a count of // matches. We could instead return a structure with more detailed information. int countOfMatches = ahoAlg.ProcessString(text);

E é isso! Agora você sabe como esse algoritmo simples, mas poderoso, funciona!

Aho-Corasick é realmente flexível. Os padrões de pesquisa não precisam ser apenas palavras, mas podemos usar frases inteiras ou cadeias aleatórias de caracteres.

atuação

O algoritmo foi testado em um Intel Core i7-4702MQ.

Para os testes, peguei dois dicionários: as 1.000 palavras mais comuns em inglês e as 10.000 palavras mais comuns em inglês.

Para adicionar todas essas palavras ao dicionário e preparar a estrutura de dados para trabalhar com cada um dos dicionários, o algoritmo exigiu 55ms e 135ms respectivamente.

O algoritmo processou livros reais de 3 a 4 milhões de caracteres em 1,0 a 1,3 segundos, enquanto um livro com cerca de 30 milhões de caracteres levou 9,6 segundos.

Paralelizando o Algoritmo Aho-Corasick

Ir em paralelo com o algoritmo Aho-Corasick não é um problema:

Um texto grande pode ser dividido em várias partes e vários segmentos podem ser usados ​​para processar cada parte. Cada thread tem acesso ao trie gerado com base no dicionário.

E as palavras sendo divididas no limite entre os pedaços? Este problema pode ser resolvido facilmente.

Seja N o comprimento do nosso texto grande, S o tamanho de um pedaço e L o comprimento do maior padrão do dicionário.

Agora podemos usar um truque simples. Dividimos pedaços com alguma sobreposição no final, por exemplo tomando [S * (i - 1), S * i + L - 1] , onde i é o índice do pedaço. Quando obtemos uma correspondência de padrão, podemos obter facilmente o índice inicial da correspondência atual e apenas verificar se esse índice está dentro do intervalo de blocos sem sobreposições, [S * (i - 1), S * i - 1] .

Um algoritmo de pesquisa de string versátil

O algoritmo Aho-Corasick é um poderoso algoritmo de correspondência de strings que oferece a melhor complexidade para qualquer entrada e não requer muita memória adicional.

O algoritmo é frequentemente usado em vários sistemas, como corretores ortográficos, filtros de spam, mecanismos de pesquisa, pesquisa de sequência de bioinformática/DNA, etc. Na verdade, algumas ferramentas populares que você pode estar usando todos os dias estão usando esse algoritmo nos bastidores.

A função de prefixo do algoritmo KMP em si é uma ferramenta interessante que reduz a complexidade da correspondência de padrão único ao tempo linear. O algoritmo Aho-Corasick segue uma abordagem semelhante e usa uma estrutura de dados trie para fazer o mesmo para vários padrões.

Espero que você tenha achado útil este tutorial sobre o algoritmo Aho-Corasick.