Wavelet Tree

In der Informatik versteht man unter einem Wavelet Tree eine kompakte Datenstruktur, um Zeichenfolgen komprimiert abzuspeichern. Er erweitert die Methoden $\mathbf {access,rang_{q}}$ und $\mathbf {select_{q}}$ von einem Bitvektor auf ein beliebiges Alphabet.

Ein Wavelet Tree aus der Zeichenfolge "abracadabra". Jeder Knoten unterteilt die Zeichenfolge abhängig vom Alphabet in zwei Teile. Ein Bitvektor ordnet jedes Zeichen aus der Folge seinem Bereich zu. Dabei ist zu beachten, dass die Datenstruktur nicht den Baum, sondern nur die Topologie und die Bitvektoren speichert. Die Zeichenfolgen in den Knoten dienen ausschließlich der Illustration.

Erstmals beschrieben wurde die Datenstruktur als Hauptbestandteil zur komprimierten Volltextindexierung und gilt als geringfügige Generalisierung einer Datenstruktur aus der algorithmischen Geometrie. 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 $S[1,n]$ über dem Alphabet $[1..\sigma ]$ kann über ein Teilalphabet $[a..b]\subseteq [1..\sigma ]$ rekursiv beschrieben werden. Ein Wavelet Tree über dem Alphabet $[a..b]$ ist ein binärer balancierter Baum mit $b-a+1$ Blättern.

1. Falls $a=b$, so besteht der Baum aus nur einem Blatt mit dem Label $a$.
2. Sonst besitzt der Baum einen Wurzelknoten $v_{root}$ mit einer Bitmap $b_{v_{root}}$, welche wie folgt definiert ist:

$B_{v_{root}}[i]={\begin{cases}0,&{\mbox{falls }}S[i]\leq (a+b)/2,\\1,&{\mbox{sonst.}}\end{cases}}$

Sei nun $S_{0}[1,n_{0}]$ die Teilsequenz aus $S[1,n]$ bestehend aus den Symbolen $c\leq (a+b)/2$ und $S_{1}[1,n_{1}]$ die Teilsequenz aus $S[1,n]$ bestehend aus den Symbolen $c>(a+b)/2$. Dann ist das linke Kind von $v_{root}$ ein Wavelet Tree von $S_{0}[1,n_{0}]$ über dem Alphabet $[a..\left\lfloor (a+b)/2\right\rfloor ]$ und das rechte Kind von $v_{root}$ ein Wavelet Tree von $S_{1}[1,n_{1}]$über dem Alphabet $[1+\left\lfloor (a+b)/2\right\rfloor ..b]$.

Eigenschaften

Der beschriebene Baum hat eine Höhe von $\left\lceil \log \sigma \right\rceil$, besitzt $\sigma$ Blätter und $\sigma -1$ interne Knoten. Er speichert $n$ Bits auf jeder Ebene und höchstens $n$ in der untersten Ebene. Somit lässt sich der Baum mit insgesamt höchstens $n\left\lceil \log \sigma \right\rceil$ Bits repräsentieren. Genau betrachtet benötigt diese Repräsentation weitere $O(\sigma \log n)$ Bits für die Zeiger.

Sei nun $S[1,n]=s_{1}s_{2}...s_{n}$ eine Zeichenfolge mit $s_{i}\in \Sigma$ aus dem Alphabet $\Sigma$ der Länge $\sigma =|\Sigma |$, so kann $S$ als Wavelet Tree mit $n\left\lceil \log \sigma \right\rceil =n\log \sigma +O(n)$ Bits repräsentiert werden.

Operationen

Der Wavelet Tree unterstützt die Operationen $\mathbf {access,rang_{q}}$, und $\mathbf {select} _{q}$ in $O(\log \sigma )$ Zeit, falls ein balancierter Baum konstruiert wurde.

Access

$access(i)$: Direktzugriff auf das i'te Element in der Zeichenfolge.

Um das Zeichen an der Position $S[i]$ zu berechnen, wird der Bitvektor $B_{v}{_{root}}[i]$ betrachtet. Falls der Wert an dieser Position $0$ ist, so ist $S[i]\leq (\sigma +1)/2$ und wir führen das Vorgehen auf dem linken Kind-Knoten rekursiv weiter, andernfalls gilt $S[i]>(\sigma +1)/2$ und der Algorithmus bearbeitet das rechte Kind. Dazu muss die neue Position von $i$ im Bitvektor $B_{v}{_{Kind}}[i]$ ermittelt werden. Die neue Position $i_{0}$ ist die Anzahl der Nullen im Vektor $B_{v}{_{root}}$ bis zur Position i, falls $B_{v}{_{root}}[i]=0$ gilt. Wird rekursiv das rechte Kind bearbeitet, so müssen die Vorkommen der Einsen aufsummiert werden. Dazu dient die Funktion $rang_{0}(B,i)$ respektive $rang_{1}(B,i)$ auf einem Bitvektor.

Die Rang-Funktion auf Bitvektoren kann in konstanter Zeit mithilfe von zusätzlichen $n+o(n)$ Bits ausgewertet werden.

Rang

$rang_{q}(i)$: Anzahl der Zeichen $q$ 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 $B_{v_{Blatt}}[i]$ bis zur Position i im Blattknoten.

Select

$select_{q}(i)$: 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 $i_{0}$ aus der Position der i-ten $0$ im zugehörigen Bitvektor. Ist das Kind ein rechter Nachfolger, so ergibt sich die neue Position $i_{1}$ aus der Position der i-ten $1$. Diese Selekt-Operation auf einem Bitvektor kann in konstanter Zeit mit zusätzlichen $n+o(n)$ ausgeführt werden.

Kompression

Der Platzverbrauch von $O(\sigma \log {n})$ kann durch Entfernung von Redundanzen mittels unterschiedlicher Verfahren auf $n\left\lceil \log {\sigma }\right\rceil +o(n)$ Bits mit gleicher Laufzeit der Operationen, bzw. $n\log {\sigma }+o(n)$ Bits und konstanter Laufzeit für Rang und Selekt verringert werden.

Anwendung

Diese Datenstruktur findet Verwendung in verschiedensten Anwendungen. Wavelet Trees kommen in Anwendungen zur Repräsentation von drei verschiedenen Klassen zum Einsatz.

Folge von Werten

Der Wavelet Tree repräsentiert eine Zeichenfolge. 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 $S$. Die Blätter des Baums repräsentieren die sortierte Folge $S_{sort}$. Daraus ergeben sich zwei zusätzliche Operationen. $access(i)$ liefert die Position des Zeichens $S[i]$ in der sortierten Folge. Umgekehrt ergibt das Aufsteigen vom r'ten Blatt zur Wurzel die Position des Elements i mit $rang(i)=r$. Diese Darstellung wurde vom Erfinder von Wavelet Trees 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. 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.

Weblinks

• Wavelet Trees. Blog, der die Konstruktion und Anfragen eines Wavelet Trees mit Beispielen beschreibt.