Conquista la ricerca di stringhe con l'algoritmo Aho-Corasick

La manipolazione di stringhe e la ricerca di modelli in esse sono attività fondamentali nella scienza dei dati e un'attività tipica per qualsiasi programmatore.

Algoritmi di stringa efficienti svolgono un ruolo importante in molti processi di scienza dei dati. Spesso sono ciò che rende tali processi sufficientemente fattibili per un uso pratico.

In questo articolo imparerai a conoscere uno degli algoritmi più potenti per la ricerca di schemi in una grande quantità di testo: l'algoritmo Aho-Coraick. Questo algoritmo utilizza una struttura di dati trie (pronunciata "try") per tenere traccia dei modelli di ricerca e utilizza un metodo semplice per trovare in modo efficiente tutte le occorrenze di un determinato insieme di modelli in qualsiasi blob di testo.

Un precedente articolo sul blog di Toptal Engineering ha dimostrato un algoritmo di ricerca di stringhe per lo stesso problema. L'approccio adottato in questo articolo offre una maggiore complessità computazionale.

L'algoritmo di Knuth-Morris-Pratt (KMP).

Per capire come cercare più pattern in un testo in modo efficiente, dobbiamo prima affrontare un problema più semplice: cercare un singolo pattern in un dato testo.

Supponiamo di avere un grande blob di testo di lunghezza N e un pattern (che vogliamo cercare nel testo) di lunghezza M . Sia che vogliamo cercare una singola occorrenza di questo modello, o tutte le occorrenze, possiamo ottenere una complessità computazionale di O(N + M) usando l'algoritmo KMP.

Funzione di prefisso

L'algoritmo KMP funziona calcolando una funzione di prefisso del pattern che stiamo cercando. La funzione del prefisso pre-calcola una posizione di fallback per ogni prefisso del pattern.

Definiamo il nostro modello di ricerca come una stringa, etichettata S . Per ogni sottostringa S[0..i] , dove i >= 1 , troveremo il prefisso massimo di questa stringa che è anche il suffisso di questa stringa. Assegneremo la lunghezza di questo prefisso P[i] .

Per il modello "abracadabra", la funzione del prefisso produrrebbe le seguenti posizioni di fallback:

La funzione di prefisso identifica una caratteristica interessante del pattern.

Prendiamo un particolare prefisso del pattern come esempio: "abracadab". Il valore della funzione prefisso per questo prefisso è due. Ciò indica che per questo prefisso "abracadab", esiste un suffisso di lunghezza due che corrisponde esattamente al prefisso di lunghezza due (cioè, il modello inizia con "ab" e il prefisso termina con "ab.") Inoltre, questo è la corrispondenza più lunga per questo prefisso.

Implementazione

Ecco una funzione C# che può essere utilizzata per calcolare la funzione di prefisso per qualsiasi stringa:

 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; }

L'esecuzione di questa funzione su un modello leggermente più lungo "abcdabcabcdabcdab" produce questo:

Complessità computazionale

Nonostante il fatto che ci siano due cicli annidati, la complessità della funzione di prefisso è solo O(M) , dove M è la lunghezza del modello S .

Questo può essere spiegato facilmente osservando come funzionano i loop.

Tutte le iterazioni del ciclo esterno attraverso i possono essere suddivise in tre casi:

1. Aumenta k di uno. Il ciclo completa un'iterazione.

2. Non cambia il valore zero di k . Il ciclo completa un'iterazione.

3. Non cambia o diminuisce un valore positivo di k .

I primi due casi possono essere eseguiti al massimo M volte.

Per il terzo caso, definiamo P(s, i) = k1 e P(s, i + 1) = k2, k2 <= k1 . Ciascuno di questi casi dovrebbe essere preceduto da k1 - k2 occorrenze del primo caso. Il conteggio delle diminuzioni non supera k1 - k2 + 1 . E in totale non abbiamo più di 2 * M iterazioni.

Spiegazione del secondo esempio

Diamo un'occhiata al secondo modello di esempio “abcdabcabcdabcdab”. Ecco come la funzione di prefisso lo elabora, passo dopo passo:

1. Per una sottostringa vuota e la sottostringa “a” di lunghezza uno, il valore della funzione di prefisso è impostato su zero. ( k = 0 )

2. Guarda la sottostringa "ab". Il valore corrente di k è zero e il carattere "b" non è uguale al carattere "a". Qui abbiamo il secondo caso della sezione precedente. Il valore di k rimane zero e anche il valore della funzione di prefisso per la sottostringa “ab” è zero.

3. È lo stesso caso per le sottostringhe "abc" e "abcd". Non ci sono prefissi che sono anche i suffissi di queste sottostringhe. Il valore per loro rimane a zero.

4. Ora diamo un'occhiata a un caso interessante, la sottostringa "abcda". Il valore corrente di k è ancora zero, ma l'ultimo carattere della nostra sottostringa corrisponde al suo primo carattere. Questo attiva la condizione di s[k] == s[i] , dove k == 0 e i == 4 . L'array è indicizzato a zero e k è l'indice del carattere successivo per il prefisso di lunghezza massima. Ciò significa che abbiamo trovato il prefisso di lunghezza massima per la nostra sottostringa che è anche un suffisso. Abbiamo il primo caso, dove il nuovo valore di k è uno, e quindi il valore della funzione di prefisso P(“abcda”) è uno.

5. Lo stesso caso si verifica anche per le due sottostringhe successive, P(“abcdab”) = 2 e P(“abcdabc”) = 3 . Qui, stiamo cercando il nostro modello nel testo, confrontando le stringhe carattere per carattere. Diciamo che i primi sette caratteri del modello corrispondono a circa sette caratteri consecutivi del testo elaborato, ma sull'ottavo carattere non corrisponde. Cosa dovrebbe succedere dopo? Nel caso di una corrispondenza ingenua di stringhe, dovremmo restituire sette caratteri e ricominciare il processo di confronto dal primo carattere del nostro modello. Con il valore della funzione prefisso (qui P(“abcdabc”) = 3 ) sappiamo che il nostro suffisso di tre caratteri corrisponde già a tre caratteri di testo. E se il carattere successivo nel testo è "d", la lunghezza della sottostringa abbinata del nostro modello e sottostringa nel testo viene aumentata a quattro ("abcd"). Altrimenti, P(“abc”) = 0 e inizieremo il processo di confronto dal primo carattere del pattern. Ma l'importante è che non si ritorni durante l'elaborazione del testo.

6. La sottostringa successiva è "abcdabca". Nella sottostringa precedente, la funzione di prefisso era uguale a tre. Ciò significa che k = 3 è maggiore di zero e allo stesso tempo abbiamo una mancata corrispondenza tra il carattere successivo nel prefisso ( s[k] = s[3] = "d" ) e il carattere successivo nel suffisso ( s[i] = s[7] = "a" ). Ciò significa che abbiamo attivato la condizione di s[k] != s[i] , e che il prefisso “abcd” non può essere il suffisso della nostra stringa. Dovremmo diminuire il valore di k e prendere il prefisso precedente per il confronto, ove possibile. Come descritto sopra, l'array è indicizzato a zero e k è l'indice del carattere successivo che controlliamo dal prefisso. L'ultimo indice del prefisso attualmente abbinato è k - 1 . Prendiamo il valore della funzione di prefisso per il prefisso attualmente abbinato k = result[k - 1] . Nel nostro caso (il terzo caso) la lunghezza del prefisso massimo verrà ridotta a zero e poi nella riga successiva verrà aumentata fino a uno, perché “a” è il prefisso massimo che è anche il suffisso della nostra sottostringa.

7. (Qui continuiamo il nostro processo di calcolo fino a raggiungere un caso più interessante.)

8. Iniziamo a elaborare la seguente sottostringa: "abcdabcabcdabcd." Il valore corrente di k è sette. Come con "abcdabca" sopra, abbiamo riscontrato una non corrispondenza: poiché il carattere "a" (il settimo carattere) non è uguale al carattere "d", la sottostringa "abcdabca" non può essere il suffisso della nostra stringa. Ora otteniamo il valore già calcolato della funzione di prefisso per "abcdabc" (tre) e ora abbiamo una corrispondenza: il prefisso "abcd" è anche il suffisso della nostra stringa. Il suo prefisso massimo e il valore della funzione di prefisso per la nostra sottostringa sono quattro, perché è quello che è diventato il valore corrente di k .

9. Continuiamo questo processo fino alla fine del modello.

In breve: entrambi i cicli non richiedono più di 3 M iterazioni, il che dimostra che la complessità è O(M). Anche l'uso della memoria è O(M).

Implementazione dell'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; }

L'algoritmo di cui sopra scorre il testo, carattere per carattere, e cerca di aumentare il prefisso massimo sia per il nostro modello che per alcune sequenze di caratteri consecutivi nel testo. In caso di fallimento non torneremo sulla nostra posizione in precedenza nel testo. Conosciamo il prefisso massimo della sottostringa trovata del pattern; questo prefisso è anche il suffisso di questa sottostringa trovata e possiamo semplicemente continuare la ricerca.

La complessità di questa funzione è la stessa di quella per la funzione di prefisso, rendendo la complessità computazionale complessiva O(N + M) con memoria O(M) .

Curiosità: i metodi String.IndexOf() e String.Contains() nel framework .NET hanno un algoritmo con la stessa complessità sotto il cofano.

L'algoritmo Aho-Corasick

Ora vogliamo fare lo stesso per più pattern.

Supponiamo che ci siano M modelli di lunghezze L1 , L2 , …, Lm . Abbiamo bisogno di trovare tutte le corrispondenze di pattern da un dizionario in un testo di lunghezza N .

Una soluzione banale sarebbe prendere qualsiasi algoritmo dalla prima parte ed eseguirlo M volte. Abbiamo complessità di O(N + L1 + N + L2 + … + N + Lm) , cioè O(M * N + L) .

Qualsiasi test abbastanza serio uccide questo algoritmo.

Prendere un dizionario con le 1.000 parole inglesi più comuni come modelli e usarlo per cercare la versione inglese di "Guerra e pace" di Tolstoj richiederebbe un bel po' di tempo. Il libro è lungo più di tre milioni di caratteri.

Se prendiamo le 10.000 parole inglesi più comuni, l'algoritmo funzionerà circa 10 volte più lentamente. Ovviamente su input maggiori di questo crescerà anche il tempo di esecuzione.

È qui che l'algoritmo Aho-Coraick fa la sua magia.

La complessità dell'algoritmo Aho-Coraick è O(N + L + Z) , dove Z è il conteggio delle corrispondenze. Questo algoritmo è stato inventato da Alfred V. Aho e Margaret J. Corasick nel 1975.

Implementazione

Qui, abbiamo bisogno di una prova e aggiungiamo al nostro algoritmo un'idea simile alle funzioni di prefisso descritte sopra. Calcoleremo i valori delle funzioni di prefisso per l'intero dizionario.

Ogni vertice nel trie memorizzerà le seguenti informazioni:

 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; }

Esistono diversi modi per implementare i collegamenti figlio. L'algoritmo avrà una complessità di O(N + L + Z) nel caso di un array, ma questo avrà un requisito di memoria aggiuntivo di O(L * q) , dove q è la lunghezza dell'alfabeto, poiché è il numero massimo di figli che un nodo può avere.

Se usiamo una struttura con accesso O(log(q)) ai suoi elementi, abbiamo un requisito di memoria aggiuntivo di O(L) , ma la complessità dell'intero algoritmo sarà O((N + L) * log(q) + Z) .

Nel caso di una tabella hash, abbiamo O(L) memoria aggiuntiva e la complessità dell'intero algoritmo sarà O(N + L + Z) .

Questo tutorial utilizza una tabella hash perché funzionerà anche con diversi set di caratteri, ad esempio caratteri cinesi.

Abbiamo già una struttura per un vertice. Successivamente, definiremo un elenco di vertici e inizializzeremo il nodo radice del 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++; } }

Quindi aggiungiamo tutti i modelli al trie. Per questo, abbiamo bisogno di un metodo per aggiungere una parola al 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); }

A questo punto, tutte le parole del modello sono nella struttura dati. Ciò richiede una memoria aggiuntiva di O(L) .

Quindi dobbiamo calcolare tutti i collegamenti di suffisso e i collegamenti di voci del dizionario.

Per renderlo chiaro e semplice da capire, attraverserò il nostro trie dalla radice alle foglie e farò calcoli simili a quelli che abbiamo fatto per l'algoritmo KMP, ma in contrasto con l'algoritmo KMP, dove troviamo la lunghezza massima prefisso che era anche il suffisso della stessa sottostringa, ora troveremo il suffisso di lunghezza massima della sottostringa corrente che è anche il prefisso di qualche pattern nel trie. Il valore di questa funzione non sarà la lunghezza del suffisso trovato; sarà il collegamento all'ultimo carattere del suffisso massimo della sottostringa corrente. Questo è ciò che intendo per collegamento suffisso di un vertice.

Elaborerò i vertici per livelli. Per questo, userò un algoritmo di ricerca in ampiezza (BFS):

E di seguito è l'implementazione di questa traversata:

 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 di seguito è riportato il metodo CalcSuffLink per calcolare il collegamento del suffisso per ciascun vertice (ovvero il valore della funzione del prefisso per ogni sottostringa nel 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; }

La complessità di questo metodo è O(L) ; a seconda dell'implementazione della raccolta figlio, la complessità potrebbe essere O(L * log(q)) .

La prova della complessità è simile alla funzione del prefisso di prova della complessità nell'algoritmo KMP.

Diamo un'occhiata all'immagine seguente. Questa è una visualizzazione del trie per il dizionario { abba, cab, baba, caab, ac, abac, bac } con tutte le sue informazioni calcolate:

I bordi del trie sono blu intenso, i collegamenti del suffisso sono azzurri e i collegamenti del suffisso del dizionario in verde. I nodi corrispondenti alle voci del dizionario sono evidenziati in blu.

E ora abbiamo solo bisogno di un altro metodo: elaborare un blocco di testo che intendiamo cercare:

 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 ora questo è pronto per l'uso:

In input, abbiamo un elenco di modelli:

 List<string> patterns;

E cerca il testo:

 string text;

Ed ecco come incollarlo insieme:

 // 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 questo è tutto! Ora sai come funziona questo algoritmo semplice ma potente!

Aho-Coraick è davvero flessibile. I modelli di ricerca non devono essere solo parole, ma possiamo usare frasi intere o catene casuali di caratteri.

Prestazione

L'algoritmo è stato testato su un Intel Core i7-4702MQ.

Per i test, ho preso due dizionari: le 1.000 parole inglesi più comuni e le 10.000 parole inglesi più comuni.

Per aggiungere tutte queste parole al dizionario e preparare la struttura dei dati in modo che funzioni con ciascuno dei dizionari, l'algoritmo ha richiesto rispettivamente 55 ms e 135 ms.

L'algoritmo ha elaborato libri reali di 3-4 milioni di caratteri in 1,0-1,3 secondi, mentre ci sono voluti 9,6 secondi per un libro con circa 30 milioni di caratteri.

Parallelizzare l'algoritmo Aho-Corasick

Andare in parallelo con l'algoritmo Aho-Coraick non è affatto un problema:

Un testo di grandi dimensioni può essere suddiviso in più blocchi e più thread possono essere utilizzati per elaborare ciascun blocco. Ogni thread ha accesso al trie generato in base al dizionario.

Che dire delle parole che vengono divise al confine tra i blocchi? Questo problema può essere risolto facilmente.

Sia N la lunghezza del nostro testo grande, S la dimensione di un pezzo e L la lunghezza del modello più grande nel dizionario.

Ora possiamo usare un semplice trucco. Dividiamo i blocchi con alcune sovrapposizioni alla fine, ad esempio prendendo [S * (i - 1), S * i + L - 1] , dove i è l'indice del blocco. Quando otteniamo una corrispondenza del modello, possiamo facilmente ottenere l'indice iniziale della corrispondenza corrente e controllare semplicemente che questo indice sia all'interno dell'intervallo di blocchi senza sovrapposizioni, [S * (i - 1), S * i - 1] .

Un versatile algoritmo di ricerca di stringhe

L'algoritmo Aho-Corasick è un potente algoritmo di corrispondenza delle stringhe che offre la migliore complessità per qualsiasi input e non richiede molta memoria aggiuntiva.

L'algoritmo viene spesso utilizzato in vari sistemi, come correttori ortografici, filtri antispam, motori di ricerca, bioinformatica/ricerca di sequenze di DNA, ecc. In effetti, alcuni strumenti popolari che potresti utilizzare ogni giorno utilizzano questo algoritmo dietro le quinte.

La funzione di prefisso dell'algoritmo KMP di per sé è uno strumento interessante che riduce la complessità dell'abbinamento a pattern singolo al tempo lineare. L'algoritmo Aho-Corasick segue un approccio simile e utilizza una struttura di dati trie per fare lo stesso per più pattern.

Spero che tu abbia trovato utile questo tutorial sull'algoritmo Aho-Coraick.