Dado un texto txt[0..n-1] y un patrón pat[0..m-1], escriba una función de búsqueda (char pat[], char txt[]) que imprima todas las apariciones de pat[] en txt []. Puede suponer que n > m.
¿Patrón de preprocesamiento o texto de preprocesamiento?
Hemos discutido los siguientes algoritmos en las publicaciones anteriores:
Algoritmo KMP Algoritmo
Rabin Karp Algoritmo
basado en autómatas finitos Algoritmo
Boyer Moore
Todos los algoritmos anteriores preprocesan el patrón para que la búsqueda de patrones sea más rápida. La mejor complejidad de tiempo que podríamos obtener mediante el patrón de preprocesamiento es O(n), donde n es la longitud del texto. En esta publicación, discutiremos un enfoque que preprocesa el texto. Se construye un árbol de sufijos a partir del texto. Después de preprocesar el texto (construir el árbol de sufijos de texto), podemos buscar cualquier patrón en tiempo O(m) donde m es la longitud del patrón.
Imagine que ha almacenado el trabajo completo de William Shakespeare y lo ha preprocesado. Puede buscar cualquier string en el trabajo completo en un tiempo proporcional a la longitud del patrón. Esta es realmente una gran mejora porque la longitud del patrón es generalmente mucho más pequeña que la del texto.
El procesamiento previo del texto puede volverse costoso si el texto cambia con frecuencia. Sin embargo, es bueno para texto fijo o texto que cambia con menos frecuencia.
Un árbol de sufijos para un texto dado es un árbol comprimido para todos los sufijos del texto dado . Hemos discutido Standard Trie . Entendamos Compressed Trie con la siguiente array de palabras.
{bear, bell, bid, bull, buy, sell, stock, stop}
El siguiente es un intento estándar para el conjunto de palabras de entrada anterior.
Lo siguiente es el trie comprimido. Compress Trie se obtiene a partir de trie estándar uniendo strings de Nodes individuales. Los Nodes de un trie comprimido se pueden almacenar almacenando rangos de índice en los Nodes.
¿Cómo construir un árbol de sufijos para un texto dado?
Como se discutió anteriormente, Suffix Tree se comprime de todos los sufijos, por lo que los siguientes son pasos muy abstractos para construir un árbol de sufijos a partir de un texto dado.
1) Generar todos los sufijos del texto dado.
2) Considere todos los sufijos como palabras individuales y construya un trie comprimido.
Consideremos un texto de ejemplo “banana\0” donde ‘\0’ es un carácter de terminación de string. Los siguientes son todos los sufijos de “banana\0”
banana\0 anana\0 nana\0 ana\0 na\0 a\0 \0
Si consideramos todos los sufijos anteriores como palabras individuales y construimos un trie, obtenemos seguimiento.
Si unimos strings de Nodes individuales, obtenemos el siguiente trie comprimido, que es el árbol de sufijos para el texto dado «banana\0»
Tenga en cuenta que los pasos anteriores son solo para crear manualmente un árbol de sufijos. Discutiremos el algoritmo real y la implementación en una publicación separada.
¿Cómo buscar un patrón en el árbol de sufijos construido?
Hemos discutido anteriormente cómo construir un árbol de sufijos que se necesita como un paso de preprocesamiento en la búsqueda de patrones. Los siguientes son pasos abstractos para buscar un patrón en el árbol de sufijos creado.
1) Comenzando desde el primer carácter del patrón y la raíz del Árbol de Sufijos, haga lo siguiente para cada carácter.
….. a) Para el carácter actual del patrón, si hay un borde del Node actual del árbol de sufijos, siga el borde.
….. b) Si no hay borde, imprime «el patrón no existe en el texto» y regresa.
2) Si se han procesado todos los caracteres del patrón, es decir, hay una ruta desde la raíz para los caracteres del patrón dado, imprima «Patrón encontrado».
Consideremos el patrón de ejemplo como «nan» para ver el proceso de búsqueda. El siguiente diagrama muestra el camino seguido para buscar «nan» o «nana».
¿Como funciona esto?
Cada patrón que está presente en el texto (o podemos decir cada substring de texto) debe ser un prefijo de uno de todos los sufijos posibles. La declaración parece complicada, pero es una declaración simple, solo necesitamos tomar un ejemplo para verificar su validez.
Aplicaciones del árbol de
sufijos El árbol de sufijos se puede utilizar para una amplia variedad de problemas. Los siguientes son algunos problemas famosos en los que los árboles de sufijos proporcionan una solución óptima de complejidad de tiempo.
1) Búsqueda de patrones
2) Encontrar la substring repetida más larga
3) Encontrar la substring común más larga
4) Encontrar el palíndromo más largo en una string
Hay muchas más aplicaciones. Vea esto para más detalles.
La construcción del árbol de sufijos de Ukkonen se analiza en los siguientes artículos:
Construcción del árbol de sufijos de Ukkonen – Parte 1
Construcción del árbol de sufijos de Ukkonen – Parte 2
Construcción del árbol de sufijos de Ukkonen – Parte 3
Construcción del árbol de sufijos de Ukkonen – Parte 4
Construcción del árbol de sufijos de Ukkonen – Parte 5
Construcción del árbol de sufijos de Ukkonen – parte 6
Referencias:
http://fbim.fh-regensburg.de/~saj39122/sal/skript/progr/pr45102/Tries.pdf
http://www.cs.ucf.edu/~shzhang/Combio12/lec3.pdf
http: //www.allisons.org/ll/AlgDS/Tree/Suffix/
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA