ıllı Internet y Tecnologías de la Información (2018)

internet, Hosting, dominios, seo, antivirus, banco de imágenes, páginas web, tiendas online

[Enciclopedia Online Gratuita] Diccionario de Internet y Tecnologías de la Información y la Comunicación (TIC):

ıllı Algoritmo Knuth-Morris-Pratt wiki: info, historia y vídeos

videos internet

salud  Algoritmo Knuth-Morris-Pratt 


El objetivo de la tabla (precalculada) de fallo 'F' es no dejar que cada carácter del array 'T()' sea examinado más de 1 vez. El procedimiento clave para conseguir esto, consiste en haber comprobado algún pedazo de la cadena donde se busca con algún pedazo de la cadena que se busca, lo que nos da exactamente en qué sitios potenciales puede existir una nueva coincidencia, sobre el ámbito analizado que señala fallo.


Dicho de otra forma, partiendo del texto a buscar, realizamos una lista con todas y cada una de las situaciones, de salto atrás que señalen cuanto se recula desde la situación actual del texto a buscar. Por servirnos de un ejemplo si el texto a buscar es 'esconderse' y estamos examinando un texto como 'se ocultan tras la mesa', cuando llegamos a la 2ª 'n' de 'esconden' (situación siete en el texto a buscar es una 'r'), falla, el interrogante lógica sería ¿ dónde está nuevamente (si existe) la primera letra en el texto 'esconderse'(ya antes del fallo), y hasta donde consigue repetirse ?. La contestación a esta pregunta va a ser el punto de salto, en el caso propuesto ('esconderse'). Dicho punto se halla en la situación seis (ya antes de la 'r'), entonces para la tabla en la próxima situación debería haber un 1.


Por tanto esta tabla se elabora con la distancia que existe desde determinado punto en la palabra a la última ocurrencia (de la 0ª letra de la palabra) diferente de la primera vez que aparece,y mientras que prosigan coincidiendo, se marca la distancia, cuando haya una rotura de coincidencia se marca 0 o bien un valor anterior ya calculado previamente, y de esta forma consecutivamente hasta acabar con el texto.


La tabla tiene sus dos primeros valores fijados, de forma que la función de fallo comienza siempre y en todo momento examinando el tres carácter del texto. La razón por la cual dichos valores están fijados es obvia: si para el 2º carácter se marcase 1, jamás se conseguiría un salto, puesto que siempre y en toda circunstancia regresaría a dicho punto. En lo que se refiere al primero, por necesidad se marca -1, puesto que de esa manera le resulta imposible volver más atrás, sino más bien siempre y en todo momento adelante.


Una forma de comprender adecuadamente el funcionamiento del algoritmo es continuar punto por punto un caso reseñando en todos y cada punto lo que hace o bien puede hacer el algoritmo en una situación dada.


Se considera tanto en los ejemplos como en el pseudocódigo que los array de caracteres se fundamentan en índice 0.


Sean dos cadenas, que se entregan como arrays de caracteres a la función, donde T es el array de caracteres donde deseamos buscar y P el array que se quiere encontrar en T, utilizando k como puntero absoluto para los caracteres de T y también i como puntero para los caracteres de P. Se emplea asimismo, una tabla (matriz) precalculada de la palabra a buscar F. Ahora se ve una figura que representan las variables consideradas para el ejemplo.

k: 01234567890123456789012T: ABC ABCDAB ABCDABCDABDEP: ABCDABDi: 0123456F:-1000012

Se muestra la tabla F, precalculada para el ejemplo.

i0123456PBCDABDF1000012
k: 01234567890123456789012T: ABC ABCDAB ABCDABCDABDEP: ABCDABDi: 0123456F:-1000012

Comienza el cálculo, los punteros 'k' y también 'i' en un inicio valen 0. Si P(i) = T(k + i), se valora ahora si i = tamaño de P en tal caso se habría encontrado la situación de la cadena. De lo contrario, se acrecienta 'i'. Esto sucede tres veces, hasta el momento en que en la 4ª ocasión, en P(tres) tenemos 'D' y en T(k + i) tenemos ' '(un espacio), instante en que actualizamos 'k', k = k + i - F(i) (k = tres). Ahora comprobamos si F(i) > -1 (F(tres) vale 0), como se da el caso hacemos para i = F(i). Esto es brincamos a la situación sobre el array 'P' que apunta 'F(i)', que en un caso así es 0, en consecuencia al comienzo del array 'P', mas ahora el puntero del array 'T' está en tres (k = tres).


Por tanto en la próxima figura avanzamos hasta la situación absoluta de T actual, tres.

k: 01234567890123456789012T: ABC ABCDAB ABCDABCDABDEP: ABCDABDi: 0123456F: -1000012

Volvemos al comienzo del bucle (toda vez que se vuelve a este punto se verifica si 'k' alcanzó el tamaño de 'T' y nuevamente comprobamos si P(i) = T(k + i). Vemos que en el punto actual en 'P' hay un espacio, con lo que, de nuevo se actualiza 'k', k = k + i - F(i) (k = cuatro), pues 'F(i) = -1'. Ahora entonces se hace i = 0 (si bien ya antes asimismo era 0).


Como volvemos al comienzo del bucle (se da por comprobado si el bucle concluye), actualizamos la figura con el puntero en 'k', (k = cuatro)

k: 01234567890123456789012T: ABC ABCDAB ABCDABCDABDEP: ABCDABDi: 0123456F: -1000012

Ahora vemos que múltiples veces se cumple que P(i) = T(k + i), mas no tantas que se alcance el tamaño de 'P', y con cada coincidencia 'i' se ha aumentado, con lo que ahora 'i=6', mas se ha aumentado inmediatamente después de contrastar si i = tamaño P entonces devolver k (si no habríamos alcanzado la solución). Al examinar nuevamente al comienzo del bucle la situación seis, falla en tanto que 'P(seis) = D' y 'T(cuatro + seis) =' . en este punto toca actualizar 'k', y hacemos k = k + i - F(i) (k = cuatro + seis - F(seis), en este punto F(seis) vale dos, con lo que por último damos un salto 'k = cuatro + seis - dos = 8'. Y actualizamos 'i', si F(seis) > -1 entonces i = F(i), o sea no solo acanzamos el puntero de 'T', sino además de esto avanzamos el puntero de 'P' a dos, por el hecho de que exactamente en la situación ocho, hay una coincidencia 'AB' tal y como empieza la cadena del array 'w'. es justo y también este punto donde hemos visto el salto y la eficiencia de la tabla F.


Actualizamos la figura, damos por verificado la comprobación del comienzo del bucle.

k: 01234567890123456789012T: ABC ABCDAB ABCDABCDABDEP: ABCDABDi: 0123456F: -1000012

Una nueva vez volvemos revisar si P(i) = T(k + i) (P(dos) = T(8+2)), o sea 'C' = ' '), como falla toca actualizar el puntero de 'T'. k = k + i - F(i) (k=8 + dos - 0 = diez), y actualizamos 'i', (si F(i) > -1 entonces i = F(i)) 'i = 0'.


Actualizamos a la próxima figura (como toda vez que se actualiza 'k' el puntero absoluto de 'T').

k: 01234567890123456789012T: ABC ABCDAB ABCDABCDABDEP: ABCDABDi: 0123456F: -1000012

Con la próxima comparación asimismo falla en tanto que 'A' <> ' ', y de nuevo debe actualizarse el puntero 'k', con su salto de tabla (si procede), k = k + i - F(i) (k = diez + 0 - (-1) = once), y asimismo actualizamos 'i', como esta vez 'F(i)= -1', entonces volvemos al comienzo de 'P', o sea i = 0.


Actualizamos la figura a la nueva situación que apunta el puntero de 'T', (k = once)

k: 01234567890123456789012T: ABC ABCDAB ABCDABCDABDEP: ABCDABDi: 0123456F: -1000012

En esta ocasión nuevamente múltiples veces se cumplirá que P(i) = T(k +i), hasta el momento en que se llega a la situación de 'i = seis, que sucede que 'P(seis)=D' que esdistinto de 'T(once + seis)=C', por tanto es preciso una nueva bifurcación cara la actualización de 'k', k = k + i - F(i) (k = once + seis - dos = quince). Nuevamente entra en juego el salto de la tabla, pues 'F(i) = 2', toca actualizar 'i', si F(i) > -1 entonces i = F(i), en consecuencia 'i = dos.


Actualizamos de nuevo la figura, hasta avanzar hasta 'k = 15'.

k: 01234567890123456789012T: ABC ABCDAB ABCDABCDABDEP: ABCDABDi: 0123456F: -1000012

Como 'i = 2' (por el hecho de que logramos avanzar hasta el índice seis que en la tabla vale dos, por el hecho de que ya antes de la 'D' final hay dos situaciones coincidentes sucesivamente), entonces ahora volvemos a hacer las comprobaciones mas ahora en quince + dos, que era: Si P(i) = T(k + i) entonces... si i = tamaño de w entonces devolver k. Esta parte se cumple hasta por último localizar por completo la cadena, antes que 'i' pueda ser aumentado a siete en la parte que prosigue a la condición precedente i = i + 1 .



El algoritmo Knuth-Morris-Pratt efectúa veintiseis comparaciones (y el último carácter de la cadena buscada se encuentra en la situación veintiuno) en el ejemplo, hasta hallar la solución, en la situación quince. Es preciso rememorar únicamente que al estar basado en array en índice 0, la solución es quince, si bien por otro lado, en las figuras se ve de qué manera los punteros de 'k' y también 'i' comienzan en 0.


  ELIGE TU TEMA DE INTERÉS: 


autoayuda.es   Internet y Tecnologias 

Está aquí: Inicio > [ INTERNET ] > ıllı Algoritmo Knuth-Morris-Pratt wiki: info, historia y vídeos

Las cookies nos permiten ofrecer nuestros servicios. Al utilizar nuestros servicios, aceptas el uso que hacemos de las cookies. Ver políticas