Cucerește căutarea șirurilor cu algoritmul Aho-Corasick

Manipularea șirurilor și căutarea modelelor în ele sunt sarcini fundamentale în știința datelor și o sarcină tipică pentru orice programator.

Algoritmii de șir eficienți joacă un rol important în multe procese de știință a datelor. Adesea, ele sunt cele care fac astfel de procese suficient de fezabile pentru utilizare practică.

În acest articol, veți afla despre unul dintre cei mai puternici algoritmi de căutare a modelelor într-o cantitate mare de text: algoritmul Aho-Corasick. Acest algoritm folosește o structură de date trie (pronunțat „încercați”) pentru a ține evidența tiparelor de căutare și folosește o metodă simplă pentru a găsi eficient toate aparițiile unui anumit set de modele în orice blob de text.

Un articol anterior de pe Toptal Engineering Blog a demonstrat un algoritm de căutare de șiruri pentru aceeași problemă. Abordarea adoptată în acest articol oferă o complexitate computațională îmbunătățită.

Algoritmul Knuth-Morris-Pratt (KMP).

Pentru a înțelege cum putem căuta mai multe modele într-un text în mod eficient, trebuie să abordăm mai întâi o problemă mai ușoară: căutarea unui singur model într-un text dat.

Să presupunem că avem o bucată mare de text de lungime N și un model (pe care vrem să-l căutăm în text) de lungime M . Indiferent dacă dorim să căutăm o singură apariție a acestui model, sau toate aparițiile, putem obține o complexitate computațională de O(N + M) folosind algoritmul KMP.

Funcția de prefix

Algoritmul KMP funcționează prin calcularea unei funcție de prefix a modelului pe care îl căutăm. Funcția de prefix precalculează o poziție de rezervă pentru fiecare prefix al modelului.

Să definim modelul nostru de căutare ca un șir, etichetat S . Pentru fiecare subșir S[0..i] , unde i >= 1 , vom găsi prefixul maxim al acestui șir care se întâmplă să fie și sufixul acestui șir. Vom eticheta lungimea acestui prefix P[i] .

Pentru modelul „abracadabra”, funcția de prefix ar produce următoarele poziții de rezervă:

Funcția de prefix identifică o caracteristică interesantă a modelului.

Să luăm ca exemplu un prefix special al modelului: „abracadab”. Valoarea funcției de prefix pentru acest prefix este două. Aceasta indică faptul că pentru acest prefix „abracadab”, există un sufix de lungime doi care se potrivește exact cu prefixul de lungime doi (adică, modelul începe cu „ab” și prefixul se termină cu „ab”). În plus, acesta este cea mai lungă astfel de potrivire pentru acest prefix.

Implementarea

Iată o funcție C# care poate fi utilizată pentru a calcula funcția de prefix pentru orice șir:

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

Rularea acestei funcții pe un model puțin mai lung „abcdabcabcdabcdab” produce acest lucru:

Complexitatea computațională

În ciuda faptului că există două bucle imbricate, complexitatea funcției de prefix este doar O(M) , unde M este lungimea modelului S .

Acest lucru poate fi explicat cu ușurință observând cum funcționează buclele.

Toate iterațiile buclei exterioare prin i pot fi împărțite în trei cazuri:

1. Mărește k cu unu. Bucla completează o iterație.

2. Nu modifică valoarea zero a lui k . Bucla completează o iterație.

3. Nu modifică sau scade o valoare pozitivă a lui k .

Primele două cazuri pot rula de cel mult M ori.

Pentru al treilea caz, să definim P(s, i) = k1 și P(s, i + 1) = k2, k2 <= k1 . Fiecare dintre aceste cazuri ar trebui să fie precedat de k1 - k2 apariții ale primului caz. Numărul scăderilor nu depăşeşte k1 - k2 + 1 . Și în total nu avem mai mult de 2 * M iterații.

Explicația celui de-al doilea exemplu

Să ne uităm la al doilea exemplu de model „abcdabcabcdabcdab”. Iată cum îl procesează funcția de prefix, pas cu pas:

1. Pentru un subșir gol și subșirul „a” de lungime unu, valoarea funcției de prefix este setată la zero. ( k = 0 )

2. Uită-te la subșirul „ab”. Valoarea curentă a lui k este zero și caracterul „b” nu este egal cu caracterul „a”. Aici, avem al doilea caz din secțiunea anterioară. Valoarea lui k rămâne la zero, iar valoarea funcției de prefix pentru subșirul „ab” este, de asemenea, zero.

3. Este același caz pentru subșirurile „abc” și „abcd”. Nu există prefixe care să fie și sufixele acestor subșiruri. Valoarea pentru ei rămâne la zero.

4. Acum să ne uităm la un caz interesant, subșirul „abcda”. Valoarea curentă a lui k este încă zero, dar ultimul caracter al subșirului nostru se potrivește cu primul său caracter. Aceasta declanșează condiția s[k] == s[i] , unde k == 0 și i == 4 . Matricea este indexată la zero și k este indexul următorului caracter pentru prefixul de lungime maximă. Aceasta înseamnă că am găsit prefixul de lungime maximă pentru subșirul nostru care este și un sufix. Avem primul caz, în care noua valoare a lui k este unu și astfel valoarea funcției de prefix P(„abcda”) este una.

5. Același caz se întâmplă și pentru următoarele două subșiruri, P(“abcdab”) = 2 și P(“abcdabc”) = 3 . Aici, căutăm modelul nostru în text, comparând șiruri caracter cu caracter. Să presupunem că primele șapte caractere ale modelului se potrivesc cu aproximativ șapte caractere consecutive ale textului procesat, dar pe al optulea caracter nu se potrivește. Ce ar trebui să se întâmple în continuare? În cazul potrivirii naive șiruri, ar trebui să returnăm șapte caractere înapoi și să începem din nou procesul de comparare de la primul caracter al modelului nostru. Cu valoarea funcției de prefix (aici P(“abcdabc”) = 3 ) știm că sufixul nostru de trei caractere se potrivește deja cu trei caractere de text. Și dacă următorul caracter din text este „d”, lungimea subșirului potrivit al modelului nostru și al subșirului din text este mărită la patru ("abcd"). În caz contrar, P(“abc”) = 0 și vom începe procesul de comparare de la primul caracter al modelului. Dar ceea ce este important este că nu ne întoarcem în timpul procesării textului.

6. Următorul subșir este „abcdabca”. În subșirul anterior, funcția de prefix era egală cu trei. Aceasta înseamnă că k = 3 este mai mare decât zero și, în același timp, avem o nepotrivire între următorul caracter din prefix ( s[k] = s[3] = "d" ) și următorul caracter din sufix ( s[i] = s[7] = "a" ). Aceasta înseamnă că am declanșat condiția s[k] != s[i] și că prefixul „abcd” nu poate fi sufixul șirului nostru. Ar trebui să reducem valoarea lui k și să luăm prefixul anterior pentru comparație, acolo unde este posibil. După cum am descris mai sus, matricea este indexată la zero și k este indexul următorului caracter pe care îl verificăm din prefix. Ultimul index al prefixului potrivit este k - 1 . Luăm valoarea funcției de prefix pentru prefixul potrivit k = result[k - 1] . În cazul nostru (al treilea caz) lungimea prefixului maxim va fi micșorată la zero și apoi în rândul următor va fi mărită până la unu, deoarece „a” este prefixul maxim care este și sufixul subșirului nostru.

7. (Aici ne continuăm procesul de calcul până ajungem la un caz mai interesant.)

8. Începem să procesăm următorul subșir: „abcdabcabcdabcd”. Valoarea curentă a lui k este șapte. Ca și în cazul „abcdabca” de mai sus, am găsit o nepotrivire: deoarece caracterul „a” (al șaptelea caracter) nu este egal cu caracterul „d”, subșirul „abcdabca” nu poate fi sufixul șirului nostru. Acum obținem valoarea deja calculată a funcției de prefix pentru „abcdabc” (trei) și acum avem o potrivire: Prefixul „abcd” este și sufixul șirului nostru. Prefixul său maxim și valoarea funcției de prefix pentru subșirul nostru este patru, pentru că asta a devenit valoarea curentă a lui k .

9. Continuăm acest proces până la sfârșitul modelului.

Pe scurt: ambele cicluri nu iau mai mult de 3 M iterații, ceea ce demonstrează că complexitatea este O(M). Utilizarea memoriei este de asemenea O(M).

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

Algoritmul de mai sus iterează prin text, caracter cu caracter, și încearcă să mărească prefixul maxim atât pentru modelul nostru, cât și pentru o secvență de caractere consecutive din text. În caz de eșec, nu ne vom întoarce la poziția de mai devreme în text. Cunoaștem prefixul maxim al subșirului găsit al modelului; acest prefix este și sufixul acestui subșir găsit și pur și simplu putem continua căutarea.

Complexitatea acestei funcții este aceeași cu cea a funcției de prefix, făcând complexitatea de calcul generală O(N + M) cu memoria O(M) .

Trivia: Metodele String.IndexOf() și String.Contains() din cadrul .NET au un algoritm cu aceeași complexitate sub capotă.

Algoritmul Aho-Corasick

Acum vrem să facem același lucru pentru mai multe modele.

Să presupunem că există M modele de lungimi L1 , L2 , …, Lm . Trebuie să găsim toate potrivirile de modele dintr-un dicționar într-un text de lungime N .

O soluție trivială ar fi să luați orice algoritm din prima parte și să îl rulați de M ori. Avem complexitatea lui O(N + L1 + N + L2 + … + N + Lm) , adică O(M * N + L) .

Orice test suficient de serios distruge acest algoritm.

Luarea unui dicționar cu cele 1.000 de cuvinte engleze cele mai comune drept modele și utilizarea lui pentru a căuta în versiunea în limba engleză a „Războiului și pacea” a lui Tolstoi ar dura destul de mult. Cartea are peste trei milioane de caractere.

Dacă luăm cele 10.000 de cuvinte englezești cele mai comune, algoritmul va funcționa de aproximativ 10 ori mai lent. Evident, pe intrări mai mari decât aceasta, timpul de execuție va crește și el.

Acesta este locul în care algoritmul Aho-Corasick își face magia.

Complexitatea algoritmului Aho-Corasick este O(N + L + Z) , unde Z este numărul de potriviri. Acest algoritm a fost inventat de Alfred V. Aho și Margaret J. Corasick în 1975.

Implementarea

Aici, avem nevoie de o încercare și adăugăm la algoritmul nostru o idee similară cu funcțiile de prefix descrise mai sus. Vom calcula valorile funcției de prefix pentru întregul dicționar.

Fiecare vârf din trie va stoca următoarele informații:

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

Există mai multe moduri de implementare a legăturilor copil. Algoritmul va avea o complexitate de O(N + L + Z) în cazul unui tablou, dar aceasta va avea o cerință suplimentară de memorie de O(L * q) , unde q este lungimea alfabetului, deoarece aceasta este numărul maxim de copii pe care un nod poate avea.

Dacă folosim o structură cu acces O(log(q)) la elementele sale, avem o cerință suplimentară de memorie de O(L) , dar complexitatea întregului algoritm va fi O((N + L) * log(q) + Z) .

În cazul unui tabel hash, avem O(L) memorie suplimentară, iar complexitatea întregului algoritm va fi O(N + L + Z) .

Acest tutorial folosește un tabel hash, deoarece va funcționa și cu diferite seturi de caractere, de exemplu, caractere chinezești.

Avem deja o structură pentru un vârf. În continuare, vom defini o listă de vârfuri și vom inițializa nodul rădăcină al trie-ului.

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

Apoi adăugăm toate modelele la încercare. Pentru aceasta, avem nevoie de o metodă pentru a adăuga un cuvânt la încercare:

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

În acest moment, toate cuvintele tip model sunt în structura de date. Acest lucru necesită o memorie suplimentară de O(L) .

În continuare trebuie să calculăm toate legăturile sufixe și legăturile de intrare din dicționar.

Pentru a fi clar și simplu de înțeles, voi parcurge încercarea noastră de la rădăcină la frunze și voi face calcule similare cu cele făcute pentru algoritmul KMP, dar spre deosebire de algoritmul KMP, unde găsim lungimea maximă. prefixul care a fost și sufixul aceluiași subșir, acum vom găsi sufixul de lungime maximă al subșirului curent care este și prefixul unui model din trie. Valoarea acestei funcții nu va fi lungimea sufixului găsit; va fi legătura către ultimul caracter al sufixului maxim al subșirului curent. Aceasta este ceea ce vreau să spun prin legătura sufixului unui vârf.

Voi procesa nodurile pe niveluri. Pentru asta, voi folosi un algoritm de căutare pe lățimea întâi (BFS):

Și mai jos este implementarea acestei traversări:

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

Și mai jos este metoda CalcSuffLink pentru calcularea legăturii sufixului pentru fiecare vârf (adică valoarea funcției de prefix pentru fiecare subșir din 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; }

Complexitatea acestei metode este O(L) ; în funcție de implementarea colecției de copii, complexitatea poate fi O(L * log(q)) .

Dovada complexității este similară cu funcția de prefix dovedirea complexității din algoritmul KMP.

Să ne uităm la următoarea imagine. Aceasta este o vizualizare a trie pentru dicționar { abba, cab, baba, caab, ac, abac, bac } cu toate informațiile calculate:

Marginile sunt albastru intens, linkurile sufixe sunt albastru deschis, iar linkurile sufixele dicționarului sunt în verde. Nodurile corespunzătoare intrărilor din dicționar sunt evidențiate cu albastru.

Și acum mai avem nevoie de o singură metodă - procesarea unui bloc de text prin care intenționăm să căutăm:

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

Și, acum, acesta este gata de utilizare:

La intrare, avem o listă de modele:

 List<string> patterns;

Și textul de căutare:

 string text;

Și iată cum să le lipiți:

 // 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);

Si asta e! Acum știi cum funcționează acest algoritm simplu, dar puternic!

Aho-Corasick este cu adevărat flexibil. Modelele de căutare nu trebuie să fie doar cuvinte, dar putem folosi propoziții întregi sau lanțuri aleatorii de caractere.

Performanţă

Algoritmul a fost testat pe un Intel Core i7-4702MQ.

Pentru teste, am luat două dicționare: Cele 1.000 de cuvinte englezești cele mai comune și cele 10.000 de cuvinte englezești cele mai comune.

Pentru a adăuga toate aceste cuvinte în dicționar și pentru a pregăti structura de date pentru a funcționa cu fiecare dintre dicționare, algoritmul a necesitat 55ms și, respectiv, 135ms.

Algoritmul a procesat cărți reale de 3-4 milioane de caractere lungime în 1,0-1,3 secunde, în timp ce a durat 9,6 secunde pentru o carte cu aproximativ 30 de milioane de caractere.

Paralelizarea algoritmului Aho-Corasick

Mersul în paralel cu algoritmul Aho-Corasick nu este deloc o problemă:

Un text mare poate fi împărțit în mai multe bucăți și mai multe fire pot fi folosite pentru a procesa fiecare bucată. Fiecare thread are acces la încercarea generată pe baza dicționarului.

Dar cuvintele sunt împărțite la limita dintre bucăți? Această problemă poate fi rezolvată cu ușurință.

Fie N lungimea textului nostru mare, S dimensiunea unei bucăți și L lungimea celui mai mare model din dicționar.

Acum putem folosi un truc simplu. Împărțim bucățile cu o suprapunere la sfârșit, de exemplu luând [S * (i - 1), S * i + L - 1] , unde i este indicele bucății. Când obținem o potrivire de tipar, putem obține cu ușurință indexul de început al potrivirii curente și doar să verificăm dacă acest indice se află în intervalul de bucăți fără suprapuneri, [S * (i - 1), S * i - 1] .

Un algoritm versatil de căutare a șirurilor

Algoritmul Aho-Corasick este un algoritm puternic de potrivire a șirurilor care oferă cea mai bună complexitate pentru orice intrare și nu necesită multă memorie suplimentară.

Algoritmul este adesea folosit în diverse sisteme, cum ar fi verificatoarele ortografice, filtrele de spam, motoarele de căutare, bioinformatica/căutarea secvenței ADN etc. De fapt, unele instrumente populare pe care le utilizați în fiecare zi folosesc acest algoritm în culise.

Funcția de prefix din algoritmul KMP în sine este un instrument interesant care reduce complexitatea potrivirii unui singur model la timp liniar. Algoritmul Aho-Corasick urmează o abordare similară și folosește o structură de date trie pentru a face același lucru pentru mai multe modele.

Sper că ați găsit util acest tutorial despre algoritmul Aho-Corasick.