Consulta mínima de rango

Construyendo el árbol cartesiano correspondiente para resolver una consulta de rango mínimo.

Consulta mínima de rango reducida al problema de ancestro común más bajo .

En informática, una consulta de rango mínimo ( RMQ ) resuelve el problema de encontrar el valor mínimo en una submatriz de una matriz de objetos comparables. Las consultas de rango mínimo tienen varios casos de uso en informática, como el problema del antepasado común más bajo y el problema del prefijo común más largo (LCP).

Definición

Dada una matriz $A$ $[1\dots$ $n$ $]$ de $n$ objetos tomados de un conjunto totalmente ordenado , como enteros, el rango mínimo de consulta $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 subarreglo 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 rango mínimo para la $submatriz$ $A [3\dots 8] = [2,5 , 4,3,1,6]$ es7 , como $A [7] = 1$ .

Algoritmos

Solución ingenua

En un entorno típico, la matriz $A$ es estática, es decir, los elementos no se insertan ni eliminan durante una serie de consultas, y las consultas deben responderse en línea (es decir, todo el conjunto de consultas no se conoce de antemano para el algoritmo ). En este caso, un procesamiento previo adecuado de la matriz en una estructura de datos garantiza una respuesta más rápida a las consultas. Una solución ingenua es calcular previamente todas las consultas posibles, es decir, el mínimo de todas las submatrices de $A$ , y almacenarlas en una matriz $B$ tal que $B [i, j] = min (A [i \dots j])$ ; luego, una consulta de rango mínimo se puede resolver en tiempo constante mediante una búsqueda de matriz en $B$ . Hay $Θ (n ²)$ consultas posibles para una matriz de longitud $n$ , y las respuestas a estas se pueden calcular en $Θ (n ²)$ tiempo mediante programación dinámica . ^[1]

Solución usando tiempo logarítmico y espacio linealítmico

Al igual que en la solución anterior, la respuesta a las consultas en un tiempo constante se logrará mediante el cálculo previo de los resultados. Sin embargo, la matriz almacenará consultas mínimas precalculadas para todos los elementos y solo los rangos cuyo tamaño sea una potencia de dos. Hay $Θ (log n)$ consultas de este tipo para cada posición de inicio $i$ , por lo que el tamaño de la tabla de programación dinámica $B$ es $Θ (n log n)$ . Cada elemento $B [i, j]$ contiene el índice del mínimo del rango $A [i \dots i +2 j -1]$ . La tabla se llena con los índices de mínimos usando la recurrencia ^[1]

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]

.

Una consulta $RMQ A (l, r)$ ahora se puede responder dividiéndola en dos consultas separadas: una es la consulta precalculada con un rango desde $l$ hasta el límite más alto menor que $r$ . La otra es la consulta de un intervalo de la misma longitud que tiene $r$ como su límite derecho. Estos intervalos pueden superponerse, pero como se calcula el mínimo en lugar de, digamos, la suma, esto no importa. El resultado general se puede obtener en tiempo logarítmico porque estas dos consultas se pueden responder en tiempo logarítmico y lo único que queda por hacer es elegir el menor de los dos resultados.

Tabla de resultados para $A = [0,5,2,5,4,3,1,6,3]$
		$k$
		0	1	2	3
$l$	1	1	1	1	1
	2	2	3	3	7
	3	3	3	3	7
	4	4	5	6	7
	5	5	6	7	7
	6	6	7	7	7
	7	7	7	7	7
	8	8	7	7	7
	9	9	7	7	7

Solución usando tiempo logarítmico y espacio lineal

Esta solución responde a las RMQ en tiempo $O (log n)$ . Sus estructuras de datos utilizan el espacio $O (n)$ y sus estructuras de datos también se pueden utilizar para responder consultas en tiempo constante. Primero, la matriz se divide conceptualmente en bloques de tamaño $s = log n / 4$ . Luego, el mínimo para cada bloque se puede calcular en $O (n)$ tiempo en general y los mínimos se almacenan en una nueva matriz.

Las RMQ ahora se pueden responder en tiempo logarítmico observando 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 buscar ingenuamente. Los elementos fuera del límite ni siquiera necesitan ser examinados. Esto se puede hacer en tiempo logarítmico.
Los mínimos de todos los bloques que están completamente contenidos en el rango, y los dos mínimos mencionados anteriormente, deben compararse para responder a la consulta.
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 usar 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, usando la matriz $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 usando tiempo constante y espacio lineal

Con la solución anterior, las subconsultas dentro de los bloques que no están completamente contenidas en la consulta aún deben responderse en un tiempo constante. Hay como máximo dos de esos bloques: el bloque que contiene $ly$ el bloque que contiene $r$ . El tiempo constante se logra almacenando los árboles cartesianos para todos los bloques de la matriz. 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$ 'número catalán
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 de todas las consultas. Esto se reduce a entradas $s 2$ u $O (log 2 n)$ . Esto significa que el tamaño total de la mesa 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 es almacenar los resultados de todos los árboles en una matriz y encontrar una proyección única de árboles binarios a enteros para abordar las entradas. Esto se puede lograr haciendo una búsqueda en amplitud primero a través del árbol y agregando nodos hoja para que cada nodo existente en el árbol cartesiano tenga exactamente dos hijos. El número entero se genera representando cada nodo interno como un bit 0 y cada hoja como un bit 1 en una palabra de bits (atravesando el árbol en orden de nivel nuevamente). Esto conduce a un tamaño de $log$ $n$ $/$ $4$ para cada árbol. Para permitir el acceso aleatorio en tiempo constante a cualquier árbol, los árboles que no están contenidos en la matriz original deben incluirse también. Una matriz con índices de $log$ $n$ $/$ $4$ bits de longitud tiene un tamaño de $2$ $log$ $n$ $/$ $4$ $=$ $O$ $($ $n$ $)$ .

Ejemplo de árboles cartesianos para

A = [0,5,2,5,4,3,1,6,3]

. Observe que el primer y tercer árbol tienen el mismo diseño, por lo que hay exactamente dos conjuntos de consultas precalculados en la tabla de la izquierda.

Resultados $precalculados$ para los tres árboles de bloques cartesianos de $A = [0,5,2,5,4,3,1,6,3]$
Índice	1			2			3
Índice	1	2	3	1	2	3	1	2	3
0	-
23 (palabra de bits 0010111)	1	2	3	-	2	3	-	-	3
39 (palabra de bits 0100111)	1	1	1	-	2	3	-	-	3
127	-

Aplicaciones

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

Calcular el antepasado común más bajo en un árbol

Las RMQ se pueden utilizar para resolver el problema del antepasado común más bajo ^[1]^[3] y se utilizan como una herramienta para muchas tareas en la coincidencia de cadenas exacta y aproximada . La consulta $LCA 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 las rutas desde la raíz a ambos $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 de RMQ, el problema de LCA se puede resolver en tiempo constante y espacio lineal. ^[2]

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

En el contexto de la indexación de texto, RMQS se pueden utilizar para encontrar el LCP (más largo prefijo común), donde $LCP T (i, j)$ calcula el LCP de los sufijos que comienzan en los índices $i$ y $j$ en $t$ . Para hacer esto, primero calculamos la matriz de sufijo $A$ y la matriz de sufijo inverso $A -1$ . A continuación, calcular la matriz LCP $H$ dando el LCP de sufijos adyacentes en $A$ . Una vez que se calculan estas estructuras de datos y se completa 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]$ (en caso contrario, swap). ^[4]

Ver también

Consulta de rango (estructuras de datos)

Referencias

Berkman, Omer; Vishkin, Uzi (1993). "Estructura de datos paralelos estrella-árbol recursiva" . Revista SIAM de Computación . 22 (2): 221–242. doi : 10.1137 / 0222017 .
Johannes Fischer (diciembre de 2009). Precisión óptima para consultas de rango mínimo (informe técnico). Universität Tübingen, Centro de Bioinformática. arXiv : 0812.2775 . Código bibliográfico : 2008arXiv0812.2775F .

^ ^a ^b c Bender, Michael A .; Farach-Colton, Martín ; Pemmasani, Giridhar; Skiena, Steven ; Sumazin, Pavel (2005). "Antepasados comunes más bajos en árboles y gráficos acíclicos dirigidos" (PDF) . Revista de algoritmos . 57 (2): 75–94. doi : 10.1016 / j.jalgor.2005.08.001 .
↑ a b Fischer, Johannes; Heun, Volker (2007). Una nueva representación sucinta de información RMQ y mejoras en la matriz de sufijos mejorada . Actas del Simposio Internacional sobre Combinatoria, Algoritmos, Metodologías Probabilísticas y Experimentales. LNCS. 4614 . Saltador. págs. 459–470. doi : 10.1007 / 978-3-540-74450-4_41 .
^ Bender, Michael; Farach-Colton, Martín (2000). El problema de LCA revisado . LATIN 2000: Informática Teórica. LNCS. 1776 . Saltador. págs. 88–94. doi : 10.1007 / 10719839_9 .
^ Fischer, J. y V. Heun (2006). "Mejoras teóricas y prácticas sobre el problema RMQ, con aplicaciones a LCA y LCE". Coincidencia de patrones combinatorios . Apuntes de conferencias en Ciencias de la Computación. 4009 . págs. 36–48. CiteSeerX 10.1.1.64.5439 . doi : 10.1007 / 11780441_5 . ISBN 978-3-540-35455-0. Falta o vacío |title=( ayuda )

enlaces externos

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

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

[fischer07-2] Fischer, Johannes; Heun, Volker (2007). Una nueva representación sucinta de información RMQ y mejoras en la matriz de sufijos mejorada . Actas del Simposio Internacional sobre Combinatoria, Algoritmos, Metodologías Probabilísticas y Experimentales. LNCS. 4614 . Saltador. págs. 459–470. doi : 10.1007 / 978-3-540-74450-4_41 .

[3] Bender, Michael; Farach-Colton, Martín (2000). El problema de LCA revisado . LATIN 2000: Informática Teórica. LNCS. 1776 . Saltador. págs. 88–94. doi : 10.1007 / 10719839_9 .

[10.1007/11780441_5-4] Fischer, J. y V. Heun (2006). "Mejoras teóricas y prácticas sobre el problema RMQ, con aplicaciones a LCA y LCE". Coincidencia de patrones combinatorios . Apuntes de conferencias en Ciencias de la Computación. 4009 . págs. 36–48. CiteSeerX 10.1.1.64.5439 . doi : 10.1007 / 11780441_5 . ISBN 978-3-540-35455-0. Falta o vacío |title=( ayuda )

[1]