Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Knuth Morris Pratt

No description
by

Juliana Buitrago

on 6 July 2011

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Knuth Morris Pratt

Knuth Morris Pratt Es Algoritmo de manejo de cadenas de texto,
para la búsqueda exacta de patrones. Objetivo El algoritmo  tiene por objeto buscar
la existencia de palabra dentro de
una cadena de texto.

Dado un texto T de longitud n -> entrada
Dado un patrón P de longitud m -> palabra a buscar

Buscar en todas las posiciones del texto
En las cuales aparece el patrón A menudo se compara el algoritmo KMP
con el de fuerza bruta. Tambien llamado “el algoritmo más simple” , consiste,
obviamente, en comparar el patrón con todas las posibles
posiciones del texto

Existen n posiciones en el texto
Existen m posiciones en el patrón

Serán necesarias nxm comparaciones Fuerza Bruta KMP es similar al algoritmo de Fuerza Bruta, pero con la ventaja de que reutiliza la información de comparaciones anteriores.


Preprocesa el patrón (proceso previo PP) para asociar a cada carácter
que lo forma la longitud del prefijo más largo posible
que sea a su vez un sufijo de la cadena de caracteres
que precede al patrón y que los caracteres siguientes
al prefijo y al sufijo sean diferentes

p a r t i c i p a r
0 0 0 0 0 0 0 1 2 3 El algoritmo KMP, trata de localizar la posición de comienzo de una cadena,
dentro de otra. Antes que nada con la cadena a localizar se precalcula una
tabla de saltos (conocida como tabla de fallos) que después al examinar entre
si las cadenas se utiliza para hacer saltos cuando se localiza un fallo. Diferencia entre KMP y Fuerza Bruta La diferencia con fuerza bruta es que éste compara el patrón
con todas las posibles posiciones del texto (nxm), mientras que
KMP utiliza información basada en los fallos previos, aprovechando
la información que la propia palabra a buscar contiene de sí
(sobre ella se pre calcula una tabla de valores), para determinar
donde podría darse la siguiente existencia, sin necesidad de
analizar más de 1 vez los caracteres de la cadena donde se busca. Ejemplo de proceso previo Algoritmo de Proceso_Previo
PP[0] = 0;
j = 0;
i = 1;
mientras(i<m) // m=8 ,largo de P si (P[i] = P[j] )
PP[i]=j+1;
i++; j++;
sino
si (j>0)
j=PP[j-1];
sino
PP[i]=0;
i++;
return PP; Casos que se presentan Caso 1 : Si (Pj !=Ti and j=0 )
el patrón reanuda las comparaciones un
lugar mas adelante.

Caso 2 : Si (Pj ==Ti and j != m-1 )
Tanto el Ti como el Pj pasan al siguiente
índice para volver a comparar.

Caso 3 : Si (Pj !=Ti and j>0 )
el patrón cambia de lugar en la posición
inicial i=i-PP[j-1] y reanuda las comparaciones en
donde falló.

Caso 4 : Si (Pj =Ti and j=m-1)
el patrón es reconocido en el texto y se retorna la
posición inicial . Mejor Caso Peor Caso KMP aprovecha el “conocimiento” adquirido en las anteriores comparaciones. En cuanto al número de comparaciones tenemos q el algoritmo de Búsqda Directa emplea por lo general un número proporcional a n·m. En el mejor de los casos :

n = m y T=P,
donde :
T=l texto
P= patrón
n=Longitud del Texto
m= Longitud de Patrón
Por otra parte tenemos q el algoritmo KMP emplea como máximo n comparaciones, por lo q podemos decir q es más eficiente. Siendo el peor caso que n!=m y T!=P Complejidad Debido a que el algoritmo precisa de 2 partes donde se analiza una cadena en cada parte, la complejidad resultante es O(k) y O(n), cuya suma resulta ser
O(n + k). KNUTH MORRIS PRATT
KMP


Juliana Buitrago I. GRACIAS! KMP
Full transcript