Algoritmos De Busqueda

Inacap La Serena
Ingenieria en informática
|
Análisis de Algoritmos |
Algoritmos de Búsqueda de texto |
|
|
10/05/2011 |

|

Integrantes:

Introducción

La búsqueda de patrones en un texto es un problema importante en la práctica. Ya que sus aplicaciones en computación son variadas, como por ejemplo la búsqueda de una palabra en un texto o problemas relacionados conbiología computacional, en donde se requiere realizar la búsqueda de patrones dentro de una secuencia de ADN, la cual puede ser modelada como una secuencia de caracteres.
Para que tenga una noción mas clara acerca de lo que se le está hablando, a continuación se le mostrara en forma grafica y con ejemplos como funcionan cada uno de estos algoritmo de búsqueda en textoKMP(Knuth-Morris-Pratt)
El algoritmo KMP, consta en encontrar la posición de comienzo de una cadena dentro de otra
Antes que todo, se pre calculada una tabla de saltos que normalmente es llamada FailureFunction.
FailureFunction puede ser representada como un arreglo y está calculada en orden de O(m).

void FailureFunction(char P[], int F[],int m){
int i,j;
F[0]=0; // asignamos a 0
j=0;
i=1;while(i<m){ //mientras i sea menor al largo del patrón
if(P[i]==P[j]){
F[i]=j+1;
i++;
j++;
}else if(j>0){
j=F[j-1];
}else {
F[i]=0;
i++;
}
}
}

Tenemos X que es la parte de lo que deseamos buscar (patrón), e Y la correspondiente al texto donde estamos buscando, y j el largo del patrón X.
En este algoritmo X es = a Y al momento de evaluar, por lo que miraprincipalmente al patrón de búsqueda. Con lo que permite pre calcular la respuesta y almacenarla en una tabla como se mencionaba anteriormente.
Por lo tanto, si deslizar el patrón en una posición no funciona, se puede intentar deslizarlo en 2, 3, ..., hasta j posiciones.
Se define la función de fracaso (failure function) del patrón como:
f(j) = max(i < j b1 .. bi = bj=i+1 …bj)

Entonces loque hace Failure función en primer lugar es evaluar desde i=1 hasta j(largo de patrón)
Intuitivamente, f(j) es el largo del mayor prefijo de X que además es sufijo de X. Note que j = 1 es un caso especial, puesto que si hay una discrepancia en b1 el patrón se desliza en una posición.
Si se detecta una discrepancia entre el patrón y el texto cuando se trata de calzar bj+1, se desliza el patrón demanera que bf(j) se encuentre donde bj se encontraba, y se intenta calzar nuevamente.

Suponiendo que se tiene f(j) o FailureFunction pre calculado, la implementación del algoritmo KMP es la siguiente:
int KMP(char T[], char P[]){
int i,j,F[100]; // máximo del tamaño del de la cadena del patron(texto a buscar)
int m=strlen(P);
int n=strlen(T);
FailureFunction(P,F,m); //(PAtron, VectorAlmacen, largoPatrón)
i=0;
j=0;
while(i<n){
if(T[i]==P[j]){
if(j==m-1)
return i-j; // es decir, en (i-j)la posición donde el matching ocurre
else{
i++;
j++;
}
}else if(j>0){
j=F[j-1];
}else{
i++;
}
}
return -1; // No encontró marcas
}

Algoritmo de Boyer-Moore

Es el algoritmo que el patrón es comparado con el texto dederecha a izquierda, empezando a comparar desde el último carácter el patrón y va avanzando de una posición cuando el patrón en relación con el texto no es compatible.

Más adelante se le va a mostrar dos variantes de este caso que son:
* Boyer-Moore-Horspool (BMH)
* Boyer-Moore-Sunday (BMS)

BMH:
Este algoritmo compara el patrón con el texto de derecha a izquierda, y se detiene cuandoencuentra una similitud con el texto, y cuando esto sucede el índice del patrón va avanzando un espacio para verificar si la otra letra del patrón es igual a la del texto ejemplo:
Código del algoritmo de búsqueda:
m ->es el largo del patrón
Los índices comienzan desde 1

int k=m;
int j=m;
while(k<=n && j>=1){
if (texto[k-(m-j)]==patron[j]) {
j--;...