ıllı Internet y Tecnologías de la Información (2018)

internet, Hosting, dominios, seo, antivirus, banco de imágenes, páginas web, tiendas online

[Enciclopedia Online Gratuita] Diccionario de Internet y Tecnologías de la Información y la Comunicación (TIC):

ıllı Algoritmo de búsqueda de cadenas Aho-Corasick : que es, definición y significado, descargar videos y fotos.

COMPARTE EN TU RED SOCIAL PREFERIDA:

videos internet

salud  ıllı Algoritmo de búsqueda de cadenas Aho-Corasick : que es, definición y significado, descargar videos y fotos.  


En Ciencias de la Computación, el Algoritmo de busca de cadenas Aho–Corasick es un algoritmo de busca 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) en un texto. Una de los beneficios que presenta es que procesa el texto de entrada únicamente una vez, esto es, efectúa la busca de todos y cada uno de los patrones de forma simultánea. Si se considera el tamaño del abecedario al que pertenecen los patrones como incesante, entonces la dificultad temporal del algoritmo es lineal en lo que se refiere a la suma de las longitudes de los patrones más la longitud del texto. Si además de esto se quieren conocer todas y cada una de las ocurrencias de forma explícita, al orden del algoritmo hay que sumarle la cantidad de ocurrencias. Es preciso resaltar que si se procuran todas y cada una de las ocurrencias, entonces puede haber un número cuadrático de ellas si cada subcadena es una ocurrencia. Por poner un ejemplo si el diccionario es a, aa, aaa, aaaa y la cadena de entrada es aaaa).


Informalmente, el algoritmo edifica un androide finito determinista afín a un trie con links auxiliares entre los nodos internos. Estos links extras dejan hacer transiciones bastante veloces entre correspondencias erradas de patrones (ejemplo, una busca para cat en un trie que no contiene a cat, mas contiene cart, y de este modo fallaría en el nodo prefijado por ca), a otras ramificaciones del trie que comparten prefijos comunes (ejemplo, en el caso precedente, una ramificación para attribute pudiese ser la mejor transición a realizar). Esto le deja al robot efectuar transiciones entre ocurrencias de patrones sin precisar backtracking.


Cuando el diccionario de patrones se conoce por adelantado (por servirnos de un ejemplo, en una base de datos de virus), la construcción del robot se puede hacer y se guarda el androide compilado para empleo futuro. En un caso así, la dificultad temporal es lineal en lo que se refiere a la longitud de la entrada más el número de entradas encontradas.


El gráfico que se muestra ahora es la estructura Aho-Corasick construida desde el diccionario concretado, con cada fila en la tabla representando un nodo en el trie, y la columna Camino señalando 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. Así, si (bca) está en el diccionario, entonces van a estar presentes nodos para (bca), (bc), (b) y (). Hay un arco dirigido "hijo" negro desde cada nodo a un nodo cuyo Camino se consigue agregando un carácter. Por tanto, hay un arco negro de (bc) a (bca). Hay un arco dirigido "sufijo" de cada nodo al nodo pertinente a su sufijo propio más largo en el grafo. Por poner un 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), con lo que hay un arco azul de (caa) a (a). Hay un arco verde "sufijo en diccionario" desde cada nodo al siguiente nodo en el diccionario que puede ser alcanzado siguiendo arcos azules. Por servirnos de un ejemplo, hay un arco verde de (bca) a (a) por el hecho de que (a) es el primer nodo pertinente a uno de los patrones en el diccionario (nodo blanco) que se alcanza siguiendo los arcos azules a (ca) y después a (a).

A diagram of the Aho-Corasick string search algorithm.svgDiccionario undefinedCaminoEn DiccionarioEnlace sufijoEnlace sufijo en Dicc()-(a)+()(ab)+(b)(b)-()(bc)+(c)(c)(bca)+(ca)(a)(c)+()(ca)-(a)(a)(caa)+(a)(a)

A la hora de encotrar las occurrencias en un texto, en todos y cada paso el nodo actual se extiende encontrando su hijo con el carácter pertinente, y si no existe, se busca se busca su "hijo sufijo" usado en link sufijo y se sigue de esta forma hasta localizar un nodo que tenga una transición con el carácter actual o bien hasta el momento en que se llegue al nodo raíz.


Cuando el algoritmo alcanza un nodo, devuelve todas y cada una de las entradas en el diccionario que acaban en la situación del carácter actual en el texto de entrada. Esto se hace imprimiendo cada nodo alcanzado siguiendo los "links sufijo en diccionario", empezando por ese nodo, y continuando hasta lograr un nodo que no tenga "link sufijo en diccionario".


La ejecución con la cadena de entrada abccab genera los próximos pasos:

Análisis de la cadena abccabNodoCadena que quedaSalida: Situación finalTransiciónSalida()abccabcomenzar en la raíz(a)bccaba:1() a hijo (a)Nodo actual(ab)ccabab:2(a) a hijo (ab)Nodo actual(bc)cabbc:3, c:3(ab) a sufijo (b) a hijo (bc)Nodo actual, Link sufijo en dicc(c)abc:4(bc) a sufijo (c) a sufijo () a hijo (c)Nodo actual(ca)ba:5(c) a hijo (ca)Nodo sufijo en dicc(ab)ab:6(ca) a sufijo (a) a hijo (ab)Nodo actual


COMPARTE EN TU RED SOCIAL PREFERIDA:


  ELIGE TU TEMA DE INTERÉS: 


autoayuda.es   Internet y Tecnologias 

 

USUARIOS:

Hay 70 invitados y ningún miembro en línea

paraiso digital

 

TODO SOBRE:

nuevas tecnologias

Está aquí: Inicio > [ INTERNET ] > ıllı Algoritmo de búsqueda de cadenas Aho-Corasick : que es, definición y significado, descargar videos y fotos.

Las cookies nos permiten ofrecer nuestros servicios. Al utilizar nuestros servicios, aceptas el uso que hacemos de las cookies. Ver políticas