Ir al contenido principal

Algoritmo de Boyer Moore Horspool en C++


Características
  • Es una simplificación del algoritmo de Boyer-Moore.
  • Es fácil de implementar.
  • Existe un preprocesamiento del patrón.
  • Necesita O(σ)en espacio y O(m+σ)en tiempo (por el preprocesamiento).
  • Realiza saltos determinados en el preprocesamiento.
  • Compara de derecha a izquierda.
  • Realiza la búsqueda del patrón en un tiempo O(mn).
  • Realiza un número promedio de comparaciones para un carácter entre 1/σy 2/(σ+1).
Lógica
  • Se calcula el preprocesamiento del patrón de la siguiente forma:
  • Se calcula la distancia mínima entre el último carácter y la ocurrencia de cada carácter del alfabeto de la hilera principal.

Para realizar la búsqueda:

Consiste en la comparación de cada carácter del texto con las posiciones del patrón en el orden m-1, 0, 1, 2, …, y m-2, si se da una ocurrencia del patrón o no.
Cuando se encuentra una no ocurrencia, al hacer la primera comparación entre el patrón y el texto, el salto se calcula bmBc[c], donde ces el carácter del texto.
Cuando se encuentra una no ocurrencia o una ocurrencia total, al hacer las siguientes comparaciones entre el patrón y el texto, el salto se calcula bmBc[c], donde ces el carácter del patrón.

Descripción

Es considerado el mejor algoritmo de búsqueda de un patrón en un texto en aplicaciones usuales.
El algoritmo escanea los caracteres del patrón con el texto iniciando con el carácter más a la derecha.
En caso de una no ocurrencia o una ocurrencia total del patrón se usa una función preprocesada para saltar:
Salto del mal carácter(bad-character shift) (o salto de ocurrencia).
Horspool propuso utilizar solamente el salto del mal carácter para calcular los saltos en el algoritmo de Boyer-Moore.

El salto del mal carácter consiste en:

Alinear cada carácter del alfabeto Σ con la ocurrencia más a la derecha en x[0, …, m-2].
Si el carácter no ocurre en el patrón x, la no ocurrencia de x puede incluir el carácter, y alinearlo en el lado más izquierdo del patrón.
Esta operación (usada en el algoritmo BM) no es muy eficiente para alfabetos pequeños, pero cuando el alfabeto es grande comparado con la longitud del patrón llega a ser muy útil. Usarlo sólo produce un algoritmo muy eficiente en la práctica.

Ejemplo

El algoritmo encuentra todas las ocurrencias del patrón en el texto.

El patrón se denota por x = x[0, ..., m-1]; su longitud es igual a m.
El texto se denota por y = y[0, ..., n-1]; su longitud es igual a n.
Ambas secuencias son estructuras sobre un sistema finito de caracteres llamado alfabetodenotado por S, con tamaño igual a s.

x = GCAGAGAG
y = GCATCGCAGAGAGTATACAGTACG



Implementación

Entradas populares de este blog

Obtener numeros aleatorios en C++ (rand, srand)

Es algo muy frecuente, cuando ya dominas todo eso de pedir y almacenar datos, ahora tu profesor te pedirá que tus programas generen números aleatorios para automatizar el proceso de llenar arreglos y todo eso.
Así que lo primero que tenemos que hacer es incluir la librería:
#include<stdlib.h>

Necesitamos esta libreria para usar la función time()
#include<time.h>

Luego inicializar los números aleatorios incluyendo esto:
srand(time(NULL));

Luego guardar el número aleatorio en alguna parte:
num = rand();

Para ajustar el rango de número aleatorios podemos hacer varias cosas.

- Número aleatorios entre 0 y 50:
  num=rand()%51;

- Número aleatorios entre 1 y 100:
  num=1+rand()%(101-1);

- Número aleatorios entre 250 y 420:
  num=250+rand()%(421-250);

De forma general es:
variable = limite_inferior + rand() % (limite_superior +1 - limite_inferior) ;

Así que un programa que muestre 10 números aleatorios entre 1 y 10 quedaría así:

Serie de Fibonacci en C++

Una sucesión de Fibonacci es aquella cuya ley de recurrencia es: an = an-1 + an-2. Es decir, cada término de la sucesión se obtiene sumando los dos anteriores. Para empezar a construirla necesitamos, por tanto, dos números de partida, a1 y a2. De esta forma, a3 sería a2 + a1 ; a4 sería a3 + a2 y así sucesivamente.


La más conocida es la que tiene a1 = 1 y a2 = 1, cuyos términos son: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377 ... números que son conocidos como Números de Fibonacci.

Los términos de cualquier sucesión de Fibonacci tienen la particularidad de que el cociente entre dos términos consecutivos se aproxima al Número de Oro (1.6180339887499...), es decir, el límite de los cocientes an+1/an tiende al Número de Oro cuando n tiende a infinito.

Además, las series de Fibonacci cumplen otras curiosas propiedades, como por ejemplo, que la suma de n términos es igual al término n+2 menos uno:

a1 + a2 + a3 + a4 + ..... + an-1 + an = an+2 - 1

Implementación

Árboles Binarios de Búsqueda en C++ | Recorrido por niveles (Amplitud)

Hola a todos en esta ocasión compartiré sobre este tema de Arboles Binarios de Búsqueda, como un poco de teoría para su mejor entendimiento seguidamente mostraré la implementación en lenguaje de programación C++. Primero una breve introducción a árboles.

¿Qué es un árbol?


Un árbol es una estructura de datos no lineal puesto que cada elemento apunta a uno o varios elementos del mismo tipo; esto es dado un elemento, no hay un único camino a seguir. El elemento que apunta a otro es llamado padre, mientras que el elemento apuntado se conoce como hijo. Todos los elementos tienen un padre a excepción de la raíz. Puede decirse que un árbol esta formado por subárboles resaltando así su naturaleza recursiva.

¿Qué es un árbol binario?

Un árbol binario es aquel es el que cada elemento apunta como máximo a otros 2 elementos, comúnmente llamados hijo izquierdo y hijo derecho.

¿Qué es un árbol binario de búsqueda?

Un árbol binario de buque da o ABB, es un árbol binario en el cual para todo elemento, …