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 luego fueron 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.
Clase | Búsqueda de cadenas |
---|---|
Estructura de datos | Cuerda |
Rendimiento en el peor de los casos | Θ (m) preprocesamiento + O (mn) coincidencia [nota 1] |
Rendimiento en el mejor de los casos | Θ (m) preprocesamiento + Ω (n / m) coincidencia |
Complejidad espacial en el peor de los casos | Θ (k) [nota 2] |
Definiciones
A | norte | PAG | A | norte | METRO | A | norte | - |
PAG | A | norte | - | - | - | - | - | - |
- | PAG | A | norte | - | - | - | - | - |
- | - | PAG | A | norte | - | - | - | - |
- | - | - | PAG | A | norte | - | - | - |
- | - | - | - | PAG | A | norte | - | - |
- | - | - | - | - | PAG | A | norte | - |
- 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 algunos i en el rango [1, n ], donde n es la longitud de S .
- Un sufijo de S es una subcadena S [ i .. n ] para algunos i en el rango [1, n ], donde n es la longitud de S .
- La cadena que se debe buscar que se llama el patrón y se denota por P . Su longitud es m .
- El ser buscada en cadena que se llama el texto y se representa por T . Su longitud es n .
- Una alineación de P a T es un índice k en T de tal manera 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 si P es equivalente a T [( n - k +1) .. k ].
Descripción
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 hay), 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 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 el final del patrón se compara 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 n caracteres más adelante en el texto, donde n es la longitud del patrón. Si el carácter en el texto está en el patrón, entonces se realiza un cambio parcial del patrón a lo largo del texto para alinearse 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 todos los caracteres del texto disminuye el número de comparaciones que deben realizarse, 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 n 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 que se alcanza el comienzo de P (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 realizan de nuevo 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 cambio se implementan como consultas de tabla de constante de tiempo, el uso de tablas generados durante el procesamiento previo de P .
Reglas de turno
Un cambio se calcula aplicando dos reglas: la regla del carácter incorrecto y la regla del sufijo bueno. La compensación de cambio real es el máximo de los cambios calculados por estas reglas.
La regla del mal carácter
Descripción
- | - | - | - | X | - | - | K | - | - | - |
A | norte | PAG | A | norte | METRO | A | norte | A | METRO | - |
- | norte | norte | A | A | METRO | A | norte | - | - | - |
- | - | - | norte | norte | A | A | METRO | A | norte | - |
La regla del carácter incorrecto considera el carácter en T en el que falló el proceso de comparación (asumiendo que ocurrió tal fallo). Se encuentra la siguiente ocurrencia de ese carácter a la izquierda en P , y se propone un cambio que alinea esa ocurrencia con la ocurrencia no coincidente en T. Si el carácter no coincidente no ocurre a la izquierda en P , se propone un cambio que mueve la totalidad de P más allá del punto de discrepancia.
Preprocesamiento
Los métodos varían en la forma exacta que debe tomar la tabla para la regla del carácter incorrecto, 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 segundo 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 altoo -1 si no existe tal ocurrencia. El turno propuesto será entonces, con tiempo de búsqueda y espacio, asumiendo un alfabeto finito de longitud k .
Las implementaciones de C y Java a continuación tienen un complejidad del espacio (make_delta1, makeCharTable). Es lo mismo que el delta1 original y la tabla de caracteres incorrectos BMH . Esta tabla mapea un personaje en la posición cambiar por , con la última instancia, la menor cantidad de turno, teniendo prioridad. Todos los caracteres no utilizados se establecen como como valor centinela.
La regla del buen sufijo
Descripción
- | - | - | - | X | - | - | K | - | - | - | - | - |
METRO | A | norte | PAG | A | norte | A | METRO | A | norte | A | PAG | - |
A | norte | A | METRO | PAG | norte | A | METRO | - | - | - | - | - |
- | - | - | - | A | norte | A | METRO | PAG | norte | A | METRO | - |
La regla del sufijo bueno es mucho más compleja tanto en concepto como en implementación que la regla de carácter incorrecto. Al igual que la regla del carácter incorrecto, también explota la función de comparaciones del algoritmo comenzando al final del patrón y avanzando hacia el inicio del patrón. Puede describirse de la siguiente manera: [5]
Suponga que para una alineación dada de P y T , una subcadena t de T coincide con un sufijo de P , pero ocurre una falta de coincidencia en la siguiente comparación a la izquierda. 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 . Shift P a la derecha para que subcadena t' en P se alinea con subcadena t en T . Si t' no existe, a continuación, desplazar el extremo izquierdo de P más allá del extremo izquierdo de T en T por la menor cantidad de modo que un prefijo del patrón desplazado coincide con un sufijo de t en T . Si no hay tal cambio es posible, entonces desplazar P por n lugares a la derecha. Si una ocurrencia de P se encuentra, a continuación, cambiar P por la menor cantidad de modo que una adecuada prefijo de la cambió P coincide con un sufijo de la ocurrencia de P en T . Si tal cambio no es posible, entonces mueva P en n lugares, es decir, mueva P más allá de t .
Preprocesamiento
La regla del sufijo bueno requiere dos tablas: una para usar en el caso general y otra para usar cuando el caso general no devuelve ningún resultado significativo o se produce una coincidencia. Estas tablas se designarán L y H respectivamente. Sus definiciones son las siguientes: [5]
Para cada i ,es la posición más grande menor que n tal que cadena coincide con un sufijo de y tal que el carácter que precede a ese sufijo no es igual a . se define como cero si no hay ninguna posición que satisfaga la condición.
Dejar denotar la longitud del sufijo más grande de que también es un prefijo de P , si existe. Si no existe ninguno, dejemos ser cero.
Ambas tablas se pueden construir en tiempo y uso espacio. El cambio de alineación para el índice i en P está dado por o . H solo debe usarse si es cero o se ha encontrado una coincidencia.
La regla de Galil
Zvi Galil propuso una optimización simple pero importante de Boyer-Moore en 1979. [6] A diferencia del cambio, 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 es comparada con T a carácter c de T . Entonces, si P se desplaza a k 2 tal 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 bajan a la posición k 1 de T , se puede registrar una ocurrencia 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 probar 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 la subcadena solo en c = 0 , es decir, una coincidencia completa. En 1985 se informó una versión generalizada para tratar 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 de solo si el patrón no aparece en el texto. Esto fue probado por primera vez por Knuth , Morris y Pratt en 1977, [8] seguidos 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 no se producen en el texto, el tiempo de funcionamiento del algoritmo original esEn 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] [10]
Implementaciones
Existen varias implementaciones en diferentes lenguajes de programación. En C ++ es parte de la biblioteca estándar desde C ++ 17, también 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 un BoyerMooreFinder para la coincidencia basada en predicados dentro de rangos como parte de la biblioteca de tiempo de ejecución de Phobos.
El algoritmo de Boyer-Moore también se usa en el grep de GNU . [11]
A continuación se muestran algunas implementaciones simples.
al escribir import * # Esta versión es sensible al alfabeto inglés en ASCII para la coincidencia que no distingue 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 en UTF-8 # bytes en lugar de crear una tabla del tamaño de 0x10FFFF.TAMAÑO_ALFABETO = 26def alphabet_index ( 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 return valdef match_length ( S : str , idx1 : int , idx2 : int ) -> int : "" "Devuelve la longitud de la coincidencia de las subcadenas de S comenzando en idx1 e idx2." "" if idx1 == idx2 : return len ( S ) - idx1 match_count = 0 mientras idx1 < len ( S ) e idx2 < len ( S ) y S [ idx1 ] == S [ idx2 ]: match_count + = 1 idx1 + = 1 idx2 + = 1 return match_countdef 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 caso de cadena vacía return [] if len ( S ) == 1 : # Maneja caso de cadena de un solo carácter return [ 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 de la caja z l = 0 r = 0 para i en el rango ( 2 + z [ 1 ], len ( S )): si i <= r : # i cae dentro de la caja z existente k = i - l b = z [ k ] a = r - i + 1 si b < a : # b termina dentro de la caja z existente z [ i ] = b else : # b termina en o después del final de la caja z , necesitamos hacer una coincidencia explícita a la derecha de la caja z z [ i ] = a + match_length ( S , a , r + 1 ) l = i r = i + z [ i ] - 1 else : # i no reside dentro del cuadro z existente z [ i ] = match_length ( S , 0 , i ) si z [ i ] > 0 : l = i r = i + z [ i ] - 1 volver 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 encontrado al atravesar S de derecha a izquierda comenzando en i. Esto se usa para una búsqueda de tiempo constante para la regla del carácter incorrecto 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. "" " si len ( S ) == 0 : devuelve [[] para un en rango ( ALPHABET_SIZE )] R = [[ - 1 ] para un dentro del rango ( ALPHABET_SIZE )] alfa = [ - 1 para un dentro del rango ( ALPHABET_SIZE )] para i , c en enumerate ( S ): alpha [ alphabet_index ( c )] = i para j , a en enumerar ( alfa ): R [ j ] . añadir ( a ) devolver Rdef good_suffix_table ( S : str ) -> List [ int ]: "" " Genera L para S, una matriz utilizada en la implementación de la regla de sufijo bueno fuerte. 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 da una cantidad para desplazar P en relación con T tal que no se omiten instancias de P en T y un sufijo de P [: L [i]] coincide con la subcadena de T emparejada 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 usa la tabla de desplazamiento completo. Dado que solo importan los sufijos propios, L [0] = . -1 """ L = [ - 1 para c en S ] N = fundamental_preprocess ( S [:: - 1 ]) # S [:: - 1] invierte S N . reverse () para j en el rango ( 0 , len ( S ) - 1 ): i = len ( S ) - N [ j ] si i ! = len ( S ): L [ i ] = j return Ldef full_shift_table ( S : str ) -> List [ int ]: "" " Genera F para S, una matriz utilizada en un caso especial de la regla de sufijo bueno en el algoritmo de búsqueda de cadenas de Boyer-Moore . F [i] es la longitud del sufijo más largo de S [i:] que también es un prefijo de S. En los casos en que se usa, la magnitud de desplazamiento del patrón P en relación con el texto T es len (P) - F [i] para un desajuste ocurriendo en i-1. "" " F = [ 0 para c en S ] Z = fundamental_preprocess ( S ) más largo = 0 para i , zv en enumerate ( invertido ( Z )): más largo = máx ( zv , más largo ) si zv == i + 1 más largo F [ - 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. Esto encuentra todas las apariciones de P en T e incorpora numerosas formas de preprocesar el patrón para determinar el óptimo cantidad para cambiar la cadena y omitir las 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 ): return [] 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 en relación con 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 si i == - 1 o h == previous_k : # Se ha encontrado una 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 el máximo de caracteres incorrectos y reglas de sufijo bueno char_shift = i - R [ alphabet_index ( T [ h ])] [ i ] si i + 1 == len ( P ): # Se produjo una falta de coincidencia en el primer intento suffix_shift = 1 elif L [ i + 1 ] == - 1 : # Sufijo coincidente 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 ) previous_k = k if shift > = i + 1 else previous_k # Regla de Galil k + = shift return coincide
#include #include #include #include #define ALPHABET_LEN 256 #define max (a, b) ((a // REGLA DEL MAL CARACTER. // 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 la cadena [i] y c! = Pat [patlen-1], podemos cambiar i // de forma segura en delta1 [c], que es la distancia mínima necesaria para desplazar // pat hacia adelante para obtener la cadena [i] alineado con algún personaje en pat. // c == pat [patlen-1] devolver cero es solo una preocupación para BMH, que // no tiene delta2. BMH hace que el valor patlen en tal caso. // Seguimos esta elección en lugar del 0 original porque omite // más. (¿corrección?) // // Este algoritmo se ejecuta en tiempo alphabet_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 ; } para ( int i = 0 ; i < patlen -2 ; i ++ ) { delta1 [ pat [ i ]] = patlen -1 - i ; } }// verdadero si el sufijo de la palabra que comienza en word [pos] es un prefijo // de la palabra bool is_prefix ( uint8_t * word , size_t wordlen , ptrdiff_t pos ) { int suffixlen = wordlen - pos ; // también podría usar la función de biblioteca strncmp () aquí // ¡return! strncmp (palabra, & palabra [pos], sufijolen); for ( int i = 0 ; i < sufijolen ; i ++ ) { if ( word [ i ] ! = word [ pos + i ]) { return false ; } } devuelve verdadero ; }// longitud del sufijo más largo de la palabra que termina en la palabra [pos]. // suffix_length ( "dddbcabc", 8, 4) = 2 size_t suffix_length ( uint8_t * palabra , size_t wordlen , ptrdiff_t pos ) { size_t i ; // incrementa la longitud del sufijo i hasta la primera discrepancia o comienzo // de la palabra para ( i = 0 ; ( palabra [ pos - i ] == palabra [ wordlen -1 - i ]) && ( i < pos ); i + + ); volver i ; }// BUENA REGLA DEL SUFIJO. // tabla delta2: dada una falta de coincidencia en pat [pos], queremos alinear // con la siguiente coincidencia completa posible que podría basarse en lo que // sabemos acerca de pat [pos + 1] a pat [patlen-1]. // // En el caso 1: // pat [pos + 1] to pat [patlen-1] no ocurre en ningún otro lugar de pat, // la siguiente coincidencia plausible comienza en o después de la falta de coincidencia. // Si, dentro de la subcadena pat [pos + 1 .. patlen-1], se encuentra un prefijo // de pat, la siguiente coincidencia plausible está aquí (si hay múltiples // 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] to pat [patlen-1] ocurre en otra parte de pat. La falta de coincidencia // nos dice que no estamos viendo el final de una coincidencia. // Sin embargo, es posible que estemos mirando a la mitad de un partido. // // El primer ciclo, que se ocupa del caso 1, es análogo a // la tabla KMP, adaptada para un orden de exploración 'hacia atrás' con la // restricción adicional de que las subcadenas que considera como // prefijos potenciales son todas sufijos. En el peor de los casos, // pat consiste en la misma letra repetida, por lo que cada sufijo es // un prefijo. Sin embargo, este ciclo por sí solo no es suficiente: // Supongamos que pat es "ABYXCDBYX" y el texto es "..... ABYXCDEYX". // Emparejaremos X, Y, y encontraremos B! = E. No hay un prefijo de pat // en el sufijo "YX", por lo que el primer ciclo nos dice que saltemos // 9 caracteres hacia adelante . // 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 ciclo aborda el caso 2. Dado que suffix_length puede no ser // único, queremos tomar el valor mínimo, que nos dirá // qué tan lejos está la coincidencia potencial más cercana. vacío make_delta2 ( ptrdiff_t * delta2 , uint8_t * pat , size_t patlen ) { ssize_t p ; size_t last_prefix_index = patlen -1 ; // primer ciclo para ( p = patlen -1 ; p > = 0 ; p - ) { if ( is_prefix ( pat , patlen , p + 1 )) { last_prefix_index = p + 1 ; } delta2 [ p ] = last_prefix_index + ( patlen -1 - p ); } // segundo ciclo para ( p = 0 ; p < patlen -1 ; p ++ ) { size_t slen = suffix_length ( pat , patlen , p ); if ( pat [ p - slen ] ! = pat [ patlen -1 - slen ]) { delta2 [ patlen -1 - slen ] = patlen -1 - p + slen ; } } }// Devuelve el puntero a la primera coincidencia. // Vea también glibc memmem () (non-BM) y std :: boyer_moore_searcher (first-match). uint8_t * boyer_moore ( uint8_t * cadena , size_t stringlen , uint8_t * pat , size_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 si ( patlen == 0 ) { return string ; } size_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 ; } if ( j < 0 ) { return & string [ i + 1 ]; } ptrdiff_t shift = max ( delta1 [ cadena [ i ]], delta2 [ j ]); i + = desplazamiento ; } return NULL ; }
/ ** * Devuelve el índice dentro de esta cadena de la primera aparición de la * subcadena especificada. Si no es una subcadena, devuelve -1. * * No hay Galil porque solo genera una coincidencia. * * @param haystack La cadena a escanear * @param needle La cadena de destino a buscar * @return El índice de inicio de la subcadena * / public static int indexOf ( char [] haystack , char [] needle ) { if ( needle . 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 ) { if ( j == 0 ) { return i ; } } // i + = aguja.longitud - j; // Para el método ingenuo i + = Math . max ( offsetTable [ aguja . longitud - 1 - j ] , charTable [ pajar [ i ]] ); } retorno - 1 ; } / ** * Hace que la tabla de salto se base en la información de los caracteres no coincidentes. * / private static int [] makeCharTable ( char [] aguja ) { final int ALPHABET_SIZE = Character . MAX_VALUE + 1 ; // 65536 int [] tabla = new int [ TAMAÑO_ALFABETO ] ; for ( int i = 0 ; i < table . length ; ++ i ) { table [ i ] = aguja . longitud ; } for ( int i = 0 ; i < aguja . longitud - 1 ; ++ i ) { tabla [ aguja [ i ]] = aguja . longitud - 1 - i ; } tabla de retorno ; } / ** * Hace que la tabla de salto se base en el desplazamiento de exploración en el que se produce la falta de coincidencia. * (regla de carácter incorrecto). * / private static int [] makeOffsetTable ( char [] aguja ) { int [] tabla = nueva 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 ] = lastPrefixPosition - i + aguja . longitud ; } for ( int i = 0 ; i < aguja . longitud - 1 ; ++ i ) { int slen = suffixLength ( aguja , i ); mesa [ slen ] = aguja . longitud - 1 - i + slen ; } tabla de retorno ; } / ** * ¿Es la aguja [p: end] un prefijo de la aguja? * / private static boolean isPrefix ( char [] needle , int p ) { for ( int i = p , j = 0 ; i < needle . length ; ++ i , ++ j ) { if ( needle [ i ] ! = aguja [ j ] ) { devolver falso ; } } devuelve verdadero ; } / ** * Devuelve la longitud máxima de la subcadena que termina en py es un sufijo. * (buena regla de sufijo) * / private static int suffixLength ( char [] aguja , int p ) { int len = 0 ; para ( int i = p , j = aguja . longitud - 1 ; i > = 0 && aguja [ i ] == aguja [ j ] ; - i , - j ) { len + = 1 ; } return len ; }
Variantes
El algoritmo de Boyer-Moore-Horspool es una simplificación del algoritmo de Boyer-Moore que utiliza solo 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 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 longitudes de coincidencia de sufijo requiere una tabla adicional del mismo tamaño que el texto que se busca.
El algoritmo de Raita mejora el rendimiento del algoritmo de Boyer-Moore-Horspool. El patrón de búsqueda de una subcadena particular en una cadena dada es diferente del algoritmo de Boyer-Moore-Horspool.
Notas
- ^ m es la longitud de la cadena de patrón, que estamos buscando en el texto, que es de longitud n . Este tiempo de ejecución es para buscar todas las apariciones del patrón, sin la regla de Galil.
- ^ k es el tamaño del alfabeto
Referencias
- ^ Hume; Domingo (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". Comm. ACM . Nueva York: Association for Computing Machinery. 20 (10): 762–772. doi : 10.1145 / 359842.359859 . ISSN 0001-0782 . S2CID 15892987 .
- ^ Knuth, Donald E .; Morris, Jr., James H .; Pratt, Vaughan R. (1977). "Coincidencia de patrones rápida en cadenas". Revista SIAM de Computación . 6 (2): 323–350. 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 .
- ^ a b Gusfield, Dan (1999) [1997], "Capítulo 2 - Coincidencia exacta: Métodos clásicos basados en la comparación", Algoritmos sobre cadenas, árboles y secuencias (1 ed.), Cambridge University Press, págs. 19-21, ISBN 0521585198
- ^ a b Galil, Z. (septiembre de 1979). "Sobre la mejora del peor tiempo de ejecución del algoritmo de coincidencia de cadenas de Boyer-Moore". Comm. ACM . Nueva York: Association for Computing Machinery. 22 (9): 505–508. doi : 10.1145 / 359146.359148 . ISSN 0001-0782 . S2CID 1333465 .
- ^ Apostolico, Alberto; Giancarlo, Raffaele (febrero de 1986). "Las estrategias de búsqueda de cadenas de Boyer-Moore-Galil revisitadas" . Revista SIAM de Computación . 15 : 98-105. doi : 10.1137 / 0215007 .
- ^ Knuth, Donald ; Morris, James H .; Pratt, Vaughan (1977). "Emparejamiento rápido de patrones en cadenas" . Revista SIAM de Computación . 6 (2): 323–350. CiteSeerX 10.1.1.93.8147 . doi : 10.1137 / 0206024 .
- ^ 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 . Washington, Distrito de Columbia: IEEE Computer Society: 189-195. doi : 10.1109 / SFCS.1977.3 . S2CID 6470193 .
- ^ a b Cole, Richard (septiembre de 1991). "Límites estrictos en la complejidad del algoritmo de coincidencia de cadenas de Boyer-Moore" . Actas del 2do Simposio Anual ACM-SIAM sobre Algoritmos Discretos . Filadelfia, Pensilvania: Sociedad de Matemáticas Industriales y Aplicadas: 224-233. ISBN 0-89791-376-0.
- ^ https://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html
enlaces externos
- Artículo original sobre el algoritmo de Boyer-Moore
- Un ejemplo del algoritmo de Boyer-Moore de la página de inicio de J Strother Moore , co-inventor del algoritmo
- El artículo de 1991 de Richard Cole que demuestra la linealidad del tiempo de ejecución