System- und Benutzerdokumentation

zum Projekt ”Packer“ SS 97

Geschrieben von Peter Langer und Thorsten Mazath

Bei Fehlern bitte E-mail an : tmazath@wmcip4.math.uni-wuppertal.de Aktuelle Edition vom 1. September 1998

Inhaltsverzeichnis

1 Vorbemerkungen 3

2 Systemdokumentation 4

2.1 Verwendete Kompressionsalgorithmen . . . . . . . . . . . . . . . . . . 4 2.1.1 Der prinzipielle LZW-Algorithmus . . . . . . . . . . . . . . . . 4 2.1.2 Erweiterungen zum LZW-Algorithmus . . . . . . . . . . . . . 6 2.1.3 Die Huffman-Codierung . . . . . . . . . . . . . . . . . . . . . 13 2.1.4 Lauflängen-Codierung . . . . . . . . . . . . . . . . . . . . . . 15

2.2 Konkrete Implementierung . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2.1 Aufbau und Modularisierung . . . . . . . . . . . . . . . . . . . 16 2.2.2 Implementierung der Unit ”LZW“ . . . . . . . . . . . . . . . . . 17 2.2.3 Implementierung der Unit ”Huff“ . . . . . . . . . . . . . . . . 23 2.2.4 Implementierung der Unit ”Lauf“ . . . . . . . . . . . . . . . . 28 2.2.5 Elementare I/O-Behandlung und Hauptprogramm . . . . . . . 31 2.2.6 Entwicklungsstadien und Historie . . . . . . . . . . . . . . . . 33 2.2.7 Anmerkungen zur Portabilität . . . . . . . . . . . . . . . . . . 34

3 Benutzerdokumentation 36

3.1 Die Anwendung des Programmes . . . . . . . . . . . . . . . . . . . . 36 3.1.1 Hard- und Softwarevoraussetzungen . . . . . . . . . . . . . . . 36 3.1.2 Installation des Programmes . . . . . . . . . . . . . . . . . . . 36 3.1.3 Der Aufruf des Programmes . . . . . . . . . . . . . . . . . . . 36 3.1.4 Optionen, Parameter und Programmablauf . . . . . . . . . . . 37 3.1.5 Mögliche Fehler und Probleme . . . . . . . . . . . . . . . . . . 38

3.2 Effizienz der Kompressionsalgorithmen . . . . . . . . . . . . . . . . . 38 3.2.1 Speicherplatzbedarf . . . . . . . . . . . . . . . . . . . . . . . . 38 3.2.2 Laufzeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.2.3 Festplatten- bzw. Diskettenbedarf . . . . . . . . . . . . . . . . 39

3.3 Erreichte Kompressionsraten . . . . . . . . . . . . . . . . . . . . . . . 39 3.3.1 Allgemeine Bemerkung . . . . . . . . . . . . . . . . . . . . . . 39 3.3.2 Einige konkrete Beispiele . . . . . . . . . . . . . . . . . . . . . 39

1 Vorbemerkungen

Sinn und Zweck des vorliegenden Programmes ist es, Binär- und Textdateien zu komprimieren bzw. zu dekomprimieren. Das Programm, das als Shell-Kommando unter DOS ausgelegt ist, soll dazu in der Lage sein, vom Benutzer angegebene Optionen bezüglich Kompressionsart, Kompressionsgüte und zu benutzenden Algorithmus korrekt zu verarbeiten. Natürlich kann das im Rahmen des Programmierpraktikums entstandene Projekt in keinster Weise mit gängigen Produkten, wie etwa lharc, zoo, zip, o.ä konkurrieren. Dafür sind die erreichten Kompressionsraten und vor allem die Ablaufgeschwindigkeit des Programmes nicht hoch genug. Dennoch sind die erzielten Ergebnisse in Anbetracht der vergleichsweise bescheidenen Mittel relativ beachtlich, wie man in den entsprechenden Kapiteln der vorliegenden Dokumentation nachlesen kann. Hier zunächst die ”Eckdaten“ des Programmierprojektes

• Autoren :

Peter Langer und Thorsten Mazath

• verwendete Programmiersprache :

     Borland-Pascal V7.0 für Windows 3.11/95

• getestete Konfiguration :

     Pentium 133 MHZ, 16 MB RAM, Windows 95

• verwendete Plattform :

DOS, d.h. das Programm ist ein Shell-Kommando (siehe Benutzer-Dokumentation)

• Portabilität :

nur bedingt (s.u.)

• verwendete Kompressionsalgorithmen : modifizierte LZW-, Huffman- und Lauflängencodierung

Leider ließen sich Abstriche in puncto Portabilität nicht ganz vermeiden, da sich gerade die Behandlung von Dateien und die hierfür notwendige Robustheit des Programmes in Standard-Pascal nur äußerst unzureichend realisieren lassen. An den betreffenden Stellen im Quelltext werden - falls möglich - Hinweise zur Portabilität gemacht. Die Grundformen der im vorliegenden Projekt zum Einsatz kommenden Kompressionsalgorithmen sind in der Informatik-Literatur gemeinhin bekannt und lassen sich in diversen Lehrbüchern, Zeitschriften, Web-Pages etc. nachlesen. Es sei an dieser Stelle nur auf die angegebene Literatur-Liste hingewiesen. Dennoch werden diese Algorithmen hier im folgenden erläutert und beschrieben, da sie nicht in ihrer ”reinen“ Form verwendet werden, sondern an einigen Stellen relativ stark modifiziert werden, um den speziellen Gegebenheiten besser angepasst zu sein.

2 Systemdokumentation

2.1 Verwendete Kompressionsalgorithmen

2.1.1 Der prinzipielle LZW-Algorithmus

Kompression: Der LZW-Algorithmus (benannt nach seinen Efindern Lempel, Ziv und Welch) ist besonders gut für die Kompression von Text-Dateien (ASCII-Files, Word-Dokumente, etc.) geeignet. Dies liegt vor allem daran, daß bei der Konzeption des Verfahrens davon ausgegangen wurde, daß die in einer Datei vorkommenden Codes nicht stochastisch unabhängig voneinander auftreten, was ja gerade bei Text-Dateien der Fall ist. So folgt z.B. nach einem ”q“ fast immer ein ”u“, und auch andere Buchstaben-Kombinationen, wie etwa ”sch“, ”er“, ”st“ usw. kommen sehr häufig vor. Genau an dieser Stelle setzt auch der LZW-Algorithmus an : Die prinzipielle Idee besteht darin, anstelle des ASCII-Codes, der ja einen Zeichenvorrat von 256 ”Buchstaben“ (codiert durch 1 Byte = 8 Bit) hat, ein erweitertes ”Alphabet“ zu verwenden, bei dem man jedes Zeichen z.B. mit 11 Bit codiert. Dann stünden statt bisher 256 Zeichen 2^{11} = 2048 Codes zu Verfügung. Den größeren Vorrat an Zeichen erkauft man sich zwar mit einem erhöhten Speicherplatzbedarf pro Code, doch insgesamt erreicht man dadurch in den meisten Fällen einen guten Kompressionseffekt, da ja ein Code im ”neuen“ Alphabet eine u.U. sehr lange Zeichenkette repräsentieren kann. Was das bedeutet, soll hier an Hand eines konkreten Beispiels erläutert werden. Wir betrachten folgende Zeichenkette :

 Wieder diese Kinder

Zunächst wird eine leere Zeichenkette Ω initialisiert. Das ausführende Programm liest dann zuerst den Buchstaben ”W“ ein und stellt fest, daß dieser Code schon im bisherigen ASCII-Alphabet vorhanden ist. Deshalb ”merkt“ sich der Algorithmus den Buchstaben in Ω, liest das nachfolgende Zeichen ”i“ ein und hängt es an die Zeichenkette Ω an. Der Algorithmus stellt nun fest, daß der Inhalt von Ω, die Zeichenkette ”Wi“, noch nicht Bestandteil des Alphabets ist und speichert sie deshalb unter der Codenummer 256 ab (Die Positionen 0 … 255 des Alphabets sind ja bereits durch die Standard-ASCII-Codes belegt). Außerdem schreibt der Kompressor das erste Zeichen von Ω ”W“ in die Ausgabedatei und initialisiert Ω mit ”i“. Als nächstes Zeichen wird ”e“ eingelesen und an Ω angehängt; das Programm erkennt, daß ”ie“ noch nicht Bestandteil des Alphabets ist, weist dieser Zeichenkette daher den nächsten ”freien“ Tabelleneintrag 257 zu und schreibt den Code für ”i“ in die Ausgabedatei. Dieses Vorgehen setzt sich nun fort. Auf die gerade beschriebene Art baut sich der Kompressor sein erweitertes Alphabet solange auf, bis die Tabelle voll ist, d.h. bis auch der Code-Nummer 2047 eine Zeichenkette zugewiesen worden ist. Sobald dies der Fall ist, wird das ”Alphabet“ nicht mehr aufgefüllt. Statt dessen werden nur noch die bereits ermittelten Einträge zur Codierung herangezogen. Nach Bearbeiten unseres Beispiels sieht die Codetabelle folgendermaßen aus:

256 257 258 259 260 261 262 263 264 265 266 267 268 269
wi ie ed de er r__d di ies se e__K Ki in
270 271
nd der

Wie man also sieht, benutzt der LZW-Algorithmus recht einfache Methoden zur Kompression.

Dekompression: Bei der Dekomprimierung einer mit dem LZW ”gepackten“ Datei geht man folgendermaßen vor : Zunächst muß auch der Dekompressor erst das erweiterte Alphabet Schritt für Schritt aufbauen. Erstaunlich hierbei ist aber, daß hierfür das während des Kompressionsvorgangs aufgebaute ”Alphabet“ nicht bekannt sein muß. Der Dekompressor entnimmt also alle benötigten Informationen, um die Ursprungsdatei wieder originalgetreu herzustellen, dem ”gepackten“ File. Dies erfolgt im einzelnen folgendermaßen: Der Entpacker startet - genau wie der Kompressor - mit einem Alphabet, bei dem die ersten 256 Positionen (0 … 255) mit dem Standard-ASCII-Code vorbelegt sind. Dann liest er das 1. Zeichen der gepackten Datei ein und schreibt es wieder unverändert in die Ausgabedatei. Anschließend liest er das 2. Zeichen ein, hängt es an das 1. Zeichen an und weist die so sentstandene Zeichenkette der Tabellenposition 256 zu. Danach wird auch das 2. Zeichen in die Ausgabedatei geschickt. Für jedes nachfolgende Zeichen führt der Dekompressor folgende Schritte ddurch :

• Falls der eingelesene Code kleiner als 256 ist - d.h. wenn also ein ASCII-Code vorliegt - wird der Code unverändert in die Ausgabedatei geschrieben. Andernfalls ”schaut“ der Dekompressor unter der angegebenen Nummer in der bisher ermittelten Tabelle nach und schreibt die dort gespeicherte Zeichenkette in die Ausgabedatei.

• Solange die Code-Tabelle nicht ”voll“ ist, modifiziert der Dekompressor nach jedem empfangenen Symbol sein eigenes erweitertes Alphabet. Dabei bildet er aus der letzten bereits dekodierten Zeichenkette und dem ersten entschlüsselten Zeichen der gerade zu bearbeitenden Zeichenkette einen neuen Eintrag für die Code-Tafel.

Wichtig: Es kann während des Dekompressionsvorgang eine Ausnahmesituation auftreten, und zwar genau dann, wenn das Programm einen Code empfängt, der noch nicht in der Code-Tabelle enthalten ist. Dies ist z.B. dann der Fall, wenn der Kompressor eine Zeichenkette der Form ”SabcSabcS“ bearbeiten soll und die Zeichenkette ”Sabc“ bereits Bestandteil des Alphabets ist. Dann schreibt er den Code für ”Sabc“ in die Ausgabedatei und fügt die Zeichenkette ”SabcS“ als neues Zeichen in die Codetabelle ein. Anschließend liest der Kompressor weiter aus der Eingabedatei und findet als nächsten bekannten String die Zeichenkette ”SabcS“ und schickt den zugehörigen Code in die Ausgabedatei. Diese Zeichenkette ist zu diesem Zeitpunkt aber noch nicht im Alphabet des Dekompressors enthalten, so daß dieser den empfangenen Code nicht unmittelbar dekodieren kann. Da dieser Ausnahmefall nur bei Zeichenketten der oben beschriebenen Form auftritt, kann man das Problem durch eine relativ einfache Extrabehandlung lösen.

2.1.2 Erweiterungen zum LZW-Algorithmus

In diesem Abschnitt soll aufgezeigt werden, wie im Projekt das oben vorgestellte Verfahren modifiziert wird, um es - zumindest einigermaßen - effizient implementieren zu können.. Diese Verbesserungen werden schrittweise erläutert und enstprechen dem Prozeß der ”Verfeinerung“ bei der Implementierung des LZW-Algorithmus, wie man den beigefügten Programmlistings LZW1.pas,…,LZW5.pas entnehmen kann. Wenn man ”naiv“ gemäß dem in 2.1 beschriebenen elementaren LZW-Algorithmus programmiert, nimmt man folgende Nachteile bzw. Probleme in Kauf:

• Hauptnachteil des oben beschriebenen Algorithmus ist, daß - ohne weitere Zusatzüberlegungen - stets sequentiell in der Code-Tabelle nach Zeichenketten, die bereits Bestandteil des Alphabets sind, gesucht wird. Da aber die sequentielle Suche in Datenbeständen i.a. sehr ineffektiv ist, wirkt sich diese negativ auf die Ablaufgeschwindigkeit des Programmes aus. Ein verbessertes Verfahren müßte also einen sehr schnellen, effizienten Zugriff auf die Tabelle ermöglichen.

• Weiterhin ist bisher noch nicht von der speziellen Struktur der Tabelleneinträge Gebrauch gemacht worden. Zwei ”aufeinanderfolgende“ Einträge im Alphabet unterscheiden sich nur um einen ASCII-Code. Es wäre also sehr ungeschickt, für jeden Tabelleneintrag die zugehörige Zeichenkette explizit abzuspeichern, wie es ja der obige Algorithmus nahelegt. Ein verbesserter LZW-Algorithmus müßte also diese spezielle Gegebenheit berücksichtigen, was dazu beitragen würde, daß das Verfahren weitaus weniger speicherintensiv wäre.

• Bislang gehen wir nur von einem 11-Bit-Alphabet aus. Natürlich ist es auch möglich (und zumeist auch sehr sinnvoll !), ein Alphabet zu verwenden, bei dem die Codelänge 12 Bit beträgt. Ebensogut kann aber in manchen Fällen auch eine Codelänge von 9 Bit angebracht sein. Für welche Zahl man sich nun entscheidet, hängt letztendlich besonders davon ab, welche Länge die zu komprimierende Datei hat. So ist es bei vergleichsweise kurzen Dateien eher angebracht, mit einer Code-Länge von 9 oder 10 Bit zu arbeiten, da ansonsten in ungüngstigen Fällen der Kompressionseffekt gar nicht zum Tragen käme (Das wäre z.B. dann der Fall, wenn die Code-Tabelle bei Datei-Ende noch gar nicht vollständig aufgefüllt ist). Andersherum gilt für große Dateien, daß ein Alphabet mit ausreichend vielen Zeichen vorteilhaft ist. Natürlich stellt sich nun die Frage, was ”groß“ bzw. ”klein“ in der jeweiligen Situation heißt. Da dies aber nur sehr schwierig zu entscheiden ist, wäre es noch vorteilhafter, wenn der Packer nicht a priori die Codelänge festlegt, sondern z.B. mit einem 9 Bit-Alphabet startet und dann während des Kompressionsvorgangs flexibel entscheidet, ob das Alphabet noch zusätzlich erweitert werden soll. Dies entspräche dann einem adaptiven LZW-Algorithmus. Dieser Kritikpunkt wird allerdings im vorliegendem Programmierprojekt nicht behoben.

• Das letzte zu erwähnende Problem ist technischer Natur und liegt darin begründet, daß Pascal keine adequaten 11-Bit-Codes bereitstellt. Wenn man z.B. statisch mit einem 11-Bit-Alphabet arbeitet, stellt sich die Frage, wie man die einzelnen Codes des erweiterten Alphabets in die Ausgabedatei schreibt. Wenn man in ein ”File of Integer“ schreibt, verliert man bei ”naiver“ Programmierung - ohne geeignete Zusatzüberlegung - pro Zeichen 5 Bit! D.h. man würde auf diese Weise den gewünschten Kompressionseffekt wieder zunichte machen! Deshalb muß man die einzelnen Codes mit Hilfe eines geeigneten Algorithmus ”zerhacken“, geeignet ”shiften“ und dann in Byte-Gruppen wieder ”aneinanderstückeln“.

Behebung der ersten beiden Kritikpunkte: Den oben geforderten effizienten ”Table-Lookup“ erreicht man mit Hilfe eines geeigneten Hash-Algorithmus. D.h. man speichert die Tabelleneinträge nicht mehr wie bisher sequentiell, sondern legt den jeweiligen Alphabetcode an der von der Hash-Funktion ermittelten Tabellenposition ab. Um dies bewerkstelligen zu können, ändert man auch - wie oben gefordert - die Speicherung von Zeichenketten. Hier kommt nun - wie angekündigt - die spezielle Struktur der Tabelleneinträge zum Zug. Ein Tabelleneintrag - d.h. ein ”Zeichen“ des Alphabets - wird nun durch einen Record der folgenden Bauweise dargestellt:

Suffix  Pred

Erklärung:

• Das Datenfeld Suffix (Anhängsel) beinhaltet stets einen ASCII-Code • Die Record-Komponente Pred (Vorgänger) beinhaltet einen Pointer auf das

vorherige Zeichen einer eingelesenen Zeichenfolge sowie einen Statusindikator, der folgende Werte annehmen kann :

a ) HasPred wird angenommen, wenn das in Suffix gespeicherte Zeichen einen Vorgänger hat.

b ) NoPred wird angenommen, falls kein Vorgänger existiert, also falls es sich bei dem Tabelleneintrag um einen ASCII-Code handelt.

c ) ImPred sperrt einzelne Einträge, die eine andere, spezielle Bedeutung haben.

d ) Free signalisiert, daß diese Tabellenposition noch frei ist.

Beschreibung des modifizierten LZW-Algorithmus Wir gehen hier von einer 12-Bit-Codierung aus, d.h. die Codetafel umfaßt 4096 Einträge. Wie üblich werden zunächst die ersten 256 Positionen der Tabelle mit dem Standard-ASCII-Code initialisiert. Die Record-Komponente Pred dieser Einträge wird jeweils mit dem Indikator NoPred vorbelegt, alle anderen Pred-Komponenten der Tabelle (d.h. die Positionen 256 … 4095) werden auf Free gesetzt. Als Hilfsvariable wird noch ein Hilfsindex eingeführt, der die selbe Bauweise wie die Record-Komponente Pred hat und mit NoPred belegt wird.

Kompression: Nach diesen vorbereitenden Arbeiten startet nun der modifizierte LZW-Algorithmus: Der Algorithmus liest ein Zeichen der Ursprungsdatei ein und prüft, ob es schon in der Tabelle enthalten ist. Wichtig ist, daß bei einem gefundenem Element auch dessen Pred-Komponente mit der des Hilfsindizes übereinstimmt. War die Suche erfolgreich, so wird die Position, an welcher der Code gefunden wurde im Hilfsindex gespeichert und mit dem Einlesen des nächsten Zeichens fortgefahren. Falls die Suche nicht erfolgreich war, bedeutet das ja, daß die Tabelle noch keine entsprechende Zeichenkette enthält und erweitert werden muß. Der Kompressor schreibt also erst einmal den Wert von Hilfsindex in die Ausgabedatei. Danach wird in der Tabelle ein freier Eintrag (d.h. Statusindikator hat den Wert Free) ermittelt, in dessen Record-Komponente Suffix das Zeichen gespeichert wird und dessen Komponente Pred auf dem in Hilfsindex vermerkten Vorgänger verweist (daher auch die Bezeichnung Pred für Predecessor). Anschließend initialisiert man den Hilfsindex wieder mit NoPred und verzweigt wieder zur Suche, wobei die zuletzt gefundene Zeichenkette als Ausgangssituation dient für die nächste zu lernende Zeichenfolge.

Pseudocode des Kompressions-Algorithmus:

        Initialisieren der Tabelle
        Hilfsindex := NoPred
Schleife1: Lies ein Zeichen ein
Schleife2: Suche in Tabelle das eingelesene Zeichen,
        wobei Pred=Hilfsindex erfüllt sein muss
        If gefunden
           Merke gefundene Position in Hilfsindex
           Goto Schleife1
        Hilfsindex als zu speichernden Code ausgeben
        Neues Zeichen in Tabelle aufnehmen, Pred auf
        Hilfsindex setzen
        Hilfsindex := NoPred
        Goto Schleife2

Beschreibung des Hash-Algorithmus Wie bereits oben angedeutet, wird die effiziente Suche in der Tabelle durch einen Hash-Algorithmus erreicht. Die entsprechende Hash-Funktion ist bei einer Tabellengröße von 4096 Einträgen, d.h. bei einer zugrundegelegten Codelänge von 12 Bit, folgendermaßen aufgebaut :

• Quadriere die Summe aus Pred und Suffix Fasse die mittleren 12 Bit des Ergebnisses als den Index auf

• Bei einer Kollision muß man einen Ausweicheintrag ermitteln. Diesen erhält man, indem man auf das Ergebnis des oben erläuterten Rechenschrittes die Primzahl 101 addiert und an der entsprechenden Stelle der Tabelle nachsieht, ob der betreffende Eintrag frei ist. Sollte dies nicht der Fall sein, so wiederholt man dieses Vorgehen solange, bis man auf einen ”freien“ Eintrag stößt. Bei Überschreitung des Tabellenendes fängt man wieder bei 0 an.

• Damit die so ermittelten Ausweicheinträge auch wiedergefunden werden können, muß zusätzlich ein sog. Link-Pointer eingeführt werden, der auf den Ausweich-2 SYSTEMDOKUMENTATION 10

eintrag referiert. Da u.U. meherere Kollisionen unter dem selben Eintrag auftreten können, verkettet man sinnvollerweise alle Elemente, zu denen die Hash-Funktion das gleiche Resultat liefert, durch eine einfach verkettete lineare Liste.

   Pseudocode zu "Einfügen eines neuen Elementes"
              Berechnen der zu (Pred, Suffix) gehörenden
              Adresse mittels Hash-Funktion
   Schleife1: If Tabelle[Adresse].Pred<>Free
                 If Tabelle[Adresse].Link<>Free
                    Adresse := Tabelle[Adresse].Link
                    Goto Schleife1
              Alte_Adresse := Adresse
              Erhöhe Adresse um 101
              While Tabelle[Adresse].Pred<>Free
                    Erhöhe Adresse um 101
              Tabelle[Alte_Adresse].Link := Adresse
              Tabelle[Adresse] := (Pred, Suffix)
              Tabelle[Adresse].Link := Free

Behebung des dritten Kritikpunktes siehe weiter unten ! Behebung des letzten Kritikpunktes Wie bereits oben erläutert, muß noch eine Lösung für das Abspeichern des komprimierten Codes auf der Festplatte bzw. Diskette gefunden werden. Bei Implementierung in Pascal liefert der LZW als Output pro Alphabet-Code Integer-Zahlen (also einen 16-Bit-Code), obwohl es sich ja in Wirklichkeit um nur um 11-Bit- respektive 12-Bit-Codes handelt. Die Lösung für dieses Problem läßt sich relativ gut illustrieren (s.u.):

Man faßt den Output vom LZW-Algorithmus als Bit-Sequenz Code^{∗} auf, d.h. man fügt direkt hinter die ersten 11 Bit die 11 Bit des 2. Codes an usw. Man erhält also - als Datenstruktur - ein Queue of Bits. Was nun folgt, ist einleuchtend : Da Pascal nur 8-Bit- bzw. 16-Bit-Datentypen zur Verfügung stellt, entfernt man nun die Bits - je nach Implementierung - in 8er bzw. 16er Grupen aus diese Warteschlange, was dann zu der Bildung von Sequenzen Byte^{∗} bzw. Integer^{∗} führt. In der Pascal-Terminologie entsprechen diese Sequenzen dann selbstverständlich einem File of Byte bzw. einem File of Integer. Bis jetzt wurden der LZW-Algorithmus und der gerade beschriebene Algorithmus zur kompakten Speicherung bewußt getrennt betrachtet, da so die Beschreibung der Algorithmen und somit die Dokumentation übersichtlicher werden. Bei der tatsächlichen Implementierung (siehe Kapitel 2.3 und 2.4) werden diese Prozesse selbstverständlich nicht mehr entkoppelt voneinander, sondern ”in einem Abwasch“ ausgeführt. Folgende Graphik veranschaulicht zunächst noch einmal den bisherigen theoretischen Standpunkt, der - wie gerade erläutert - von einem preprocessing durch den LZW-Algorithmus mit anschließender Nachbearbeitung gemäß soeben erläuterter Methode ausgeht :

Als Beispiel soll das Resultat, das nach Anwenden des LZW auf die Zeichenkette

                      Ω = "wieder diese kinder"

entstanden ist - nämlich die Sequenz

Code^{∗} = {119; 105; 101; 100; 101; 114; 32; 100; 257; 115; 101; 32; 75; 105; 110; 259; 114}

- dienen :

1.Byte  2.Byte  3.Byte
14  225  164
0 0 0 0 1 1 1 0 1 1 1 0 0 0 0 1 1 0 1 0 0 1 0 0
119  105  ↘
1.Code  2.Code  ↘
4.Byte  5.Byte  6.Byte
50  134  64
0 0 1 1 0 0 1 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0
101  100  ↘
3.Code  4.Code  ↘

7.Byte  8.Byte  9.Byte
202  28  129
1 1 0 0 1 0 1 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 1
101  114  32
5.Code  6.Code  7.Code
10.Byte  11.Byte  12.Byte
0  100  32
0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0
↪  100  257
↪  8.Code  9.Code
13.Byte  14.Byte  15.Byte
33  204  50
0 0 1 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 0
↪  115  101
↪  10.Code  11.Code
16.Byte  17.Byte  18.Byte
2  0  150
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0
32  75
12.Code  13.Code
19.Byte  20.Byte  21.Byte
26  67  113
0 0 0 1 1 0 1 0 0 1 0 0 0 0 1 1 0 1 1 1 0 0 0 1
105  110  ↘
14.Code  15.Code  ↘
22.Byte  23.Byte  24.Byte
3  14  64
0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0
259  114
16.Code  17.Code

Dieser Graphik kann man nun sofort die resultierende Byte-Sequenz entnehmen, indem man die einzelnen Werte in der jeweiligen 2. Zeile abliest.

2.1.3 Die Huffman-Codierung

Allgemeines: Die Grundidee des Huffman-Algorithmus ist, häufiger vorkommende Zeichen in einem Text durch weniger und seltener vorkommende Zeichen durch mehrere Bits zu ersetzen. Zu diesem Zweck wird die Datei zuerst einmal komplett durchgesehen und dabei Anzahl jedes Zeichens festgestellt. Kennt man jetzt von jedem Zeichen die Häufigkeit, so wird diese Kenntniss in einer Häufigkeits-Tabelle festgehalten. Im nächsten Schritt wird nun der sog. Huffman-Baum aufgebaut. In den Blättern stehen jeweils die einzelnen Zeichen und deren Häufigkeit. Nun sucht der Algorithmus die beiden Zeichen, die am seltensten vorkommen, und verbindet beide durch einen gemeinsamen Knoten. Der alte linke Knoten bekommt den Code ”0“ und der rechte den Code ”1“. In dem neuen Knoten steht die Summe der Häufigkeit der beiden Zeichen. Durch diesen Schritt ist also die Anzahl der zu betrachtenden Elemente um eins gesunken. Diese Schritte werden wiederholt, bis am Ende nur noch ein Element, die Wurzel, übrigbleibt. Hat man nun den Baum aufgebaut, kann man mit dem Komprimieren bzw. Dekomprimieren beginnen.

Komprimieren: Man beginnt in dem Blatt, welches das zu kodierende Zeichen enthält. Nun geht man von diesem Blatt aus bis zur Wurzel und ”merkt“ sich dabei jeweils den Code jedes einzelnen Knotens. Diese Folge von Nullen und Einsen muß nur noch umgedreht werden und man hat den Code des Zeichens. Dieser Code wird nun in die komprimierte Datei geschrieben. Damit man hinterher diese Datei auch wieder entpacken kann, muß die Häufigkeits-Tabelle auch noch in der komprimierten Datei abgespeichert werden.

Dekomprimieren: Bei der Dekomprimierung wird zunächst die Häufigkeits-Tabelle aus der Datei gelesen und mit ihr der Huffman-Baum aufgebaut. Man beginnt in der Wurzel und liest das folgende Zeichen aus der komprimierten Datei. Entsprechend seinem Wert verzweigt man nun nach links oder rechts. Gelangt man so in einen Knoten, von dem es keinen linken und rechten Zweig gibt, weiß man, daß man das entsprechende Zeichen gefunden hat und schreibt es in die neue Datei.

Beispiel: Beispieltext: Schubidubidu Häufigkeit:

u b d i S c h
3 2 2 2 1 1 1

Hieraus ergibt sich der in Abb. 1 gezeigte Baum.

Abbildung 1: Huffman-Baum

[figure: 0; 1; h; c; S; i; d; b; u; 3; 1; 2; 2; 2; 1; 1; 2; 3; 4; 5; 7; 12]

Und daraus die Codetabelle

u b d i S c h
%11 %101 %100 %011 %010 %001 %000

Am Ende wurden aus 12 Buchstaben (96 Bit) folgende Bitfolge:

%0100010001110101110001110101110011 (34 Bit)

Stärken und Schwächen: Eine Stärke des Huffman-Algorithmus ist, daß er unabhängig vom Typ der zu komprimierenden Datei ist, d.h. es komprimiert sowohl ASCII- als auch Binärdateien relativ gut. Zu den größten Schwächen des Algorithmus zählt sicherlich, daß die Häufigkeits-Tabelle in der Datei abgespeichert werden muß. Aus diesem Grund wird die Komprimierung erst bei Dateien ab einer Länge von ca. 5 Kb effektiv. Bei kürzeren Dateien kann die komprimierte Datei sogar länger als die Originaldatei sein. Ein weiterer Nachteil ist, daß nur einzelne Zeichen einen Code erhalten und nicht, wie beim LZW-Algorithmus, Zeichenketten kodiert werden.

2.1.4 Lauflängen-Codierung

Allgemeines: Die Lauflängenkodierung ist ein sehr einfaches, nicht besonders effizientes, dafür aber sehr schnelles, Verfahren Dateien zu komprimieren. Die Idee dieses Verfahrens ist es, Zeichen, die mehrmals hintereinander vorkommen, nur einmal zusammen mit einem Zähler zu kodieren. Da auch der Zähler Platz kostet, bleiben zwei- oder dreimal vorkommende Zeichen uncodiert. Wie man sofort erkennt, ist dieses Verfahren weniger für reine Textdateien geeignet, da sehr selten vier gleiche Zeichen hintereinander vorkommen. Bei Grafikdateien, insbesondere Bitmaps, ist dieses Verfahren jedoch oft recht wirksam. Strukturlose Flächen werden somit oft durch wenige Bytes ersetzt. Bei dem Verfahren, das ich anwende, werden mehrfach vorkommende Bytes durch drei Bytes ersetzt: das urspüngliche Byte, $90 und ein Zähler. $90 bedeutet in diesem Fall, daß ein Zähler für das ursprüngliche Byte folgt. Weiterhin ist eine besondere Kodierung für das Zeichen $90 erforderlich. Dieses wird mit $90 $00 kodiert. Die Zeichenfolge kann sonst in keinem Fall auftreten, da der Zähler niemals null sein kann.

Beispiel: Folgende Tabelle verdeutlich an Hand eines konkreten Beispiels, wie die Kodierung vonstatten geht:

Zeichenfolge: a b b b b c c c d d d d e $90 ˆ= 14Byte
Kodiert: a  b $90 4  c c c  d $90 4  e $90 $00 ˆ= 12Byte

2.2 Konkrete Implementierung

2.2.1 Aufbau und Modularisierung

Wie bereits in der Einleitung erwähnt, soll das vorliegende Projekt als Shell-Kommando Verwendung finden. Dabei soll es mehrere vom Benutzer wählbare Optionen geben, wie etwa

• Run : Die Datei wird mittels Lauflängen-Codierung gepackt.

• Squeeze : Die zu komprimierende Datei wird erst mittels Run-Length-Encoding vorbearbeitet und danach mit dem Huffman-Algorithmus komprimiert

• Crunch : Die zu komprimierende Datei wird mit dem LZW-Algorithmus ”gepackt“.

Siehe hierzu auch Kapitel 3 der vorliegenden Dokumentation. Dies legt prinzipiell folgende Modularisierung des Projektes nahe:

Hauptprogramm:

• globale Steuerung des Programmablaufs Hierunter ist z.B. die Auswertung der vom Benutzer via Shell übergebenen Parameter und die entsprechende Weiterleitung an die entsprechenden Subroutinen der jeweiligen Unit zu verstehen.

• elementare I/O-Behandlung Hiermit ist z.B. gemeint, daß das Programm im Fall eines Fehlers (z.B. Datei nicht gefunden) angemessen reagiert und die entsprechende Fehlermeldung ausgibt.

Units :

• Lzw (Routinen für Kompression/Dekompression nach LZW)

• Huff (Routinen für Huffman-Codierung)

• Lauf (Prozeduren für Lauflängencodierung)

2.2.2 Implementierung der Unit ”LZW“

Allgemeines: Die Kompressions- und Dekompressionsalgorithmen wurden als Turbo-Pascal-Unit implementiert. Intern wird noch auf die Unit IntQueue zugegriffen, die die Datenkapsel fuer a priori unbeschränkte Warteschlangen von integer-Werten zur Verfügung stellt. Wenn der Anwender die Unit lzw.tpu einbindet, kann er auf einer der beiden öffentlichen im folgenden beschriebenen Prozeduren zugreifen:

Dem Benutzer zugängliche öffentliche Funktionen

function LzwPack(name : string; var ratio : real;
                               var errmsg : string) : boolean;

Diese Funktion komprimiert die unter dem angegebenen Dateinamen abgespeicherte Datei mit Hilfe des LZW-Algorithmus und speichert die komprimierte Datei ab. Sie erhält die Endung .lzw. Wenn kein Fehler aufgetreten ist, liefert die Funktion als Rückgabewert true zurück. Außerdem kann man sich durch den var-Parameter ratio über die erreichte Kompressionsrate informieren. Anderenfalls wird false zurückgegeben und der Benutzer kann mittels des Var-Parameters errmsg Aufschluß über die Art des Fehlers erlangen.

function LzwUnPack(name : string; var ext : string;
                                 var errmsg : string) : boolean;

Diese Funktion dekomprimiert die unter dem angegebenen Dateinamen abgespeicherte Datei mit Hilfe des LZW-Algorithmus. Voraussetzung ist allerdings, daß der übergebene Dateiname die Endung .lzw hat. Verlief der Algorithmus erfolgreich, so liefert die Funktion als Resultat den Bool-Wert true zurück und die entpackte Datei wird unter ihrem ursprünglichen Namen gespeichert. Die Endung des Namens der wiederhergestellten Datei wird durch den var-Parameter ext dem Anwender zugänglich gemacht. Trat während des Dekompressions-Vorganges ein Fehler auf, so wird false zurückgegeben. In diesem Fall kann sich der Anwender durch Auslesen des Var-Parameters errmsg ueber die Art des Fehlers informieren.

Die wichtigsten Typen und Variablen In diesem Abschnitt werden die wichtigsten Typen und Variablen, die für den LZW-Algorithmus in der vorliegenen Fassung maßgeblich sind etwas näher erläutert:

• Konstanten

     const codelength = 12;

Diese Konstante gibt an, mit wieviel Bits der LZW-Algorithmus codiert. Durch evtl. Ändern dieser Konstante erreicht man eine andere Kompressionsgüte.

• Typen

type  status   = (NoPred, ImPred, Free, HasPred);
      index    = record
                  sort   : status;
                  pred   : integer;
                 end;
      entry    = record
                  suffix : byte;
                  tail   : index;
                  link   : index;
                 end;
      alphabet = array[0..4095] of entry;

Dieser Auszug aus dem Pascal-Listing zum Unit lzw.tpu demonstriert wieder einmal auf eindrucksvolle Weise, wie sich durch aufeinander folgende Typen-Definitionen quasi baukastenartig eigene Datenstrukturen definieren lassen. In Verbindung mit Kapitel 2.1.2 der Dokumentation sind die verwendeten Bezeichnungen für die Typen nahezu selbsterklärend. Der Aufzählungstyp status ist dazu gedacht, die Eigenschaft eines Tabelleneintrages bzw. eines Indizes näher zu beschreiben. Der Record index ist ein häufig gebrauchter Datentyp für Hilfszeiger bei Analyse des Alphabets. Der Record entry ist der Datentyp für einen Eintrag bzw. ein ”Zeichen“ im Alphabet. Das Array alphabet ist - logischerweise - ein Feld von solchen Einträgen.

• Variablen

Da diese im Quelltext relativ ausführlich erläutert und kommentiert sind, wird hier einfach der entsprechende Auszug aus dem Quelltext aufgeführt:

var {Hier zunaechst die Variablen, die fuer den "eigentlichen" Kompressionsvorgang}
      {benoetigt werden ...  }
      errs         : array[1..3] of string; { Array fuer die Fehlermeldungen  }
      rough        : file of byte;
      comp         : file of byte;
      elaborated   : Queue; { <---- Hier tritt die entscheidende Aenderung auf ! }

2 SYSTEMDOKUMENTATION 19

                        { Statt in eine elaborated-Datei wird der Zwischen- }
                        { code in einen elaborated-Queue geschrieben !  }
codetable    : alphabet;{ konkrete Instanz des Alphabets  }
ch           : byte;
help, found  : index;
readin       : boolean; {Boolean-Hilfsvariable. Gibt an, ob naechstes Zeichen }
                        {eingelesen werden soll  }
roughname,  {Name der "Rough"-Datei}
compname,  {Name der "Comp"-Datei, d.h. der komprimierten Datei }
path         : PathStr; {Name des Pfades  }
dir          : DirStr; {Name des Directory's  }
extension    : ExtStr; {Endung der zu komprimierenden Datei  }
e            : String; {Hilfstring, ebenfalls fuer die Endung  }
oldsize,  {Groesse der zu packenden und  }
newsize      : longint; {der komprimierten Datei  }
i,  {Zaehlvariable fuer For-Schleifen  }
counter,  {Zaehler, um zu ueberpruefen, ob Tabelle schon voll }
co           : integer; {eigelesener Code beim De-komprimieren  }

{Hier folgen nun diejenigen Variablen, die fuer diejenigen Subroutinen  }
{benoetigt werden, die urspruenglich in "encode.pas" bzw. "decode.pas"  }
{vorkamen, also die fuer das "Shiften" des Codes in das endgueltige Format  }
{zustaendig sind ...  }
Code,
partii,
Bitnum,
BytePos,
CodePos      : integer;  {aktuelle Bearbeitungsposition}
Interrupted,
Finished,
Passed,
Written,
ByteReady,
CodeReady    : boolean;  {bool'sche Hilfsvariablen}
part,
hack         : byte;  {Zu schreibendes Byte}
{-----------------------------------------------------------------------------------}

Prozeduren und Funktionen, welche die ”eigentliche Arbeit“ leisten: Hier folgen zunaechst die Unterprogramme fuer den LZW-Algorithmus:

function hash(c : byte; h : index) : integer;

Diese Funktion trägt die Hauptverantwortung dafür, daß der Zugriff auf die Tabelle, d.h das Alphabet, schnell und effektiv ist. Übergabeparameter sind ein byte, sowie ein Parameter vom Typ index (s.o). Zurückgegeben wird ein integer-Wert, der mutmaßliche Index im Feld codetable ist, unter dem ein neues ”Zeichen“ ins Alphabet aufgenommen werden kann, bzw. unter dem sich ein gesuchtes ”Zeichen“ im Alphabet befindet. Allerdings muß man ggf. auch noch Ausweichseinträge berücksichtigen, auf die mittels des record-Members link verwiesen wird. Genaueres hierzu ist ebenfalls unter Kapitel 2.1.2 nachzulesen.

function InAlphabet(c : byte; h : index; var f : index) : boolean;

Diese Funktion prüft, ob eine Zeichenkette, repräsentiert durch ein byte und einen Parameter vom Typ index (s.o), bereits Bestandteil des Alphabetes ist. Falls ja, wird der boolean-Wert true zurückgegeben. Andernfalls liefert die Funktion false zurück. Der var-Parameter f enthält im Erfolgsfall denjenigen Index, der auf den gesuchten Code zeigt. Diese Funktion macht Gebrauch von der oben erläuterten Funktion hash.

procedure AddToAlphabet(c : byte; h : index);

Diese Prozedur sorgt dafür, daß eine Zeichenkette, die durch das byte c und den index h repräsentiert wird, in das Alphabet einsortiert wird. Auch diese Prozedur greift auf die Funktion hash zurück.

procedure DisplayEntry(i : integer);

Diese Prozedur ist nur beim Dekompressionsvorgang relevant. Sie gibt rekursiv einen Code des Alphabets aus, und zwar in die rough-Datei, die ja sowohl beim Packen als auch beim Entpacken die Originaldatei repräsentiert. Der integer-Parameter i gibt an, welcher Eintrag des Feldes codetable ausgegeben werden soll.

function FirstElement(i:integer) : byte;

Diese Funktion gibt das erste byte der unter i im Array codetable gespeicherten Zeichenkette zurück.

procedure Initialize;

Streng genommen bewirkt diese Prozedur einen - allerdings verzeihbaren - Seiteneffekt! Es werden alle wichtigen Variablen initialisiert. Diese Prozedur wird auch im Initialisierungsteil der Unit lzw.tpu aufgerufen.

Unterprozeduren und Unterfunktionen von LzwPack Im wesentlichen handelt es sich hierbei um die Funktionen bzw. Prozeduren des oben schon öfter erwähnten Programmes encode.pas. Sie werden im Verlauf des Programmflusses innerhalb der Funktion LzwPack aufgerufen.

procedure GetBits(c : integer; p : integer; var s : byte);

Diese Prozedur isoliert aus dem integer-code c ab dem p-ten Bit ein byte und übergibt dieses dem var-Parameter s.

procedure PutBits(var b : byte; p : integer; s : byte);

Diese Prozedur schreibt führt eine bitweise or-Verknüpfung des Bytes b mit dem um p Bit ”geshifteten“ Byte s durch. Das Resultat dieser Bitoperation wird dem var-Parameter b übergeben.

procedure CalcHack;

Diese Prozedur koordiniert das ”Ausschneiden“ von Bits aus der Code-Sequenz und dem ”Zusammenstellen“ von Byte-Blöcken (in der Terminologie des Programmes auch ”Hack“ genannt). Innerhalb dieser Prozedur werden GetBits sowie PutBits aufgerufen.

procedure DoShift;

Auch diese Prozedur uebernimmt Koordinations- und Verwaltungsaufgaben. Anhand der Flags CodeReady bzw. ByteReady erkennt die Prozedur, ob ein Byte in die Datei geschrieben werden kann, bzw. ob ein neuer Code von der Warteschlange geholt werden kann. Innerhalb dieser Prozedur wird CalcHack aufgerufen.

Unterprozeduren und Unterfunktionen von LzwUnPack Hier gilt das gleiche wie im vorhergehenden Abschnitt. Die verwendeten Prozeduren bzw. Funktionen entstammen zum größten Teil dem Programm decode.pas.

procedure GetBits(c : byte; p : integer; var s : integer);

Diese Prozedur tut im Prinzip das gleiche wie die entsprechende Unterprozedur von LzwPack, allerdings mit dem Unterschied, daß nicht aus einem integer-Code ausgeschnitten wird, sondern aus einem byte ab der p-ten Position. Hier wird via var-Parameter ein integer-Wert zurückgegeben.

procedure PutBits(var b : integer; p : integer; s : integer);

Diese Prozedur ist ebenfalls ein Analogon zur gleichnamigen Unterprozedur von LzwPack. Auch hier erfolgt eine bitweise or-Verknüpfung, und zwar von b mit dem um p Bit ”geshifteten“ s. Das Ergebnis wird im var-Parameter b abgelegt.

procedure CalcCode;

Analogon zu CalcHack. Diese Prozedur koordiniert das ”Ausschneiden“ von Bits aus der Byte-Sequenz und dem ”Zusammenstellen“ von integer-Blöcken (in der Terminologie des Programmes auch ”Code“ genannt). Innerhalb der Prozedur werden GetBits sowie PutBits aufgerufen.

function UnShift : integer;

Analogon zu DoShift. Anhand der Flags CodeReady bzw. ByteReady erkennt die Prozedur, ob ein integer-Code in die Datei geschrieben werden kann, bzw. ob ein neues byte aus der gepackten Datei gelesen werden kann. Innerhalb der Funktion wird CalcCode aufgerufen. Der Rückgabewert der Funktion ist vom Typ integer.

Die Unit ”intqueue“ Wie man dem Quelltext zur Unit lzw entnehmen kann, wird in der uses-Klausel intqueue eingebunden. Wie der Name schon nahelegt, werden in dieser Unit Prozeduren und Funktionen zur Behandlung von a priori unbeschränkten Warteschlangen (”Queues“) von integer-Zahlen bereitgestellt. Warum es nötig ist, Gebrauch vom ADT Queue zu machen, wurde bereits am Ende von Abschnitt 2.1.2 der Dokumentation erörtert. Die für die Implementierung notwendige dynamische Datenstruktur wird hierbei folgendermaßen modelliert (Auszug aus dem Listing) :

type  QueuePtr    = ^QueueItem;
      QueueItem   = record
                     element : integer;
                     next    : QueuePtr;
                    end;
      Queue       = record
                     first : QueuePtr;
                     last  : QueuePtr;
                    end;

Der Benutzer hat Zugriff auf folgende Funktionen und Prozeduren:

procedure NewQueue       (var q : Queue);
procedure AddToQueue     (var q : Queue; item : integer );
procedure DeleteFromQueue(var q : Queue);
procedure CopyQueue      (q1 : Queue; var q2 : Queue);
function  Front          (q : Queue)     : integer;
function  QueueEmpty     (q : Queue)     : boolean;
function  IsEqual        (q1,q2 : Queue) : boolean;
procedure RemoveQueue    (var q : Queue);

Hier bei ist NewQueue der Konstruktor und RemoveQueue der Destruktor für eine Instanz der Datenstruktur. Die Prozeduren AddToQueue und DeleteFromQueue fügen ein Element bei bzw. löschen ein Element aus der Warteschlange. Dies geschieht nach dem FiFo-Prinzip. Mit Hilfe der Prozedur CopyQueue kann man eine deep-Copy einer bereits bestehenden Warteschlange erstellen. Die Funktion front liefert das vorderste Element einer bestehenden Warteschlange. Mit der Funktion QueueEmpty kann man testen, ob ein Queue leer ist. Die Funktion isEqual testet, ob 2 Warteschlangen elementweise gleich sind.

2.2.3 Implementierung der Unit ”Huff“

Allgemeines: Der Algorithmus wurde komplett als Turbo-Pascal Unit programmiert. Um den Algorithmus zu verwenden, muß man die Unit huff.tpu einbinden und die Funktion huffman aufrufen. Die Funktion liefert einen boolschen Wert zurück, der angibt, ob ein Fehler aufgetreten ist oder nicht.

FUNCTION Huffman(org_datei : String; VAR ext : String;
                                    VAR ratio : Real;
                                    art : Char) : Boolean;

org_datei : Name der Datei die komprimiert oder dekomprimiert werden soll ext : Dieser var-Parameter enthält nach dem Dekompressionsvorgang

die Endung der wiederhergestellten Datei.

ratio : Dieser var-Parameter enthält die erreichte Kompressionsrate. art : k um zu komprimieren, d um zu dekomprimieren

Die komprimierte Datei bekommt die Endung .huf. Achtung, diese Endung darf nicht geändert werden! Sie besteht aus Zahlen zwischen 0 und 255 (Typ: Byte). Diese Zahlen werden später in Bitfolgen umgerechnet, die den Code des ASCII-Zeichens repräsentieren. Diese Umrechnung ist notwendig, da es in Turbo-Pascal nicht möglich ist, ein einzelnes Bit abzuspeichern. Das Programm ist in der Lage alle evtl. auftretenden Fehler abzufangen und entsprechend zu reagieren.

Erklärung zum Record baumtyp

wert : Zeichen, welches in der Datei vorkommt anzahl : Häufigkeit des ASCII-Zeichens oder des folgenden Teilbaums code : entweder 0 oder 1, je nachdem, ob es sich um einen linken oder

rechten Teilbaum handelt

vor : Zeiger auf den vorherigen Knoten (wichtig beim Komprimieren)

links,

rechts : Zeiger auf den linken/rechten Teilbaum (wichtig beim Dekomprimieren)

Die Variable status wird zu Beginn fast jeder Prozedur überprüft. Sollte irgendwo im Programm vorher ein Fehler aufgetreten sein, hat diese den Wert false und die Prozedur wird sofort abgebrochen. Hat status am Ende des Programms den Wert true, ist die Komprimierung bzw. Dekomprimierung erfolgreich durchgeführt worden.

Prozeduren, die sowohl beim De-, als auch beim Komprimieren verwendet werden:

• Erstelle_Baum:

In dieser Prozedur wird der Huffman-Baum aufgebaut.

1.) Zuerst wird eine Kopie der Häufigkeits-Tabelle (baumfeld[i]) und dessen Länge (hilflaenge) erstellt. Dies ist notwendig, damit die Variablen tabelle[i] weiterhin auf die einzelne Blätter zeigen. Im folgenden wird nur noch mit dieser Kopie gearbeitet.

2.) Als nächstes wird ein neuer Knoten (hilf) eingefügt. Die beiden letzten Einträge in dem Feld baumfeld haben die geringste Häufigkeit und werden somit durch den neuen Knoten verbunden. Der Zeiger hilf^.links zeigt auf das vorletzte und hilf^.rechts auf den letzten Eintrag. In hilf^.anzahl wird die Summe der beiden Häufigkeiten eingetragen. Der letzte Eintrag im baumfeld bekommt nun den Code ”0“ und der vorletzte den Code ”1”.

3.) Sind die beiden letzten Einträge durch einen neuen Knoten verbunden, müssen sie beim weiteren Aufbau nicht mehr berücksichtigt werden. Die Variable hilflaenge wird um 1 verringert und der nun letzte Eintrag im Feld baumfeld zeigt auf den neuen Knoten.

4.) Sind jetzt noch mindestens 2 Einträge im baumfeld enthalten, werden diese in der Unterprozedur Einsortieren wieder sortiert. Die geschieht mit dem Bubble-Sort Verfahren. Dieses Verfahren ist in diesem Fall das günstigste, da nur der letzte Eintrag neu einsortiert werden muß. Das Einsortieren ist notwendig, damit in Punkt 2.) immer die letzten beiden Einträge verbunden werden können.

5.) Die Punkte 2.), 3.) und 4.) werden solange wiederholt, bis nur noch ein

Eintrag vorhanden ist. 6.) Ist letztendlich nur noch ein Eintrag vorhanden, zeigt die Variable baum auf

diesen. Nach diesen Schritten ist der Huffman-Baum komplett aufgebaut und die Variablen tabelle[i] zeigen auf seine Blätter, und die Variable baum auf seine Wurzel.

• Speicher_freigeben:

In dieser Prozedur wird der Speicher, den der Baum belegt, wieder freigegeben.

1.) Die Prozedur beginnt an der Wurzel und geht rekursiv mittels der Unterprozedur rek zuerst in den linken und dann in den rechten Teilbaum des Huffman-Baums.

2.) Gelangt man so in ein Blatt, wird dieses gelöscht.

Komprimieren

init:

In dieser Prozedur werden einige Variablen initialisiert.

1.) Das Feld tabelle[i]) wird mit den Startwerten belegt, d.h. die Anzahl wird auf 0 gesetzt, die Zeiger vor, links, rechts zeigen auf NIL und der i.te Eintrag enthält das i.te von den 256 vorkommenden Zeichen.

2.) Die Länge der Häufigkeits-Tabelle wird auf Maximallänge, d.h. 255, gesetzt.

Erstelle_Dateinamen:

In dieser Prozedur wird der Name der komprimierten Datei erstellt.

1.) Mittels des Befehls Fsplit aus dem Pascal-Unit Dos wird der Dateiname der zu komprimierenden Datei in seine drei Bestandteile (Pfad, Name und Endung) aufgeteilt.

2.) Bei der komprimierten Datei wird der Pfad und der Name übernommen, nur die Endung wird in .huf geändert. Sollte die angegebene Datei bereits die Endung .huf haben, so bekommt die neu erstellte komprimierte Datei die Endung hu$. Diese Endung darf auch später vom Benutzer nicht mehr geändert werden, da beim Dekomprimieren nur Dateien mit diesen Endungen angenommen werden.

Erstelle_Haeufigkeitstabelle:

In dieser Prozedur wird die Häufigkeits-Tabelle erstellt.

1.) Zuerst wird die zu komprimierende Datei geöffnet. Hierbei wird die automatische Fehlerabfrage mit {I-} abgeschaltet um so festzustellen, ob die Datei existiert. Hat IoResult einen Wert ungleich Null, ist ein Fehler aufgetreten und das Programm wird beendet.

2.) Im nächsten Schritt wird die Größe der Datei festgestellt. Dies geschieht mit dem Befehl FileSize aus dem Turbo-Pascal Unit Dos. Ist sie größer als 2 Gbyte, wird das Programm ebenfalls beendet. Diese Abfrage ist notwendig, da im Huffman-Baum in der Wurzel die Gesamtanzahl der Zeichen steht, diese wird aber durch MaxLongInt begrenzt. Diese Größenordnung dürfte allerdings nie erreicht werden, somit stellt diese Abfrage keine wirkliche Einschränkung dar. Wird sie doch erreicht, wird hier auch gleich wieder der Speicher für die Häufigkeits-Tabelle freigegeben.

3.) In der folgenden Schleife wird nun die Häufigkeit jedes Zeichens in der Datei festgestellt und in dem Feld tabelle[i] gespeichert.

Entferne_Elemente:

In dieser Prozedur werden die Zeichen aus der Häufigkeits-Tabelle gelöscht, die in der Datei nicht vorkommen.

1.) Die Schleife in dieser Prozedur beginnt beim letzten Eintrag in der Häufigkeits-Tabelle und überprüft dessen Anzahl. Ist sie ungleich Null, wird dieser Eintrag übersprungen und zum nächsten gegangen. Ist sie jedoch gleich Null, wird dieser Eintrag entweder, wenn es der letzte ist, gelöscht oder mit dem letzten getauscht und dieser dann gelöscht.

2.) Dieses Entfernen ist wichtig, damit nicht unnötig Zeichen kodiert werden und somit der Algorithmus ineffektiv wird.

Sortiere_Tabelle:

In dieser Prozedur wird die Häufigkeits-Tabelle sortiert. Da die Prozedur Erstelle_Baum von einem sortierten Feld ausgeht, wird die Tabelle der auftretenden Häufigkeiten nun in dieser Prozedur in absteigender Reihenfolge sortiert. Dies geschieht mit einem ganz naiven Algorithmus: Zuerst wird das größte Element gesucht und mit dem letzten getauscht, dann wird das zweitgrößte gesucht und mit dem vorletzten getauscht, usw. Hier wird auf einen komplizierteren Algorithmus verzichtet, da im Höchstfall nur 256 Einträge in der Häufigkeits-Tabelle sortiert werden, in der Regel aber bei Textdateien nicht mehr als 50.

Kodiere:

In dieser Prozedur wird die komprimierte Datei geschrieben.

1.) Die komprimierte Datei wird zum Schreiben geöffnet.

2.) Die ersten drei Byte in der komprimierten Datei werden für die Endung der Originaldatei verwendet.

3.) Im Anschluß an die Endung, wird die Häufigkeits-Tabelle in die komprimierte Datei geschrieben. Dies ist notwendig, da ohne diese ein späteres Dekomprimieren nicht mehr möglich wäre! Hierbei wird ein Byte für den Zeichencode (0 … 255) verwendet und vier Byte für die Häufigkeit des Zeichens. Die Longint-Zahl wird in einen 32-Bit-Code umgerechnet und jeweils 8 Bit zu einem Byte zusammengefaßt. Ein Eintrag in der Häufigkeits-Tabelle benötigt also 5 Byte in der komprimierten Datei. Wurde die Häufigkeits-Tabelle komplett in die Datei geschrieben, werden 5 Nullen als Endmarke geschrieben. Die erste für das Zeichen und die restlichen 4 für die Häufigkeit.

4.) Im nächsten Schritt wird ein Tabelle erzeugt, in der steht, in welchem Blatt im Huffman-Baum der Code für das i.te Zeichen beginnt. Dies verhindert, daß beim Kodieren jedesmal nach dem passenden Blatt gesucht werden muß.

5.) Nun beginnt das Komprimieren der Datei. In der Unterprozedur Fuelle_Feld wird das erste Zeichen aus der Originaldatei gelesen und vom zugehören Blatt ausgehend, wird der Code für dieses Zeichen bestimmt. Sollte dieser mehr als 7 Zeichen lang sein, werden jeweils 8 Zeichen mittels des Horner-Schemas in eine Dualzahl umgerechnet und in die komprimierte Datei geschrieben. So bleiben am Ende 7 oder weniger Zeichen übrig. Diese werden nun mit dem Code für das nächste Zeichen aus der Originaldatei analog verrechnet. Dieses wiederholt sich nun so lange, bis alle Zeichen kodiert wurden. Damit die letzte berechnete Dualzahl stimmt, muß sie noch mit einer bestimmten Zweier-Potenz multipliziert werden.

Dekomprimieren

Lies_Endung:

In dieser Prozedur wird die Endung aus der komprimierten Datei gelesen.

1.) Der angegebene Dateiname wird in seine drei Bestandteile aufgeteilt. Sollte die Endung ungleich huf oder hu$ sein, wird das Programm abgebrochen, da es sich (wahrscheinlich) nicht um eine komprimierte Datei handelt.

2.) Im nächsten Schritt wird die komprimierte Datei zum Lesen geöffnet und geprüft, ob sie länger als 13 Byte ist. Dies ist die Minimallänge einer komprimierten Datei: ein Eintrag in der Häufigkeits-Tabelle (5 Byte) + Endmarke für Häufigkeits-Tabelle (5 Byte) + ein codiertes Zeichen (1 Byte) = 13 Byte. Während des Öffnens und Prüfens wird die automatische Fehlerabfrage von Turbo-Pascal abgestellt und ein evtl. auftretender Fehler mit der Funktion IoResult abgefangen.

3.) Sollten bis hier keine Fehler aufgetreten sein, handelt es sich wirklich um eine komprimierte Datei. Nun werden die ersten drei Byte, die die Endung der Originaldatei enthalten, aus ihr gelesen.

Lies_Tabelle:

In dieser Prozedur wird die Häufigkeits-Tabelle aus der komprimierten Datei gelesen.

1.) In der äußeren Schleife werden solange 5 Byte-Blöcke aus der Datei gelesen, bis die Endmarke der Häufigkeits-Tabelle oder das Dateiende erreicht wird. Im letzeren Fall ist ein Fehler aufgetreten und das Programm wird abgebrochen.

2.) Als erstes wird ein Byte aus der Datei gelesen, welches dem Code des Zeichens entspricht.

3.) In der folgenden Schleife werden 4 Byte aus der Datei gelesen, welche der Häufigkeit des Zeichens entsprechen. Diese 4 Byte werden nun in eine LongInt-Zahl umgerechnet.

4.) Für diese 5 Byte wird nun ein neuer Eintrag in der Häufigkeits-Tabelle reserviert.

5.) Da für die Endmarke ebenfalls ein Eintrag reserviert wurde, muß dieser noch am Ende der Prozedur gelöscht werden.

6.) Mit dieser Häufigkeits-Tabelle kann nun der Huffman-Baum aufgebaut werden.

Dekodiere:

In dieser Prozedur wird die Datei dekomprimiert.

1.) Die Unterprozedur Berechne_Code berechnet aus einer Dezimalzahl die zugehörige Dualzahl.

2.) Die neue Datei wird zum Schreiben geöffnet und ein Hilfszeiger auf die Wurzel des Huffman-Baums gesetzt.

3.) In der folgenden Schleife werden solange Zeichen aus der komprimierten Datei gelesen, bis das Dateiende erreicht wird.

4.) Wurde ein Byte aus der komprimierten Datei gelesen, wird mit der Unterprozedur Berechne_Code sein Dualcode erzeugt. Mit diesem Code kann nun im Huffman-Baum das entsprechende Zeichen gesucht werden. Ausgehend von der aktuellen Position im Huffman-Baum verzweigt man in den linken, wenn es sich um eine 1 handelt, oder in den rechten, wenn es sich um eine 0 handelt, Zweig des Baumes. Gelangt man so in ein Blatt und ist die Anzahl der Gesamtzeichen, diese steht in der Wurzel des Baumes, noch nicht erreicht, wird das Zeichen in die neue Datei geschrieben und der Hilfszeiger wieder auf die Wurzel gesetzt. Sollte nach diesen 8 Schritten (8 Bit des Zeichens) noch kein Blatt erreicht sein, wird das nächste Zeichen aus der komprimierten Datei gelesen und mit dessen Code fortgefahren.

2.2.4 Implementierung der Unit ”Lauf“

Allgemeines Der Algorithmus wurde komplett als Turbo-Pascal Unit programmiert. Um den Algorithmus zu verwenden muß man nur die Unit lauf.tpu einbinden und die Funktion lauflaengenkodierung aufrufen. Die Funktion liefert einen boolschen Wert zurück, der angibt, ob ein Fehler aufgetreten ist oder nicht.

FUNCTION lauflaengenkodierung(name:String; VAR ext : String;
                                          VAR ratio : Real;
                                          art:Char) : Boolean;

name : Name der Datei die komprimiert oder dekomprimiert werden soll ext : Dieser var-Parameter enthält nach dem Dekompressionsvorgang

die Endung der wiederhergestellten Datei. ratio : Dieser var-Parameter enthält die erreichte Kompressionsrate. art : k um zu komprimieren, d um zu dekomprimieren

Die komprimierte Datei bekommt die Endung .len bzw. le$, wenn die ursprüngliche Datei bereits diese Endung hatte. Achtung, diese Endung darf nicht geändert werden! Das Programm ist in der Lage, alle evtl. auftretenden Fehler abzufangen und entsprechend zu reagieren.

Variablen und Prozeduren Die beiden Konstanten trenn und null entsprechen jeweils den ASCII-Codes 144 (=$90) und 0. In den Variablen gepackn und packn wird der Name der komprimierten und der zu komprimierenden Datei gespeichert. Die Variable status wird zu Beginn fast jeder Prozedur überprüft. Sollte irgendwo im Programm vorher ein Fehler aufgetreten sein, hat diese den Wert false und die Prozedur wird sofort abgebrochen. Hat status am Ende des Programms den Wert true, ist die Komprimierung bzw. Dekomprimierung erfolgreich durchgeführt worden.

Komprimieren Zu Beginn wird die Datei, deren Name vom Benutzer angegeben wurde, zum Lesen geöffnet. Hierbei werden die nicht portablen Compileroptionen {I-} und {I+} verwendet, um die automatische Fehlerabfrage von Turbo-Pascal ab- bzw. einzuschalten. Sollte beim Öffnen ein Fehler aufgetreten sein, liefert die Funktion IoResult einen Wert ungleich null zurück. In diesem Fall bekommt die Variable status den Wert false, und das Programm wird beendet. Gleichzeitig wird auch überprüft, ob es sich um eine leere Datei handelt. Sollte dies der Fall sein, wird das Programm ebenfalls beendet.

erstelle_dateinamen:

In dieser Prozedur wird der Name der komprimierten Datei erstellt.

1.) Der angebene Name wird mittels der Prozedur Fsplit aus dem Turbo-Pascal Unit Dos in seine drei Bestandteile (Pfad, Dateiname und Endung) aufgeteilt.

2.) Im nächsten Schritt wird die Endung der komprimierten Datei bestimmt. Normalerweise bekommt sie die Endung .len, sollte die angegebene Datei aber schon diese Endung haben, wird die Endung auf .le$ gesetzt.

kodiere:

In dieser Prozedur wird die Datei komprimiert.

1.) Am Anfang wird die neue Datei erstellt und zum Schreiben geöffnet. Hierbei wird wieder die automatische Fehlerabfrage abgestellt und mittels der Funktion IoResult überprüft, ob ein Fehler aufgetreten ist. Sollte dies der Fall sein, wird das Programm beendet.

2.) Als zweites wird die Endung der angegenen Datei in die komprimierte Datei geschrieben.

3.) In der Unterprozedur schreiben, wird das zu kodierende Zeichen in die neue Datei geschrieben. Hierbei hängt die Art der Kodierung von der Häufigkeit, die in der Variable zaehler gespeichert ist, des Zeichens ab. Kommt das Zeichen mehr als 3 mal vor und ist sein ASCII-Code nicht $90 wird in der komprimierten Datei folgende Zeichenkette gespeichert: ASCII-Code+$90+zaehler. Ist der ASCII-Code des Zeichens $90, wird die Zeichenkette folgendermaßen abgeändert: ASCII-Code+0+$90+zaehler. Diese zusätzliche 0 ist notwendig, damit das Zeichen $90 nicht mit dem Zeichen Zaehler_folgt verwechselt wird. Ist der Zähler jedoch kleiner als 3 wird das Zeichen nicht speziell kodiert, sondern nur gemäß seiner Häufigkeit in die komprimierte Datei geschrieben. Hierbei ist allerdings wieder die zusätzliche 0 für das Zeichen $90 notwendig.

4.) Im eigentlichen Hauptteil der Prozedur kodiere wird die Häufigkeit jedes Zeichens festegestellt. Von dieser Anzahl hängt es dann ab, wie das Zeichen in der Unterprozedur schreiben kodiert wird. Um die Häufigkeit des Zeichens festzustellen, wird nacheinander jedes Zeichen (akt_byte) aus der Datei gelesen und mit dem Vorgänger (vor_byte) verglichen. Sind beide Zeichen identisch, wird der Zähler um 1 erhöht. Dies wird solange wiederholt, bis das Ende der Datei erreicht ist.

Dekomprimieren Das Dekomprimieren der komprimierten Datei wird mit zwei Prozeduren realisiert.

lies_endung:

In dieser Prozedur wird die Endung aus der komprimierten Datei gelesen.

1.) Zu Beginn wird der angegebene Dateiname mittels des Befehls Fsplit in seine drei Bestandteile aufgeteilt. Sollte die Endung der Datei ungleich .len oder .le$ sein, wird das Programm abgebrochen, da es sich wahrscheinlich nicht um ein von diesem Programm komprimierte Datei handelt.

2.) Im nächsten Schritt wird die angegebene Datei zum Lesen geöffnet und überpüft, ob sie mindestens vier Byte lang ist. Dieses ist die Minimallänge einer komprimierten Datei (Endung+1 Zeichen). Hierbei wird wieder die automatische Fehlerabfrage von Turbo-Pascal abgestellt (siehe kodiere).

3.) Als nächstes werden die ersten drei Byte aus der Datei gelesen. Diese werden als Endung der neuen Datei verwendet.

dekodiere:

In dieser Prozedur wird die Datei dekomprimiert.

1.) Ist bis hier hin kein Fehler aufgetreten, wird eine Datei mit der neuen Endung erstellt und zum Schreiben geöffnet.

2.) In den folgenden Schritten wird jeweils ein Byte (akt) aus der angegenen Datei gelesen und entsprechend seinem Nachfolger (next) wird akt in die neue Datei geschrieben. Hirbei können drei verschiedene Fälle auftreten:

• Ist next nicht $90, wird akt in die neue Datei geschrieben und akt bekommt den Wert von next.

• Hat next jedoch den Wert $90, wird das folgende Byte (hilf) gelesen und entsprechend seinem Wert wird akt geschrieben:

a) Hat hilf den Wert 0, bedeutet dies, daß es sich um keinen Zähler handelt. akt wird in die Datei geschrieben, und akt bekommt den Wert von next.

b) Hat hilf jedoch einen Wert gößer als 0, ist dies die Häufigkeit des Zeichens akt. Dieses wird gemäß hilf in die Datei geschrieben und akt wird neu aus der angegebenen Datei gelesen.

Diese Schritte werden solange wiederholt, bis das Ende der Datei erreicht ist.

2.2.5 Elementare I/O-Behandlung und Hauptprogramm

Ähnlich wie im Abschnitt zur Beschreibung der Unit Lzw wird hier zur Dokumentation der verwendeten Variablen der entsprechende Auszug aus dem Quelltext gedruckt :

var response : char;
erfolg   : boolean;
name     : string;  { Name der zu bearbeitenden Datei  }
param    : string;  { Uebergebener Parameter  }
fehler   : string;  { evtl. auftretende Fehlermeldung  }
i        : integer;  { Zaehlvariable fuer die Schleife  }

    numargs  : integer;  { Anzahl der uebergebenen Argumente }
    rate     : real;  { erreichte Kompressionsrate  }
    rate2    : real;  { erreichte Kompressinsrate im  }
                            { 2. Schritt. Tritt nur bei "Squeeze" }
                            { auf !  }
    optionen : set of char; { Menge der zulaessigen Optionen  }
    P        : PathStr;  { Dies sind alles Hilfsvariablen,  }
    D        : DirStr;  { die fuer den Aufruf der Non-  }
    N        : NameStr;  { Standardprozedur 'FSplit' benoetigt }
    E        : ExtStr;  { werden.  }

Die verwendeten Funktionen bzw. Prozeduren sind schnell erläutert:

procedure StringToUpper(var s : string);

Diese Prozedur verwandelt den als var-Parameter übergebenen String in Großbuchstaben.

procedure Info;

Diese Prozedur gibt den Info-Text zum Programm packer.pas aus.

procedure Correct_Usage;

Diese Prozedur gibt die Liste aller gültigen Parameter für den Shell-Aufruf von

packer.exe aus.
procedure Komp(name : string; Algo : char);

Diese Prozedur sorgt dafür, daß die unter name abgespeicherte Datei mit dem durch Algo näher bestimmten Algorithmus komprimiert wird. Innerhalb dieser Prozedur werden die Kompressionsfunktionen der Units lzw, huff und lauf aufgerufen. Außerdem gibt die Prozedur - im Erfolgsfall - den Namen der gepackten Datei sowie die erreichte Kompressionsrate in Prozent aus. Im Mißerfolgsfall wird - soweit möglich - die entsprechende Fehlermeldung ausgegeben.

procedure Dekomp(name : string; Algo : char);

Diese Prozedur leitet den durch name übergebenen Dateinamen an den durch Algo bestimmten Dekompressionsalgorithmus der jeweiligen Unit (lzw, huff oder lauf weiter. Die Prozedur gibt - falls kein Fehler auftrat - den Namen der entpackten Datei aus. Im Mißerfolgsfall wird - soweit möglich - die entsprechende Fehlermeldung ausgegeben.

Hauptprogramm: Im wesentlichen beschränkt sich die Aufgabe des Hauptprogrammes darauf, die vom Benutzer übergebene Kommandozeile zu parsen und die Aufgaben - je nach Option - weiterzudeligieren. Bei Fehlbedienung (zu viele / zu wenige oder falsche Parameter) verzweigt das Programm und reagiert mit einer entsprechenden Meldung.

2.2.6 Entwicklungsstadien und Historie

Auf Grund der Tatsache, daß das vorliegende Projekt Packer von zwei Personen bearbeitet wurde und der daraus resultierenden Arbeitsteilung, läßt sich die Entwicklung in zwei weitestgehend voneinander unabhängige und parallel verlaufende ”Entwicklungsblöcke“ sowie einen “Abschlußblock“ einteilen :

1. In diesem Block werden die für die Huffman- und Lauflängencodierung nötigen Überlegungen angestellt und in eine Implementierung in Form der Units Huff und Lauf umgesetzt. Die Entwicklung dieser Units gestaltete sich folgendermaßen:

• Erste lauffähige Version eines Huffman-Komprimierers

• Verbesserte Version ohne ”Kinderkrankheiten“

• Entwurf einer Routine für die Lauflängenkomprimierung

• Optimierung der bisherigen Codes und Modularisierung in Form der Units

         Huff und Lauf

2. Dieser Block ist der LZW-Codierung gewidmet. Über die Entwicklung gibt die folgende Auflistung Auskunft:

• V0.5 : Erste lauffähige, aber extrem ineffektive Version eines Komprimierers nach dem LZW-Algorithmus (LZW.pas).

• V1.0 : Erste effektive Version mit einem 11-Bit-Alphabet. Arbeitet bereits mit Hashing (LZW1.pas).

• V1.1 : Arbeitet mit einem 12-Bit-Alphabet (LZW2.pas).

• V1.11: Komprimiert ab jetzt beliebige Binärdateien, bis jetzt war nur die Kompression von ASCII-Dateien möglich (LZW3.pas).

• V1.2 : In dieser Version des LZW-Komprimierers wird endlich die letzte offensichtliche Schwäche und Kinderkrankheit beseitigt, nämlich die bislang extrem ineffektive Speicherung des komprimierten Codes in einer Datei. Dieser Mangel wird durch die in den Programmen encode.pas bzw. decode.pas entwickelten Methoden behoben (LZW4.pas).

• Als letzter Schritt wird der bislang als Stand-Alone-Applikation arbeitende LZW-Komprimierer entsprechend dem Vorgehen bei Huffman- und Lauflängencodierung in einer Unit LZW modularisiert.

3. Nach den beiden ersten, voneinander unabhängigen Entwicklungsblöcken wird in der Endphase der Entwicklung ein Hauptprogramm entworfen, in dem die bisher erarbeiteten Units eingebunden werden und in dem die endgültige Form des Projektes in Gestalt eines Shell-Kommandos erreicht wird.

Für genauere und detailliertere Erläuterungen zur Historie siehe auch die Quelletexte zu den einzelnen Programmen.

2.2.7 Anmerkungen zur Portabilität

Wie bereits in der Einführung bemerkt, gibt es hier einige Probleme. Dies liegt vor allem an folgenden Punkten:

• Die Dateibehandlung ist in Pascal äußerst unzureichend standardisiert. So existiert im Standard z.B. überhaupt keine Möglichkeit, zu prüfen, ob eine Datei existiert. Auch vereinfachende Funktionen, wie etwa FSplit, die an vielen Stellen des Projektes verwendet werden, sind im Standard nicht vorgesehen. In diesem Zusammenhang sollte auch erwähnt werden, daß die vorliegende Implementierung auf das Dateisystem unter DOS zugeschnitten wurde. Bei einer evtl. Portierung auf andere Systeme muß man dies berücksichtigen.

• Ebenfalls problematisch ist die Übergabe der Parameter der Kommandozeile an das Programm. Auch hierfür ist im Pascal-Standard nichts vorgesehen. Die meisten gängigen Pascal-Dialekte stellen hierfür jedoch meistens probate Mittel zur Verfügung, so daß sich dieser Punkt nicht allzu negativ bemerkbar macht.

• Aus mehreren Gründen ist es in diesem Projekt erforderlich, auf den Datentyp byte zurückzugreifen. Auch hier besteht das Problem darin, daß dieser ADT im Standard der Sprache nicht vorgesehen ist. Auf anderen Entwicklungsplattformen ist es hier aber evtl. möglich, auf den ADT char auszuweichen, der ja in den meisten Fällen ebenfalls auf 1 byte ausgelegt ist.

• Unproblematisch ist der Gebrauch der Non-Standard-Prozeduren shr oder shl, die beim ”Shiften“ benötigt werden. Hier kann man sich mit div bzw. einer Multiplikation mit einer 2er-Potenz behelfen. Im vorliegenden Projekt wird aber dennoch auf shr und shl zurückgegriffen, da dies dem Wesen der ausgeführten Operation entspricht und eleganter ist.

• Leider ist nicht in jedem Pascal-Dialekt (so auch nicht im Standard) die Modularisierung in Form von Units vorgesehen. Wenn man Pech hat, existiert überhaupt kein Konzept, das die Modularisierung eines Projektes unterstützt.

3 Benutzerdokumentation

3.1 Die Anwendung des Programmes

3.1.1 Hard- und Softwarevoraussetzungen

Genau wie in den folgenden Abschnitten können wir uns hier kurz fassen. Da das Programm unter Borland-Pascal V7.0 entwickelt wurde und als Shell-Kommando fungiert, sind die Anforderungen an System, Speicher etc. nicht besonders hoch. Getestet wurde das Programm auf einem Pentium-133 MHz-System mit 16 MB RAM unter Windows '95, sowie auf einem Pentium-75 MHz-System mit 24 MB RAM ebenfalls unter Windows '95. Das Programm sollte auf jeden Fall auch unter weitaus schwächeren Systemvoraussetzungen lauffähig sein, genauer gesagt unter allen Systemen, auf denen auch der Borland-Pascal-Compiler arbeitet. Ein Intel-486-System mit 8 MB Hauptspeicher sollte jedenfalls keine Probleme bereiten.

3.1.2 Installation des Programmes

Dieser Abschnitt wurde - wie man sich leicht denken kann - nur der Vollständigkeit halber in die Benutzerdokumentation aufgenommen. Entweder kopiert man sich die Datei Packer.exe in das gewünschte Verzeichnis oder man besorgt sich den Pascal-Quelltext und kompiliert auf dem jeweiligen System. Zum Compilieren des Projektes benötigt man folgende Dateien:

   • packer.pas
   • lzw.pas
   • huff.pas
   • lauf.pas
   • intqueue.pas

Das Hauptprogramm ist in packer.pas codiert, die restlichen Dateien enthalten die benötigten Units.

3.1.3 Der Aufruf des Programmes

Der Aufruf des Programmes erfolgt in einer DOS-Shell, wobei die gewünschten Parameter (Kompressionsart, zu komprimierende Datei) in der Kommandozeile mit übergeben werden. Siehe hierzu den folgenden Abschnitt:

3.1.4 Optionen, Parameter und Programmablauf

Wenn man im DOS-Shell lediglich Packer ohne Angabe von Parametern eingibt, so verhält sich das Programm genau so, wie man es von einem Shell-Kommando erwartet: Es gibt dem Benutzer Hinweise auf den korrekten Gebrauch des Programmes, indem es eine Liste aller gültigen Parameter ausgibt. Werden zu viele, zu wenige oder unzulässige Parameter verwendet, so reagiert das Programm mit einer entsprechenden Fehlermeldung.

Die Syntax für den Aufruf von packer.exe lautet :

packer [-parameter] name

Folgende Parameter sind hierbei zulässig :

-c Komprimieren mit der ”Crunch“-Option. Die Angabe dieses Parameters hat dieselbe Wirkung wie -l, nämlich die Kompression mit dem LZW-Algorithmus.

-h Diese Option bewirkt, daß die durch name bezeichnete Datei mit dem Huffman-Algorithmus komprimiert wird.

-l Kompression nach dem LZW-Algorithmus

-r Kompression mittels Lauflängenkodierung (”Run-Length-Encoding“)

-s Kompression mit der ”Squeeze“-Option, d.h.es wird in 2 Durchläufen komprimiert. Im 1. Durchlauf wird die Datei mittels Lauflängenkodierung vorbearbeitet. Die resultierende Datei wird dann mit dem Huffman-Algorithmus gepackt.

Wie man der Syntax etnehmen kann, ist der Parameter optional. Wenn man also keinen Parameter angibt, so geht das Programm folgendermaßen vor:

• Hat die Datei name eine der Endungen ”.lzw“, ”.lz$“, ”.huf“, ”.hu$“, ”.len“ oder ”.le$“, so wird der entsprechende Dekompressionsalgorithmus auf die durch name bezeichnete Datei angewendet. Besitzt nun die entpackte Datei (der ursprüngliche Dateiname wird beim Dekomprimieren originalgetreu wieder hergestellt) eine der oben genannten Endungen, so ”merkt“ das Programm dies und wendet den entsprechenden Dekompressions-Algorithmus auf die entpackte Datei an. Dieses Spiel setzt sich so lange fort, bis die im aktuellen Schritt entpackte Datei eine Endung ungleich der eingangs erwähnten Endungen hat. Durch dieses Vorgehen wird es beispielsweise möglich, Dateien, die mit der ”Squeeze“-Option gepackt wurden, mit einem Aufruf von packer zu dekomprimieren.

• Hat die Datei keine dieser Endungen, so wird die Datei defaultmäßig mittels Huffman-Kodierung komprimiert.

Beim Komprimieren ist auf folgende, bereits in der Systemdokumentation erwähnte Besonderheit zu achten: Komprimiert man z.B. eine Datei mit der Endung ”.huf“ mit dem Huffman-Algorithmus, so erhält die komprimierte Datei aus Konsistenzgründen die Endung ”.hu$“. Analoges gilt natürlich auch für die anderen Kompressionsalgorithmen. Bei auftretenden Fehlern und Problemen bricht das Programm ab und reagiert mit einer entsprechenden Fehlermeldung.

3.1.5 Mögliche Fehler und Probleme

Nach unseren Erfahrungen kann es zu Problemen kommen, wenn man beim Compilieren als Plattform nicht den Real-Modus angibt. Außerdem sollte man nach Möglichkeit beim Compilieren noch auf die mit Borland Pascal V7.0 mitgelieferte DOS-orientiere Oberfläche zurückgreifen. In den gerade erwähnten Fällen kann es manchmal vorkommen, daß bereits geöffnete Dateien als geschlossen erkannt werden. Hierbei handelt es sich nach unserer Kenntnis um einen noch nicht beseitigten Bug im Laufzeitsystem von Borland Pascal V7.0. Das vorliegende Projekt wurde nach bestem Wissen und Gewissen programmiert und getestet. Dennoch ist es natürlich nicht auszuschließen, daß sich nicht doch irgendwo der Fehlerteufel eingeschlichen hat. Wir haben jedenfalls den Packer auf alle möglichen Dateien mit allen zur Verfügung stehenden Kompressionsalgorithmen losgelassen und festgestellt, daß alles ordnungsgemäß funktioniert hat. Falls irgendwelche Mängel auftreten sollten, dann sollte man uns per e-mail entweder unter

      planger@wmpi06.math.uni-wuppertal.de

oder

      tmazath@wmpi06.math.uni-wuppertal.de

kontaktieren.

3.2 Effizienz der Kompressionsalgorithmen

3.2.1 Speicherplatzbedarf

Was den Speicherplatzbedarf anbelangt, ist das vorliegende Programm recht genügsam. Einerseits nimmt der Programm-Code nicht allzuviel Hauptspeicher in Anspruch.

Auch das Datensegment beansprucht nur mäßig viel Speicher, im wesentlichen nur 4096 Tabelleneinträge zu je 16 Bit beim LZW-Algorithmus.

3.2.2 Laufzeit

Wesentlich mehr Kopfzerbrechen bereitet die Laufzeit des Programmes. Sowohl die Kompression nach Huffman als auch die LZW-Kompression können in der vorliegenden Version ab einer Dateigröße von etwa 100 KB schon relativ zeitintensiv werden (Laufzeit ≫ 40 Sekunden). Dies ist vor allem der Tatsache zuzuschreiben, daß das Programm in Pascal programmiert wurde, das bekanntlichermaßen nicht gerade durch seine Schnelligkeit besticht. Vor allem in diesem Punkt ist das vorliegende Programm den gängigen Programme deutlich unterlegen.

3.2.3 Festplatten- bzw. Diskettenbedarf

Das Programm packer.exe beansprucht nicht besonders viel Speicher auf Diskette bzw. Festplatte, nämlich gerade mal 29 KB. Auch ansonsten ist dieser Punkt der Dokumentation eher ein Lichtblick: Die Intention des Projektes ist ja gerade, den Festplatten- bzw. Diskettenbedarf zu reduzieren.

3.3 Erreichte Kompressionsraten

3.3.1 Allgemeine Bemerkung

Wie schon im einführenden Kapitel angeschnitten, läßt sich hierzu folgendes sagen: Die erreichten Kompressionsraten sind - je nach verwendetem Algorithmus - relativ beachtlich, wenn auch nicht überragend, wenn man wieder den Vergleich zu den ”professionellen“ Programmen wie ”zip“, ”zoo“ etc. bemüht. Allgemein läßt sich feststellen, daß die LZW-Kompression eher besser für Textdateien geeignet ist, wohingegen Huffman- und Lauflängenkodierung vor allem bei Binärdateien zu bevorzugen sind. Geringfügig effektiver als die bloße Anwendung des Huffman-Algorithmus ist zumeist das Komprimieren nach der ”Squeeze“-Option. Diese Beobachtungen lassen sich auch an Hand des nächsten Abschnittes verifizieren. Wer sich für die konkreten, im Einzelfall erreichten Kompressionsraten interessiert, sei ebenfalls auf den folgenden Abschnitt verwiesen:

3.3.2 Einige konkrete Beispiele

Die sog. Kompressionsrate (in Prozent) ist folgendermaßen definiert :

Kompressionsrate = \frac{Länge der komprimierten Datei}{Länge der alten Datei} ∗ 100

3 BENUTZERDOKUMENTATION 40

Sie hängt im wesentlichen von folgenden 3 Faktoren ab:

1. gewählter Kompressionsalgorithmus

2. Typ der Datei (Textdatei, Bitmap etc.)

3. Länge der Datei Hier zunächst einmal eine Auflistung der von uns getesteten Dateien:

Dateiname  Typ der Datei  Länge der Datei (in Kb)
epic.wav  Sound-Datei  446.615

ana3.dvi      Dvi-Datei  136.828
lzw0.pas      Pascal-Quelltext  12.945

ana3.tex  TEX-Datei  83.195

angeldus.jpg  JPG-Datei  187.626
kodieren.doc  Word-Datei  154.112

Und nun die Auflistung der erreichten Kompressionsraten in Abhängigkeit vom gewählten Algorithmus bzw. von der gewählten Option:

                   -h       -s       -l       -r

epic.wav  86, 94% 87, 90% 116, 82% 100, 79%
ana3.dvi  83, 71% 83, 66% 79, 44% 99, 32%
lzw0.pas  63, 01% 62, 00% 48, 87% 89, 28%
ana3.tex  64, 77% 63, 41% 53, 04% 94, 18%
angeldus.jpg 100, 39% 100, 66% 138, 87% 100, 33%
kodieren.doc 50, 92% 39, 27% 104, 85% 53, 22%

Literatur

[1] Informatik Duden, Meyers Lexikonverlag 1991

[2] http://ttripl.worms.fh-rpl.de/sem/WS95_96/Kompressionsalgorithmen (Adresse im World Wide Web)

[3] DOS,10/92 (Computerzeitschrift)