Consulta de rango mínimo

En informática , una consulta de mínimo de rango ( RMQ ) resuelve el problema de encontrar el valor mínimo en un subconjunto de un conjunto de objetos comparables. Las consultas de mínimo de rango tienen diversas aplicaciones en informática, como el problema del ancestro común más bajo y el problema del prefijo común más largo (LCP).

Definición

Construir el árbol cartesiano correspondiente para resolver una consulta de mínimo de rango. — La consulta de rango mínimo se reduce al problema del ancestro común más bajo .

Dado un array $A$ $[1 \dots$ $n$ $]$ de $n$ objetos tomados de un conjunto totalmente ordenado , como enteros, la consulta de mínimo de rango $RMQ$ $A$ $($ $l$ $,$ $r$ $) =arg min$ $A$ $[$ $k$ $]$ (con $1 \leq$ $l$ $\leq$ $k$ $\leq$ $r$ $\leq$ $n$ ) devuelve la posición del elemento mínimo en el sub-array especificado $A$ $[$ $l$ $\dots$ $r$ $]$ .

Por ejemplo, cuando $A = [0,5,2,5,4,3,1,6,3]$ , entonces la respuesta a la consulta de mínimo de rango para el subconjunto $A [3 \dots 8] = [2,5,4,3,1,6]$ es7 , ya que $A [7] = 1$ .

Algoritmos

Solución ingenua

En un entorno típico, el array $A$ es estático, es decir, no se insertan ni se eliminan elementos durante una serie de consultas, y las consultas que se responden en línea (es decir, el algoritmo no conoce de antemano el conjunto completo de consultas). En este caso, un preprocesamiento adecuado del array en una estructura de datos garantiza una respuesta más rápida a las consultas. Una solución ingenua consiste en precalcular todas las consultas posibles, es decir, el mínimo de todos los sub-arrays de $A$ , y almacenarlas en un array $B$ tal que $B [i, j] = min(A [i \dots j])$ ; entonces, una consulta de rango mínimo se puede resolver en tiempo constante mediante una búsqueda en el array $B.$ Hay $Θ(n²)$ consultas posibles para un array de longitud $n$ , y las respuestas a estas se pueden calcular en tiempo $Θ(n²) mediante$ programación dinámica . ^{[ 1 ]}

Solución utilizando tiempo constante después del preprocesamiento espacio-temporal linealítmico.

Como en la solución anterior, responder consultas en tiempo constante se logrará mediante el preprocesamiento de resultados. Sin embargo, el arreglo almacenará consultas de mínimos de rango precalculados no para cada rango $[i, j]$ , sino solo para rangos cuyo tamaño sea una potencia de dos . Hay $O(log n)$ de estas consultas para cada posición inicial $i$ , por lo que el tamaño de la tabla de programación dinámica $B$ es $O(n log n)$ . El valor de $B [i, j]$ es el índice del mínimo del rango $A [i \dots i + 2j -1]$ . Llenar la tabla toma un tiempo $O(n log n)$ , con los índices de los mínimos usando la siguiente recurrencia ^{[ 1 ]}^{[ 2 ].}

Si

A [B [i, j -1]] \leq A [B [i +2 j -1, j -1]]

, entonces

B [i, j] = B [i, j -1]

;

de lo contrario,

B [i, j] = B [i +2 j -1, j -1]

.

Tras este paso de preprocesamiento, una consulta $RMQ A (l, r)$ puede responderse en tiempo constante dividiéndola en dos consultas separadas: una es la consulta precalculada con un rango desde $l$ hasta el mayor valor memorizado menor que $r$ . La otra es la consulta de un intervalo de la misma longitud cuyo límite derecho es $r$ . Estos intervalos pueden superponerse, pero dado que intentamos calcular el mínimo en lugar de, por ejemplo, la suma de los números en el arreglo, esto no importa. El resultado global puede obtenerse, tras el preprocesamiento de tiempo linealítmico, en tiempo constante: las dos consultas pueden responderse en tiempo constante y lo único que queda por hacer es elegir el menor de los dos resultados.

Solución que utiliza un tiempo de consulta logarítmico después de un preprocesamiento lineal de tiempo y espacio.

Esta solución realiza el preprocesamiento en tiempo $O (n)$ . Sus estructuras de datos utilizan espacio $O (n) y pueden utilizarse para responder consultas en tiempo logarítmico.$ ^{[ 2 ]} El arreglo se divide conceptualmente en bloques de tamaño $s = log n / 4. Luego,$ el mínimo para cada bloque se puede calcular en tiempo $O (n)$ en total y los mínimos se almacenan en un nuevo arreglo $.$

Ahora, las RMQ pueden responderse en tiempo logarítmico examinando los bloques que contienen el límite de consulta izquierdo, el límite de consulta derecho y todos los bloques intermedios:

Los dos bloques que contienen los límites se pueden explorar de forma sencilla. No es necesario examinar los elementos que se encuentran fuera del límite. Esto se puede realizar en tiempo logarítmico.
Para responder a la consulta, es necesario comparar los mínimos de todos los bloques que están completamente contenidos en el rango, junto con los dos mínimos mencionados anteriormente.
Debido a que la matriz se dividió en bloques de tamaño $⁠$ $log$ $n$ $/$ $4$ $⁠$ , hay como máximo $⁠$ $4$ $n$ $/$ $log$ $n$ $⁠$ bloques que están completamente contenidos en la consulta.
Al utilizar la solución linealítmica se puede encontrar el mínimo general entre estos bloques. Esta estructura de datos tiene un tamaño $O (⁠ n / log n ⁠ log (⁠ n / log n ⁠)) = O (n)$ .
Ahora, solo es necesario comparar tres mínimos.

Por ejemplo, utilizando el array $A = [0,5,2,5,4,3,1,6,3]$ y un tamaño de bloque de3 (solo con fines ilustrativos) produce la matriz mínima $A' = [0,3,1]$ .

Solución utilizando tiempo constante y espacio lineal

Utilizando la solución anterior, las subconsultas dentro de los bloques que no están completamente contenidos en la consulta aún deben responderse en tiempo constante. Hay como máximo dos de esos bloques: el bloque que contiene $l$ y el bloque que contiene $r$ . El tiempo constante se logra almacenando los árboles cartesianos de todos los bloques en el arreglo. Algunas observaciones:

Los bloques con árboles cartesianos isomorfos dan el mismo resultado para todas las consultas en ese bloque.
El número de árboles cartesianos diferentes de $s$ nodos es $C s$ , el $s$ -ésimo número de Catalan.
Por lo tanto, el número de árboles cartesianos diferentes para los bloques está en el rango de $4 s$

Para cada árbol de este tipo, es necesario almacenar el resultado posible para todas las consultas. Esto se reduce a $s 2$ o $O (log 2 n)$ entradas. Esto significa que el tamaño total de la tabla es $O (n)$ .

Para buscar resultados de manera eficiente, el árbol cartesiano (fila) correspondiente a un bloque específico debe ser direccionable en tiempo constante. La solución consiste en almacenar los resultados de todos los árboles en un array y encontrar una proyección única de árboles binarios a enteros para direccionar las entradas. Esto se puede lograr realizando una búsqueda en anchura a través del árbol y agregando nodos hoja de manera que cada nodo existente en el árbol cartesiano tenga exactamente dos hijos. El entero se genera representando cada nodo interno como un bit 0 y cada hoja como un bit 1 en una palabra de bits (recorriendo el árbol en orden de nivel nuevamente). Esto da como resultado un tamaño de $log n /$ $4$ $para$ $cada$ $árbol$ $.$ Para permitir el acceso aleatorio en tiempo constante a cualquier árbol, también se deben incluir los árboles que no están contenidos en el array original. Un array con índices de $log$ $n$ $/$ $4$ $bits$ $de$ longitud tiene un $tamaño$ $de$ $2$ $log$ $n$ $/$ $4$ $=$ $O$ $($ $n$ $)$ .

Aplicaciones

Las RMQ se utilizan como herramienta para muchas tareas de coincidencia de cadenas exacta y aproximada . Varias aplicaciones se pueden encontrar en Fischer y Heun (2007). ^{[ 3 ]}^{: 3}

Cálculo del ancestro común más bajo en un árbol

Las RMQ se pueden usar para resolver el problema del ancestro común más bajo ^{[ 1 ]}^{[ 2 ]} y se utilizan como herramienta para muchas tareas en la coincidencia de cadenas exacta y aproximada . La consulta LCA $S (v, w) de$ un árbol con raíz $S = (V, E)$ y dos nodos $v, w \in V$ devuelve el nodo más profundo $u$ (que puede ser $v$ o $w$ ) en los caminos desde la raíz hasta $w$ y $v$ . Gabow, Bentley y Tarjan (1984) demostraron que el problema LCA se puede reducir en tiempo lineal al problema RMQ. De ello se deduce que, al igual que el problema RMQ, el problema LCA se puede resolver en tiempo constante y espacio lineal. ^{[ 3 ]}

Calcular el prefijo común más largo en una cadena.

En el contexto de la indexación de texto, las RMQ se pueden usar para encontrar el LCP (prefijo común más largo), donde $LCP T (i, j)$ calcula el LCP de los sufijos que comienzan en los índices $i$ y $j$ en $T$ . Para ello, primero calculamos el array de sufijos $A$ y el array de sufijos inverso $A -1$ . Luego calculamos el array LCP $H$ que da el LCP de los sufijos adyacentes en $A$ . Una vez calculadas estas estructuras de datos y completado el preprocesamiento de RMQ, la longitud del LCP general se puede calcular en tiempo constante mediante la fórmula: $LCP(i, j) = RMQ H (A -1 [i] + 1, A -1 [j])$ , donde asumimos por simplicidad que $A -1 [i] + 1 <= A -1 [j]$ (de lo contrario, intercambiar). ^{[ 4 ]}

Véase también

Consulta de rango (estructuras de datos)

Referencias

Berkman, Omer; Vishkin, Uzi (1993). «Estructura de datos paralela recursiva en forma de árbol estrella» . SIAM Journal on Computing . 22 (2): 221– 242. doi : 10.1137/0222017 . Archivado del original el 23 de septiembre de 2017.
Johannes Fischer (dic. 2009). Concisión óptima para consultas de rango mínimo (Informe técnico). Universidad de Tubinga, Centro de Bioinformática. arXiv : 0812.2775 . Bibcode : 2008arXiv0812.2775F .
^{[ 2 ]}

1 2 3 Bender, Michael A.; Farach-Colton, Martín ; Pemmasani, Giridhar; Skiena, Steven ; Sumazin, Pavel (2005). "Ancestros comunes más bajos en árboles y grafos acíclicos dirigidos" (PDF) . Journal of Algorithms . 57 (2): 75– 94. doi : 10.1016/j.jalgor.2005.08.001 .
1 2 3 4 Bender, Michael; Farach-Colton, Martín (2000). "El problema del ACV revisitado". LATIN 2000: Informática teórica . LNCS. Vol. 1776. Springer. pp. 88–94 . doi : 10.1007/10719839_9 . ISBN 978-3-540-67306-4.
1 2 Fischer, Johannes; Heun, Volker (2007). "Una nueva representación sucinta de la información RMQ y mejoras en el arreglo de sufijos mejorado". Combinatoria, algoritmos, metodologías probabilísticas y experimentales . Actas del Simposio Internacional sobre Combinatoria, Algoritmos, Metodologías Probabilísticas y Experimentales. LNCS. Vol. 4614. Springer. págs. 459–470 . doi : 10.1007/978-3-540-74450-4_41 . ISBN 978-3-540-74449-8.
↑ Fischer, J. y V. Heun (2006). «Mejoras teóricas y prácticas en el problema RMQ, con aplicaciones a LCA y LCE». Combinatorial Pattern Matching . Lecture Notes in Computer Science. Vol. 4009. pp. 36–48 . CiteSeerX 10.1.1.64.5439 . doi : 10.1007/11780441_5 . ISBN 978-3-540-35455-0.

Enlaces externos

Un artículo sobre consultas de rango mínimo en TopCoder
Artículo sobre consulta de rango mínimo en PEGWiki / P3G
Diapositivas de introducción al curso RMQ de CS166 de Stanford

[bender-jalg-1] 1 2 3 Bender, Michael A.; Farach-Colton, Martín ; Pemmasani, Giridhar; Skiena, Steven ; Sumazin, Pavel (2005). "Ancestros comunes más bajos en árboles y grafos acíclicos dirigidos" (PDF) . Journal of Algorithms . 57 (2): 75– 94. doi : 10.1016/j.jalgor.2005.08.001 .

[bender-latin-2] 1 2 3 4 Bender, Michael; Farach-Colton, Martín (2000). "El problema del ACV revisitado". LATIN 2000: Informática teórica . LNCS. Vol. 1776. Springer. pp. 88–94 . doi : 10.1007/10719839_9 . ISBN 978-3-540-67306-4.

[fischer07-3] 1 2 Fischer, Johannes; Heun, Volker (2007). "Una nueva representación sucinta de la información RMQ y mejoras en el arreglo de sufijos mejorado". Combinatoria, algoritmos, metodologías probabilísticas y experimentales . Actas del Simposio Internacional sobre Combinatoria, Algoritmos, Metodologías Probabilísticas y Experimentales. LNCS. Vol. 4614. Springer. págs. 459–470 . doi : 10.1007/978-3-540-74450-4_41 . ISBN 978-3-540-74449-8.

[10.1007/11780441_5-4] Fischer, J. y V. Heun (2006). «Mejoras teóricas y prácticas en el problema RMQ, con aplicaciones a LCA y LCE». Combinatorial Pattern Matching . Lecture Notes in Computer Science. Vol. 4009. pp. 36–48 . CiteSeerX 10.1.1.64.5439 . doi : 10.1007/11780441_5 . ISBN 978-3-540-35455-0.

[ 1 ]

[ 2 ].

[ 3 ]

[ 4 ]