Der Binärsuchbaum in lexikalischer Ordnung ergibt sich wie folgt:

Erklärung:

• Der Binärsuchbaum hat maximal 15 Wörter und jedes Wort enthält 5 Zeichen. Der Suchbaum soll ausbalanciert sein. Das bedeutet, dass zu jedem Knoten des Suchbaumes die Höhendifferenz seines linken und rechten Teilbaumes nicht größer als eins ist. In diesem Fall ist der Aufwand beim Suchen einer übereinstimmenden Zeichenfolge O(log n), wobei n die Länge des Suchpuffers ist.
• Kodierung von "ein_a" : (15, 4) (Offset = 15, Länge = 4)
• Die beiden Puffer werden um 4 Zeichen nach rechts verschoben. Die Wörter "ein_K", "in_Ki", "n_Kin", und "_Kind" werden aus dem Suchbaum entfernt, während die "ein_a", "in_an", "n_and", "_ande", "ander" neu hinzugefügt. Der Suchbaum muss im Allgemeinen umsortiert werden, damit er ausbalanciert ist.

Dekodierung

Die Informationen sind:

• die Anzahl der Durchläufe. Jedes Mal wenn wir entweder einen Zeiger oder ein einzelnes unkomprimiertes Zeichen in die Ausgabe schreiben, zählen wir dies als einen Durchlauf.
• die Größe des Bitfeldes.
• das Bitfeld. Wir speichern in einem Bitfeld, ob wir im entsprechenden Durchlauf einen Zeiger oder ein einzelnes Zeichen gespeichert haben. Angenommen, wir haben 10 Durchläufe, dann gibt es 10 Bits in unserem Bitfeld. Wir schreiben eine Eins in ein Bitfeld, wenn in dem Durchlauf ein Zeiger gespeichert wird, sonst schreiben wir eine Null hinein.

Am Anfang der Ausgabe, im Header, speichern wir nun diese Informationen. Die ersten 8 Byte sind für die Anzahl der Durchläufe und für die Größe des Bitfeldes reserviert (jeweils 4 Byte). Dann kommt das Bitfeld, das in Bytes umgewandelt wurde, und zuletzt die komprimierten Daten.

2.3 LZH