Range Minimum Query

Grundidee und Ziel

Range Minimum Queries (RMQs) sind Anfragen nach dem kleinsten Element in einem festgelegten Bereich eines Arrays. Sie sind in der Informatik wichtig, unter anderem für Textindizierung und -kompression sowie Flussgraphen.

Sei A ein Array der Länge 1..n, dessen Elemente total geordnet sind. Dann bezeichnet RMQ_A(l,r) = arg min_{l ≤ k ≤ r} A[k] mit 1 ≤ l ≤ r ≤ n und n = |A| die Position des kleinsten Elements im Intervall von l bis r. Gesucht ist also nicht nur der kleinste Wert, sondern seine Arrayposition.

Das betrachtete Array ist statisch, wird also nach der Vorbereitung nicht verändert. Die Anfragen werden on-line gestellt, das heißt einzeln während der Nutzung. Ziel ist eine Datenstruktur mit möglichst geringer Vorbereitungszeit und geringem Platzbedarf, die jede Anfrage fast beziehungsweise ganz konstant schnell beantwortet.

Einfache und vorberechnete Lösungen

Beim linearen Scannen werden für eine Anfrage alle Elemente aus A[l,r] geprüft. Das benötigt im Worst Case O(n) Zeit pro Anfrage und O(n) Platz.

Eine andere einfache Lösung speichert die Antwort für jede mögliche RMQ in einer Lookup-Tabelle. Dann dauert eine Anfrage O(1), doch es müssen (n über 2) mögliche Bereiche gespeichert werden. Der Platzbedarf beträgt daher O(n²).

Effiziente RMQ-Datenstrukturen werden in Array-Indexierung und Array-Codierung eingeteilt. Bei der Array-Indexierung braucht die vorberechnete Struktur weiterhin Zugriff auf A; bei der Array-Codierung nicht. Die beschriebenen Verfahren gehören zur Array-Indexierung, weil zum Vergleich vorberechneter Minima Werte aus A gelesen werden.

Verfahren mit linearithmischem Platz

Das Verfahren von M. A. Bender et al. (2005) erreicht ⟨O(n log n), O(1)⟩: O(n log n) Platz und Vorbereitungszeit, aber konstante Anfragezeit. Es berechnet für jede Startposition und für Bereichslängen der Form 2^i vorberechnete Minima.

Für eine Anfrage [l,r] wird h = ⌊log₂(r-l+1)⌋ gewählt. Der Bereich wird durch zwei möglicherweise überlappende Teilbereiche der Länge 2^h abgedeckt. Mit einer Tabelle M gilt:

• RMQ_A(l,l+2^h-1) = m₁ = M[l][h] • RMQ_A(r-2^h+1,r) = m₂ = M[r-2^h+1][h] • RMQ_A(l,r) = arg min {A[m₁], A[m₂]}

Die Anfrage benötigt nur zwei Tabellenzugriffe und den Vergleich der beiden zugehörigen Arraywerte, also O(1) Zeit. Pro Arrayposition gibt es höchstens log n vorberechnete Minima; deshalb benötigt M O(n log n) Platz.

Die Tabelle wird dynamisch programmiert. Ihre Rekurrenz lautet M[i][h] = arg min {A[M[i][h-1]], A[M[i+2^(h-1)][h-1]]}. Auch die Vorberechnung benötigt O(n log n) Schritte.

Lineare Datenstruktur durch Blöcke

Das Verfahren von Johannes Fischer and Heun (2011) reduziert den Platzbedarf auf O(n), bei konstanter Anfragezeit. Das Eingabearray wird in Blöcke der Länge s = log n/(2+ε) zerlegt; ohne Beschränkung der Allgemeinheit wird ε = 2 gesetzt. Eine RMQ zerfällt in höchstens drei Teile: einen Bereich aus vollständigen Blöcken und bis zu zwei Bereiche innerhalb der Randblöcke. Die höchstens drei gefundenen Minima werden anschließend anhand ihrer Werte in A verglichen.

Für vollständige Blöcke wird das Minimum jedes Blocks in einer Liste D gespeichert. Mit m = |D| = n/s wird auf D das Verfahren mit Zweierpotenzen angewandt. Sein Platzbedarf ist O(m log m) = O((n/log n) log(n/log n)) = O(n); Anfragen über vollständige Blöcke dauern O(1).

Für Anfragen innerhalb eines Blocks erhält jeder Block Bᵢ einen kartesischen Baum. Seine Wurzel ist die Position des Minimums m in Bᵢ[1,s]; das linke Kind ist der kartesische Baum von Bᵢ[1,m-1], das rechte Kind der von Bᵢ[m+1,s]. Haben zwei Blöcke dieselbe Baumstruktur, gilt für alle zulässigen l und r: RMQ_Bᵢ(l,r) = RMQ_Bⱼ(l,r). Daher müssen nicht die Antworten für jeden einzelnen Block gespeichert werden, sondern nur für jede mögliche Form eines kartesischen Baums mit s Knoten.

Die Anzahl dieser Bäume ist die Catalan-Zahl C_s = 1/(s+1) · (2s über s). Eine Bijektion ordnet jedem solchen Baum eine Zahl aus [1,C_s] zu; diese Zahl dient als Index der vorberechneten Tabelle P[1,C_s][1,s][1,s]. Mit der Abschätzung log₂ C_s ≈ 2s ergibt sich |P| = O(2^(2s) · s · s) = O(√n · log² n) = o(n). Zusammen mit der Struktur für vollständige Blöcke bleibt der gesamte Platzbedarf linear.

Anwendungen bei Bäumen und Texten

Eine wichtige Anwendung ist der Lowest Common Ancestor (LCA). Für einen Wurzelbaum S = (V,E) und zwei Knoten v,w liefert eine LCA-Anfrage v beziehungsweise w, falls einer auf dem Weg von der Wurzel zum anderen liegt. Andernfalls liefert sie den Knoten u, an dem der gemeinsame Pfad zu v und w endet. Gabow, Bentley, and Tarjan (1984) beschrieben eine lineare Reduktion von LCA auf RMQ; auch die umgekehrte Reduktion ist möglich. Dadurch können LCA-Anfragen mit ⟨O(n), O(1)⟩ gelöst werden.

Dazu wird der LCA-Baum T in O(n) Zeit per Eulertour beziehungsweise in-Order-Baumtraversal in ein Array N abgebildet. Ein Array D speichert zu jedem Eintrag die Traversalnummer: Beim Abstieg wird um 1 dekrementiert, beim Aufstieg um 1 inkrementiert. Für D wird eine RMQ-Struktur vorbereitet. Für p_v ≤ p_w, wobei p_v und p_w die Positionen der Knoten in N sind, gilt: LCA_T(v,w) = N[RMQ_D(p_v,p_w)].

Bei der Textindizierung dienen RMQs zum Bestimmen des längsten gemeinsamen Präfixes (LCP) zweier Suffixe; für längste gemeinsame Suffixe kann RMQ auf dem umgedrehten Text verwendet werden. LCP_T(i,j) ist das gemeinsame Präfix der Suffixe, die in T an den Positionen i und j beginnen. Verwendet werden das LCP-Array H des Suffix-Arrays A und das inverse Suffix-Array A⁻¹. Die LCP-Länge lässt sich dann in konstanter Zeit berechnen: LCP(i,j) = RMQ_H(A⁻¹[i]+1,A⁻¹[j]).