Wavelet Tree

In der Informatik versteht man unter einem Wavelet Tree eine kompakte Datenstruktur, um Zeichenfolgen komprimiert abzuspeichern. Er erweitert die Methoden und von einem Bitvektor auf ein beliebiges Alphabet. 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.