Algoritme de busca de cadenes Aho-Corasick
En Ciències de la Computació, el Algoritme de busca de cadenes Aho–Corasick és un algoritme de busca de cadenes inventat per Alfred V. Aho i Margaret J. Corasick. És un algoritme que busca elements (patrons) d'un conjunt finito de cadenes (diccionari) dins d'un text. Una de les ventages que presenta és que processa el text d'entrada solament una volta, és dir, realisa la busca de tots els patrons de forma simultànea. Si es considera el tamany de l'alfabet al com pertanyen els patrons com a constant, llavors la complexitat temporal de l'algoritme és llineal sobre la suma de les llongituts dels patrons més la llongitut del text. Si ademés es volen conéixer totes les ocurrències de forma explícita, al orde de l'algoritme cal sumar-li la cantitat d'ocurrències. És necessari destacar que si es busquen totes les ocurrències, llavors pot haver un número quadràtic d'elles si cada subcadena és una ocurrència. Per eixemple si el diccionari és a, aa, aaa, aaaa i la cadena d'entrada és aaaa).
Informalmente, l'algoritme construïx un autómata finito determinista similar a un trie en enllaços adicionals entre els nodos interns. Estos enllaços extres permeten portar a terme transicions prou ràpides entre correspondències fallanques de patrons (eixemple, una busca per a cat en un trie que no conté a cat, pero conté cart, i d'esta manera fallaria en el nodo prefixat per ca), a atres ramificacions del trie que compartixen prefixos comuns (eixemple, en el cas anterior, una ramificació per a attribute poguera ser la millor transició a efectuar). Açò li permet a l'autómata realisar transicions entre ocurrències de patrons sense necessitat de backtracking.
Quan el diccionari de patrons es coneix de bestreta (per eixemple, en una base de senyes de virus), la construcció de l'autómata es pot portar a terme i es guarda l'autómata compilado per a us futur. En este cas, la complexitat temporal és llineal sobre la llongitut de l'entrada més el número d'entrades trobades.
El gràfic que es mostra a continuació és l'estructura Aho-Corasick construïda a partir del diccionari especificat, en cada fila en la taula representant un nodo en el trie, i la columna Camine indicant la (única) seqüència de caràcters des de la raïl del trie al nodo en qüestió.
L'estructura de senyes té un nodo per a cada prefix de cada cadena en el diccionari. D'esta manera, si (bca) està en el diccionari, llavors estaran presents nodos per a (bca), (bc), (b) i (). Hi ha un arc dirigit "fill" negre des de cada nodo a un nodo el Camí del qual s'obté afegint un caràcter. Per lo tant, hi ha un arc negre de (bc) a (bca). Hi ha un arc dirigit "sufix" de cada nodo al nodo corresponent al seu sufix propi més llarc en el grafo. Per eixemple, per al nodo (caa), el seu sufixos propis són (aa), (a) i (). El més llarc d'estos que existix en el grafo és (a), per lo que hi ha un arc blau de (caa) a (a). Hi ha un arc vert "sufix en diccionari" des de cada nodo al següent nodo en el diccionari que pot ser alcançat seguint arcs blaus. Per eixemple, hi ha un arc vert de (bca) a (a) perque (a) és el primer nodo corresponent a un dels patrons en el diccionari (nodo blanc) que s'alcança seguint els arcs blaus a (ca) i després a (a).
| Camí | En Diccionari | Enllace sufix | Enllace sufix en Dicc |
|---|---|---|---|
| () | - | ||
| (a) | + | () | |
| (ab) | + | (b) | |
| (b) | - | () | |
| (bc) | + | (c) | (c) |
| (bca) | + | (ca) | (a) |
| (c) | + | () | |
| (ca) | - | (a) | (a) |
| (caa) | + | (a) | (a) |
A l'hora de trobar les occurrencias en un text, en cada pas el nodo actual s'estén trobant el seu fill en el caràcter corresponent, i si no existix, es busca el seu "fill sufix" utilisat en enllaç sufix i es continua d'esta manera fins a trobar un nodo que tinga una transició en el caràcter actual o fins que s'aplegue al nodo raïl.
Quan l'algoritme alcança un nodo, torna totes les entrades en el diccionari que terminen en la posició del caràcter actual en el text d'entrada. Açò es fa imprimint cada nodo alcançat seguint els "enllaces sufix en diccionari", començant per eixe nodo, i continuant fins a alcançar un nodo que no tinga "enllace sufix en diccionari".
L'eixecució en la cadena d'entrada abccab produïx els següents passos:
| Nodo | Cadena que queda | Eixida: Posició final | Transició | Eixida |
|---|---|---|---|---|
| () | abccab | començar en la raïl | ||
| (a) | bccab | a:1 | () a fill (a) | Nodo actual |
| (ab) | ccab | ab:2 | (a) a fill (ab) | Nodo actual |
| (bc) | cab | bc:3, c:3 | (ab) a sufix (b) a fill (bc) | Nodo actual, Enllace sufix en dicc |
| (c) | ab | c:4 | (bc) a sufix (c) a sufix () a fill (c) | Nodo actual |
| (ca) | b | a:5 | (c) a fill (ca) | Nodo sufix en dicc |
| (ab) | ab:6 | (ca) a sufix (a) a fill (ab) | Nodo actual |
Referències
[editar | editar còdic]- (L'accés al text complet pot estar restringit.)
- Este artícul conté una traducció derivada de «Algoritmo de búsqueda de cadenas Aho-Corasick» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.