Hispanopedia Wiki
Articulo de referencia

Algoritmo de Raita

En informática, el algoritmo Raita es un algoritmo de búsqueda de cadenas que mejora el rendimiento del algoritmo Boyer-Moore-Horspool . Este algoritmo preprocesa la cadena que ...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática, el algoritmo Raita es un algoritmo de búsqueda de cadenas que mejora el rendimiento del algoritmo Boyer-Moore-Horspool . Este algoritmo preprocesa la cadena que se busca para encontrar el patrón, de forma similar al algoritmo de búsqueda de cadenas de Boyer-Moore . El patrón de búsqueda de una subcadena específica dentro de una cadena dada difiere del algoritmo Boyer-Moore-Horspool. Este algoritmo fue publicado por Timo Raita en 1991. [ 1 ]

Descripción

El algoritmo 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".

  1. En primer lugar, se compara el último carácter del patrón con el carácter situado más a la derecha de la ventana.
  2. Si hay una coincidencia, el primer carácter del patrón se compara con el carácter situado más a la izquierda de la ventana.
  3. Si vuelven a coincidir, compara el carácter central del patrón con el carácter central de la ventana.

Si la comprobación previa es exitosa, la comparación original comienza desde el segundo carácter hasta el penúltimo. Si se produce una discrepancia en cualquier etapa del algoritmo, se aplica la función de desplazamiento de caracteres incorrectos, calculada en la fase de preprocesamiento. Esta función es idéntica a la propuesta en el algoritmo de Boyer-Moore-Horspool. [ 1 ]

Una formulación moderna de una comprobació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 de Raita

#include <limits.h> #include <stddef.h>#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 ; for ( i = 0 ; i < ALPHABET_SIZE ; ++ i ) bmBc [ i ] = lpat ; for ( 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 ];/* Casos límite rápidos. */ 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 ) { OUTPUT ( match_ptr - s ); match_ptr ++ ; } else return ; } }preBmBc ( palmadita , lpat , bmBc );/* La ventana previa al partido. */ char firstCh = pat [ 0 ]; char middleCh = palmadita [ lpat / 2 ]; char lastCh = palmadita [ lpat - 1 ];/* Búsqueda */ ptrdiff_t j = 0 ; while ( j <= n - m ) { char c = s [ j + lpat - 1 ]; /* Esto podría perjudicar la localidad de los 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 ) OUTPUT ( j ); j ​​+= bmBc [ c ]; } }

Ejemplo

Patrón: abddb

Texto: abbaabaabddbabadbb

Etapa de preprocesamiento:

 yd 4 3 1
Intento 1: abbaabaabddbabadbb ....b Desplazamiento de 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. Existe una discrepancia y se ha desplazado 4 posiciones según el valor de la etapa de preprocesamiento.

Intento 2: abbaabaabddbabadbb AdB Desplazamiento de 3 (bmBc[b])

Aquí, el primer y el último carácter del patrón coinciden, pero el carácter central no coincide. Por lo tanto, el patrón se desplaza según la etapa de preprocesamiento.

Intento 3: abbaabaabddbabadbb ABDDB Desplazamiento de 3 (bmBc[b])

Hemos encontrado una coincidencia exacta, pero el algoritmo continúa hasta que no pueda avanzar más.

Intento 4: abbaabaABDDBabadbb ....b Desplazamiento de 4 (bmBc[a])

En esta etapa, necesitamos desplazar 4 posiciones y no podemos mover el patrón 4 posiciones. Por lo tanto, el algoritmo finaliza. Las letras en mayúscula coinciden exactamente con el patrón del texto.

Complejidad

  1. La etapa de preprocesamiento toma un tiempo O(m), donde "m" es la longitud del patrón "P".
  2. La etapa de búsqueda tiene una complejidad temporal de O(mn), donde "n" es la longitud del texto "T".

Véase también

Referencias

  1. 1 2 RAITA T., 1992, Ajuste del algoritmo de búsqueda de cadenas de Boyer–Moore–Horspool, Software - Practice & Experience, 22(10):879-884
  2. ↑ "⚙ D27068 Mejorar string::find" . Revisión de código LLVM .
  • Animación de applet y descripción del algoritmo Raita