Algoritmo de búsqueda de cadenas de Boyer-Moore

En informática , el algoritmo de búsqueda de cadenas de Boyer-Moore es un algoritmo de búsqueda de cadenas eficiente que es el estándar de referencia para la literatura práctica de búsqueda de cadenas. ^[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 patrones sin una explicación de cómo producirlos. El algoritmo para producir las tablas se publicó en un artículo posterior; este artículo contenía errores que fueron corregidos posteriormente por Wojciech Rytter en 1980. ^[3]^[4]

El algoritmo preprocesa la 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 a lo largo de múltiples búsquedas. El algoritmo de Boyer-Moore utiliza información recopilada durante el paso de preprocesamiento para omitir secciones del texto, lo que da como resultado 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 la búsqueda en la cola del patrón en lugar de la cabeza, y la búsqueda en saltos de múltiples caracteres en el texto.

Definiciones

Alineaciones del patrón PAN con el texto ANPANMAN ,
desde k=3 hasta k=8 . Se produce una coincidencia en k=5 .

T indica el texto de entrada que se buscará. Su longitud es n .
P denota la cadena que se va a buscar, llamada patrón . Su longitud es m .
S [ i ] denota el carácter en el índice i de la cadena S , contando desde 1.
S [ i .. j ] denota la subcadena de la cadena S que comienza en el índice i y termina en j , inclusive.
Un prefijo de S es una subcadena S [ 1.. i ] para algún i en el rango [1, l ], donde l es la longitud de S.
Un sufijo de S es una subcadena S [ i .. l ] para algún i en el rango [1, l ], donde l es la longitud de S .
Una alineación de P a T es un índice k en T tal que el último carácter de P está alineado con el índice k de T.
Una coincidencia u ocurrencia de P ocurre en una alineación k si P es equivalente a T [( k - m +1).. k ].

Descripción

El algoritmo de Boyer-Moore busca ocurrencias de $P$ en $T$ realizando comparaciones explícitas de caracteres en diferentes alineaciones. En lugar de una búsqueda por fuerza bruta de todas las alineaciones (de las cuales hay ⁠ ⁠ $n-m+1$ ), Boyer-Moore utiliza 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 en un texto era examinar cada carácter del texto en busca del primer carácter del patrón. Una vez encontrado, se comparaban los caracteres siguientes del texto con los caracteres del patrón. Si no se producía ninguna coincidencia, se volvía a comprobar el texto carácter por carácter en un intento de encontrar una coincidencia. Por lo 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 hacer saltos a lo largo del texto en lugar de comprobar 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 hay necesidad de seguir buscando hacia atrás en el texto. Si el carácter del texto no coincide con ninguno de los caracteres del patrón, entonces el siguiente carácter del texto que se debe comprobar se encuentra $m$ caracteres más adelante en el texto, donde $m$ es la longitud del patrón. Si el carácter del texto está en el patrón, entonces se realiza un desplazamiento parcial del patrón a lo largo del texto para alinearse con el carácter coincidente y se repite el proceso. Saltar a lo largo del texto para hacer comparaciones en lugar de comprobar cada carácter del texto reduce la cantidad de comparaciones que se deben hacer, lo que es la clave de la eficiencia del algoritmo.

Más formalmente, el algoritmo comienza en la alineación ⁠ ⁠ ${\estilo de visualización k=m}$ , por lo que el inicio de $P$ está alineado con el inicio de $T$ . Luego, los caracteres en $P$ y $T$ se comparan comenzando en el índice $m$ en $P$ y $k$ en $T$ , moviéndose hacia atrás. Las cadenas coinciden desde el final de $P$ hasta el inicio de $P$ . Las comparaciones continúan hasta que se alcanza el comienzo de $P$ (lo que significa que hay una coincidencia) o ocurre una falta de coincidencia en la que la alineación se desplaza hacia adelante (a la derecha) de acuerdo con el valor máximo permitido por una serie de reglas. Las comparaciones se realizan nuevamente 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.

Las reglas de desplazamiento se implementan como búsquedas de tablas de tiempo constante, utilizando tablas generadas durante el preprocesamiento de $P.$

Reglas de turnos

Un desplazamiento se calcula aplicando dos reglas: la regla del carácter incorrecto y la regla del sufijo correcto. El desplazamiento real es el máximo de los desplazamientos calculados por estas reglas.

La regla del mal carácter

Descripción

Demostración de la regla de caracteres incorrectos con el patrón P = NNAAMAN . Hay una discrepancia entre N (en el texto de entrada) y A (en el patrón) en la columna marcada con una X . El patrón se desplaza a la derecha (en este caso por 2) de modo que se encuentre la siguiente ocurrencia del carácter N (en el patrón P ) a la izquierda del carácter actual (que es la A del medio ).

La regla del carácter incorrecto considera el carácter en $T$ en el que falló el proceso de comparación (suponiendo que se produjo tal falla). Se encuentra la siguiente ocurrencia de ese carácter a la izquierda en $P$ y se propone un desplazamiento que pone esa ocurrencia en línea con la ocurrencia no coincidente en $T.$ Si el carácter no coincidente no ocurre a la izquierda en $P$ , se propone un desplazamiento que mueve la totalidad de $P$ más allá del punto de no coincidencia.

Preprocesamiento

Los métodos varían en la forma exacta que debe adoptar la tabla para la regla de caracteres incorrectos, pero una solución de búsqueda simple en tiempo constante es la siguiente: cree una tabla 2D que esté indexada primero por el índice del carácter $c$ en el alfabeto y segundo por el índice $i$ en el patrón. Esta búsqueda devolverá la ocurrencia de $c$ en $P$ con el siguiente índice más alto ⁠ ⁠ $j<i$ o -1 si no hay tal ocurrencia. El cambio propuesto será entonces ⁠ ⁠ ${\estilo de visualización ij}$ , con ⁠ ⁠ ${\estilo de visualización O(1)}$ tiempo de búsqueda y ⁠ ⁠ $O(km)$ espacio, asumiendo un alfabeto finito de longitud $k$ .

Las implementaciones de C y Java que se muestran a continuación tienen una complejidad espacial de ⁠ ⁠ $O(k)$ (make_delta1, makeCharTable). Es la misma que la delta1 original y la tabla de caracteres incorrectos de BMH . Esta tabla asigna un carácter en la posición ⁠ ⁠ ${\estilo de visualización i}$ para desplazarlo por ⁠ ⁠ $\operatorname {len} (p)-1-i$ , y la última instancia (la menor cantidad de desplazamiento) tiene prioridad. Todos los caracteres no utilizados se establecen como ⁠ ⁠ $\nombre del operador {len} (p)$ como valor centinela.

La regla del sufijo bueno

Descripción

Demostración de la regla del sufijo correcto con el patrón P = ANAMPNAM . Aquí, t es T [6..8] y t ′ es P [2..4].

La regla del sufijo bueno es notablemente más compleja tanto en concepto como en implementación que la regla del carácter malo. Al igual que esta última, también explota la característica del algoritmo de realizar comparaciones que comienzan al final del patrón y continúan hacia el inicio del mismo. Puede describirse de la siguiente manera: ^[5]

Supongamos que para una alineación dada de P y T , una subcadena t de T coincide con un sufijo de P y supongamos que t es la subcadena más grande para la alineación dada.
Luego, encuentre, si existe, la copia más a la derecha t ′ de t en P tal que t ′ no sea un sufijo de P y el carácter a la izquierda de t ′ en P difiera del carácter a la izquierda de t en P. Desplace P hacia la derecha para que la subcadena t ′ en P se alinee con la subcadena t en T.
Si t ′ no existe, entonces desplace el extremo izquierdo de P hacia la derecha en la menor cantidad posible (más allá del extremo izquierdo de t en T ) de modo que un prefijo del patrón desplazado coincida con un sufijo de t en T . Esto incluye casos en los que t es una coincidencia exacta de P .
Si no es posible tal desplazamiento, entonces desplace P m (longitud de P ) lugares hacia la derecha.

Preprocesamiento

La regla del sufijo correcto requiere dos tablas: una para usar en el caso general (cuando se encuentra una copia t ′ ) y otra para usar cuando el caso general no devuelve ningún resultado significativo. Estas tablas se designarán $L$ y $H$ respectivamente. Sus definiciones son las siguientes: ^[5]

Para cada $i$ , ⁠ ⁠ $L[i]$ es la posición más grande menor que $m$ tal que la cadena ⁠ ⁠ $P[i..m]$ coincide con un sufijo de ⁠ ⁠ $P[1..L[i]]$ y tal que el carácter que precede a ese sufijo no es igual a ⁠ ⁠ $P[i-1]$ . ⁠ ⁠ $L[i]$ se define como cero si no hay ninguna posición que satisfaga la condición.

Sea ⁠ ⁠ $H[i]$ la longitud del sufijo más grande de ⁠ ⁠ $P[i..m]$ que también sea un prefijo de $P$ , si existe alguno. Si no existe ninguno, sea ⁠ ⁠ $H[i]$ cero.

Ambas tablas se pueden construir en tiempo y $O(m)$ espacio de uso $O(m)$ . El cambio de alineación para el índice $i$ en $P$ está dado por o . $ml[i]$ H $solo$ se debe utilizar si es cero o se $mH[i]$ ha encontrado una coincidencia . $L[i]$

Ejemplo de cambio de uso del patrón ANPANMAN

Índice | Desajuste | Cambio  0 | N| 1  1 | UN| 8  2 | HOMBRE | 3  3 | NMAN| 6  4 | ANMAN | 6  5 | PANMAN| 6  6 | NPANMAN| 6  7 | ANPANMAN | 6

Explicación:

Índice 0, no se encontraron caracteres coincidentes, el carácter leído no fue N. La longitud del sufijo correcto es cero. Como hay muchas letras en el patrón que tampoco son N, tenemos información mínima aquí: el desplazamiento en 1 es el resultado menos interesante.

Índice 1: hemos encontrado la N, y estaba precedida por algo distinto de A. Ahora, observe el patrón a partir del final: ¿dónde tenemos la N precedida por algo distinto de A? Hay otras dos N, pero ambas están precedidas por A. Eso significa que ninguna parte del sufijo correcto puede resultarnos útil: desplace la longitud total del patrón 8.

Índice 2: Coincidimos con el AN, y no estaba precedido por M. En el medio del patrón hay un AN precedido por P, por lo que se convierte en el candidato a desplazamiento. Desplazar ese AN hacia la derecha para alinearse con nuestro patrón es un desplazamiento de 3.

Índice 3 y superiores: los sufijos coincidentes no coinciden con nada más en el patrón, pero el sufijo final AN coincide con el inicio del patrón, por lo que los cambios aquí son todos 6. ^[6]

La regla de Galil

En 1979, Zvi Galil propuso una optimización simple pero importante de Boyer–Moore. ^[7] A diferencia del desplazamiento, la regla de Galil trata de acelerar las comparaciones reales realizadas en cada alineación saltando secciones que se sabe que coinciden. Supongamos que en una alineación $k 1$ , $P$ se compara con $T$ hasta el carácter $c$ de $T$ . Entonces, si $P$ se desplaza a $k 2$ de modo que su extremo izquierdo esté entre $c$ y $k 1$ , en la siguiente fase de comparación un prefijo de $P$ debe coincidir con la subcadena $T [(k 2 - n).. k 1]$ . Por lo tanto, si las comparaciones llegan hasta la posición $k 1$ de $T$ , se puede registrar una ocurrencia de $P$ $sin comparar explícitamente más allá de k 1$ . Además de aumentar la eficiencia de Boyer–Moore, la regla de Galil es necesaria para demostrar la ejecución en tiempo lineal en el peor de los casos.

La regla de Galil, en su versión original, solo es efectiva para versiones que generan múltiples coincidencias. Actualiza el rango de subcadenas solo en $c = 0$ , es decir, una coincidencia completa. En 1985 se informó sobre una versión generalizada para tratar con subcoincidencias como el algoritmo Apostolico–Giancarlo . ^[8]

Actuación

El algoritmo de Boyer-Moore tal como se presenta en el artículo original tiene un tiempo de ejecución en el peor de los casos de ⁠ ⁠ $O(n+m)$ solo si el patrón no aparece en el texto. Esto fue demostrado por primera vez por Knuth , Morris y Pratt en 1977, ^[3] seguido por Guibas y Odlyzko en 1980 ^[9] con un límite superior de $5 n$ comparaciones en el peor de los casos. Richard Cole dio una prueba con un límite superior de $3 n$ comparaciones en el peor de los casos en 1991. ^[10]

Cuando el patrón aparece en el texto, el tiempo de ejecución del algoritmo original es ⁠ ⁠ $O(nm)$ en el peor de los casos. Esto es fácil de ver cuando tanto el patrón como el texto consisten únicamente en el mismo carácter repetido. Sin embargo, la inclusión de la regla de Galil da como resultado un tiempo de ejecución lineal en todos los casos. ^[7]^[10]

Implementaciones

Existen varias implementaciones en diferentes lenguajes de programación. En C++, es parte de la biblioteca estándar desde C++17 y Boost proporciona la implementación genérica de búsqueda de Boyer-Moore en la biblioteca de algoritmos . En Go (lenguaje de programación), hay una implementación en search.go. D (lenguaje de programación) utiliza un Boyer-MooreFinder para la búsqueda basada en predicados dentro de rangos como parte de la biblioteca de tiempo de ejecución Phobos.

El algoritmo Boyer-Moore también se utiliza en grep de GNU . ^[11]

Variantes

El algoritmo de Boyer–Moore–Horspool es una simplificación del algoritmo de Boyer–Moore que utiliza únicamente la regla de los caracteres malos.

El algoritmo Apostolico–Giancarlo acelera el proceso de verificación de si se ha producido una coincidencia en la alineación dada omitiendo las comparaciones explícitas de caracteres. Esto utiliza información obtenida durante el preprocesamiento del patrón junto con las longitudes de coincidencia de sufijo registradas en cada intento de coincidencia. El almacenamiento de las longitudes de coincidencia de sufijo requiere una tabla adicional de igual tamaño que el texto que se está buscando.

El algoritmo Raita mejora el rendimiento del algoritmo Boyer–Moore–Horspool. El patrón de búsqueda de una subcadena particular en una cadena dada es diferente del algoritmo Boyer–Moore–Horspool.

Notas

^ m es la longitud de la cadena de patrones que estamos buscando en el texto, que tiene una longitud n . Este tiempo de ejecución es para encontrar todas las ocurrencias del patrón, sin la regla de Galil.
^ k es el tamaño del alfabeto. Este espacio es para la tabla de caracteres incorrectos delta1 original en las implementaciones de C y Java y la tabla de sufijos correctos.

Referencias

^ Hume, Andrew; Sunday, Daniel (noviembre de 1991). "Búsqueda rápida de cadenas". Software: práctica y experiencia . 21 (11): 1221–1248. doi :10.1002/spe.4380211105. S2CID 5902579.
^ Boyer, Robert S. ; Moore, J Strother (octubre de 1977). "Un algoritmo rápido de búsqueda de cadenas". Comm. ACM . 20 (10). Nueva York: Association for Computing Machinery: 762–772. doi : 10.1145/359842.359859 . ISSN 0001-0782. S2CID 15892987.
^ ab Knuth, Donald E. ; Morris, James H. Jr. ; Pratt, Vaughan R. (1977). "Coincidencia rápida de patrones en cadenas". Revista SIAM de Computación . 6 (2): 323–350. CiteSeerX 10.1.1.93.8147 . doi :10.1137/0206024. ISSN 0097-5397.
^ Rytter, Wojciech (1980). "Un algoritmo de preprocesamiento correcto para la búsqueda de cadenas de Boyer-Moore". Revista SIAM de Computación . 9 (3): 509–512. doi :10.1137/0209037. ISSN 0097-5397.
^ ab Gusfield, Dan (1999) [1997], "Capítulo 2 - Coincidencia exacta: métodos clásicos basados en la comparación", Algorithms on Strings, Trees, and Sequences (1.ª ed.), Cambridge University Press, págs. 19-21, ISBN 0-521-58519-8
^ "Construcción de una buena tabla de sufijos: comprensión de un ejemplo". Desbordamiento de pila . 11 de diciembre de 2014 . Consultado el 30 de julio de 2024 . Este artículo incorpora texto de esta fuente, que está disponible bajo la licencia CC BY-SA 3.0.
^ ab Galil, Z. (septiembre de 1979). "Sobre la mejora del tiempo de ejecución en el peor de los casos del algoritmo de coincidencia de cadenas de Boyer–Moore". Comm. ACM . 22 (9). Nueva York: Association for Computing Machinery: 505–508. doi : 10.1145/359146.359148 . ISSN 0001-0782. S2CID 1333465.
^ Apostolico, Alberto; Giancarlo, Raffaele (febrero de 1986). "Revisión de las estrategias de búsqueda de cadenas de Boyer-Moore-Galil". Revista SIAM de Computación . 15 : 98–105. doi :10.1137/0215007.
^ Guibas, Leonidas ; Odlyzko, Andrew (1977). "Una nueva prueba de la linealidad del algoritmo de búsqueda de cadenas de Boyer–Moore". Actas del 18.º Simposio Anual sobre Fundamentos de la Ciencia de la Computación . SFCS '77. Washington, Distrito de Columbia: IEEE Computer Society: 189–195. doi :10.1109/SFCS.1977.3. S2CID 6470193.
^ ab Cole, Richard (septiembre de 1991). "Límites estrictos en la complejidad del algoritmo de coincidencia de cadenas de Boyer-Moore". Actas del 2º Simposio anual ACM-SIAM sobre algoritmos discretos . Soda '91. Filadelfia, Pensilvania: Society for Industrial and Applied Mathematics: 224–233. ISBN 0-89791-376-0.
^ Haertel, Mike (21 de agosto de 2010). "Por qué GNU grep es rápido". Archivo de la lista de correo de FreeBSD-current .

Enlaces externos

Wikimedia Commons alberga una categoría multimedia sobre Algoritmo de búsqueda de cadenas de Boyer-Moore .

Artículo original sobre el algoritmo de Boyer-Moore
Un ejemplo del algoritmo Boyer-Moore de la página de inicio de J Strother Moore , co-inventor del algoritmo
Artículo de Richard Cole de 1991 que demuestra la linealidad del tiempo de ejecución