Codierung mit dem Huffman-Algorithmus
von Konrad Rudolph
Übersicht
In meinem letzten Tutorial habe ich gezeigt, wie man Zeiger in VB ohne API verwenden kann. Dieses Tutorial erklärt ein etwas umfangreicheres Praxisbeispiel: die Datenkompression mittels des Huffman-Codes. Obwohl große Teile des Codes eine direkte Praxisanwendung der Zeiger sind, sollte an dieser Stelle bemerkt werden, dass der Schwierigkeitsgrad dieses Tutorials sehr viel höher ist. Aus diesem Grund habe ich bei dem Code auch in erster Linie auf die Übersichtlichkeit und erst in zweiter auf die Geschwindigkeit geachtet.
Mit freundlichen Grüßen
Konrad L. M. Rudolph
Einleitung
Motivation
Obwohl die Festplatten immer größer werden, es inzwischen DVD-Brenner gibt und Breitband fast schon Standardausstattung geworden ist, hat Datenkompression Hochkonjunktur. Einer der meistverwendeten Algorithmen der Datenkompression ist der so genannte Huffman-Code.
Der Huffman-Code ist allerdings nicht nur ein recht gutes Kompressionsverfahren, sondern auch ein guter Algorithmus, an dem sich die Rolle der Zeiger in der Programmierung zeigen lässt. Um besser auf die theoretischen Aspekte des Algorithmus eingehen zu können, wurde bei der Implementierung ausschließlich VB-Code verwendet. APIs oder fremde Komponenten kommen nicht zum Einsatz.
In der Praxis ist die Implementierung dadurch allerdings nur bedingt einsetzbar: trotz einiger kleiner Optimierungen ist VB einfach zu langsam. In der Praxis sollte man eher eine Assembler-Implementierung verwenden. Den Algorithmus umzusetzen sollte nach der Lektüre dieses Tutorials nicht zu schwer sein, wenn man über genügend Kenntnisse in der Assembler-Programmierung verfügt.
Voraussetzungen
Das Tutorial baut auf Erkenntnissen aus dem Tutorial Zeiger in VB [Tutorial 4012] auf. Man sollte zumindest aber über ein grundsätzliches Verständnis der Zeigerprogrammierung verfügen und außerdem mit den beiden Datenstrukturen Liste und Binärbaum vertraut sein. Auch Kenntnisse im Umgang mit Bits und Bitoperationen werden benötigt. Einige Grundlagen hierzu bieten Bits & Bytes [Tutorial 4008] und Verwendung von Flags [Tutorial 4006].
Theoretische Grundlagen
Bitcodes
Standardmäßig werden Dateien so gespeichert, dass jedes Zeichen der Binärdaten (oder des Textes) ein Byte an Speicher einnehmen. Auf heutigen Systemen ist ein Byte ein Oktet, das heißt acht Bit.
Wenn man nun die Häufigkeit der verschiedenen Zeichen einer Datei (unter "Datei" verstehe ich im Folgenden immer ein Paket von Daten im Byteformat, egal ob Binärdaten oder Text, auf der Festplatte oder im Speicher) auszählt, wird man merken, dass nicht alle Zeichen gleich häufig auftauchen - logisch. Diesen Unterschied kann man sich bei der Kompression zunutze machen: stellen wir uns vor, wir würden nicht jedes Zeichen durch eine feste Anzahl an Bits codieren, sondern durch eine variable und stellen wir uns weiterhin vor, dass häufiger benötigte Zeichen kürzere Bitcodes besitzen als seltene Zeichen. Auf diese Weise ließe sich eventuell einiges an Platz sparen. In der Tat ist die Kompression um so größer, je unterschiedlicher die Häufigkeit der Zeichen ist. Bei Dateien mit ausgewogener Zeichenhäufigkeit kann man durch Huffman-Codierung nichts gewinnen.
Das Problem eines solchen Codes leuchtet ein: bei Dateien mit fester Codelänge ist klar, wo ein Zeichen endet und das nächste anfängt. Wenn die Bitcodelänge variabel ist, haben wir a priori keinen Anhaltspunkt, wie lang ein Zeichen ist.
Die naheliegende Lösung wird im Morsecode verwendet: eine Pause zwischen den einzelnen Zeichen dient als Trennzeichen. Es gibt jedoch eine bessere Lösung: die Verwendung eines so genannten Präfixcodes. Präfixcodes sind Codes, bei denen kein Zeichen das Präfix eines anderen Zeichens ist, soll heißen: wenn wir ein Zeichen und seinen Code haben, so gibt es kein anderes Zeichen, dessen Code mit dem Code des gewählten Zeichens anfängt.
Konfus? Nun, hier ist ein Beispiel mit einem Präfixbitcode für die Zeichen "A", "V" und "B":
A 1010 V 1101 B 011 X 01 AVB 10101101011
Listing 1
"X" kann kein Zeichen unseres Codes sein, denn der Bitcode von "B" beginnt mit der Bitsequenz von "X". Wenn wir den String "AVB" mit unserem Code codieren, könnte man nicht entscheiden, ob hinter dem "V" ein "B" kommt oder ein "X".
Ein geläufigeres Beispiel für einen Präfixcode sind Telefonnummern. Mit jeder weiteren Ziffer, die man wählt, wird man im Netz der Telekom um einen "Ast" weitergeleitet. Vielleicht ist es dem einen oder anderen Leser bereits passiert, dass das "Falsche Nummer"-Zeichen kam, obwohl man noch gar nicht die ganze Nummer gewählt hatte. Dies ist nur möglich, da die Nummer eben ein Präfixcode ist: sobald eine falsche Ziffer gewählt wurde, kann es vorkommen, dass der entsprechende "Ast" nicht existiert.
Huffman
Präfixcodes sind schön und gut, aber sie sind an sich nicht kürzer als unser gewöhnlicher Bytecode. Wir bräuchten ein Verfahren, um für eine gegebene Datei den Präfixcode zu finden, der die kürzesten Bitfolgen hat, in Abhängigkeit der Häufigkeit eines Zeichens.
Ein solches ist das nach Huffman benannte Verfahren.
David A. Huffman (1925 - 1999) gilt als Pionier auf dem Gebiet der Informatik. Im Alter von 25 wurde ihm von seinem Professor an der Universität die Wahl zwischen einer Abschlussklausur und einer Seminararbeit gegeben. Die Aufgabe der Seminararbeit war, den effektivsten Weg zu finden, um Nummern darzustellen. Huffman versuchte mehrere Lösungswege, um die Aufgabe zu lösen, gab jedoch letztendlich auf und wollte sich bereits dem Üben für die Abschlussarbeit widmen, als er eine plötzliche Eingebung hatte, die das Problem löste, an dem sich bereits sein Professor Robert M. Fano vergeblich versucht hatte. Seine Lösung ist heute als das Huffman-Verfahren bekannt.
Es ermittelt für eine gegebene Datei einen günstigsten Präfixcode (dieser günstigste Präfixcode ist nicht unbedingt eindeutig). Dazu benutzt der Algorithmus einen Binärbaum, dessen Blätter einzelne Zeichen und dessen Äste die Bitfolgen repräsentieren. Ein solcher Baum heißt Huffmanbaum.
Der Huffmanbaum
Die Knoten des Huffmanbaumes verwalten wir für den einfachen Zugriff in einem linearen Datencontainer. Ich habe für meine Implementierung eine einfach verbundene Liste gewählt. Es gibt definitiv effizientere Methoden, aber eine Liste funktioniert, außerdem braucht dieser Teil der Codierung einen verhältnismäßig geringen Teil der Gesamtlaufzeit.
Zu Anfang erstellen wir für jedes verwendete Zeichen einen Knoten, den wir in unserem Container ablegen. Neben dem Zeichencode enthält der Knoten noch eine andere Information: die Häufigkeit des Zeichens in der Eingabedatei. Diese Knoten werden später die Blätter unseres Huffman-Baums.
Wir hatten bereits gesagt, dass die Äste des Baumes die Binärfolge eines Zeichens repräsentieren. Genauer gesagt folgen wir den Ästen von der Wurzel bis zum Blatt, das ein Zeichen repräsentiert. Immer, wenn wir den linken Ast nehmen, fügen wir eine Null zum Binärcode, beim rechten Ast eine Eins. Je länger der Weg, desto länger der Binärcode.
Den Baum werden wir von den Blättern zur Wurzel hin konstruieren ("bottom up"). Aus diesem Grund fangen wir mit den Zeichen an, die die geringste Häufigkeit haben: in einer Schleife entnehmen wir aus der Liste jeweils die zwei Knoten mit dem geringsten Wert. Dann erzeugen wir einen neuen Knoten, dessen linkes Kind der zuerst entnommene und dessen rechtes Kind der als zweites entnommene Knoten wird. Als Wert des neuen Knotens setzen wir die Summe der Werte seiner beiden Kindesknoten.
Falls sich nun noch Knoten in der Liste befinden, packen wir den neu erstellten Knoten ebenfalls in die Liste. Andernfalls verlassen wir die Schleife und definieren den neu erstellten Knoten als Wurzel des Huffmanbaumes.
Beweisführung (Ansatz)
Warum ist dieser Code ein Präfixcode? Diese Frage ist einfach zu beantworten: jedes Zeichen ist ein Blatt, das heißt es hat keine weiteren Kinder und daher gibt es keinen anderen Code, der mit der Bitfolge eines anderen Zeichens beginnt.
Warum ist dieser Code von seiner Länge her optimal? Zuerst einmal, da seltenere Zeichen die längeren Codes haben. Zum Anderen, da die Gewichtung der Häufigkeit beachtet wird. Das bedeutet, dass zwei Zeichen, die zusammengezählt eine Häufigkeit von 20 besitzen, einen kürzeren Code haben als ein Zeichen, das alleine 19 Mal vorkommt.
Nehmen wir an, wir hätten eine Datei mit den Zeichen "A", "V", "B" und "X" respektive mit den Häufigkeiten 6, 3, 2 und 20. Daraus ergäbe sich folgender Huffmanbaum:
Abbildung 1
Die Übersetzungstabelle
Aus diesem Baum können wir uns nun eine Übersetzungstabelle erstellen, die für jedes Zeichen einen Eintrag mit der Bitfolge enthält. In dem Beispiel wird die Bitfolge in einem Long abgelegt sein. Dabei tut sich allerdings ein Problem auf: ein Long besitzt 32 Bit, d.h. plötzlich hätte jeder unserer Codes 32 Bit, was ja nicht stimmt. Aus diesem Grund müssen wir noch einen zweiten Wert für jeden Eintrag der Tabelle haben: die Länge der Bitfolge.
Zum Erstellen der Tabelle verwenden wir einen Depth-first-Durchlauf des Baumes beginnend bei der Wurzel. Das ganze funktioniert mit einer rekursiven Prozedur, die zwei Argumente besitzt: den aktuellen Knoten und den Bitcode des aktuellen Knotens. In der Prozedur testen wir, ob der Knoten Kinder hat. Wenn nicht, ist er ein Blatt und somit ein Zeichen. Wir tragen also den aktuellen Bitwert in die Tabelle ein. Ansonsten rufen wir die Prozedur erneut für beide Kindesknoten auf, wobei wir den Bitcode für den linken Knoten mit Eins, für den rechten mit Null erweitern.
Bitspielereien
Ein anderes Problem muss noch aus der Welt geschafft werden, bevor wir uns der Implementierung widmen: wie speichern wir die Bitcodes ab? Die kleinste Dateneinheit, auf die wir direkt Zugriff haben, ist das Byte. Praktisch sieht es so aus, dass wir unsere Daten in Bytefelder schreiben werden und jeweils die einzelnen Bits eines Byte manipulieren. Das ganze geschieht in einer Schleife, allerdings brauchen wir statt einem Zähler zwei: einer für das aktuelle Byte, einer für das aktuelle Bit im aktuellen Byte.
Schnittstellendesign
Die Huffman-Klasse
Die Huffman-Klasse hat eine recht einfache Schnittstelle: wir brauchen lediglich Funktionen zum Codieren und Decodieren der Daten. Sicher könnte man das ganze noch verfeinern, aber ich schlage für den Anfang folgende Schnittstelle vor:
Public Function EncodeString(Text As String) As String Public Function DecodeString(Text As String) As String Public Function EncodeBytes(Text() As Byte) As Byte() Public Function DecodeBytes(Text() As Byte) As Byte()
Listing 2
Die Stringfunktionen sind dabei lediglich für den Komfort des Benutzers und rufen intern die Bytefunktionen auf. Diese Klasse wird die einzige sein, auf die wir von außen zugreifen müssen. Sie delegiert jedoch einige Aufgaben an andere Klassen.
Die Dictionary-Klasse
Funktionen, die mit dem Erstellen der Übersetzungstabelle zu tun haben, habe ich in einer Lexikon-Klasse zusammengefasst. Hier stoßen wir jedoch auf ein Problem: Aufrufe in Klassen sind extreme Bremsen. Es bietet sich daher an, in der Praxis eine andere Schnittstelle zu wählen oder eventuell ganz auf eine eigene Klasse für das Lexikon zu verzichten.
Public Sub Create(Text() As Byte) Public Function Serialize() As Byte() Public Function Read(Code() As Byte, StartCell As Long) As Long Public Function GetLetter( _ Text() As Byte, _ ByRef Cell As Long, _ ByRef Offset As Long _ ) As Byte Friend Property Get Char() As ByteCode()
Listing 3
Wie man sieht, wird hier ausschließlich mit Bytefeldern gearbeitet - kein String weit und breit.
Create() erstellt für eine gegebene Datei die Übersetzungstabelle. Serialize() verpackt unser Lexikon in ein Bytefeld, das mit den codierten Daten zusammen die neue Datei bildet - ansonsten könnte man die Daten ja nicht wieder decodieren. Read() liest auf diese Weise gespeicherte Daten aus.
Char() gibt die Übersetzungstabelle an die Huffman-Klasse zurück. Diese Eigenschaft ist als Friend deklariert, da Public-Prozeduren in Klassen keine Datensätze (UDTs) als Parameter oder Rückgabewert verwenden können.
GetLetter() wird zum Decodieren gebraucht: Diese Funktion durchläuft den Huffmanbaum auf der Suche nach dem aktuellen Zeichen im Eingabetext.
Die List-Klasse
Unser Container muss recht wenig können: neben einer Funktion zum Hinzufügen von Elementen brauchen wir auch eine zum Entfernen des kleinsten Knotens. Damit haben wir folgende Schnittstelle:
Public Sub Clear() Public Sub Push(Node As Pointer, Frequency As Long) Public Function PopLowest() As Pointer Public Property Get Size() As Long
Listing 4
Die Datentypen, die wir für die Liste und den Baum sowie für die Bitcodes verwenden, sind folgendermaßen definiert:
Public Type MapItem Char As Byte Freq As Long End Type Public Type TreeNode Data As MapItem Left As Pointer Righ As Pointer End Type Public Type ListItem Data As Pointer Freq As Long Next As Pointer End Type Public Type ByteCode Bits As Long Len As Byte End Type
Listing 5
Implementierung
Im Folgenden werde ich keine vollständigen Quelltexte abbilden, sondern jeweils nur die interessanten Teile. Um die vollständigen Quelltexte einzusehen, kann man sich das Beispielprojekt herunterladen.
Die Liste
Public Sub Push(Node As Pointer, Frequency As Long) Dim pItem As Pointer pItem = Alloc() Heap(pItem).Seg.Data = Node Heap(pItem).Seg.Freq = Frequency Heap(pItem).Seg.Next = m_First m_First = pItem m_Size = m_Size + 1 End Sub
Listing 6
Hierbei geschieht nichts besonderes. Es wird lediglich ein neues Element erzeugt und in die Kette eingehängt.
Public Function PopLowest() As Pointer Dim pIter As Pointer, _ pLast As Pointer Dim Min As Long Dim pMin As Pointer, _ pTmp As Pointer pIter = m_First Min = &HFFFFFFF Do While pIter If Heap(pIter).Seg.Freq < Min Then Min = Heap(pIter).Seg.Freq pMin = pLast End If pLast = pIter pIter = Heap(pIter).Seg.Next Loop If pMin = 0 Then PopLowest = Heap(m_First).Seg.Data pTmp = m_First m_First = Heap(m_First).Seg.Next Else pTmp = Heap(pMin).Seg.Next PopLowest = Heap(pTmp).Seg.Data Heap(pMin).Seg.Next = Heap(pTmp).Seg.Next End If Call Free(pTmp) m_Size = m_Size - 1 End Function
Listing 7
Hier wird etwas mehr Aufwand getrieben, da zuerst das kleinste Element bestimmt werden muss. Hierzu setzen wir am Anfang die Variable Min auf einen sehr großen Wert. Dies kann problematisch werden, wenn wir mit größeren Dateien arbeiten: falls die Datei mehr als 255 MB haben sollte, kann es vorkommen, dass ein Zeichen häufiger auftaucht und die Prozedur somit falsche Resultate liefert. Ich nehme aber einmal an, dass niemand versuchen wird, eine derart große Datei in VB zu komprimieren.
In der Schleife merken wir uns nun immer das Element unmittelbar vor dem kleinsten. Dies müssen wir tun, da wir das vorhergehende Element brauchen, um das kleinste Element aus der Kette zu eliminieren und die Kette trotzdem intakt zu lassen.
Nach Durchlaufen der Schleife müssen wir prüfen, ob es sich bei dem kleinsten Element um das erste Element der Kette handelt, in diesem Fall müssen wir die Variable m_First nämlich neu zuweisen. Nachdem wir das Element aus der Kette ausgegliedert und den Wert ausgelesen haben, wird der Zeiger per Free() freigegeben.
Das Lexikon
Die Implementierung des Lexikons ist um einiges umfangreicher. Ich werde zunächst die Funktionen zum Erstellen desselben erklären, da diese den Huffman-Algorithmus implementieren.
Public Sub Create(Text() As Byte) Dim Idx As Long Call SetHeapSize(200) Call SetDynamic(True, 50) For Idx = 0 To UBound(Text) m_Freqs(Text(Idx)) = m_Freqs(Text(Idx)) + 1 Next Idx m_Root = CreateHuffmanTree() If m_Root = 0 Then _ Exit Sub Dim NewCode As ByteCode Call CreateTable(m_Root, NewCode) End Sub
Listing 8
Zuerst wird der Heap dimensioniert. Die Start- und Vergrößerungswerte für den Heap sind hierbei mehr oder weniger willkürlich; sie sollten aber in etwa im oben gewählten Bereich liegen.
Nun werden in einer einfachen Schleife die Häufigkeiten der einzelnen Zeichen ausgezählt. Danach wird der Huffmanbaum mit der Wurzel Root erstellt. Zuletzt erzeugen wir aus dem Baum eine Übersetzungstabelle.
Es folgen nunmehr die Prozeduren CreateHuffmanTree() und CreateTable():
Private Function CreateHuffmanTree() As Pointer Dim Idx As Long Dim List As List Dim Node As Pointer Set List = New List For Idx = 0 To 255 If m_Freqs(Idx) > 0 Then Node = Alloc() Heap(Node).Seg.Data.Char = CByte(Idx) Heap(Node).Seg.Data.Freq = m_Freqs(Idx) Call List.Push(Node, m_Freqs(Idx)) End If Next Idx Dim Left As Pointer, _ Righ As Pointer Dim Freq As Long Do While List.Size > 0 Left = List.PopLowest() Righ = List.PopLowest() Node = Alloc() Freq = Heap(Left).Seg.Data.Freq + Heap(Righ).Seg.Data.Freq Heap(Node).Seg.Data.Freq = Freq Heap(Node).Seg.Left = Left Heap(Node).Seg.Righ = Righ If List.Size = 0 Then CreateHuffmanTree = Node Exit Do End If Call List.Push(Node, Freq) Loop End Function
Listing 9
Sieht eigentlich ganz einfach aus - ist es auch. Huffman entzaubert.
In einem ersten Schritt wird für jedes Zeichen, das im Text vorkommt, ein Listeneintrag erzeugt. Dann geht es richtig los: in der Schleife werden zuerst die beiden Knoten mit dem niedrigsten Gewicht entfernt. Dann wird ein neuer Knoten erstellt, als Kinder werden ihm die beiden Knoten zugewiesen und seine Gewichtung entspricht der Summe der Gewichtungen der beiden Kindesknoten. Dieser neue Knoten wird in die Liste eingefügt, es sei denn, die Liste ist leer. In diesem Fall wird die Prozedur verlassen und der neu erstellte Knoten als Wurzel des Huffmanbaumes zurückgegeben.
Private Sub CreateTable(Node As Pointer, Code As ByteCode) If Heap(Node).Seg.Left = 0 Then m_Table(Heap(Node).Seg.Data.Char) = Code Else Dim LeftCode As ByteCode Dim RighCode As ByteCode LeftCode.Len = Code.Len + 1 LeftCode.Bits = Code.Bits * 2& Call CreateTable(Heap(Node).Seg.Left, LeftCode) RighCode.Len = Code.Len + 1 RighCode.Bits = (Code.Bits * 2&) Or 1& Call CreateTable(Heap(Node).Seg.Righ, RighCode) End If End Sub
Listing 10
Diese Prozedur ist sogar noch einfacher. Zuerst wird geprüft, ob das aktuelle Kind des aktuellen Knotens definiert ist. Wenn nicht, so handelt es sich um ein Blatt, also einen Knoten, der ein Zeichen enthält. Wir notieren uns daher den aktuellen Code in der Übersetzungstabelle.
Ansonsten rufen wir die Prozedur nacheinander erneut mit den beiden Kindern des aktuellen Knotens auf. Beim Aufruf verändern wir den aktuellen Code: die Länge des Codes wird um eins erhöht (denn wir befinden uns einen Ast tiefer), außerdem fügen wir für den linken Ast eine Null an den Code, für den rechten eine Eins. Das geht ganz einfach, indem wir den Code mit zwei multiplizieren (was einem Verschieben der Bits um eine Stelle nach links entspricht) und eins addieren. Statt der Addition nehmen wir hier den bitweise-Or-Operator, der dasselbe macht aber schneller ist.
Nun stehen noch die Funktionen aus, die die Daten des Lexikons in einem Datenblock ablegen und wieder auslesen. Als einzige Information zum Erstellen des Huffmanbaumes brauchen wir die Häufigkeit der einzelnen Zeichen. Daher speichern wir einfach für jedes Byte-Zeichen einen Long-Wert ab. Dies nimmt allerdings einiges an Speicherplatz weg, nämlich 256 * 4 Bytes = 1 KB. Dadurch lohnt sich eine Kompression von vornherein nur für Dateien, die größer als 1 KB sind.
Um die Long-Werte in ein Bytefeld zu bekommen, verwenden wir folgende Prozedur:
Public Function Serialize() As Byte() Dim Buff() As Byte Dim Idx As Long Dim BufIdx As Long ReDim Buff(256 * 4 - 1) For Idx = 0 To 255 BufIdx = Idx * 4 Buff(BufIdx) = m_Freqs(Idx) \ &H1000000 Buff(BufIdx + 1) = m_Freqs(Idx) \ &H10000 And &HFF& Buff(BufIdx + 2) = m_Freqs(Idx) \ &H100& And &HFF& Buff(BufIdx + 3) = m_Freqs(Idx) And &HFF& Next Idx Serialize = Buff End Function
Listing 11
Um an die einzelnen Bytes des vier-Byte-Long heranzukommen, verwenden wir die Ganzzahldivision, um die Bytes nach rechts zu verschieben. Die anschließende And-Operation sorgt dafür, dass wirklich nur das nun unterste Byte ausgelesen wird und die oberen Bytes wegfallen.
Public Function Read(Code() As Byte, StartCell As Long) As Long Dim Idx As Long Call SetHeapSize(200) Call SetDynamic(True, 50) Read = StartCell For Idx = 0 To 255 m_Freqs(Idx) = CLng(Code(Read)) * &H1000000 Or _ CLng(Code(Read + 1)) * &H10000 Or _ CLng(Code(Read + 2)) * &H100& Or _ CLng(Code(Read + 3)) Read = Read + 4 Next Idx m_Root = CreateHuffmanTree() End Function
Listing 12
Hier geschieht nun genau das Gegenteil: wir übergeben ein Bytefeld und eine Startzelle (da die relevanten Daten sich nicht ganz zu Anfang des Feldes befinden). Zuerst wird, wie in Create(), der Heap initialisiert. Dann werden die Häufigkeiten ausgelesen und der Huffmanbaum erstellt. Da wir für das Decodieren keine Übersetzungstabelle brauchen, wird auch keine erstellt.
Zum Codieren brauchen wir die Übersetzungstabelle, daher wird sie von außen für Lesezugriffe zugänglich gemacht:
Friend Property Get Char() As ByteCode() Char = m_Table End Property
Listing 13
Um den Baum für die Decodierung nutzbar zu machen, verwenden wir die folgende Funktion, die jeweils immer das nächste Zeichen in einer Huffmandatei ausliest:
Public Function GetLetter( _ Text() As Byte, _ ByRef Cell As Long, _ ByRef Offset As Long _ ) As Byte Dim Node As Pointer Node = m_Root Do If Heap(Node).Seg.Left = 0 Then GetLetter = Heap(Node).Seg.Data.Char Exit Function End If If IsBitSet(Text(Cell), Offset) Then _ Node = Heap(Node).Seg.Righ _ Else _ Node = Heap(Node).Seg.Left Offset = Offset + 1 If Offset = 8 Then Offset = 0 Cell = Cell + 1 End If Loop End Function
Listing 14
Dieser Funktion werden sowohl die aktuelle Zelle als auch das aktuelle Bit in der Zelle des Feldes übergeben. Dies ist nötig, da wir ja auf Bitebene statt auf Byteebene manipulieren.
Zuerst weisen wir einem Knoten die Wurzel als Start zu. Dann führen wir eine Schleife aus, in der geprüft wird, ob der Knoten Kinder besitzt. Falls nicht, haben wir das Zeichen fertig ausgelesen und können es zurückgeben. Ansonsten testen wir anhand der Funktion IsBitSet(), ob das aktuelle Bit gesetzt ist oder nicht und setzen in Abhängigkeit den Knoten auf sein rechtes oder linkes Kind. Dann erhöhen wir die aktuelle Bitposition. Sollte sie größer als acht sein, haben wir das Byte fertig abgearbeitet und erhöhen die Zellenposition um eins.
Auf diese Weise tasten wir uns, ähnlich wie bei den Telefonnummern, immer näher an unser Ziel heran.
Huffman
Bei den Funktionen EncodeString() und DecodeString() handelt es sich lediglich um eine "Verpackung" für die Bytependants der Funktionen:
Public Function EncodeString(Text As String) As String EncodeString = _ StrConv( _ EncodeBytes(StrConv(Text, vbFromUnicode)), _ vbUnicode _ ) End Function Public Function DecodeString(Text As String) As String DecodeString = _ StrConv( _ DecodeBytes(StrConv(Text, vbFromUnicode)), _ vbUnicode _ ) End Function
Listing 15
Die Funktion EncodeBytes() muss die meiste Arbeit verrichten: sie codiert die Daten und setzt die Ausgabedaten aus Kennung, Kopf und Daten zusammen. Bei der Kennung handelt es sich um die ersten vier Bytes der Huffmandatei: nur wenn diese Kennung vorhanden ist, erkennt die Klasse eine Datei als Huffmandatei an und decodiert sie. Dies unterbindet Fehleingaben und stellt gleichzeitig eine Versionskontrolle zur Verfügung.
Public Function EncodeBytes(Text() As Byte) As Byte() Dim Dict As Dictionary Dim Head() As Byte, _ Data() As Byte Dim DatLen As Long Dim TextLen As Long Dim Pos As Long, _ Bit As Long Dim Offset As Long Dim Cell As Long Dim Bits() As ByteCode Set Dict = New Dictionary Call Dict.Create(Text) TextLen = UBound(Text) Bits = Dict.Char For Pos = 0 To TextLen DatLen = DatLen + Bits(Text(Pos)).Len Next Pos ReDim Data((DatLen - 1) \ 8) For Pos = 0 To TextLen For Bit = Bits(Text(Pos)).Len - 1 To 0 Step -1 Call SetBit( _ Data(Cell), _ Offset, _ DWIsBitSet(Bits(Text(Pos)).Bits, Bit) _ ) Offset = Offset + 1 If Offset = 8 Then Offset = 0 Cell = Cell + 1 End If Next Bit Next Pos Head = Dict.Serialize() If UBound(Head) + UBound(Data) + 8 < UBound(Text) Then Dim StrID As String, _ StrHead As String, _ StrLen As String, _ StrData As String TextLen = TextLen + 1 StrID = HeaderID StrHead = Head StrLen = _ StrConv( _ Chr$(TextLen \ &H1000000) & _ Chr$(TextLen \ &H10000 And &HFF&) & _ Chr$(TextLen \ &H100& And &HFF&) & _ Chr$(TextLen And &HFF&), _ vbFromUnicode _ ) StrData = Data EncodeBytes = StrID & StrHead & StrLen & StrData Else EncodeBytes = Text End If End Function
Listing 16
Zuerst wird das Lexikon erstellt. Dann wird die Länge der Ausgabedaten errechnet und das Feld neu dimensioniert. Da die Länge in Bits ist, müssen wir den Wert durch acht teilen, um auf Bytes zu kommen.
Nun gehen wir der Reihe nach alle Zeichen der Eingabedatei durch. In einer weiteren Schleife gehen wir die Bits des Bitcodes des aktuellen Zeichens durch, testen, ob sie gesetzt sind und setzen in diesem Falle das aktuelle Zeichen im Ausgabefeld. Hier arbeiten wir wieder mit zwei Indizes: einem für die aktuelle Zelle des Ausgabefeldes und einem für das aktuelle Bit des Ausgabefeldes. Wenn das Bit den Wert acht hat, wird die Zelle erhöht und die Bitposition zurück auf null gesetzt.
Nachdem wir auf diese Weise den Text codiert haben, speichern wir im Feld Head die Häufigkeiten der Zeichen. Nun testen wir, ob die Ausgabedatei kleiner wäre als die Eingabe. Nur wenn dies der Fall ist, geben wir die codierten Daten zurück, ansonsten belassen wir die Eingabedatei unverändert: unser Algorithmus kann sie nicht verkleinern.
Nun müssen wir noch die einzelnen Felder (die Identifikation, den Kopf, die Daten sowie die Datenlänge) zusammenführen. Dies geht in VB am einfachsten, indem man die Bytefelder in temporäre Strings speichert und diese dann verkettet. Die Länge des Texts wird hierbei wieder in vier Bytes abgelegt, wie das auch mit den Häufigkeitswerten passiert.
Bei diesem doch recht großen Aufwand ist es verwunderlich, dass das Decodieren - dank unserer Vorarbeit im Lexikon - viel einfacher geht:
Public Function DecodeBytes(Text() As Byte) As Byte() Dim Dict As Dictionary Dim Offset As Long Dim CharPos As Long Dim Cell As Long Dim TextLen As Long Dim Res() As Byte If Not ByteCompare(Text, HeaderID, 4) Then DecodeBytes = Text Exit Function End If Set Dict = New Dictionary Cell = Dict.Read(Text, UBound(HeaderID) + 1) If Cell = 0 Then _ Exit Function TextLen = CLng(Text(Cell)) * &H1000000 Or _ CLng(Text(Cell + 1)) * &H10000 Or _ CLng(Text(Cell + 2)) * &H100& Or _ CLng(Text(Cell + 3)) Cell = Cell + 4 ReDim Res(TextLen) For CharPos = 0 To TextLen - 1 Res(CharPos) = Dict.GetLetter(Text, Cell, Offset) Next DecodeBytes = Res End Function
Listing 17
Zuerst wird mit der Prozedur ByteCompare() getestet, ob die ersten vier Bytes unserer Kennung entsprechen. Dann lesen wir die Häufigkeiten der Zeichen aus und erstellen mit diesen Informationen das Lexikon. Nun wird die Textlänge ausgelesen und unser Ergebnisfeld entsprechend dimensioniert. In der anschließenden Schleife ermitteln wir nacheinander alle Ausgabezeichen dank der Prozedur GetLetter() im Lexikon.
Hilfsfunktionen
Wir haben einige Hilfsfunktionen zur Bit- und Bytemanipulation verwendet. Diese Funktionen habe ich in ein Modul ausgegliedert:
Option Explicit Private m_Init As Boolean Private m_BitTable(31) As Long '---------------------------------------------------- Public Sub InitBits() Dim I As Long If Not m_Init Then m_BitTable(0) = 1 m_BitTable(31) = -2147483648# For I = 1 To 30 m_BitTable(I) = m_BitTable(I - 1) * 2 Next I End If End Sub Public Sub SetBit( _ ByRef Char As Byte, _ Offset As Long, _ Condition As Boolean _ ) If Condition Then _ Char = Char Or m_BitTable(Offset) End Sub Public Function DWIsBitSet(DWord As Long, Offset As Long) As Boolean DWIsBitSet = DWord And m_BitTable(Offset) End Function Public Function IsBitSet(Char As Byte, Offset As Long) As Boolean IsBitSet = Char And m_BitTable(Offset) End Function Public Function ByteCompare( _ Haystack() As Byte, _ Compare() As Byte, _ Number As Long, _ Optional Start As Long = 0 _ ) As Boolean Dim I As Long On Error Goto ERR_ByteCompare For I = Start To Start + Number - 1 If Haystack(I) <> Compare(I) Then _ Exit Function Next I ByteCompare = True ERR_ByteCompare: End Function
Listing 18
In der Prozedur InitBits() wird eine Tabelle mit Bitwerten initialisiert. Dies erspart uns später die Zweiterpotenzierung, die recht zeitaufwändig ist.
SetBit() setzt ein angegebenes Bit in einem Byte. IsBitSet() liest aus, ob ein angegebenes Bit in einem Byte gesetzt ist. DWIsBitSet() tut das selbe in einem Longwert. ByteCompare() geht eine gegebene Anzahl von Bytes in zwei Feldern durch und vergleicht, ob diese gleich sind. Bei der ersten Abweichung wird False zurückgeliefert.
Schlusswort
Danksagungen
Die Implementierung dieses Codes ging nicht ohne gewisse Probleme vonstatten. Denn ganz ehrlich: VB ist nun einmal langsam. Aus diesem Grund habe ich an vielen Stellen versucht, so sehr zu optimieren wie möglich, allerdings nie zum Preis der Lesbarkeit. Hiermit möchte ich mich bei einigen Leuten für ihre Unterstützung im Forum oder Chat bedanken, ohne die der Code längst nicht so schnell oder lesbar geworden wäre, wie er jetzt ist. Ich danke Guido Beckmann, Claus von der Burchard, Philipp Claves, Kai Liebenau, Stefan Maag, Peter Sauer, Philipp Stephani und Marco Wünschmann.
Abschließende Feststellung
Die vorgestellte Implementierung ist nicht die einzige und sicher nicht die bestmögliche. Sie beleuchtet allerdings recht gut die verschiedenen Einsatzgebiete von Zeigern und arbeitet konsequent mit zwei verschiedenen Datenbehältern, der Liste und dem Baum. Sie zeigt außerdem, dass der Gebrauch von API in VB nur bedingt sinnvoll ist: der obige Code lässt sich durch den Gebrauch von API kaum beschleunigen. Einzig die Prozeduren zum Speichern und Auslesen der Longwerte in einem Bytefeld wären durch API-Gebrauch eventuell schneller. Allerdings nehmen sie nur einen kleinen Bruchteil der gesamten Verarbeitungszeit ein, wodurch diese Optimierung nur bedingt sinnvoll ist.
In der Einleitung habe ich geschrieben, VB sei zu langsam, als dass diese Implementierung praktisch einsetzbar sei. In der Tat wäre es gerade bei solchen und ähnlichen Algorithmen sinnvoll, eine in C++ oder Assembler geschriebene Bibliothek zu verwenden. Trotzdem musste ich meinen persönlichen Ersteindruck revidieren und muss meine Aussage korrigieren: Mit wenigen Handgriffen (namentlich: dem Eingliedern der drei Klassen in eine einzige) lässt sich der Code noch einmal erheblich bei der Decodierung beschleunigen. Als kompilierter Code ist diese Klasse tatsächlich schnell genug für den Einsatz in der Praxis - vorausgesetzt, die Eingabe ist nicht allzu groß. Man darf freilich keinen Erfolg im direkten Vergleich mit ASM erwarten, aber für kleinere Aufgaben ist der Code vollauf ausreichend. Reines VB, ohne API.
Einige Daten
Der Huffman-Code ergibt sehr unterschiedliche Ergebnisse, je nachdem, wie die Eingabe aussieht. Das beste Ergebnis wird bei Textdateien erzielt, welche viele mögliche Zeichen nicht verwenden. Bei Binärdateien ergeben sich teilweise sehr schlechte Ergebnisse: eine 9,2 MB große Datei habe ich gerade einmal auf 9 MB reduzieren können. Eine 5MB-Textdatei hingegen konnte auf knapp unter 3 MB komprimiert werden.
Die Geschwindigkeit in kompilierter Form lässt sich wirklich sehen: für eine 10 MB große Datei braucht der Algorithmus auf meinem PC etwas weniger als 10 Sekunden. Fürs Dekomprimieren kann man noch einmal rund ein Fünftel abziehen. Dies alles bei einer CPU-Taktung von 1,1 GHz mit 512 MB RAM.
Für eine wirklich gute Kompression werden in der Praxis mehrere Verfahren verbunden. An dieser Stelle sei auf Kompression mit LZSS [Tutorial 4002] und Kompressionsverfahren [Tutorial 4007] (LZW) hingewiesen.
Beispiel herunterladen
Es können zwei VB-Implementierungen heruntergeladen werden: das erste Projekt enthält die vollständige Umsetzung des obigen Codes mit einem kleinen Beispiel. Bei dem zweiten Code handelt es sich um ein Dll-Projekt, das eine in bestimmten Bereichen optimierte Form des Codes verwendet, ebenfalls mit Beispiel.
Der dritte Download enthält eine Implementierung als C++-Dll. Das Archiv enthält das C++-Projekt, die kompilierte Dll und eine VB-Klasse, welche die Dll kapselt.
Code-Implementierung aus dem Tutorial
Ihre Meinung
Falls Sie Fragen zu diesem Tutorial haben oder Ihre Erfahrung mit anderen Nutzern austauschen möchten, dann teilen Sie uns diese bitte in einem der unten vorhandenen Themen oder über einen neuen Beitrag mit. Hierzu können sie einfach einen Beitrag in einem zum Thema passenden Forum anlegen, welcher automatisch mit dieser Seite verknüpft wird.