En informática , el algoritmo de coincidencia de cadenas bidireccional es un algoritmo de búsqueda de cadenas eficiente que se puede ver como una combinación del algoritmo avanzado Knuth-Morris-Pratt y el algoritmo de búsqueda de cadenas Boyer-Moore retroactivo . Maxime Crochemore y Dominique Perrin inventaron este algoritmo en 1991. [1] El tiempo de preprocesamiento es lineal al tamaño de la aguja. Tiene un rendimiento lineal en el peor de los casos en comparaciones de 2n − m. [2] Breslauer tiene dos mejoras con menos comparaciones: una con comparaciones de espacio constante y n + piso (1 + eps / 2 × (n − m)), la otra con espacio log (m) y n + piso ((n− m) / 2) comparaciones. [3]
Clase | Algoritmo de búsqueda de cadenas |
---|---|
Estructura de datos | Cualquier cadena con un alfabeto ordenado |
Rendimiento en el peor de los casos | En) |
Rendimiento en el mejor de los casos | En) |
Complejidad espacial en el peor de los casos | O (1) |
Al igual que con KMP y BM, los algoritmos utilizan turnos basados en períodos que se repiten parcialmente en el patrón. Sin embargo, lo hace mediante la división (factorización crítica) de la aguja en dos mitades, de modo que solo se debe recordar un valor del preprocesamiento.
El algoritmo se considera bastante eficiente en condiciones del mundo real, es compatible con la memoria caché y contiene operaciones susceptibles de ser reemplazadas por funciones de biblioteca. Se selecciona como el algoritmo glibc (y newlib derivado; str-two-way.h) y musl para la familia de funciones de subcadena memmem y strstr. [4] [5] [6] Sin embargo, como con la mayoría de los algoritmos avanzados de búsqueda de cadenas, tiende a haber un punto de equilibrio en el tamaño tanto del pajar como de la aguja, antes del cual una cuadrática ingenua (memchr-memcmp) la implementación es más eficiente. [7] Glibc proporciona el algoritmo de Breslauer en ambas formas. [6]
Factorización crítica
Antes de definir la factorización crítica, debemos definir: [1]
- Factorización: una cadena se considera factorizada cuando se divide en dos mitades. Supongamos que una cadena x se divide en dos partes (u, v) , luego (u, v) se llama factorización de x。
- Período : un período p para una cadena x se define como un valor tal que para cualquier número entero 0 < i ≤ | x | - p , x [ i ] = x [ i + p ] . En otras palabras, " p es un período de x si dos letras de x a una distancia p siempre coinciden". El período mínimo de x es un número entero positivo denotado como p (x) .
- Una repetición w en (u, v) es una subcadena de x tal que:
- w es un sufijo de u o al revés;
- w es un prefijo de vo al revés;
- En otras palabras, w ocurre en ambos lados del corte con un posible desbordamiento en ambos lados. Cada factorización trivialmente tiene al menos una repetición, la cadena vu . [2]
- Un período local es la duración de una repetición en (u, v) . El período local más pequeño en (u, v) se denota como r (u, v) . Para cualquier factorización, 0 < r (u, v) ≤ | x | .
- Una factorización crítica es una factorización (u, v) de x tal que r (u, v) = p (x) . Para una aguja de longitud m en un alfabeto ordenado, se puede calcular en comparaciones de 2 m , calculando el lexicográficamente mayor de dos sufijos máximos ordenados, definidos para el orden ≤ y ≥. [6]
El algoritmo
El algoritmo comienza con la factorización crítica de la aguja como paso de preprocesamiento. Este paso produce el índice (punto de partida) de la mitad derecha periódica y el período de este tramo. El cálculo del sufijo aquí sigue la formulación de los autores. Alternativamente, se puede calcular utilizando el algoritmo de Duval más simple , que es más lento pero también lineal. [8]
Taquigrafía para inversión. función cmp (a, b) si a> b devuelve 1 si a = b devuelve 0 si a devuelve -1función maxsuf (n, rev) l ← len (n) p ← 1 período conocido actualmente. k ← 1 índice para pruebas de período, 0j ← 0 índice para la prueba maxsuf. mayor que maxs. i ← -1 el índice inicial propuesto de maxsuf mientras que j + k cmpv ← cmp (n [j + k], n [i + k]) si rev cmpv ← -cmpv invierte la comparación si cmpv <0 El sufijo (j + k) es menor. El punto es el prefijo completo hasta ahora. j ← j + k k ← 1 p ← j - i de lo contrario, si cmpv = 0 Son lo mismo, deberíamos continuar. si k = p Terminamos de comprobar este tramo de p. restablecer k. j ← j + p k ← 1 demás k ← k + 1 de lo contrario, el sufijo es más grande. Empiece desde aquí. i ← j j ← j + 1 p ← 1 k ← 1 volver [i, p]función crit_fact (n) [idx1, per1] ← maxsuf (n, falso) [idx2, per2] ← maxsuf (n, verdadero) if idx1> idx2 return [idx1, per1] else return [idx2, per2]
La comparación procede primero haciendo coincidir para el lado derecho, y luego para el lado izquierdo si coincide. La omisión de tiempo lineal se realiza utilizando el punto.
función de coincidencia (n, h) nl ← len (n) hl ← len (h) [l, p] ← hecho_crítico (n) P ← {} juego de fósforos. Coincide con el sufijo. Utilice una función de biblioteca como memcmp o escriba su propio bucle. si n [0] ... n [l] = n [l + 1] ... n [l + p] P ← {} pos ← 0 s ← 0 QUE HACER. Al menos pon el salto.
Referencias
- ^ a b Crochemore, Maxime; Perrin, Dominique (1 de julio de 1991). "Coincidencia de cadenas bidireccional" (PDF) . Revista de la ACM . 38 (3): 650–674. doi : 10.1145 / 116825.116845 .
- ^ a b "Algoritmo bidireccional" .
- ^ Breslauer, Dany (mayo de 1996). "Guardar comparaciones en el algoritmo de coincidencia de cadenas de Crochemore-Perrin" . Informática Teórica . 158 (1-2): 177-192. doi : 10.1016 / 0304-3975 (95) 00068-2 .
- ^ "musl / src / string / memmem.c" . Consultado el 23 de noviembre de 2019 .
- ^ "newlib / libc / string / memmem.c" . Consultado el 23 de noviembre de 2019 .
- ^ a b c "glibc / string / str-two-way.h" .
- ^ "Eric Blake - Re: PATCH] Mejorar el rendimiento de memmem" . Lista de correo de Newlib .
- ^ Adamczyk, Zbigniew; Rytter, Wojciech (mayo de 2013). "Una nota sobre un simple cálculo del sufijo máximo de una cuerda" . Diario de algoritmos discretos . 20 : 61–64. doi : 10.1016 / j.jda.2013.03.002 .