En informática, el algoritmo de Raita es un algoritmo de búsqueda de cadenas que mejora el rendimiento del algoritmo de Boyer-Moore-Horspool . Este algoritmo preprocesa la cadena que se busca para el patrón, que es similar al algoritmo de búsqueda de cadenas de Boyer-Moore . El patrón de búsqueda de una subcadena particular en una cadena dada es diferente del algoritmo de Boyer-Moore-Horspool. Este algoritmo fue publicado por Timo Raita en 1991. [1]
Descripción
El algoritmo de Raita busca un patrón "P" en un texto dado "T" comparando cada carácter del patrón en el texto dado. La búsqueda se realizará de la siguiente manera. La ventana para un texto "T" se define como la longitud de "P".
- Primero, el último carácter del patrón se compara con el carácter más a la derecha de la ventana.
- Si hay una coincidencia, el primer carácter del patrón se compara con el carácter más a la izquierda de la ventana.
- Si vuelven a coincidir, compara el carácter intermedio del patrón con el carácter intermedio de la ventana.
Si todo en la verificación previa es exitoso, entonces la comparación original comienza desde el segundo carácter hasta el último menos uno. Si hay una falta de coincidencia en cualquier etapa del algoritmo, realiza la función de cambio de carácter incorrecto que se calculó en la fase de preprocesamiento. La función de cambio de carácter incorrecto es idéntica a la propuesta en el algoritmo de Boyer-Moore-Horspool. [1]
Una formulación moderna de una verificación previa similar se encuentra en std::string::find
, un comparador de cadenas lineal / cuadrático, en libc ++ y libstdc ++. Suponiendo una versión bien optimizada de memcmp
, no omitir caracteres en la "comparación original" tiende a ser más eficiente ya que es probable que el patrón esté alineado. [2]
Código C para el algoritmo Raita
#include #include #define ALPHABET_SIZE (1 << CHAR_BITS) / * normalmente 256 * // * Preprocesamiento: la tabla de coincidencias incorrectas de BMH. * / static inline void preBmBc ( char * pat , size_t lpat , ptrdiff_t bmBc []) { size_t i ; para ( i = 0 ; i < TAMAÑO_ALFABETO ; ++ i ) bmBc [ i ] = lpat ; para ( i = 0 ; i < lpat - 1 ; ++ i ) bmBc [ pat [ i ]] = lpat - i - 1 ; }void Raita ( Char * pat , size_t LPAT , Char * s , size_t n ) { ptrdiff_t BMBC [ ALPHABET_SIZE ]; / * Estuches de borde rápido. * / if ( lpat == 0 || lpat > n ) return ; if ( lpat == 1 ) { char * match_ptr = s ; while ( match_ptr < s + n ) { match_ptr = memchr ( match_ptr , pat [ 0 ], n - ( match_ptr - s )); if ( match_ptr ! = NULL ) { SALIDA ( match_ptr - s ); match_ptr ++ ; } else return ; } } preBmBc ( pat , lpat , bmBc ); / * La ventana de prematch. * / char firstCh = pat [ 0 ]; char middleCh = pat [ lpat / 2 ]; char lastCh = pat [ lpat - 1 ]; / * Buscando * / ptrdiff_t j = 0 ; while ( j <= n - m ) { char c = s [ j + lpat - 1 ]; / * Esto podría dañar la localidad de datos en patrones largos. Para estos, considere reducir * el número de pruebas previas o usar índices más agrupados. * / if ( lastCh == c && middleCh == s [ j + lpat / 2 ] && firstCh == s [ j ] && memcmp ( & pat [ 1 ], & s [ j + 1 ], lpat - 2 ) = = 0 ) SALIDA ( j ); j + = bmBc [ c ]; } }
Ejemplo
Patrón: abddb
Texto: abbaabaabddbabadbb
Etapa de preprocesamiento:
abd 4 3 1
Intento 1: abbaabaabddbabadbb ....B Desplazar en 4 (bmBc [a])
Comparación del último carácter del patrón con el carácter situado más a la derecha en la ventana. Es un desajuste y se desplazó en 4 de acuerdo con el valor en la etapa de preprocesamiento.
Intento 2: abbaabaabddbabadbb AdB Desplazar en 3 (bmBc [b])
Aquí el último y el primer carácter del patrón coinciden, pero el carácter intermedio no coincide. Entonces, el patrón se cambia de acuerdo con la etapa de preprocesamiento.
Intento 3: abbaabaabddbabadbb ABDDB Desplazar en 3 (bmBc [b])
Encontramos una coincidencia exacta aquí, pero el algoritmo continúa hasta que no puede avanzar más.
Intento 4: abbaabaABDDBabadbb ....B Desplazar en 4 (bmBc [a])
En esta etapa, necesitamos cambiar en 4 y no podemos mover el patrón en 4. Entonces, el algoritmo termina. Las letras en mayúscula coinciden exactamente con el patrón del texto.
Complejidad
- La etapa de preprocesamiento toma O (m) tiempo donde "m" es la longitud del patrón "P".
- La etapa de búsqueda toma O (mn) complejidad de tiempo donde "n" es la longitud del texto "T".
Ver también
Referencias
- ^ a b RAITA T., 1992, Ajuste del algoritmo de búsqueda de cadenas de Boyer-Moore-Horspool, Software - Práctica y experiencia, 22 (10): 879-884 [1]
- ^ "⚙ D27068 Mejorar cadena :: buscar" . Revisión del código LLVM .