Wavelet Tree
In der Informatik versteht man unter einem Wavelet Tree eine kompakte Datenstruktur, um Zeichenfolgen komprimiert abzuspeichern. Er erweitert die Methoden <math>\mathbf{access, rang_q}</math> und <math>\mathbf{select_q}</math> von einem Bitvektor auf ein beliebiges Alphabet.
Erstmals beschrieben wurde die Datenstruktur als Hauptbestandteil zur komprimierten Volltextindexierung<ref name="GGV03"/> und gilt als geringfügige Generalisierung einer Datenstruktur aus der algorithmischen Geometrie<ref name="CB88"/>. Der Wavelet Tree lässt sich rekursiv beschreiben. Jeder Knoten verteilt die Zeichenfolge auf seine zwei Nachfolger. Dabei wird das verbleibende Alphabet unter den Kind-Knoten aufgeteilt. Ein Bitvektor speichert für jedes Zeichen die zugeordnete Partition.
Der Namensursprung der Trees liegt bei der Wavelet-Transformation, eingesetzt zur Reduzierung von Bilddaten und zur approximativen Evaluierung von Ausdrücken der relationalen Algebra.
Aufbau
Ein Wavelet Tree der Folge <math>S[1,n]</math> über dem Alphabet <math>[1..\sigma]</math> kann über ein Teilalphabet <math>[a..b]\subseteq[1..\sigma]</math> rekursiv beschrieben<ref name="Navarro12"/> werden. Ein Wavelet Tree über dem Alphabet <math>[a..b]</math> ist ein binärer balancierter Baum mit <math>b-a +1</math> Blättern.
- Falls <math>a=b</math>, so besteht der Baum aus nur einem Blatt mit dem Label <math>a</math>.
- Sonst besitzt der Baum einen Wurzelknoten <math>v_{root}</math> mit einer Bitmap <math>b_{v_{root}}</math>, welche wie folgt definiert ist:
- <math>B_{v_{root}}[i] = \begin{cases}0, & \mbox{falls } S[i]\leq(a+b)/2,\\ 1, & \mbox{sonst.}\end{cases}</math>
- Sei nun <math>S_0[1,n_0]</math> die Teilsequenz aus <math>S[1,n]</math> bestehend aus den Symbolen <math>c\leq(a+b) /2</math> und <math>S_1[1,n_1]</math> die Teilsequenz aus <math>S[1,n]</math> bestehend aus den Symbolen <math>c>(a+b) /2</math>. Dann ist das linke Kind von <math>v_{root}</math> ein Wavelet Tree von <math>S_0[1,n_0]</math> über dem Alphabet <math>[a..\left\lfloor(a+b)/2\right\rfloor]</math> und das rechte Kind von <math>v_{root}</math> ein Wavelet Tree von <math>S_1[1,n_1]</math>über dem Alphabet <math>[1+\left\lfloor(a+b)/2\right\rfloor..b]</math>.
Eigenschaften
Der beschriebene Baum hat eine Höhe von <math>\left\lceil\log\sigma\right\rceil</math>, besitzt <math>\sigma</math> Blätter und <math>\sigma - 1</math> interne Knoten. Er speichert <math>n</math> Bits auf jeder Ebene und höchstens <math>n</math> in der untersten Ebene. Somit lässt sich der Baum mit insgesamt höchstens <math>n\left\lceil\log\sigma\right\rceil</math> Bits repräsentieren. Genau betrachtet benötigt diese Repräsentation weitere <math>O(\sigma \log n)</math> Bits für die Zeiger.
Sei nun <math>S[1, n] = s_1s_2...s_n</math> eine Zeichenfolge mit <math>s_i \in \Sigma</math> aus dem Alphabet <math>\Sigma</math> der Länge <math>\sigma=|\Sigma|</math>, so kann <math>S</math> als Wavelet Tree mit <math>n\left\lceil\log\sigma\right\rceil = n\log\sigma + O(n)</math> Bits repräsentiert werden.
Operationen
Der Wavelet Tree unterstützt die Operationen <math>\mathbf{access, rang_q}</math>, und <math>\mathbf{select}_q</math> in <math>O(\log \sigma)</math> Zeit, falls ein balancierter Baum konstruiert wurde.
Access
<math>access(i)</math>: Direktzugriff auf das i'te Element in der Zeichenfolge.
Um das Zeichen an der Position <math>S[i]</math> zu berechnen, wird der Bitvektor <math>B_v{_{root}}[i]</math> betrachtet. Falls der Wert an dieser Position <math>0</math> ist, so ist <math>S[i]\leq(\sigma + 1)/2</math> und wir führen das Vorgehen auf dem linken Kind-Knoten rekursiv weiter, andernfalls gilt <math>S[i]>(\sigma + 1)/2</math> und der Algorithmus bearbeitet das rechte Kind. Dazu muss die neue Position von <math>i</math> im Bitvektor <math>B_v{_{Kind}}[i]</math> ermittelt werden. Die neue Position <math>i_0</math> ist die Anzahl der Nullen im Vektor <math>B_v{_{root}}</math> bis zur Position i, falls <math>B_v{_{root}}[i] = 0</math> gilt. Wird rekursiv das rechte Kind bearbeitet, so müssen die Vorkommen der Einsen aufsummiert werden. Dazu dient die Funktion <math>rang_0(B,i)</math> respektive <math>rang_1(B,i)</math> auf einem Bitvektor.
Die Rang-Funktion auf Bitvektoren kann in konstanter Zeit<ref name="Jacobson89"/> mithilfe von zusätzlichen <math>n+o(n)</math> Bits ausgewertet werden.
Rang
<math>rang_q(i)</math>: Anzahl der Zeichen <math>q</math> bis zur Position i in der Zeichenfolge.
Die Bestimmung des Rangs erfolgt analog zur Access-Operation. Nach Ausführung des Access-Algorithmus ergibt sich der Rang aus der Anzahl der Vorkommen von <math>B_{v_{Blatt}}[i]</math> bis zur Position i im Blattknoten.
Select
<math>select_q(i)</math>: Position des i-ten Vorkommens vom Zeichen q in der Zeichenfolge.
Um diese Position zu bestimmen, beginnt der Algorithmus bei dem Blatt, das q repräsentiert. Nun durchläuft der Algorithmus die Knoten rekursiv zur Wurzel: Falls der Knoten ein linkes Kind ist, so ergibt sich die neue Position im Elternknoten <math>i_0</math> aus der Position der i-ten <math>0</math> im zugehörigen Bitvektor. Ist das Kind ein rechter Nachfolger, so ergibt sich die neue Position <math>i_1</math> aus der Position der i-ten <math>1</math>. Diese Selekt-Operation auf einem Bitvektor<ref name="Clark96"/><ref name="Munro96" /> kann in konstanter Zeit mit zusätzlichen <math>n+o(n)</math> ausgeführt werden.
Kompression
Der Platzverbrauch von <math>O( \sigma \log{n})</math> kann durch Entfernung von Redundanzen mittels unterschiedlicher Verfahren auf <math>n\left\lceil\log{\sigma}\right\rceil+o(n)</math> Bits<ref name="Navarro05"/><ref name="Navarro07"/> mit gleicher Laufzeit der Operationen, bzw. <math>n\log{\sigma}+o(n)</math> Bits<ref name="GAGR07"/> und konstanter Laufzeit für Rang und Selekt verringert werden.
Anwendung
Diese Datenstruktur findet Verwendung in verschiedensten Anwendungen<ref name="FGM09"/><ref name="Navarro12"/>. Wavelet Trees kommen in Anwendungen zur Repräsentation von drei verschiedenen Klassen zum Einsatz.
Folge von Werten
Der Wavelet Tree repräsentiert eine Zeichenfolge<ref name="FERRA04"/><ref name="FERRA07"/>. Die verwendeten Operationen sind die drei genannten Grundoperationen auf dem Baum. Diese Repräsentation ist die am weitesten verbreitete.
Sortierung
Der Baum beschreibt eine geordnete Darstellung von der ausgehenden Zeichenfolge <math>S</math>. Die Blätter des Baums repräsentieren die sortierte Folge <math>S_{sort}</math>. Daraus ergeben sich zwei zusätzliche Operationen. <math>access(i)</math> liefert die Position des Zeichens <math>S[i]</math> in der sortierten Folge. Umgekehrt ergibt das Aufsteigen vom r'ten Blatt zur Wurzel die Position des Elements i mit <math>rang(i)=r</math>. Diese Darstellung wurde vom Erfinder von Wavelet Trees<ref name="GGV03"/> verwendet.
Grid von Punkten
Hierbei repräsentiert der Wavelet Tree eine Menge von Punkten.
Erweiterungen
In der Literatur finden sich einige Erweiterungen der Bäume. Um die Höhe von Wavelet Trees zu minimieren, werden t'näre anstatt binäre Knoten verwendet<ref name="FGM09" />. Somit erhöht sich der Knotengrad auf t Kinder und die Tiefe des Baumes sinkt. Operationen wie das Einfügen und Löschen von Zeichen an beliebigen Positionen in der Zeichenfolge erhöhen die Dynamik des Wavelet Trees und ermöglichen die Unterstützung dynamischer FM-Indizes<ref name="CHLK07"/>.
Weblinks
- Wavelet Trees. Blog, der die Konstruktion und Anfragen eines Wavelet Trees mit Beispielen beschreibt.
Einzelnachweise
<references> <ref name="GGV03"> R. Grossi, A. Gupta, and J. S. Vitter, High-order entropy-compressed text indexes (PDF; 292 kB), Proceedings of the 14th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA), January 2003, 841-850 </ref> <ref name="CB88"> B. Chazelle, A functional approach to data structures and its use in multidimensional searching, SIAM Journal on Computing, Volume 17, Issue 3, June 1988, Pages 427-462 </ref> <ref name="FGM09"> P. Ferragina, R. Giancarlo, G. Manzini, The myriad virtues of Wavelet Trees (PDF; 529 kB), Information and Computation, Volume 207, Issue 8, August 2009, Pages 849-866 </ref> <ref name="Navarro12"> G. Navarro, Wavelet Trees for All (PDF; 397 kB), Proceedings of 23rd Annual Symposium on Combinatorial Pattern Matching (CPM), 2012 </ref> <ref name="Jacobson89"> G. Jacobson, Space-efficient static trees and graphs (PDF; 381 kB), International Journal of Foundations of Computer Science (IJFCS), 1989, Pages 549-554 </ref> <ref name="Clark96"> D. Clark, Compact Pat Tree (PDF; 6,7 MB), University of Waterloo, Canada, 1996 </ref> <ref name="Munro96"> I. Munro, Tables, University of Waterloo, Canada, 1996, Pages 37-42 </ref>
<ref name="Navarro05"> V.Mäkinen, G. Navarro, Position-Restricted Substring Searching, Springer Heidelberg, Technische Fakultät Universität Bielefeld, 2006, Pages 703-714 </ref> <ref name="Navarro07"> V.Mäkinen, G. Navarro, Rank and select revisited and extended, Springer Heidelberg, University of Helsinki, 2007, Pages 332-347 </ref>
<ref name="GAGR07"> A. Golynski, R. Grossi, A. Gupta, R. Raman, On the Size of Succinct Indices, Springer Heidelberg, 2007, Pages 371-382 </ref>
<ref name="FERRA04"> P. Ferragina, G. Manzini, V. Mäkinen, G. Navarro, An Alphabet-Friendly FM-Index, Springer Heidelberg, 2004, Pages 150-160 </ref> <ref name="FERRA07"> P. Ferragina, G. Manzini, V. Mäkinen, G. Navarro, Compressed representations of sequences and full-text indexes, Association for Computing Machinery (ACM), 2007, Article 20 </ref>
<ref name="CHLK07">
H.-L. Chan, W.-K. Hon, T.-W. Lam, and K. Sadakane, Compressed Indexes for
dynamic text collections, ACM Transactions on Algorithms, 3(2), 2007
</ref>
</references>