Metraipolis › archive › dc_bd56fe602b1c

Algoritmo de búsqueda de cadenas Aho-Corasick — Wikipedia (es)

Source
Wikipedia (es)
Original
https://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda_de_cadenas_Aho-Corasick
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-17T06:42:59.419Z
SHA-256 of the archived text
2fd8213250195390f3e766a2595222d736d7a1355e9c43dd0ff6a612e0055438
Stable URL of this page
https://metraipolis.com/documento/dc_bd56fe602b1c

How to cite

Algoritmo de búsqueda de cadenas Aho-Corasick — Wikipedia (es) — Wikipedia (es), https://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda_de_cadenas_Aho-Corasick (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_bd56fe602b1c (Metraipolis archive dc_bd56fe602b1c, sha256 2fd8213250195390f3e766a2595222d736d7a1355e9c43dd0ff6a612e0055438)
BibTeX
@misc{dcbd56fe602b1c,
  title = {Algoritmo de búsqueda de cadenas Aho-Corasick — Wikipedia (es)},
  howpublished = {Wikipedia (es)},
  url = {https://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda_de_cadenas_Aho-Corasick},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_bd56fe602b1c; sha256 2fd8213250195390f3e766a2595222d736d7a1355e9c43dd0ff6a612e0055438},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (es), https://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda_de_cadenas_Aho-Corasick. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

En Ciencias de la Computación, el Algoritmo de búsqueda de cadenas Aho–Corasick es un algoritmo de búsqueda de cadenas inventado por Alfred V. Aho y Margaret J. Corasick. Es un algoritmo que busca elementos (patrones) de un conjunto finito de cadenas (diccionario) dentro de un texto. Una de las ventajas que presenta es que procesa el texto de entrada solamente una vez, es decir, realiza la búsqueda de todos los patrones de forma simultánea. Si se considera el tamaño del alfabeto al cual pertenecen los patrones como constante, entonces la complejidad temporal del algoritmo es lineal en cuanto a la suma de las longitudes de los patrones más la longitud del texto. Si además se quieren conocer todas las ocurrencias de forma explícita, al orden del algoritmo hay que sumarle la cantidad de ocurrencias. Es necesario destacar que si se buscan todas las ocurrencias, entonces puede haber un número cuadrático de ellas si cada subcadena es una ocurrencia. Por ejemplo si el diccionario es a, aa, aaa, aaaa y la cadena de entrada es aaaa). Informalmente, el algoritmo construye un autómata finito determinista similar a un trie con enlaces adicionales entre los nodos internos. Estos enlaces extras permiten llevar a cabo transiciones bastante rápidas entre correspondencias fallidas de patrones (ejemplo, una búsqueda para cat en un trie que no contiene a cat, pero contiene cart, y de esta manera fallaría en el nodo prefijado por ca), a otras ramificaciones del trie que comparten prefijos comunes (ejemplo, en el caso anterior, una ramificación para attribute pudiera ser la mejor transición a efectuar). Esto le permite al autómata realizar transiciones entre ocurrencias de patrones sin necesidad de backtracking. Cuando el diccionario de patrones se conoce de antemano (por ejemplo, en una base de datos de virus), la construcción del autómata se puede llevar a cabo y se guarda el autómata compilado para uso futuro. En este caso, la complejidad temporal es lineal en cuanto a la longitud de la entrada más el número de entradas encontradas. El gráfico que se muestra a continuación es la estructura Aho-Corasick construida a partir del diccionario especificado, con cada fila en la tabla representando un nodo en el trie, y la columna "Camino" indicando la (única) secuencia de caracteres desde la raíz del trie al nodo en cuestión. La estructura de datos tiene un nodo para cada prefijo de cada cadena en el diccionario. De esta manera, si (bca) está en el diccionario, entonces estarán presentes nodos para (bca), (bc), (b) y (). Hay un arco dirigido "hijo" de color negro desde cada nodo a un nodo cuyo "Camino" se obtiene añadiendo un carácter. Por lo tanto, hay un arco negro de (bc) a (bca). Hay un arco dirigido "sufijo" de cada nodo al nodo correspondiente a su sufijo propio más largo en el grafo. Por ejemplo, para el nodo (caa), su sufijos propios son (aa), (a) y (). El más largo de estos que existe en el grafo es (a), por lo que hay un arco azul de (caa) a (a). Hay un arco ve

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in spagnolo, in ordine alfabetico).
Fonte: Wikipedia in spagnolo, voce «Algoritmo de búsqueda de cadenas Aho-Corasick» — https://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda_de_cadenas_Aho-Corasick
Wikidata Q402342: «string searching algorithm» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q402342
Autori: i contributori di Wikipedia (cronologia: https://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda_de_cadenas_Aho-Corasick?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 175807316, consultata il 2026-10-17T06:37:27.819Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 36839dd77372aa2632520cd875d65095244c0060641c0ed0092a375a10e6bb9c