Quelltext der Seite Range Minimum Query

[[Datei:01 array.png|mini|Abbildung 1: Range Minimum Anfrage auf Integer-Array]]
'''Range Minimum Queries''' ('''RMQ'''s) adressieren innerhalb der [[Informatik]] das Problem, eine Anfrage nach dem kleinsten Element innerhalb eines spezifizierten Bereichs eines [[Feld (Datentyp)|Arrays]] zu beantworten. Eine effiziente Beantwortung hat Relevanz für weitere Probleme der Informatik, wie z.&nbsp;B. für die Textindizierung und -kompression, Flussgraphen etc.

== Definition ==
Sei <math>A</math> ein Array der Länge <math>1..n</math> mit Elementen eines Universums [[Totale Ordnung|totaler Ordnung]], dann liefere <math>\operatorname{RMQ}_A(l, r) = \arg\min_{l\le k \le r} A[k]</math> (mit <math>1 \le l \le r \le n</math> und <math> n = |A|</math>) die Position des kleinsten Elements innerhalb des angegebenen Intervalls<ref name="10.1137/090779759">{{Literatur |Autor=Fischer, J. and V. Heun |Titel=Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays |Sammelwerk=SIAM J. Comput. 40 (apr) |Datum=2011 |Seiten=465–492 |DOI=10.1137/090779759}}</ref>. Abbildung&nbsp;1 veranschaulicht die Anfrage auf eine Beispielsequenz.

== Triviale Bearbeitung ==
Es existieren zwei triviale Lösungen zur Problembearbeitung, die entweder platz- oder zeitineffizient sind.<ref name="10.1137/090779759" />

* '''Lineares Scannen: ''' Durch ''Scannen'' von <math>A[l, r]</math> wird für jede Query eine ''lineare'' Anfragezeit in <math>\mathcal{O}(n)</math> worst-case und ein Platzbedarf von <math>\mathcal{O}(n)</math> 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 <math>\mathcal{O}(1)</math> erreicht, wobei <math>\tbinom{n}{2}</math> Kombinationen <math>\mathcal{O}(n^2)</math> Platz benötigen.

Angenommen wird allerdings, dass es sich bei <math>A</math> 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 ==
Die vorberechneten RMQ-Datenstrukturen können in zwei Kategorien eingeteilt werden: (a) Array-Indexierung und (b) Array-Codierung. Im Fall (a) benötigt die vorberechnete Struktur Zugriff auf das Array <math>A</math> um darauf RMQs zu beantworten. Im Fall (b) ist ein Zugriff auf <math>A</math> nicht notwendig, um eine RMQ zu beantworten.<ref name="10.1007/3-540-45061-0_28">{{Literatur |Autor=Gál, A. and Miltersen, P. |Titel=The Cell Probe Complexity of Succinct Data Structures |Sammelwerk=Automata, Languages and Programming |Datum=2003 |Seiten=190–190 |DOI=10.1007/3-540-45061-0_28}}</ref> Die vorgestellten Lösungen sind der Kategorie der Array-Indexierung zuzuordnen.

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

=== Linearithmischer Platzbedarf ===
[[Datei:02-logn.png|mini|Abbildung 2: Zwei Teilanfragen für die RMQ]]

In M. A. Bender et al. (2005)<ref name="10.1016/j.jalgor.2005.08.001">{{Literatur |Autor=Bender, M. A., M. Farach-Colton, G. Pemmasani, S. Skiena, and P. Sumazin |Titel=Lowest common ancestors in trees and directed acyclic graphs |Sammelwerk=Journal of Algorithms |Band=57 |Nummer=2 |Datum=2005-11 |ISSN=0196-6774 |Seiten=75–94 |Online=https://linkinghub.elsevier.com/retrieve/pii/S0196677405000854 |DOI=10.1016/j.jalgor.2005.08.001}}</ref> wird eine Möglichkeit beschrieben, um <math>\langle\mathcal{O}(n \log n), \mathcal{O}(1)\rangle</math> zu erreichen. Hierzu werden die Ergebnisse für alle möglichen Startpositionen <math>(1, \dots, n)</math> und Längen der Form <math>2^i :  i \leq x=\mathcal{O}(\log n)</math> vorberechnet. Aufgrund dessen wird die tatsächliche RMQ in maximal zwei gleich lange Teilanfragen zerlegt, deren Längen Zweierpotenzen sind und sich möglicherweise überlappen. Hierbei wird die größtmögliche Zweierpotenz <math>h</math> gewählt, wobei <math>h = \lfloor \log_2{(r-l+1)} \rfloor</math> ist. Aufgrund der Vorberechnung kann das Ergebnis über das Intervall von <math>2^h</math> in konstanter Zeit bestimmt werden. Abbildung&nbsp;2 verbildlicht das Vorgehen und zeigt beispielhaft, wie die RMQ (Intervall = rote Linie) in zwei RMQs (graue Linien) zerlegt wird.<br />
Sei <math>M</math> die Tabelle mit den vorberechneten Antworten. Der Algorithmus umfasst insgesamt drei Schritte, um das Ergebnis einer RMQ zu bestimmen:

# <math>\operatorname{RMQ}_A(l, l+2^h-1) = m_1 = M[l][h]</math>
# <math>\operatorname{RMQ}_A(r-2^h+1, r) = m_2 = M[r-2^h+1][h]</math>
# <math>\operatorname{RMQ}_A(l, r) = \arg\min\{A[m_1], A[m_2]\}</math>

An dieser Stelle wird ersichtlich, dass die angegebene Lösung zur Kategorie (a) Array-Indexierung gehört, weil das kleinere der beiden Minima der Teilanfragen ermittelt werden muss und hierzu zwei Zugriffe auf <math>A</math> benötigt werden.

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

=== Linearer Platzbedarf ===
[[Datei:04-blockbildung.png|mini|Abbildung 4: Blockbildung und Speicherung der Minima]]
Die vorgestellte Lösung stammt von Johannes Fischer and Heun (2011)<ref name="10.1137/090779759" />. Hierbei wird der Platzbedarf auf <math>\mathcal{O}(n)</math> reduziert, wobei das Eingabearray <math>A</math> in Blöcke der Länge <math>s=\frac{\log n}{2+\epsilon}</math> zerlegt wird. O.B.d.A. sei <math>\epsilon = 2</math>. Visuell ist die Blockbildung in Abbildung&nbsp;4 dargestellt, wobei <math>A</math> 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 (<math>3</math>).
* Zwei Anfragen, die jeweils einen Teil eines Blocks [''in-Block''] betreffen (<math>1</math>, <math>2</math>).

Aufgrund der Bearbeitung der max. drei Teilanfragen erhält man das jeweilige Minimum über den umspannten Bereich. Im letzten Schritt werden die konkreten Werte aus <math>A</math> geladen und verglichen. Daraufhin kann die Position des kleinsten der max. drei Werte als Ergebnis ausgegeben werden. Auch an dieser Stelle wird ersichtlich, dass die angegebene Lösung der Kategorie (a) Array-Indexierung zuzuordnen ist.

==== 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&nbsp;3.1 in <math>\mathcal{O}(1)</math> mittels zwei überlappender Anfragen beantwortet werden. Man speichere das Minimum eines jeden Blockes in einer Liste <math>D</math> (Abbildung&nbsp;4), zudem sei <math>m = |D| = \frac{n}{s}</math> . Hierauf wird die bekannte Konstruktion angewandt, wodurch sich ein Platzbedarf von
:<math>\mathcal{O}(m \log m) =  \mathcal{O}\left(\frac{n}{\log n} \log \frac{n}{\log n}\right) = \mathcal{O}(n)</math>
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 ====
[[Datei:05-cartesian.png|mini|Abbildung 5: Beispiel für Kartesische Bäume]]
Jedem Block <math>B_i</math> wird ein [[Kartesischer Baum]] zugeordnet. Ein Kartesischer Baum wird nach folgender, rekursiver Vorschrift konstruiert und ist beispielhaft in Abbildung&nbsp;5 zu sehen.

# Wurzel: Position des Minimums in <math>B_i[1,s] = m</math>
# Linkes Kind: Kartesischer Baum von <math>B_i[1, m-1]</math>
# Rechtes Kind: Kartesischer Baum von <math>B_i[m+1, s]</math>

'''Lemma: ''' Falls die Kartesischen Bäume zweier Arrays <math>B_i, B_j; i\ne j</math> die gleiche Struktur aufweisen, so gilt <math>\forall l,r; 1 \le l \le r \le n : \operatorname{RMQ}_{B_i}(l, r) = \operatorname{RMQ}_{B_j}(l, r)</math>.<br />
Der interessierte Leser kann den Beweis des Lemmas in Johannes Fischer and Heun (2011, S.&nbsp;472)<ref name="10.1137/090779759" /> 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 <math>s</math> Elementen ausreichen, denn jeder Block lässt sich in Linearzeit (Johannes Fischer and Heun 2011)<ref name="10.1137/090779759" /> auf einen Kartesischen Baum abbilden, da die Baumkonstruktion amortisiert in <math>\mathcal{O}(n)</math> liegt. Die Anzahl der Bäume entspricht der Catalan-Zahl <math>\textstyle C_s = \frac{1}{s+1} \binom{2s}{s}</math>, und es existiert eine Bijektion zwischen allen kartesischen Bäumen auf <math>s</math> Knoten und den Zahlen <math>[1, C_s]</math>, die mittels einem Algorithmus in Linearzeit berechnet werden kann<ref>{{Literatur |Autor=Donald E. Knuth |Hrsg= |Titel=Generating All Trees— History of Combinatorial Generation |Sammelwerk=The Art of Computer Programming |Band=Vol. 4 |Nummer=Fasc. 4 |Verlag=Addison-Wesley |Ort=Upper Saddle River, NJ |Datum=2006 |ISBN=0-321-33570-8 |Seiten=4 ff.}}</ref>. Diese numerische Repräsentation eines kartesischen Baumes wird als ''Index'' für die vorberechnete in-Block Tabelle <math>P[1,C_s][1,s][1,s]</math> verwendet, und ihr Platzbedarf kann mittels [[Stirlingformel]] als <math>\log_2 C_s \approx 2s</math> Bits abgeschätzt werden.<br />
Insgesamt ergibt sich daraus ein Platzbedarf von <math>|P| = \mathcal{O}(2^{2s} \cdot s \cdot s) = \mathcal{O}(\sqrt{n}\,\log^2 n) = o(n)</math>.

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&nbsp;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 ==
Im Folgenden werden zwei Anwendungsfälle für RMQs vorgestellt. Weitere Anwendungen sind z.&nbsp;B. in Johannes Fischer and Heun (2007, S. 3)<ref name="fischer07">{{Literatur |Autor=Fischer, J. and V. Heun |Titel=A new succinct representation of RMQ-information and improvements in the enhanced suffix array |Sammelwerk=Combinatorics, Algorithms, Probabilistic and Experimental Methodologies |Datum=2007 |Seiten=459–470 |DOI=10.1007/978-3-540-74450-4_41}}</ref> nachzulesen.

=== Lowest Common Ancestor ===
[[Datei:06-trafo.png|mini|Abbildung 6: Reduktion von LCA auf RMQ]]

Eine [[Lowest Common Ancestor|LCA-Anfrage]] bzgl. eines Baumes <math>S=(V, E)</math> und zwei Knoten <math>v, w \in V</math> liefert entweder <math>v</math> (bzw. <math>w</math>), falls sich dieser auf dem Pfad von der Wurzel zu <math>w</math> (bzw. <math>v</math>) befindet, oder denjenigen Knoten <math>u</math>, an dem der gemeinsame Pfad zu <math>u</math> und <math>v</math> endet.

Wie erstmals von Gabow, Bentley, and Tarjan (1984)<ref name="10.1145/800057.808675">{{Literatur |Autor=Gabow, H.N., J.L. Bentley, and R.E. Tarjan |Titel=Scaling and related techniques for geometry problems |Sammelwerk=Proceedings of the sixteenth annual ACM symposium on Theory of computing |Datum=1984 |Seiten=135–143 |DOI=10.1145/800057.808675}}</ref> beschrieben wurde, kann das LCA Problem linear auf das RMQ Problem reduziert werden (und umgedreht, siehe hierzu Bender and Farach-Colton (2000)<ref name="10.1007/10719839_9">{{Literatur |Autor=Bender, M. A. and M. Farach-Colton |Titel=The LCA Problem Revisited |Sammelwerk=LATIN 2000: Theoretical Informatics |Datum=2000 |Seiten=88–94 |DOI=10.1007/10719839_9}}</ref>). Dies ist von Relevanz, da somit auch LCA-Anfragen in ''konstanter Zeit'' und ''linearem Platzbedarf'' bzgl. der Eingabe (<math>\langle \mathcal{O}(n), \mathcal{O}(1)\rangle</math>) gelöst werden können, wie es zum Beispiel in J. Fischer and Heun (2007)<ref name="fischer07" /> dargestellt wird.

Die Reduktion beinhaltet eine [[Eulerkreisproblem|Eulertour]] (bzw. einen ''in-Order Baumtraversal'') in <math>\mathcal{O}(n)</math> Zeit über den LCA-Baum <math>T</math> zur Abbildung in ein Array <math>N</math>, wobei für jedes Element in <math>N</math> eine entsprechende Traversalnummer in <math>D</math> gespeichert wird, indem beim Abstieg um <math>1</math> dekrementiert (bzw. beim Aufstieg inkrementiert) wird, siehe hierzu Abbildung&nbsp;6. Das Array <math>N</math> benötigt ''linear'' viel Platz, weil die Kantenanzahl des Ursprungsbaumes durch dessen Knoten beschränkt ist. Für das Array <math>D</math> kann nun die zuvor-beschriebene Vorberechnung für RMQs durchgeführt werden. Zur Lösung des LCA-Problems gilt nun: <math>\operatorname{LCA}_T(v, w) = N[\operatorname{RMQ}_D(p_v, p_w)], p_v \le p_w</math>, wobei <math>p_v, p_w</math> die Position der Eingabeknoten innerhalb <math>N</math> kennzeichnen.

=== Längstes gemeinsames Präfix ===

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

Hierzu wird das [[LCP-Array]] <math>H</math> des [[Suffix-Array]]s <math>A</math> verwendet und zu <math>T</math> ein ''inverses Suffix-Array'' <math>A^{-1}</math> berechnet, welches zum <math>i</math>-ten Suffix im Suffixarray dessen Anfangsposition in <math>T</math> liefert. Auf Basis dieser beiden Strukturen kann nun in konstanter Zeit die Länge des LCP mittels folgender Vorschrift berechnet werden: <math>\operatorname{LCP}(i, j) = \operatorname{RMQ}_H(A^{-1}[i]+1, A^{-1}[j])</math>.<ref name="10.1007/11780441_5">{{Literatur |Autor=Fischer, J. and V. Heun |Titel=Theoretical and practical improvements on the RMQ-problem, with applications to LCA and LCE |Sammelwerk=Combinatorial Pattern Matching |Datum=2006 |Seiten=36–48 |DOI=10.1007/11780441_5}}</ref>

== Einzelnachweise ==
<references />

[[Kategorie:Suchalgorithmus]]