algorithm - rabin - Boyer Moore ¿Algoritmo de comprensión y ejemplo?
kmp search (6)
¿Qué pasa con el sitio web del co-inventor de este algoritmo? ¿Ayuda esto?
http://www.cs.utexas.edu/users/moore/best-ideas/string-searching/index.html
¡aclamaciones!
Estoy enfrentando problemas para entender el algoritmo de búsqueda de cuerdas de Boyer Moore.
Estoy siguiendo el siguiente documento. Link
No soy capaz de encontrar mi camino para determinar exactamente cuál es el significado real de delta1 y delta2 aquí, y cómo están aplicando esto para encontrar el algoritmo de búsqueda de cadenas. El lenguaje se veía poco vago ..
Amablemente, si alguien puede ayudarme a entender esto, sería muy útil.
O, si conoce algún otro enlace o documento disponible que sea fácil de entender, por favor, comparta.
Gracias por adelantado.
Esta explicación de HW Lang es realmente clara, ya que explica B&M caso por caso, con descripciones detalladas. Solo después de leer esto entendí el algoritmo B&M.
http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/bmen.htm
He encontrado este enlace, esto explica el algoritmo de la manera más básica. Espero que esto ayude. http://www.blackbeltcoder.com/Articles/algorithms/fast-text-search-with-boyer-moore
La idea detrás de Boyer-Moore es que si comienza a buscar un patrón en una cadena que comienza con el último carácter en el patrón, puede hacer que su búsqueda avance varios caracteres cuando se encuentra con una discrepancia.
Digamos que nuestro patrón p es la secuencia de los caracteres p1 , p2 , ..., pn y estamos buscando una cadena s , actualmente con p alineada para que pn esté en el índice i en s .
P.ej:
s = WHICH FINALLY HALTS. AT THAT POINT...
p = AT THAT
i = ^
El trabajo de BM hace las siguientes observaciones:
(1) si intentamos hacer coincidir un carácter que no está en p entonces podemos saltar n caracteres hacia adelante:
''F'' no está en p , por lo tanto avanzamos n caracteres:
s = WHICH FINALLY HALTS. AT THAT POINT...
p = AT THAT
i = ^
(2) si intentamos hacer coincidir un carácter cuya última posición es k desde el final de p entonces podemos saltar k caracteres hacia adelante:
La última posición en p es 4 desde el final, por lo que avanzamos 4 caracteres:
s = WHICH FINALLY HALTS. AT THAT POINT...
p = AT THAT
i = ^
Ahora escaneamos hacia atrás desde i hasta que triunfamos o nos encontramos con una falta de coincidencia. (3a) si la falta de coincidencia tiene k caracteres desde el inicio de p y el carácter que no coincide no está en p , entonces podemos avanzar (al menos) k caracteres.
''L'' no está en p y el desajuste se produjo contra p6 , por lo que podemos avanzar (al menos) 6 caracteres:
s = WHICH FINALLY HALTS. AT THAT POINT...
p = AT THAT
i = ^
Sin embargo, podemos hacerlo mejor que esto. (3b) ya que sabemos que en la antigüedad ya habíamos emparejado algunos caracteres (1 en este caso). Si los caracteres coincidentes no coinciden con el inicio de p , entonces podemos avanzar un poco más (esta distancia adicional se llama ''delta2'' en el documento):
s = WHICH FINALLY HALTS. AT THAT POINT...
p = AT THAT
i = ^
En este punto, la observación (2) se aplica de nuevo, dando
s = WHICH FINALLY HALTS. AT THAT POINT...
p = AT THAT
i = ^
y el bingo! Hemos terminado
Otra explicación detallada ... http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides03.pdf
Primer consejo, respira hondo. Está claramente estresado, y cuando está estresado, lo primero que sucede es que grandes trozos de su cerebro se cierran. Esto dificulta la comprensión, lo que aumenta el estrés y usted tiene un problema.
Un tiempo de espera de 5 minutos para mejorar su espacio de cabeza puede parecer imposible de tomar, pero puede ser sorprendentemente útil.
Ahora que dicho, el algoritmo se basa en un principio simple. Supongamos que estoy tratando de hacer coincidir una subcadena de longitud m . Voy a ver primero el personaje en el índice m . Si ese carácter no está en mi cadena, sé que la subcadena que quiero no puede comenzar en caracteres en los índices 1, 2, ... , m .
Si ese carácter está en mi cadena, asumiré que puede estar en el último lugar de mi cadena. Luego saltaré hacia atrás y comenzaré a intentar unir mi cadena desde ese posible lugar de inicio. Esta pieza de información es mi primera mesa.
Una vez que empiezo a hacer coincidencias desde el principio de la subcadena, cuando encuentro una falta de coincidencia, no puedo empezar de cero. Podría ser parcialmente a través de un partido que comienza en un punto diferente. Por ejemplo, si estoy tratando de hacer coincidir ananand en ananand exitosamente, anan , darme cuenta de que lo siguiente a no es una d , pero acabo de emparejar y, por lo tanto, debería volver a intentar encontrar mi tercer personaje en mi subcadena Esta información de "Si falla después de hacer coincidir x caracteres, podría estar en el yy carácter de una coincidencia", la información se almacena en la segunda tabla.
Tenga en cuenta que cuando no coincido con la segunda tabla, se sabe en qué medida de una coincidencia podría basarme en lo que acabo de hacer coincidir. La primera tabla sabe hasta qué punto podría estar basado en el personaje que acabo de ver y que no pude encontrar. Desea utilizar el más pesimista de esos dos datos.
Con esto en mente, el algoritmo funciona así:
start at beginning of string
start at beginning of match
while not at the end of the string:
if match_position is 0:
Jump ahead m characters
Look at character, jump back based on table 1
If match the first character:
advance match position
advance string position
else if I match:
if I reached the end of the match:
FOUND MATCH - return
else:
advance string position and match position.
else:
pos1 = table1[ character I failed to match ]
pos2 = table2[ how far into the match I am ]
if pos1 < pos2:
jump back pos1 in string
set match position at beginning
else:
set match position to pos2
FAILED TO MATCH