TRABAJO FINAL ALGORITMOS II:
Algoritmos de String Matching
Integrantes:
Barragn, Ariel
Giorda, Mauro
Docente:
1
Favre, Liliana
SUMARIO
Como esta organizada nuestra charla:
Introduccin a String Matching
Objetivos del proyecto y de la aplicacin
Componentes de la aplicacin
Herramientas del programa
Algoritmos implementados
Detalles de diseo
Ejemplos utilizando el programa 2
INTRODUCCION
String matching es el problema de la bsqueda de
ocurrencias de un patrn dentro de una cadena de texto. Su
utilidad comprende tanto editores de texto como complejas
secuencias de ADN.
Un tipo de clasificacin posible es:
Preprocesamiento
Algoritmos Ninguno Patrn Texto
Fuerza Bruta
Rabin-Karp
Autmata Finito
Knuth-Morris-Pratt
Boyer-Moore
Index. Longitud 3
Index. Letra
OBJETIVOS
4
COMPONENTES DE LA APLICACIN
Seguimiento del algoritmo Fuerza Bruta
Lista de operaciones
Rabin-Karp
Visor de estado
Esquema de autmata Autmata Finito
Informacin de resultados Knuth-Morris-Pratt
Cantidad de ocurrencias Boyer-Moore
Tiempo de procesamiento
Index. Longitud
Comparaciones carcter a
carcter Index. Letra 5
HERRAMIENTAS DEL PROGRAMA
Herramienta
de bsqueda
Lista de
operaciones
Resultados
obtenidos
Visor de estado
Esquema de
Autmata
6
ALGORITMO: FUERZA BRUTA
MEJORADO
Caractersticas PseudoCodigo
Pseudo Cdigo
Pre-procesamiento: FUERZA-BRUTA(T,P){
ninguno n = longitud(T);
m= longitud(P);
for (s=0; s <= n-m; s++){
Complejidad: O(n.m)
j = s; k= 1;
while( P[k] == T[j])
Desplazamiento: siempre if (k == j)
uno a la derecha cout<< ocurrencia<<s;
else
j++; k++;
} 7
}
ALGORITMO: RABIN-KARP
Caractersticas Pseudo Cdigo
Pseudo Codigo
Pre-procesamiento: RABIN-KARP(T,P,d,q){
patrn en O(m) n = longitud(T);
m= longitud(P);
Complejidad: O(n.m) p = Hash(P,d,q);
t0 = Hash(T[1..m],d,q);
Desplazamiento: siempre for (s=0; s <= n-m; s++){
uno a la derecha if (p == ts)
if (P[1..m] == T[s..s+m]
Usa una funcion de cout<< ocurrencia<< s;
Hashing (Rolling hash)
ts+1= RollingHash(T[s+1], d,q)
Eficiente para patrones
} 8
mltiples }
ALGORITMO: AUTMATA FINITO
Caractersticas Pseudo Cdigo
Pseudo Codigo
Pre-procesamiento: A-FINITO-MATCHER(T,P){
patrn en O(m3||) n = longitud(T);
m = longitud(P);
Complejidad: O(n) q = 0;
for (s=0; s <= n; s++){
Desplazamiento: q = d(q,T[s]);
siempre uno a derecha if (q == m)
Lee cada carcter del cout<< ocurrencia<< s;
texto solo una vez }
}
Genera un AF
determnistico
9
ALGORITMO: KNUTH-MORRIS-PRATT
Caractersticas Pseudo Cdigo
Pseudo Codigo
Pre-procesamiento: KNUTH-MORRIS-PRATT(T,P){
patrn en O(m) n = longitud(T);
m = longitud(P);
F = FuncionPrefijo(P);
Complejidad: O(n+m)
q=0;
for (i=1;i<=n; i++){
Desplazamiento:
while (q >0 and P[q+1] <> T[i]
siempre uno a derecha
q = P[q];
Genera una tabla con if (P[q+1] == T[i]) q=q+1;
la funcin prefijo if (q=m) {cout <<ocurrencia<< i-m;
q = P[q];
Reconstruye en la tabla }
cualquier transicin }
} 10
ALGORITMO: BOYER-MOORE
Caractersticas Pseudo Cdigo
Pseudo Codigo
BOYER-MOORE(T,P, ){
Pre-procesamiento: patrn en n = longitud(T);
O(m)
m = longitud(P);
BC[ ] = BadCharacter(P,m,);
Complejidad: O(n) en el peor caso GS[ ] = GoodSuffix(P,m);
y O(n/m) en el mejor
q=0;
while (q <= n m){
Desplazamiento: variable j = m;
while (q >0 and P[q] == T[q + j]
q = q 1;
Compara de atrs hacia delante del if (j == 0)
patrn
cout << ocurrencia;
q = q + GS [0];
Utiliza dos funciones para el pre else
procesado, BadCharacter y
GoodSuffix q = q + max ( GS [ j ], j BC [ T [q+j] ] );
}
11
}
Bad-Character. Luego del mismatch con b, se detecta una b
ms a la izquierda en el patrn e indica ese desplazamiento.
12
Good-Suffix. Luego del mismatch con b, se encuentra el sufijo u ms a
la izquierda en el patrn precedido por c e indica ese desplazamiento.
ALGORITMO: INDEXACIN POR LONG. DE PALABRA
Caractersticas Pseudo Cdigo
Pseudo Codigo
Pre-procesamiento: texto en INDEX-LONGITUD(T,P){
O(n).
n = longitud(T);
Complejidad: segn el mtodo
m = longitud(P);
elegido para las comparaciones. if(I[] == null)
I[] = tablaIndexLONG(T);
Desplazamiento: variable
L[] = I[m];
q = 0;
Alta eficiencia en textos estticos while ( L[q] <= n-m ){
algBusq(T[ L[q]..L[q] + m],P);
Indexa el texto segn longitud de
las palabras
q++;
} 13
}
ALGORITMO: INDEXACIN POR LETRA
Caractersticas Pseudo Cdigo
Pseudo Codigo
Pre-procesamiento: texto en INDEX-LETRA(T,P){
O(n)
n = longitud(T);
Complejidad: segn el mtodo m = longitud(P);
elegido para las comparaciones.
if(I[][] == null)
Desplazamiento: variable I[][] = tablaIndexLETRA(T);
L[] = I[ P[1] ];
Implementa una variante en el q = 0;
mtodo de indexacin
while ( L[q] <= n-m ){
Indexa el texto segn la posicin algBusq(T[ L[q]..L[q] + m],P);
de cada letra
q++;
14
}
DETALLES DE DISEO
15
DETALLES DE DISEO CONT.
16