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 punto de referencia estándar 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 patrón 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 posteriormente fueron corregidos 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 muy 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 previo al proceso 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 hacer coincidir la cola del patrón en lugar de la cabeza, y saltar el texto en saltos de varios caracteres en lugar de buscar cada carácter del texto.

Definiciones

Alineaciones del patrón PAN al texto ANPANMAN ,
de k=3 a k=8 . Se produce una coincidencia en k=5 .

T indica el texto de entrada que se va a 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 alguna i en el rango [1, l ], donde l es la longitud de S .
Un sufijo de S es una subcadena S [ i .. l ] para alguna 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 o aparición 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 apariciones de $P$ en $T$ realizando comparaciones explícitas de caracteres en diferentes alineamientos. En lugar de una búsqueda por fuerza bruta de todas las alineaciones (de las cuales existen ), Boyer-Moore utiliza la información obtenida mediante el preprocesamiento de $P$ para omitir tantas alineaciones como sea posible. $n-m+1$

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 encontrado esto, los caracteres siguientes 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 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 realizar 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 es necesario 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 a verificar se ubica $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 alinearlo a lo largo del carácter coincidente y se repite el proceso. Saltar a lo largo del texto para hacer comparaciones en lugar de verificar cada carácter del texto disminuye la cantidad de comparaciones que deben realizarse, lo cual es la clave de 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.$ 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 se produce una discrepancia 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 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. $k=m$

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

reglas de turno

Un cambio se calcula aplicando dos reglas: la regla del carácter malo y la regla del sufijo bueno. El desplazamiento de desplazamiento real es el máximo de los desplazamientos calculados según estas reglas.

La regla del mal carácter

Descripción

Demostración de la regla del mal carácter con el patrón P = NNAAMAN . Hay una discrepancia entre N (en el texto ingresado) y A ( en el patrón) en la columna marcada con una X. El patrón se desplaza hacia la derecha (en este caso 2) para que se encuentre la siguiente aparición 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 malo considera el carácter en $T$ en el que falló el proceso de comparación (suponiendo que tal falla haya ocurrido). Se encuentra la siguiente aparición de ese carácter a la izquierda en $P$ , y se propone un desplazamiento que alinee esa aparición con la aparición no coincidente en $T.$ Si el carácter no coincidente no aparece hacia la izquierda en $P$ , se propone un desplazamiento que mueva la totalidad de $P$ más allá del punto de no coincidencia.

Preprocesamiento

Los métodos varían según la forma exacta que debe tomar la tabla para la regla de caracteres incorrectos, pero una solución simple de búsqueda 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 en segundo lugar por el índice $i$ en el patrón. Esta búsqueda devolverá la aparición de $c$ en $P$ con el siguiente índice más alto o -1 si no existe tal aparición. El cambio propuesto será entonces , con tiempo y espacio de búsqueda, suponiendo un alfabeto finito de longitud $k$ . $j<i$ $ij$ $O(1)$ $O(km)$

Las implementaciones de C y Java siguientes tienen complejidad espacial (make_delta1, makeCharTable). Esto es lo mismo que el delta1 original y la tabla de caracteres incorrectos de BMH . Esta tabla asigna un carácter en la posición para cambiar , teniendo prioridad la última instancia (la menor cantidad de cambio). Todos los caracteres no utilizados se establecen como valor centinela. $O(k)$ $i$ $\operatorname {len} (p)-1-i$ $\operatorname {len} (p)$

La regla del buen sufijo

Descripción

Demostración de la regla del buen sufijo 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 la regla del carácter malo, 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 patrón. Se puede describir 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 difiere del carácter a la izquierda de t en P . Desplaza 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 (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 tal cambio no es posible, entonces desplace P m ( longitud de P) lugares hacia la derecha.

Preprocesamiento

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

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

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

Ambas mesas son construibles en el tiempo y utilizan el espacio. El cambio de alineación para el índice $i$ en $P$ viene dado por o . $H$ sólo debe usarse si es cero o se ha encontrado una coincidencia. $O(m)$ $O(m)$ $mL[i]$ $mH[i]$ $L[i]$

El gobierno de Galil

Zvi Galil propuso una optimización simple pero importante de Boyer-Moore en 1979. ^[6] A diferencia del desplazamiento, la regla de Galil se ocupa de acelerar las comparaciones reales realizadas en cada alineación omitiendo 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 manera que su extremo izquierdo esté entre $cy 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 a la posición $k 1$ de $T$ , se puede registrar una aparición de $P$ $sin comparar explícitamente el pasado k 1$ . Además de aumentar la eficiencia de Boyer-Moore, se requiere la regla de Galil 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ó de una versión generalizada para tratar las subcoincidencias como el algoritmo Apostolico-Giancarlo . ^[7]

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 solo si el patrón no aparece en el texto. Esto fue demostrado por primera vez por Knuth , Morris y Pratt en 1977, ^[3] seguidos por Guibas y Odlyzko en 1980 ^[8] 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. ^[9] $O(n+m)$

Cuando el patrón aparece en el texto, el tiempo de ejecución del algoritmo original es el peor de los casos. Esto es fácil de ver cuando tanto el patrón como el texto constan únicamente del 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. ^[6]^[9] $O(nm)$

Implementaciones

Existen varias implementaciones en diferentes lenguajes de programación. En C++ es parte de la biblioteca estándar desde C++ 17; además, Boost proporciona la implementación de búsqueda genérica 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 BoyerMooreFinder para coincidencias basadas en predicados dentro de rangos como parte de Phobos Runtime Library.

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

Implementación de Python

al  escribir  import  * # Esta versión es sensible al alfabeto inglés en ASCII para coincidencias que no distinguen entre mayúsculas y minúsculas. # Para eliminar esta característica, defina Alphabet_index como ord(c) y reemplace las instancias de "26" # con "256" o cualquier punto de código máximo que desee. Para Unicode, es posible que desee hacer coincidir el número de bytes en UTF-8 en lugar de crear una tabla de tamaño 0x10FFFF.ALFABETO_TAMAÑO  =  26def  índice_alfabeto ( c :  str )  ->  int : """Devuelve el índice del carácter dado en el alfabeto inglés, contando desde 0.""" val = ord ( c . lower ()) - ord ( "a" ) afirmar val >= 0 y val < ALPHABET_SIZE devolver val                def  match_length ( S :  str ,  idx1 :  int ,  idx2 :  int )  ->  int : """Devuelve la longitud de la coincidencia de las subcadenas de S que comienzan en idx1 e idx2.""" if idx1 == idx2 : devuelve len ( S ) - idx1 match_count = 0 mientras que idx1 < len ( S ) e idx2 < len ( S ) y S [ idx1 ] == S [ idx2 ]: match_count += 1 idx1 += 1 idx2 += 1 return match_count                                   def  fundamental_preprocess ( S :  str )  ->  list [ int ]: """Devuelve Z, el preprocesamiento fundamental de S.  Z[i] es la longitud de la subcadena que comienza en i, que también es un prefijo de S.  Este preprocesamiento se realiza en tiempo O(n), donde n es la longitud de S.  """  si  len ( S )  ==  0 : # Maneja el caso de  retorno de cadena vacía  [] if len ( S ) == 1 : # Maneja el caso de retorno de cadena de un solo carácter [ 1 ] z = [ 0 para x en S ] z [ 0 ] = len ( S ) z [ 1 ] = match_length ( S , 0 , 1 ) para i en el rango ( 2 , 1 + z [ 1 ]): # Optimización del ejercicio 1-5 z [ i ] = z [ 1 ] - i + 1 # Define los límites inferior y superior del cuadro z l = 0 r = 0 para i en el rango ( 2 + z [ 1 ], len ( S )): si i <= r : # i cae dentro del cuadro z existente k = i - l b = z [ k ] a = r - i + 1 si b < a : # b termina dentro del z-box existente z [ i ] = b else : # b termina en o después del final del z-box , necesitamos hacer una coincidencia explícita a la derecha del cuadro z z [ i ] = a + match_length ( S , a , r + 1 ) l = i r = i + z [ i ] - 1                                                                                                      else :  # i no reside dentro del z-box existente  z [ i ]  =  match_length ( S ,  0 ,  i )  if  z [ i ]  >  0 :  l  =  i  r  =  i  +  z [ i ]  -  1  return  zdef  bad_character_table ( S :  str )  ->  list [ list [ int ]]: """  Genera R para S, que es una matriz indexada por la posición de algún carácter c en el  alfabeto inglés. En ese índice en R hay una matriz de longitud |S|+1, especificando para cada  índice i en S (más el índice después de S) la siguiente ubicación del carácter c encontrada al  atravesar S de derecha a izquierda comenzando en i. Esto se utiliza para una búsqueda en tiempo constante  de la regla de caracteres incorrectos en el algoritmo de búsqueda de cadenas de Boyer-Moore, aunque tiene  un tamaño mucho mayor que las soluciones de tiempo no constante.  """ if len ( S ) == 0 : devuelve [[] para a dentro del rango ( ALPHABET_SIZE )] R = [[ - 1 ] para dentro del rango ( ALPHABET_SIZE ) ] alfa = [ - 1 para dentro del rango ( ALPHABET_SIZE )] para i , c en enumerar ( S ): alfa [ alfabeto_index ( c )] = i para j , a en enumerar ( alfa ): R [ j ] . agregar ( a ) devolver R                                         def  good_suffix_table ( S :  str )  ->  list [ int ]: """  Genera L para S, una matriz utilizada en la implementación de la regla fuerte del sufijo bueno.  L[i] = k, la posición más grande en S tal que S[i:] (el sufijo de S que comienza en i) coincide con  un sufijo de S[:k] (una subcadena en S que termina en k). Usado en Boyer-Moore, L proporciona una cantidad para  desplazar P en relación con T, tal que no se omita ninguna instancia de P en T y que un sufijo de P[:L[i]]  coincida con la subcadena de T que coincida con un sufijo de P en el intento de coincidencia anterior.  Específicamente, si la discrepancia tuvo lugar en la posición i-1 en P, la magnitud del desplazamiento viene dada  por la ecuación len(P) - L[i]. En el caso de que L[i] = -1, se utiliza la tabla de desplazamiento completa.  Dado que sólo importan los sufijos adecuados, L[0] = -1.  """ L = [ - 1 para c en S ] N = fundamental_preprocess ( S [:: - 1 ]) # S[::-1] invierte S N . invertir () para j en el rango ( 0 , len ( S ) - 1 ): i = len ( S ) - N [ j ] si i ! = len ( S ): L [ i ] = j devolver L                                  def  full_shift_table ( S :  str )  ->  list [ int ]: """  Genera F para S, una matriz utilizada en un caso especial de la regla del sufijo bueno en el  algoritmo de búsqueda de cadenas de Boyer-Moore. F[i] es el longitud del sufijo más largo de S[i:] que también es un  prefijo de S. En los casos en que se utiliza, la magnitud de desplazamiento del patrón P en relación con el  texto T es len(P) - F[i] para un falta de coincidencia que ocurre en i-1.  """ F = [ 0 para c en S ] Z = fundamental_preprocess ( S ) más largo = 0 para i , zv en enumerar ( invertido ( Z )): más largo = max ( zv , más largo ) si zv == i + 1 else F más largo [ - i - 1 ] = retorno más largo F                                      def  string_search ( P ,  T )  ->  list [ int ]: """  Implementación del algoritmo de búsqueda de cadenas de Boyer-Moore. Este encuentra todas las apariciones de P  en T e incorpora numerosas formas de preprocesar el patrón para determinar el patrón óptimo.  cantidad para cambiar la cadena y omitir comparaciones. En la práctica, se ejecuta en  tiempo O(m) (e incluso sublineal), donde m es la longitud de T. Esta implementación realiza una  búsqueda que no distingue entre mayúsculas y minúsculas en caracteres alfabéticos ASCII, espacios no incluidos.  """ si len ( P ) == 0 o len ( T ) == 0 o len ( T ) < len ( P ): devolver []                coincidencias  =  [] # Preprocesamiento  R  =  bad_character_table ( P )  L  =  good_suffix_table ( P )  F  =  full_shift_table ( P ) k  =  len ( P )  -  1  # Representa la alineación del final de P con respecto a T  anterior_k  =  - 1  # Representa la alineación en la fase anterior (regla de Galil)  mientras  k  <  len ( T ):  i  =  len ( P )  -  1  # Carácter para comparar en P  h  =  k  # Carácter para comparar en T  mientras  i  >=  0  y  h  >  anterior_k  y  P [ i ]  ==  T [ h ]:  # Coincidencias comenzando desde el final de P  i  -=  1  h  -=  1  if  i  ==  - 1  o  h  ==  anterior_k :  # Se ha encontrado coincidencia (regla de Galil)  coincidencias . append ( k  -  len ( P )  +  1 )  k  +=  len ( P )  -  F [ 1 ]  if  len ( P )  >  1  else  1  else :  # No coincide, cambia al máximo de reglas de caracteres malos y sufijos buenos  char_shift  =  i  -  R [ Alphabet_index ( T [ h ])][ i ]  if  i  +  1  ==  len ( P ):  # La falta de coincidencia ocurrió en el primer intento  suffix_shift  =  1  elif  L [ i  +  1 ]  ==  - 1 :  # Coincidente el sufijo no aparece en ninguna parte de P  suffix_shift  =  len ( P )  -  F [ i  +  1 ]  else :  # El sufijo coincidente aparece en P  suffix_shift  =  len ( P )  -  1  -  L [ i  +  1]  shift  =  max ( char_shift ,  suffix_shift )  anterior_k  =  k  if  shift  >=  i  +  1  else  anterior_k  # La regla de Galil  k  +=  shift  return  coincide

implementación de C

#incluir <stdint.h> #incluir <stddef.h > #incluir < stdbool.h> #incluir <stdlib.h> #incluir <unistd.h>     #definir ALPHABET_LEN 256 #definir max(a, b) ((a < b)? b : a)// REGLA DEL MAL CARÁCTER. // tabla delta1: delta1[c] contiene la distancia entre el último // carácter de pat y la aparición más a la derecha de c en pat. // // Si c no aparece en pat, entonces delta1[c] = patlen. // Si c está en cadena[i] y c != pat[patlen-1], podemos desplazar i // con seguridad en delta1[c], que es la distancia mínima necesaria para desplazar // avanzar para obtener la cadena [i] alineado con algún personaje en pat. // c == pat[patlen-1] devolver cero es sólo una preocupación para BMH, que // no tiene delta2. En tal caso, BMH hace que el valor sea palpable. // Seguimos esta opción en lugar del 0 original porque omite // más. (¿Corrección?) // // Este algoritmo se ejecuta en tiempo alfabeto_len+patlen. void make_delta1 ( ptrdiff_t * delta1 , uint8_t * pat , size_t patlen ) { for ( int i = 0 ; i < ALPHABET_LEN ; i ++ ) { delta1 [ i ] = patlen ; } for ( int i = 0 ; i < patlen ; i ++ ) { delta1 [ pat [ i ]] = patlen -1 - i ; } }                                 // verdadero si el sufijo de la palabra que comienza con palabra[pos] es un prefijo // de la palabra bool is_prefix ( uint8_t * palabra , tamaño_t palabralen , ptrdiff_t pos ) { int suffixlen = palabralen - pos ; // también podría usar la función de biblioteca strncmp() aquí // return ! strncmp(palabra, &palabra[pos], sufijo); for ( int i = 0 ; i < suffixlen ; i ++ ) { if ( palabra [ i ] ! = palabra [ pos + i ]) { return false ; } } devuelve verdadero ; }                                    // longitud del sufijo más largo de la palabra que termina en palabra[pos]. // longitud_sufijo("dddbcabc", 8, 4) = 2 tamaño_t longitud_sufijo ( uint8_t * palabra , tamaño_t palabralen , ptrdiff_t pos ) { tamaño_t i ; // incrementa la longitud del sufijo i hasta la primera discrepancia o comienzo // de la palabra for ( i = 0 ; ( word [ pos - i ] == palabra [ wordlen -1 - i ]) && ( i <= pos ); i ++ ); devolver yo ; }                         // REGLA DEL BUEN SUFIJO. // tabla delta2: dada una discrepancia en pat[pos], queremos alinear // con la siguiente posible coincidencia completa que podría basarnos en lo que // sabemos sobre pat[pos+1] y pat[patlen-1]. // // En el caso 1: // pat[pos+1] a pat[patlen-1] no ocurre en ningún otro lugar de pat, // la siguiente coincidencia plausible comienza en o después de la discrepancia. // Si, dentro de la subcadena pat[pos+1 .. patlen-1], se encuentra un prefijo // de pat, la siguiente coincidencia plausible es aquí (si hay varios // prefijos en la subcadena, elija el más largo). De lo contrario, // la siguiente coincidencia plausible comienza después del carácter alineado con // pat[patlen-1]. // // En el caso 2: // pat[pos+1] a pat[patlen-1] ocurre en otra parte de pat. El // desajuste nos dice que no estamos viendo el final de un partido. // Sin embargo, es posible que estemos ante la mitad de un partido. // // El primer bucle, que se ocupa del caso 1, es análogo a // la tabla KMP, adaptada para un orden de escaneo 'hacia atrás' con la // restricción adicional de que las subcadenas que considera // prefijos potenciales son todas sufijos. En el peor de los casos, // pat consta de la misma letra repetida, por lo que cada sufijo es // un prefijo. Sin embargo, este bucle por sí solo no es suficiente: // Supongamos que pat es "ABYXCDBYX" y el texto es ".....ABYXCDEYX". // Coincidiremos con X, Y y encontraremos B != E. No hay ningún prefijo pat // en el sufijo "YX", por lo que el primer bucle nos indica que avancemos // 9 caracteres. // Aunque superficialmente similar a la tabla KMP, la tabla KMP // se basa en información sobre el comienzo de la coincidencia parcial // que el algoritmo BM no tiene. // // El segundo bucle aborda el caso 2. Dado que suffix_length puede no ser // único, queremos tomar el valor mínimo, que nos dirá // a qué distancia está la posible coincidencia más cercana. void make_delta2 ( ptrdiff_t * delta2 , uint8_t * pat , size_t patlen ) { ssize_t p ; tamaño_t último_prefijo_índice = 1 ;              // primer bucle for ( p = patlen -1 ; p >= 0 ; p - ) { if ( is_prefix ( pat , patlen , p + 1 )) { last_prefix_index = p + 1 ; } delta2 [ p ] = último_prefijo_índice + ( patlen -1 - p ); }                       // segundo bucle for ( p = 0 ; p < patlen -1 ; p ++ ) { size_t slen = suffix_length ( pat , patlen , p ); if ( palmadita [ p - slen ] != palmadita [ patlen -1 - slen ]) { delta2 [ patlen -1 - slen ] = patlen -1 - p + slen ; } } }                                 // Devuelve el puntero a la primera coincidencia. // Véase también glibc memmem() (no BM) y std::boyer_moore_searcher (primera coincidencia). uint8_t * boyer_moore ( uint8_t * cadena , tamaño_t cadena , uint8_t * pat , tamaño_t patlen ) { ptrdiff_t delta1 [ ALPHABET_LEN ]; ptrdiff_t delta2 [ patlen ]; // C99 VLA make_delta1 ( delta1 , pat , patlen ); make_delta2 ( delta2 , pat , patlen );                      // El patrón vacío debe considerarse especialmente if ( patlen == 0 ) { return string ; }         tamaño_t i = patlen - 1 ; // str-idx while ( i < stringlen ) { ptrdiff_t j = patlen - 1 ; // pat-idx while ( j >= 0 && ( cadena [ i ] == pat [ j ])) { -- i ; -- j ; } si ( j < 0 ) { retorno y cadena [ i + 1 ]; }                                       ptrdiff_t shift = max ( delta1 [ cadena [ i ]], delta2 [ j ]); yo += cambio ; } devolver NULO ; }

implementación de java

 /**  * Devuelve el índice dentro de esta cadena de la primera aparición de la  * subcadena especificada. Si no es una subcadena, devuelve -1.  *  *No existe Galil porque solo genera una coincidencia.  *  * @param haystack La cadena a escanear  * @param aguja La cadena de destino a buscar  * @return El índice inicial de la subcadena  */ public static int indexOf ( char [] haystack , char [] aguja ) { if ( aguja . longitud == 0 ) { retorno 0 ; } int charTable [] = makeCharTable ( aguja ); int offsetTable [] = makeOffsetTable ( aguja ); for ( int i = aguja . longitud - 1 , j ; i < pajar . longitud ;) { for ( j = aguja . longitud - 1 ; aguja [ j ] == pajar [ i ] ; - i , - j ) { si ( j == 0 ) { retorno i ; } } // i += aguja.longitud - j; // Para método ingenuo i += Math . max ( offsetTable [ aguja . longitud - 1 - j ] , charTable [ pajar [ i ]] ); } retorno - 1 ; }                                                                       /**  * Crea la tabla de salto basándose en la información de caracteres que no coinciden.  */ private static int [] makeCharTable ( char [] aguja ) { final int ALPHABET_SIZE = Carácter . MAX_VALUE + 1 ; // 65536 int [] tabla = nuevo int [ ALPHABET_SIZE ] ; for ( int i = 0 ; i < table . length ; ++ i ) { table [ i ] = aguja . longitud ; } for ( int i = 0 ; i < aguja . longitud ; ++ i ) { tabla [ aguja [ i ]] = aguja . longitud - 1 - i ; } tabla de retorno ; }                                                       /**  * Crea la tabla de salto en función del desplazamiento de escaneo en el que se produce una discrepancia.  * (regla del mal carácter).  */ private static int [] makeOffsetTable ( char [] aguja ) { int [] tabla = new int [ aguja . longitud ] ; int lastPrefixPosition = aguja . longitud ; for ( int i = aguja . longitud ; i > 0 ; - i ) { if ( isPrefix ( aguja , i )) { lastPrefixPosition = i ; } mesa [ aguja . longitud -i ] = últimaPosiciónPrefijo -i + aguja . longitud ; } for ( int i = 0 ; i < aguja . longitud - 1 ; ++ i ) { int slen = sufijoLongitud ( aguja , i ); mesa [ slen ] = aguja . longitud - 1 - i + esbelto ; } tabla de retorno ; }                                                                          /**  * ¿Es aguja[p:end] un prefijo de aguja?  */ privado estático booleano isPrefix ( char [] aguja , int p ) { for ( int i = p , j = 0 ; i < aguja . longitud ; ++ i , ++ j ) { if ( aguja [ i ] ! = aguja [ j ] ) { return false ; } } devuelve verdadero ; }                                   /**  * Devuelve la longitud máxima de la subcadena que termina en p y es un sufijo.  * (regla de buen sufijo)  */ private static int suffixLength ( char [] aguja , int p ) { int len = 0 ; for ( int i = p , j = aguja . longitud - 1 ; i >= 0 && aguja [ i ] == aguja [ j ] ; -- i , -- j ) { len += 1 ; } devolver longitud ; }

Variantes

El algoritmo de Boyer-Moore-Horspool es una simplificación del algoritmo de Boyer-Moore que utiliza únicamente la regla del carácter incorrecto.

El algoritmo Apostolico-Giancarlo acelera el proceso de comprobar si se ha producido una coincidencia en la alineación dada omitiendo comparaciones explícitas de caracteres. Esto utiliza información obtenida durante el preprocesamiento del patrón junto con las longitudes de coincidencia de sufijos registradas en cada intento de coincidencia. El almacenamiento de longitudes coincidentes de sufijos requiere una tabla adicional del mismo tamaño que el texto que se busca.

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

Notas

^ m es la longitud de la cadena del patrón que estamos buscando en el texto, que tiene una longitud n . Este tiempo de ejecución sirve para encontrar todas las apariciones 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 buenos.

Referencias

^ Hume, Andrés; Domingo, 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 de búsqueda rápida de cadenas". Com. ACM . Nueva York: Asociación de Maquinaria de Computación. 20 (10): 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 comparación", Algoritmos sobre cadenas, árboles y secuencias (1 ed.), Cambridge University Press, págs. ISBN 0-521-58519-8
^ 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". Com. ACM . Nueva York: Asociación de Maquinaria de Computación. 22 (9): 505–508. doi :10.1145/359146.359148. ISSN 0001-0782. S2CID 1333465.
^ Apostólico, 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, Leónidas ; Odlyzko, Andrés (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 Informática . 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 segundo simposio anual ACM-SIAM sobre algoritmos discretos . Refresco '91. Filadelfia, Pensilvania: Sociedad de Matemáticas Industriales y Aplicadas: 224–233. ISBN 0-89791-376-0.
^ Haertel, Mike (21 de agosto de 2010). "Por qué GNU grep es rápido". Archivo de lista de correo actual de FreeBSD .

enlaces externos

Wikimedia Commons tiene medios relacionados con el 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 , coinventor del algoritmo
Artículo de Richard Cole de 1991 que demuestra la linealidad del tiempo de ejecución