En informática , el algoritmo de Boyer-Moore-Horspool o 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 caso , donde la longitud del patrón es m y la longitud de la cadena de búsqueda es 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 de forma segura. 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í utilizamos índices basados en cero. función preprocesar ( 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 retorna T La búsqueda de patrones se realiza de la siguiente manera. El procedimiento de búsqueda informa el índice de la primera aparición de needle in haystack .
// Compara dos cadenas, hasta los primeros len caracteres. // Nota: esto es equivalente a !memcmp(str1, str2, len). function same ( str1 , str2 , len ) i := len - 1 // El algoritmo original intenta ser inteligente aquí: verifica el // último carácter, luego el penúltimo, etc. while str1 [ i ] == str2 [ i ] if i == 0 return true i := i - 1 return false función buscar ( aguja , pajar ) T := preprocesar ( aguja ) saltar := 0 // pajar[saltar:] significa subcadena que comienza en el índice `saltar`. Sería &haystack[saltar] en C. mientras longitud ( pajar ) - saltar >= longitud ( aguja ) si es igual ( pajar [ saltar : ] , aguja , longitud ( aguja )) volver saltar saltar := saltar + T [ pajar [ saltar + longitud ( aguja ) - 1 ]] volver - 1 El algoritmo funciona mejor con cadenas de agujas largas, cuando encuentra constantemente un carácter no coincidente en el byte final o cerca del mismo de la posición actual en el pajar y el byte final de la aguja no aparece en ningún otro lugar dentro de la aguja. Por ejemplo, una aguja de 32 bytes que termina en "z" que busca en un pajar de 255 bytes que no tiene un byte "z" requerirí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 de cada bucle es menor.
El peor de los casos se produce cuando el salto de caracteres incorrectos 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 caracteres incorrectos solo es bajo, en una coincidencia parcial, cuando el carácter final de la aguja también aparece en otra parte dentro de la aguja, y se produce un movimiento de 1 byte cuando el mismo byte está en las dos últimas posiciones.
El caso degenerado canónico 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), lo que lleva el total de comparaciones de bytes a 7168 (32 × 224). (Un bucle de comparación de bytes diferente tendrá un comportamiento diferente).
El peor caso es significativamente más alto que el del 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 algoritmo ingenuo (pero habitual) memcmp(), aunque la implementación de este tiende a estar significativamente optimizada (y es más amigable con la memoria caché).
El algoritmo original tenía un bucle same() más sofisticado. Utiliza una comprobación previa adicional antes de continuar en la dirección positiva: [1]
función same_orig(str1, str2, len) yo ← 0 si str1[len - 1] = str2[len - 1] mientras str1[i] = str2[i] si i = len - 2 devuelve verdadero yo ← yo + 1 devuelve falso
Una versión optimizada del algoritmo BMH es el algoritmo Raita . Agrega una verificación previa adicional para el carácter del medio, en el orden de último-primero-medio. El algoritmo ingresa al bucle completo solo cuando se aprueba la verificación: [2]
función same_raita(str1, str2, len) yo ← 0 medio ← 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 bucle 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 mantiene su ventaja de rendimiento en las máquinas modernas. La razón de los autores es que el texto real suele contener algunos patrones que pueden prefiltrarse de forma eficaz con estos tres caracteres. Parece que Raita no está al tanto de la antigua comprobación previa del último carácter (creía que la misma rutina de solo lectura hacia atrás es la implementación de Horspool), por lo que se recomienda a los lectores que tomen los resultados con cautela. [2]
En las máquinas modernas, las funciones de biblioteca como memcmp tienden 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 Algoritmo de búsqueda de cadenas , que tiene un análisis detallado de otros algoritmos de búsqueda de cadenas.