Alumno: José Luis Segura Velázquez 8157349
Profesora: Mtra. Maria Elena Chávez Solís
Materia: Tópicos Selectos de Algoritmos
Autores
• El algoritmo fue publicado en 1977 por :
– Donald Ervin Knuth(1938): Es uno de los más reconocidos
expertos en ciencias de la computación por su
investigación dentro del análisis de algoritmos y
compiladores. Es Profesor Emérito de la Universidad de
Stanford.
– Vaughan Ronald Pratt (1944): Es uno de los pioneros en el
campo de la ciencia computacional, sus principales
aportaciones son en la materia de algoritmos de busqueda
y de ordenamiento
– James Hiram Morris (1941): Desarrollo conceptos
fundamentales en la teoría de lenguajes computacionales
como : protección inter módulos y evaluación tardía de
variables.
Descripción
• El algoritmo de Knuth-Morris-Pratt es un método lineal
para la búsqueda exacta de patrones.
• Se basa en el hecho que, después de encontrar el
primer símbolo que no coincide entre el patrón y la
secuencia, nosotros ya conocemos los símbolos del
patrón que hemos comparado hasta ese punto.
• De esta manera, se consigue que después de un
emparejamiento incorrecto el proceso no continúe
(desde el inicio del patrón) con el siguiente carácter de
la secuencia, y así no tener que comparar posiciones
que ya se sabe previamente que no darán lugar a una
ocurrencia exacta del patrón.
Eficiencia
• Las particularidades de este algoritmo son que
es capaz de realizar la búsqueda en un tiempo
lineal, con un tiempo adicional de pre
procesado que es lineal al patrón que vamos a
buscar. Lo cual hace una aproximación para
realizar las búsquedas rápidamente.
• Denotado como: O(m+n)
Descripción
• El KMP se beneficia de la información que el propio patrón
contiene ya que se desconoce la secuencia donde se realiza
la búsqueda.
• Para aprovechar este hecho, hay que construir una tabla de
desplazamientos coincidentes dentro del patrón antes de
empezar la búsqueda.
• Esta tabla, llamada next table, tiene una posición para cada
posición del patrón, y en cada posición n se introducirá el
número máximo de símbolos coincidentes con el patrón
antes de esa posición (sin coincidir el prefijo entero de n
símbolos). Es decir, en cada posición n se comprueban las
coincidencias existentes entre los diferentes prefijos de n y
el patrón que precede a n.
Pseudocódigo de
Pre procesamiento
• Algoritmo next_table:
– entrada:
• char [] W (El patron a buscar)
• int [] T (la tabla que se llenara)
– salida:
• nada (solo se llena la tabla en el proceso)
– variables:
• int pos ← 2 (la posicion que estamos procesando en T)
• int cnd ← 0 (El indice con base 0 en W del siguiente
caracter de la subcadena candidata)
– T[0] = -1, T[1] = 0
– while (pos < W.lenght)
if (W[pos - 1] = W[cnd])
T[pos] = cnd + 1, pos++ , cnd++
else if (cnd > 0)
cnd = T[cnd]
else
T[pos] = 0, pos++
Pseudocódigo de
Búsqueda
• Algoritmo kmp_search:
– entrada:
• char [] S (El texto donde se buscará)
• char [] W (El patron a buscar)
– salida:
• Un int (el índice con base 0 de S donde W es encontrado)
– variables:
• int m = 0 (el inicio de la concidencia actual en S)
• int i = 0 (la posición del caracter actual en W)
• int [] T (la tabla que se pre proceso)
Pseudocódigo de
Búsqueda
– while (m + i < S.length)
if (W[i] = S[m + i])
i = i++
if (i == W.length)
return m
else
m = m + i - T[i]
if (T[i] > -1)
i = T[i]
else
i=0
(Si se llega a este punto entonces no se encontró el patron)
return S.length
Ejemplo
• Encontrar el patrón: GCAGAGAG
• En el texto: GCATCGCAGAGAGTATACAGTACG
• La tabla calculada es:
Descargar

knuth-morris_luissegura