Algoritmo de Boyer-Moore-Horspool
El algoritmo de Boyer-Moore-Horspool es un algoritmo para encontrar una subcadena en una cadena , una versión simplificada del algoritmo de Boyer-Moore . ABMX funciona mejor que el algoritmo de Boyer-Moore en textos aleatorios, la puntuación promedio es de a a un carácter del texto [1] . Además, se omite la heurística de sufijo de coincidencia computacionalmente intensiva.
Sin embargo, la estimación ( en el peor de los casos en plantillas no periódicas) para ABMX es | aguja |·| pajar | (en lugar de 3 | pajar | para Boyer-Moore).
Descripción del algoritmo
El algoritmo es una modificación del algoritmo de Boyer-Moore . La idea del algoritmo es esta.
1. Escaneo de izquierda a derecha, comparación en el modo "caja negra". Como en el algoritmo primitivo, se combinan el comienzo del texto y la plantilla, se realiza una comparación utilizando el procedimiento habitual de “ comparar secciones de memoria ” . Si todos los caracteres del patrón coincidieron con los caracteres superpuestos de la cadena, entonces se encontró la subcadena y la búsqueda terminó.
Si algún carácter del patrón no coincide con el carácter correspondiente de la cadena, el patrón se desplaza unos pocos caracteres hacia la derecha. Estos "pocos" se eligen de acuerdo con tal heurística.
2. Se modificó la heurística del símbolo de parada. Tomamos el carácter del texto que apareció sobre el último carácter del patrón (¡independientemente de dónde ocurrió la falta de coincidencia!). Es "b" en la imagen.
↓ símbolo de parada Texto abadb * * * * patrón abad Próximo control abbadCambiamos la plantilla para que la letra "b" de la plantilla esté debajo del símbolo de parada. Esto se implementa mediante una tabla de desplazamiento: para cada carácter del alfabeto, almacenamos el desplazamiento máximo posible que no salta un carácter de parada. Es decir (al numerar líneas con 1): shift ( c ) = | aguja |−lastpos( c , aguja [1..| aguja |−1]) , donde últimapos es la última aparición de un carácter en la cadena, aguja [ a .. b ] es la operación de subcadena.
Para el patrón "abbad", la tabla se ve así.
| Símbolo | a | b | (otro) |
|---|---|---|---|
| Parcialidad | una | 2 | 5 |
Para los símbolos no incluidos en la plantilla, el valor de compensación se establece igual a la longitud de la plantilla - 5. El último símbolo de la plantilla no se considera al calcular la tabla de compensación (está plagado de bucles ).
Es más conveniente calcular la tabla pasando por todos los símbolos del patrón:
para c=MIN_CHAR..MAX_CHAR shift[c] = |aguja| para i=1..|aguja|-1 shift[aguja[i]] = |aguja|-iUn ejemplo de cómo funciona el algoritmo
El patrón deseado es "abbad" (la tabla para este patrón se construye arriba).
abeccacbadbabbad abadImponemos una muestra en la línea. El último carácter de la cadena de origen "c" no está contenido en el patrón. Mueva el patrón a la derecha en 5 posiciones de acuerdo con el valor de compensación para "c":
abeccacbadbabbad abadTres caracteres del patrón coincidían, pero el cuarto no. Mueva el patrón a la derecha en 5 posiciones de acuerdo con el valor de compensación para "d":
abeccacbadbabbad abadEl último carácter de la cadena "a" no coincide con el carácter del patrón. Desplace el patrón a la derecha en 1 de acuerdo con el valor de desplazamiento de "a" y obtenga la ocurrencia deseada del patrón:
abeccacbadbabbad abadOpciones
Algoritmo de Sandi
Para el carácter de parada, tomamos el carácter que sigue a la aguja .
Algoritmo de Wright
Un algoritmo empírico optimizado para textos en inglés . Compara el último carácter, luego el primero, luego el medio, luego todos los demás; en caso de desajuste, turno de Horspool.
Ventajas
Muy rápido en promedio[ especificar ] . Fácil de implementar. Utiliza la función estándar para comparar áreas de memoria, por regla general, optimizada a nivel de ensamblador para un procesador específico.
Desventajas
Al igual que otros algoritmos de la familia Boyer-Moore, no se modifica para búsqueda aproximada, búsqueda simultánea de varias cadenas.
La regresión en datos "malos" ocurre algo más a menudo que en el algoritmo de Boyer-Moore. Cuanto más diversos sean los caracteres en el texto de origen, mejor se comporta ABMX.
Literatura
- Niklaus Wirth Algoritmos y estructuras de datos. — M.: Nevsky Dialect, 2006. S. 352. ISBN 5-7940-0065-1
Notas
- ↑ Algoritmo de Horspool . Consultado el 12 de agosto de 2012. Archivado desde el original el 29 de agosto de 2012.
Enlaces
| Instrumentos de cuerda | |
|---|---|
| Medidas de similitud de cadenas | |
| Búsqueda de subcadena | |
| palíndromos | |
| Alineación de secuencia | |
| Estructuras de sufijos | |
| Otro | |