Algoritmo de búsqueda de cadenas de Boyer-Moore
En ciencias de la computación , la cadena-algoritmo de búsqueda de Boyer-Moore es una eficiente cadena-algoritmo de búsqueda que es el punto de referencia estándar para la práctica literatura cadena de búsqueda. [1] Fue desarrollado por Robert S. Boyer y J Strother Moore en 1977. [2] El artículo original contenía tablas estáticas para calcular los cambios de patrón sin una explicación de cómo producirlos. El algoritmo para producir las tablas se publicó en un artículo de seguimiento; este artículo contenía errores que fueron posteriormente corregidos por Wojciech Rytter en 1980. [3] [4] El algoritmo preprocesala cadena que se busca (el patrón), pero no la cadena que se busca (el texto). Por lo tanto, es adecuado para aplicaciones en las que el patrón es mucho más corto que el texto o donde persiste en múltiples búsquedas. El algoritmo de Boyer-Moore utiliza información recopilada durante el paso de preproceso para omitir secciones del texto, lo que resulta en un factor constante más bajo que muchos otros algoritmos de búsqueda de cadenas. En general, el algoritmo se ejecuta más rápido a medida que aumenta la longitud del patrón. Las características clave del algoritmo son hacer coincidir la cola del patrón en lugar de la cabeza, y saltar a lo largo del texto en saltos de varios caracteres en lugar de buscar todos los caracteres del texto.
El algoritmo de Boyer-Moore busca apariciones de P en T realizando comparaciones explícitas de caracteres en diferentes alineaciones. En lugar de una búsqueda de fuerza bruta de todas las alineaciones (de las cuales las hay ), Boyer-Moore usa la información obtenida mediante el preprocesamiento de P para omitir tantas alineaciones como sea posible.
Antes de la introducción de este algoritmo, la forma habitual de buscar dentro del texto era examinar cada carácter del texto en busca del primer carácter del patrón. Una vez que se encontró eso, los caracteres subsiguientes del texto se compararían con los caracteres del patrón. Si no se producía ninguna coincidencia, el texto se volvería a comprobar carácter por carácter en un esfuerzo por encontrar una coincidencia. Por tanto, es necesario examinar casi todos los caracteres del texto.
La idea clave de este algoritmo es que si se compara el final del patrón con el texto, se pueden realizar saltos a lo largo del texto en lugar de verificar cada carácter del texto. La razón por la que esto funciona es que al alinear el patrón con el texto, el último carácter del patrón se compara con el carácter del texto. Si los caracteres no coinciden, no es necesario seguir buscando hacia atrás a lo largo del texto. Si el carácter en el texto no coincide con ninguno de los caracteres en el patrón, entonces el siguiente carácter en el texto para verificar se ubica m caracteres más a lo largo del texto, donde m es la longitud del patrón. Si el carácter del texto esen el patrón, luego se realiza un cambio parcial del patrón a lo largo del texto para alinearlo a lo largo del carácter coincidente y el proceso se repite. Saltar a lo largo del texto para hacer comparaciones en lugar de verificar cada carácter del texto disminuye el número de comparaciones que se deben hacer, que es la clave para la eficiencia del algoritmo.
Más formalmente, el algoritmo comienza en la alineación , por lo que el inicio de P está alineado con el inicio de T . Los caracteres en P y T se comparan entonces comenzando en el índice m en P y K en T , se mueve hacia atrás. Las cuerdas están emparejados desde el final de P al inicio del P . Las comparaciones continúan hasta el comienzo de Pse alcanza (lo que significa que hay una coincidencia) o se produce una falta de coincidencia en la que la alineación se desplaza hacia adelante (hacia la derecha) de acuerdo con el valor máximo permitido por una serie de reglas. Las comparaciones se vuelven a realizar en la nueva alineación y el proceso se repite hasta que la alineación se desplaza más allá del final de T , lo que significa que no se encontrarán más coincidencias.
