Range Minimum Query

Abbildung 1: Range Minimum Anfrage auf Integer-Array

Range Minimum Queries (RMQs) adressieren innerhalb der Informatik das Problem, eine Anfrage nach dem kleinsten Element innerhalb eines spezifizierten Bereichs eines Arrays zu beantworten. Eine effiziente Beantwortung hat Relevanz für weitere Probleme der Informatik, wie z.B. für die Textindizierung und -komrpession, Flussgraphen etc. (Johannes Fischer 2008; Vishkin and Berkman 1990)

Definition

Sei $A$ ein Array der Länge $1..n$ mit Elementen eines Universums totaler Ordnung, dann liefere $\operatorname {RMQ} _{A}(l,r)=\arg \min _{l\leq k\leq r}A[k]$ (mit $1\leq l\leq r\leq n$ und $n=|A|$) die Position des kleinsten Elements innerhalb des angegebenen Intervalls (Johannes Fischer and Heun 2011). Abbildung 1 veranschaulicht die Anfrage auf eine Beispielsequenz.

Triviale Bearbeitung

Es existieren zwei triviale Lösungen zur Problembearbeitung, die entweder platz- oder zeitineffizient sind. (Johannes Fischer and Heun 2011)

• Lineares Scannen: Durch scannen von $A[l,r]$ wird für jede Query eine lineare Anfragezeit in ${\mathcal {O}}(n)$ worst-case und ein Platzbedarf von ${\mathcal {O}}(n)$ erreicht.
• Vorberechnung einer Lookup Tabelle: Naiv wird eine Tabelle vorberechnet, die die Antworten auf alle möglichen Range Minimum Anfragen speichert. Somit wird eine konstante Anfragezeit in ${\mathcal {O}}(1)$ erreicht, wobei ${\tbinom {n}{2}}$ Kombinationen ${\mathcal {O}}(n^{2})$ Platz benötigen.

Angenommen wird allerdings, dass es sich bei $A$ um ein statisches Array handelt und die Anfragen on-line gestellt werden, wodurch eine geschickte Vorberechnung und die Konstruktion einer geeigneten Datenstruktur die Anfragezeit deutlich reduzieren kann. Hierbei wird eine nahezu konstante Anfragezeit mit linearem Platzverbrauch angestrebt.

Effiziente Konstruktion

Im Folgenden wird Schrittweise dargestellt, wie das gegebene Problem mittels geschickter Vorberechnung auf eine Komplexität von $\langle {\mathcal {O}}(n),{\mathcal {O}}(1)\rangle$ (linearer Platzbedarf/Vorberechnungszeit, konstante Anfragezeit) reduziert werden kann.

Logarithmischer Platzbedarf

Abbildung 2: Zwei Teilanfragen für die RMQ

Um $\langle {\mathcal {O}}(n\log n),{\mathcal {O}}(1)\rangle$ zu erreichen, werden alle Anfragen vorberechnet, deren Länge $2^{x}:x={\mathcal {O}}(\log n)$ umfassen. Aufgrund dessen wird die tatsächliche RMQ in maximal zwei gleich lange Teilanfragen zerlegt, deren Längen 2er-Potenz sind und sich überlappen. Hierbei wird die größtmögliche 2er-Potenz $h$ gewählt, wobei $h=\lfloor \log _{2}{(r-l-1)}\rfloor$ ist. Aufgrund der Vorberechnung kann das Ergebnis über das Intervall von $2^{h}$ in konstanter Zeit bestimmt werden. Abbildung [fig:02-logn] verbildlicht das Vorgehen und zeigt beispielhaft, wie die RMQ (Intervall = rote Linie) in zwei RMQs (graue Linien) zerlegt wird.
Sei $M$ die Tabelle mit den vorberechneten Antworten. Der Algorithmus umfasst insgesamt drei Schritte, um das Ergebnis einer RMQ zu bestimmen:

1. $\operatorname {RMQ} _{A}(l,l+2^{h}-1)=m_{1}=M[l][h]$
2. $\operatorname {RMQ} _{A}(r-2^{h}+1,r)=m_{2}=M[r-2^{h}+1][h]$
3. $\operatorname {RMQ} _{A}(l,r)=\arg \min\{A[m_{1}],A[m_{2}]\}$

Analyse

Abbildung 3: Vorberechnung

Aufgrund der Vorberechnung kann eine RMQ in ${\mathcal {O}}(1)$ beantwortet werden. Die zusätzliche Datenstruktur entält für jede Position innerhalb des Arrays maximal $\log n$ vorberechnete Minima, weil es im worst-case $\log n$ Zweierpotenzen von der ersten Arrayposition bis zum Ende gibt. Hierdurch reduziert sich der Platzbedarf von ${\mathcal {O}}(n^{2})$ auf ${\mathcal {O}}(n\log n)$.
Die Vorberechnung benötigt mittels dynamischer Programmierung eine Laufzeit von ${\mathcal {O}}(n\log n)$ Schritten, wobei folgende Rekurrenz gelöst wird: $M[i][h]=\arg \min {\{A[M[i][h-1]],A[M[i+2^{h-1}][h-1]]\}}$ (siehe Abbildung 3), um die entsprechende Tabelle $M$ zu berechnen. Die benötigte Zeit für die Vorberechnung liegt in ${\mathcal {O}}(n\log n)$.

Linearer Platzbedarf

Abbildung 4: Blockbildung und Speicherung der Minima

Im zweiten Optimierungsschritt wird der Platzbedarf auf ${\mathcal {O}}(n)$ reduziert. Dabei wird das Eingabearray $A$ in Blöcke der Länge $s={\frac {\log n}{2+\epsilon }}$ zerlegt. O.B.d.A. sei $\epsilon =2$. Visuell ist die Blockbildung in Abbildung 4 dargestellt, wobei $A$ hier beispielhaft in vier Blöcke zerlegt wurde. Die RMQ kann nun in max. drei Teile zerlegt werden:

• Eine Anfrage, die vollständige Blöcke umfasst ($3$).
• Zwei Anfragen, die jeweils einen Teil eines Blocks [in-Block] betreffen ($1$, $2$).

Anfrage über vollständige Blöcke

Die RMQ, die an Blockgrenzen abschließt (also vollständige Blöcke umfasst), kann mittels der Konstruktion aus Abschnitt [sub:red_log] in ${\mathcal {O}}(1)$ mittels zwei überlappender Anfragen beantwortet werden. Man speichere das Minimum eines jeden Blockes in einer Liste $D$ (Abbildung [fig:04-blockbildung], zudem sei Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle m = |D| = \frac{n}{s}} . Hierauf wird die bekannte Konstruktion angewandt, woduch sich ein Platzbedarf von ${\mathcal {O}}(m\log m)={\mathcal {O}}({\frac {n}{\log n}}\log {\frac {n}{\log n}})={\mathcal {O}}(n)$ ergibt. Zusammenfassend kann gesagt werden, dass für diesen Fall eine RMQ in konstanter Zeit berechnet werden kann, wobei die Hilfsdatenstruktur linear viel Platz benötigt.

Anfragen auf Blockteile

Abbildung 5: Beispiel für Karteische Bäume

Jedem Block $B_{i}$ wird ein Kartesischer Baum zugeordnet. Ein Kartesischer Baum wird nach folgender, rekursiver Vorschrift konstruiert (Johannes Fischer and Heun 2011) und ist beispielhaft in Abbildung 5 zu sehen.

1. Wurzel: Postition des Minimums in $B_{i}[1,s]=m$
2. Linkes Kind: Kartesischer Baum von $B_{i}[1,m-1]$
3. Rechtes Kind: Kartesischer Baum von $B_{i}[m+1,s]$

Lemma: Falls die Kartesischen Bäume zweier Arrays $B_{i},B_{j};i\neq j$ die gleiche Struktur aufweisen, so gilt $\forall l,r;1\leq l\leq r\leq n:\operatorname {RMQ} _{B_{i}}(l,r)=\operatorname {RMQ} _{B_{j}}(l,r)$.
Der interessierte Leser kann den Beweis des Lemmas in (Johannes Fischer and Heun 2011, S.472) nachlesen.

Aufgrund des Lemmas ergibt sich eine Reduktion für in-Block RMQs, da nicht jeder Block einzeln vorberechnet wird, sondern nur die Antworten für alle möglichen Kartesischen Bäume über $s$ Elementen ausreichen, denn jeder Block lässt sich in Linearzeit (Johannes Fischer and Heun 2011) auf einen Kartesischen Baum abbilden, da die Baumkonstruktion armotisiert in ${\mathcal {O}}(n)$ liegt. Die Anzahl der Bäume entspricht der Catalan-Zahl $C_{s}={\frac {1}{s+1}}{\tbinom {s}{2s}}$. Die Bitmuster der Bäume dienen als Index für die vorberechnete in-Block Tabelle $P[1,C_{s}][1,s][1,s]$. Ein Kartesischer Baum wird hierbei durch seine Level-order unary degree sequence (LOUDS) eindeutig repräsentiert, welche in (Jacobson 1989) beschrieben ist und $2n-1$ Bits benötigt.
Insgesamt ergibt sich daraus ein Platzbedarf von Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle |P| = \mathcal{O}(2^{2s} * s * s) = \mathcal{O}(\sqrt{n}\log^2 n) = o(n)} .

Wie gezeigt wurde, kann das Problem auf linearen Platzbedarf und konstante Anfragezeit reduziert werden, indem die ursprüngliche RMQ in drei Teilanfragen zerlegt wird. Das Minimum über vollständig umfasste Blöcke wird unter Zuhilfenahme des Schemas aus Abschnitt 3.1 berechnet, für in-Block Anfragen werden Blöcke auf Kartesische Bäume abgebildet, deren Ergebnisse vollständig vorberechnet nicht mehr als linear viel Platz bzgl. der Eingabe benötigen.

Anwendungen

Lowest Common Ancestor

Abbildung 6: Reduktion von LCA auf RMQ

Eine LCA-Anfrage bzgl. eines Baumes $S=(V,E)$ und zwei Knoten Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle v, w \in V} liefert entweder $v$ (bzw. $w$), falls sich dieser auf dem Pfad von der Wurzel zu $w$ (bzw. Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle v} ) befindet, oder denjenigen Knoten $u$, an dem der gemeinsame Pfad zu $u$ und $v$ endet.

Wie erstmals von in (Gabow... 1984) beschrieben wurde, kann das LCA Problem linear auf das RMQ Problem reduziert werden (und umgedreht, siehe hierzu Bender and Farach-Colton (2000)). Dies ist von Relevanz, da somit auch LCA-Anfragen in konstanter Zeit und linearem Platzbedarf bzgl. der Eingabe ($\langle {\mathcal {O}}(n),{\mathcal {O}}(1)\rangle$) gelöst werden können, wie es zum Beispiel in J. Fischer and Heun (2007) dargestellt wird.

Die Reduktion beinhaltet eine Eulertour (bzw. einen in-Order Baumtraversal) in ${\mathcal {O}}(n)Zeit$ über den LCA-Baum $T$ zur Abbildung in ein Array $N$, wobei für jedes Element in Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle N} eine entsprechende Traversalnummer in $D$ gespeichert wird, indem beim Abstieg um $1$ dekrementiert (bzw. beim Aufstieg inkrementiert) wird, siehe hierzu Abbildung [fig:06-trafo]. Das Array $N$ benötigt linear viel Platz, weil die Kantenanzahl des Ursprungsbaumes durch dessen Knoten beschränkt ist. Für das Array $D$ kann nun die zuvor-beschriebene Vorberechnung für RMQs durchgeführt werden. Zur Lösung des LCA-Problems gilt nun: $\operatorname {LCA} _{T}(v,w)=N[\operatorname {RMQ} _{D}(p_{v},p_{w})],p_{v}\leq p_{w}$, wobei $p_{v},p_{w}$ die Position der Eingabeknoten innnerhalb $N$ kennzeichnen.

Längstes gemeinsames Präfix

In der Textindizierung können RMQs zum Auffinden von LCPs (Longest Common Prefix) bei der Mustersuche verwendet werden (bzw. Longest Common Suffix durch RMQ auf den umgedrehten Text), wobei $\operatorname {LCP} _{T}(i,j)$ das LCP eines gemeinsamen Präfixes der Suffixe berechnet, die in $T$ an Position $i$ und $j$ beginnen.

Hierzu wird das LCP-Array $H$ des Suffix-Arrays $A$ verwendet und zu $T$ ein inverses Suffix-Array $A^{-1}$ berechnet, welches zum $i$-ten Suffix im Suffixarray dessen Anfangsposition in Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle T} liefert. Auf Basis dieser beiden Strukturen kann nun in konstanter Zeit die Länge des LCP mittels foldenger Vorschrift berechnet werden: $\operatorname {LCP} (i,j)=\operatorname {RMQ} _{H}(A^{-1}[i]+1,A^{-1}[j])$. (J. Fischer and Heun 2006, S.43-43)
Für weitere Anwendungsfälle von RMQs sei auf J. Fischer and Heun (2007, S.3) verwiesen.

Literatur

1. Bender, M., and M. Farach-Colton. 2000. “The LCA problem revisited.” LATIN 2000: Theoretical Informatics: 88–94.
2. Fischer, J., and V. Heun. 2006. “Theoretical and practical improvements on the RMQ-problem, with applications to LCA and LCE.” In Combinatorial Pattern Matching, 36–48.
3. Fischer, J., and V. Heun. 2007. “A new succinct representation of RMQ-information and improvements in the enhanced suffix array.” Combinatorics, Algorithms, Probabilistic and Experimental Methodologies: 459–470.
4. Fischer, Johannes. 2008. “Range Minimum Queries: Simple and Optimal, At Last!”
5. Fischer, Johannes, and Volker Heun. 2011. “Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays.” SIAM J. Comput. 40 (apr): 465–492. doi:10.1137/090779759. http://dx.doi.org/10.1137/090779759.
6. Jacobson, G. 1989. “Space-efficient static trees and graphs.” In Foundations of Computer Science, 1989., 30th Annual Symposium on, 549–554.
7. Vishkin, U., and O. Berkman. 1990. “Recursive Star-Tree Parallel Data-Structure.” Maryland Univ College Park Inst For Advanced Computer Studies.

Verweise

doi:10.1137/090779759