En informática , el algoritmo de Boyer-Moore-Horspool o el algoritmo de Horspool es un algoritmo para encontrar subcadenas en cadenas . Fue publicado por Nigel Horspool en 1980 como SBM. [1]
Es una simplificación del algoritmo de búsqueda de cadenas de Boyer-Moore que está relacionado con el algoritmo de Knuth-Morris-Pratt . El algoritmo intercambia espacio por tiempo para obtener una complejidad de caso promedio de O (n) en texto aleatorio, aunque tiene O (nm) en el peor de los casos , donde la longitud del patrón es my la longitud de la búsqueda. cadena es n .
Descripción
Al igual que Boyer-Moore, Boyer-Moore-Horspool preprocesa el patrón para producir una tabla que contiene, para cada símbolo del alfabeto , el número de caracteres que se pueden omitir con seguridad. La fase de preprocesamiento, en pseudocódigo, es la siguiente (para un alfabeto de 256 símbolos, es decir, bytes):
A diferencia del original, aquí usamos índices de base cero. función preproceso (patrón) T ← nueva tabla de 256 enteros para i de 0 a 256 exclusivo T [i] ← longitud (patrón) para i de 0 a longitud (patrón) - 1 exclusivo T [patrón [i]] ← longitud (patrón) - 1 - i volver T
La búsqueda de patrones procede de la siguiente manera. La búsqueda de procedimiento informa el índice de la primera aparición de aguja en pajar .
function same (str1, str2, len) Compara dos cadenas, hasta los primeros caracteres len. i ← len - 1 while str1 [i] = str2 [i] Nota: esto es equivalente a! memcmp (str1, str2, len). if i = 0 El algoritmo original intenta jugar inteligentemente aquí: verifica el retorno verdadero del último carácter, y luego comienza desde el primero hasta el penúltimo. yo ← yo - 1 devolver falsobúsqueda de función (aguja, pajar) T ← preproceso (aguja) saltar ← 0 while length (pajar) - saltar ≥ longitud (aguja) pajar [saltar:] - subcadena que comienza con "saltar". & pajar [saltar] en C. si es igual (pajar [saltar:], aguja, longitud (aguja)) volver saltar saltar ← saltar + T [pajar [saltar + longitud (aguja) - 1]] retorno no encontrado
Actuación
El algoritmo funciona mejor con cadenas de agujas largas, cuando golpea consistentemente un carácter no coincidente en o cerca del byte final de la posición actual en el pajar y el byte final de la aguja no ocurre en ningún otro lugar dentro de la aguja. Por ejemplo, una aguja de 32 bytes que termina en "z" buscando en un pajar de 255 bytes que no tiene un byte "z" tomaría hasta 224 comparaciones de bytes.
El mejor caso es el mismo que para el algoritmo de búsqueda de cadenas de Boyer-Moore en notación O grande , aunque la sobrecarga constante de inicialización y para cada bucle es menor.
El peor comportamiento de caso ocurre cuando el salto de carácter incorrecto es constantemente bajo (con el límite inferior de movimiento de 1 byte) y una gran parte de la aguja coincide con el pajar. El salto de carácter incorrecto es solo bajo, en una coincidencia parcial, cuando el carácter final de la aguja también ocurre en otro lugar dentro de la aguja, con un movimiento de 1 byte cuando el mismo byte está en las dos últimas posiciones.
El caso canónico degenerado similar al "mejor" caso anterior es una aguja de un byte 'a' seguido de 31 bytes 'z' en un pajar que consta de 255 bytes 'z'. Esto hará 31 comparaciones de bytes exitosas, una comparación de 1 byte que falla y luego avanzará 1 byte. Este proceso se repetirá 223 veces más (255 - 32), llevando el total de comparaciones de bytes a 7,168 (32 × 224). (Un bucle de comparación de bytes diferente tendrá un comportamiento diferente).
El peor de los casos es significativamente más alto que para el algoritmo de búsqueda de cadenas de Boyer-Moore, aunque obviamente esto es difícil de lograr en casos de uso normales. También vale la pena señalar que este peor caso es también el peor caso para el memcmp()
algoritmo ingenuo (pero habitual) , aunque la implementación de eso tiende a optimizarse significativamente (y es más amigable con la caché).
Sintonizando el bucle de comparación
El algoritmo original tenía un bucle same () más sofisticado. Utiliza una comprobación previa adicional antes de proceder en la dirección positiva: [1]
función same_orig (str1, str2, len) yo ← 0 if str [len - 1] = str2 [len - 1] while str1 [i] = str2 [i] if i = len - 2 devuelve verdadero yo ← yo + 1 devolver falso
Una versión ajustada del algoritmo BMH es el algoritmo Raita . Agrega una precomprobación adicional para el carácter del medio, en el orden de último, primero, del medio. El algoritmo entra en el ciclo completo solo cuando pasa la verificación: [2]
función same_raita (str1, str2, len) yo ← 0 mediados ← len / 2 Tres comprobaciones previas. si len ≥ 3 si str [mid]! = str2 [mid] devuelve falso si len ≥ 1 si str [0]! = str2 [0] devuelve falso si len ≥ 2 si str [len - 1]! = str2 [len - 1] devuelve falso Cualquier ciclo de comparación antiguo. devuelve len <3 o SAME (& str1 [1], & str2 [1], len - 2)
No está claro si este ajuste de 1992 todavía tiene su ventaja de rendimiento en las máquinas modernas. El razonamiento de los autores es que el texto real generalmente contiene algunos patrones que pueden ser prefiltrados de manera efectiva por estos tres caracteres. Parece que Raita no está al tanto de la antigua verificación previa del último carácter (él creía que la la misma rutina es la implementación de Horspool), por lo que se recomienda a los lectores que tomen los resultados con un grano de sal. [2]
En las máquinas modernas, la biblioteca funciona como memcmp tiende a proporcionar un mejor rendimiento que cualquiera de los bucles de comparación escritos a mano. El comportamiento de un bucle "SFC" (terminología de Horspool) tanto en libstdc ++ como en libc ++ parece sugerir que una implementación moderna de Raita no debería incluir ninguno de los cambios de un carácter, ya que tienen efectos perjudiciales en la alineación de datos. [3] [4] Véase también String-searching_algorithm que ha detallado análisis de otros algoritmos de búsqueda de cadena.
Referencias
- ↑ a b R. N. Horspool (1980). "Práctica búsqueda rápida en cadenas". Software: práctica y experiencia . 10 (6): 501–506. CiteSeerX 10.1.1.63.3421 . doi : 10.1002 / spe.4380100608 . S2CID 6618295 .
- ^ a b RAITA T., 1992, Ajuste del algoritmo de búsqueda de cadenas de Boyer-Moore-Horspool, Software - Práctica y experiencia, 22 (10): 879-884 [1]
- ^ "⚙ D27068 Mejorar cadena :: buscar" . Revisión del código LLVM .
- ^ "[PATCH] mejora el algoritmo de búsqueda de cadenas" . GCC .