!!! In Arbeit !!!

Wir wollen auf diesen Seiten etwas die theoretische Seite unseres Programms beschreiben, sowie dessen Umsetzung in unserem Programm. Da zu geben wir vorerst eine kurze Einführung in die verwendeten Algorithmen, bevor wir beschreiben, wie wir das Ganze in der Programmiersprache C umgesetzt haben.

Theorie:

Bevor wir anfangen unseren Quellcode näher zu erklären, sollten einige theoretische Fragen geklärt werden.

Nun was ist Kompression und warum wird es benötigt? Auch in der heutigen Zeit der Breitbandinternetanschlüsse und Gigabytefestplatten sind Daten noch immer gleichzusetzen mit Kosten, dh. je mehr Daten übertragen/gespeichert werden müssen, umso mehr "kostet" die jeweilige Information. Um diese Datenmengen möglichst gering zu halten, wurden im Laufe der Zeit Verfahren (=Algorithmen) entwickelt, die in Daten überflüssige Information aufspüren und diese dann kürzen. Dies kann man sich in etwa wie Fließbandarbeit vorstellen. Ein festgesetzter Arbeitsprozeß wird hintereinander ausgeführt. Dabei werden wiederholte, unnötige (redundante Information entdeckt) und verändert. Bei diesem Prozess wird prinzipiell in 2 Arten unterschieden:

• die reversible Komprimierung: wichtig dabei ist, dass die komprimierten Daten wieder genau in die Ursprungsform zurückgeführt werden können (z.B. alle möglichen Archivprogramme wie WinZIP oder dergleichen und auch unser kleines Programm "niCE")
• die irreversible Komprimierung: Im Gegensatz zur vorhergenannten Methode werden hier irrelevante Daten komplett gestrichen und gehen somit für immer verloren. Ein bekanntes Dateiformat, das diese Art der Komprimierung nützt, ist das MP3 Format für Musikdateien. Dabei werden im Gegensatz zu normalen Musikstücken von der CD Töne, die das menschliche Gehör ohnehin nicht wahrnehmen kann, weggeschnitten. Somit tritt ein nicht hörbarer Qualitätsverlust auf bei fallender Datenmenge.

Ich werde mich fortan mit der reversiblen Datenkomprimierung beschäftigen.

Diagramm zur Funktionsweise der reversiblen Komprimierung: Daten am Anfang und Daten am Ende sind ident.

Bei unserem Programm haben wir 2 gängige Algorithmen verwendet:

• die Lauflängenkomprimierung (einfaches und relativ ineffizientes Verfahren, jedoch sehr schnell)
• die dynamische Huffmankomprimierung (Datei wird zuerst analysiert und dann komprimiert)

Lauflängenkomprimierung:

Wie bereits erwähn handelt es sich bei diesem Verfahren nicht gerade um das effizienteste. Jedoch liegt sein Vorteil in der Geschwindigkeit. Die Idee hinter dem Verfahren ist es, bei wiederholten Zeichen, statt tatsächlich jedes Zeichen zu wiederholen, ein Escape Zeichen zu vereinbaren. Dieses weist darauf hin, dass es beim nächsten Zeichen um kein normales Zeichen in der Bitfolge handelt, sondern um mehrere. Nun weiss der Dekomprimierer, dass sich das nächste Zeichen wiederholen wird, bleibt nur noch die Frage offen, wie oft die Wiederholung stattfinden wird. Somit wird das 3.te eingelesene Zeichen einfach als Zahl interpretiert.

Ein Beispiel, um die Sache vielleicht etwas klarer zu gestalten:

Gegeben sei der Text: blaaaaaabbbllllaa

Die erste Idee wäre nun die wiederholten Buchstaben zu streichen und dafür eine Zahl zu notieren:

Dabei wäre folgendes Ergebnis zu erwarten: bla(6)b(3)l(4)a(2)

• Exkurs: Bytes (= 8 Bits = Zahlen von 0 - 255) können für gewöhnlich als ASCII Zeichen oder als normale Zahlen ausgelesen werden. Wird ein Byte als ASCII Zeichen ausgelesen, so wird die ausgelesene Zahl als Zeichen interpretiert. Dazu gibt es eine Tabelle, in der alle Zahlen einem Zeichen zugeordnet sind. Wie ein ausgelesenes Byte zu interpretieren ist, ist die Entscheidung des Programmierers.
• In den Beispielen sollen normale Zeichen als ASCII Code angenommen werden, Zahlen in Klammern jedoch als "normale" Zahlen.

Wie im Exkurs nun klar geworden sein sollte, ist aus der Bitfolge nicht ersichtlich, ob es sich um eine als ASCII Zeichen zu interpretierende Zahl handelt oder als normale Zahl. Hat man diese Überlegung verstanden sollte, man sich das vorhergehende Beispiel noch einmal ansehen:

bla(6)b(3)l(4)a(2)

Woher weiss das Programm, wann die "5" nicht als Buchstabe, sondern als Zeichen zu lesen ist?

Die Lösung erfordert wieder ein sogenanntes ESCAPE Symbol. Das soll ein Symbol sein, das beim Einlesen nicht als normales Symbol behandelt wird, sondern Ankündigt das nun eine spezielle Aktion folgt. Genau ein derartiges Symbol wird man hier benötigen. Dabei gibt es mehrere Möglichkeiten. Die von uns gewählte und auch näher beschriebene, war es die Datei vor dem Komprimieren zu durchsuchen und das am wenigsten vorkommende Zeichen zu ermitteln. Dieses haben wir dann als ESCAPE Zeichen benutzt.

In unserem Beispieltext kommt neben vielen anderen Zeichen kein "u" vor. Somit könnten wir das "u" als ESCAPE Zeichen nutzen. Dabei würde folgende Zeichenkette entstehen:

blua(6)ub(3)ul(4)ua(2)

Ein "u" in unserem Text würde somit aussagen: Achtung gleich folgt ein Buchstabe der sich wiederholt.

Um zu gewährleisten, dass beim Dekomprimieren auch das ESCAPE Zeichen eindeutig ist, kann man als weitere Regel einführen, dass am Anfang jeder Datei das ESCAPE Zeichen angeführt wird.

Letztendlich würde diese Datei entstehen:

ublua(6)ub(3)ul(4)ua(2) -> 15 Buchstaben (Bytes)

Originaltext: blaaaaaabbbllllaa -> 17 Buchstaben (Bytes)

Obwohl dieses Beispiel nicht wirklich die Vorteile des RLE Verfahrens hervorhebt, zeigt es denoch die Vorgehensweise und Idee hinter dem Prinzip sehr gut. Auch wenn es nun so scheinen mag, als hätte RLE keine Nutzen, so sei jedoch erähnt, dass nicht nur reine Textdateien komprimiert werden sollen, sondern zum Beispiel Bilddaten ohne komplexe Strukturen, die somit sich oft wiederholende Bytefolgen beinhalten.

Huffmankomprimierung

Nun zur 2ten Methode mit der unser Tool Daten komprimiert. Wir werden hier nur die dynamische Huffmankomprimierung behandeln, obwohl es noch die statische und die adaptive gibt (Wer daran interessiert ist, möge sich bei unseren weiterführenden Links (INFO Seite) weiterinfomieren). Ein wesentlicher Unterschied ist, dass bei dieser Art die Häufigkeit jedes Zeichens eine wichtige Rolle spielt. Das Grundprinzip ist dabei: die Zeichenhäufigkeiten feststellen, dh. es wird eine Statistik erstellt, welches Zeichen wie oft vorkommt und dann wird aufgrund dieser Statistik entschieden, welche Zeichen einen kurzen Code bekommen sollen und welche einen längeren. Dabei sollte dem Leser auch gleich auffallen, dass hierbei Codewörter mit unterschiedlichen Codewörtern entstehen. Bei der Lauflängencodierung haben wir stets einen sogenannten Blockcode benutzt. Dh. alle Codewörter besitzen die gleiche Länge und somit kann leicht damit gearbeitet werden, da man stets weiß, wo ein Codewort endet und ein anderes beginnt. Bei unseren neuen Codewörtern ist das nicht so klar. Damit man die Codewörter überhaupt eindeutig unterscheidbar sind, muss die Regel festgelegt werden, dass kein Codewort der Beginn eines anderen Codeworts sein darf. Diese Definition entspricht der Definition eines Prefixcodes.

Noch mal kurz zur Wiederholung unseres bisherigen Algorithmus:

1. Datei durchlaufen und zählen, wie oft jedes Zeichen vorkommt. Nun sollte eine Tabelle wie folgt entstehen:

   N	1
   u	1
   r	3
   Leerzeichen	7
   w	1
   e	6
   d	1
   a	2
   s	2
   Z	1
   i	1
   l	1
   k	2
   n	5
   t	2
   ,	1
   f	2
   .	1

2. Diese Tabelle soll nun nach der Zeichenhäufigkeit und dem Rang im Alphabet geordnet werden.

   7	Leerzeichen
   6	e
   5	n
   3	r
   2	a
   2	f
   2	k
   2	s
   2	t
   1	,
   1	.
   1	N
   1	Z
   1	d
   1	i
   1	l
   1	u
   1	w

Hier finden Sie genaue Informationen zum Code unseres Programms. Die Reihenfolge dieser Information ist durch die Codedateien bestimmt. Es wird also nicht in Programmausführungsrichtung gearbeitet.

Das Codesegment, das gerade erläutert wird, wird ebenfalls angegeben und hervorgehoben, um Ihnen das Leben leichter zu machen.

Achtung! Es können in den Binaries noch einige Tippfehler enthalten sein, die aber bei der genauen Durchsicht für folgende Dokumentation ausgebessert worden sind und den ordnungsgemäßen Ablauf des Programms nicht behindern. Sollten Sie in den Binaries auf Tippfehler stoßen, dann vergleichen Sie bitte mit folgender Dokumentation. Der Fehler ist in diesem Dokoument höchstwahscheinlich schon ausgebessert. Ist das nicht der Fall, dann teilen Sie uns diesen Bug bitte mit. Danke!

• Es werden Grundkenntnisse in der C-Programmierung vorausgesetzt.

Inhalt

Codedateien:

• nice_main.c (Hauptdatei mit Parameterbehandlung und main-Funktion)
• int check_parameters_main (int, char *[])
• int check_target_extension (char *)
• void main (int, char *[])
• void usage()
• statistics.c (Quelldatei für die Statistikfunktion des Programms)
• void calc_avg_length_of_code (BitSequence *)
• void calc_coding_percentage (double, double)
• void calc_entropy (char *, int)
• int get_number_of_chars (char *)
• double get_size_of_file (char *, int)
• FILE * open_file_read_access (char *)
• double start_general_statistics (char *)
• start_and_control_coding.c (Quelldatei zur Steuerung der Huffman-Codierung, Aufruf von Basisfunktionen)
• void control_coding (char *, char *)
• huffman_analyse.c (Quelldatei zur Vorbereitung des Wahrscheinlichkeitsarray)
• void calc_probability (int, double *)
• void count_char (int, double *)
• double *huffman_analyse_program (char *)
• save_tree.c (Hilfsquelldatei zum Abspeichern des Huffman-Baumes)
• BitSequence SaveTree (FILE *, Node *, BitSequence)
• void OpenFiletoSave (char *, char *, Node *, BitSequence *, char)

Headerdateien:

• globals.h
• huffman.h
• nice.h
• parameter.h

Codedateien

nice_main.c

• Dieser Codeteil enthält nur Kommentar, der aber bei jeder Codedatei enthalten sein sollte, falls es im Rahmen der Configuration Identification keine Datenbank gibt, die diese Informationen speichert.

• Diese Variable zählt Fehler, die in der Programmausführung aufgetreten sind. Die globale Definition macht es möglich aus jeder zum Projekt gehörenden Datei auf diese Variable zuzugreifen.

Variablen so lokal wie möglich, aber so global wie notwendig deklarieren.

• Notwendige Headerdateien inkludieren.
• Danach folgt der Funktionskopf der ersten Funktion (wird hier nicht angeführt). Ob Sie ihn innerhalb Ihrer Codedatei oder irgendwo außerhalb in einer Datenbank speichern, bleibt Ihnen überlassen. Sie sollten allerdings schnell darauf zugreifen können.

• Funktion zum Überprüfen der Erweiterung von filename auf Gleichheit mit REQUESTED_EXTENSION (definiert in huffman.h).
• run_a und run_b sind Laufvariablen.
• start_position_extension wird im weiteren Funktionsablauf die Stelle des Beginns der Dateierweiterung markieren. Diese muss ja erst gefunden werden.
• int_check_extension ist der Rückgabewert der Funktion. Wenn int_check_extension==0, ist die Erweiterung ok, ansonsten ist ein Fehler aufgetreten.
• check_extension speichert die gewünschte Dateierweiterung.

• Die for-Schleife durchläuft den gesamten Dateinamen.
• Wird an irgendeiner Stelle im Dateinamen ein Punkt gefunden, so wird die Positionsvariable start_position_extension dementsprechend gesetzt (run_a+1 deswegen, weil Laufvariable bei 0 beginnt).

• Die Funktion strcmp(...) vergleicht zwei Strings auf Gleichheit und gibt 0 bei Gleichheit zurück.
• Wenn strcmp(...) nicht gleich 0, stimmt die Erweiterung (, die übrigens an filename+start_position_extension.Stelle liegt) nicht mit der spezifizierten Erweiterung überein. Deshalb wird die Fehlervariable um 1 erhöht und 1 zurückgegeben.
• Andernfalls stimmt die Erweiterung, es wird 0 zurückgegeben.
• BEMERKUNG: Hier müsste man theoretisch das fix codierte \"nice\" in der printf-Anweisung gegen die Variable check_extension tauschen.

• Es folgt die Funktion, die die Benutzungshinweise zum Programm wiedergibt. Da diese Funktion selbsterklärend ist, wird sie hier nicht seziert.

• Diese Funktion liest die Parameter ein und wertet sie aus. Aus diesem Grund wird ihr sowohl argc als auch argv übergeben.
• file_source wird zum Speichern des Quelldateinamens verwendet
• file_target wird zum Speichern des Zieldateinamens verwendet
• temp_filename bezeichnet die temporäre Datei, die zwischen den beiden Codierungsalgorithmen (RLE und Huffman) übergeben wird.
• size_source bezeichnet die Größe der Quelldatei.
• size_target bezeichnet die Größe der Zieldatei.
• Die beiden zuletzt genannten Variablen sind notwendig, damit das Programm überprüfen kann, ob die Zieldatei tatsälich kleiner als die Quelldatei ist (vor allem bei Komprimierung interessant). Ist sie das nicht, wird eine Warnung ausgegeben.
• temp_check_valid bestimmt, ob die Parameter richtig eingegeben worden sind. Bei 0 liegt ein Fehler vor, bei 1 stimmt die Eingabe. Ob die Eingabe stimmt oder nicht, hängt davon ab, ob der User dem Parameter ein '-' vorangeschickt hat.
• temp_get_parameter enthält den eigentlichen Parameterbuchstaben (c)

• Diese Anweisung lässt das Programm die vom User eingegebenen Parameter durchlaufen.
• 1. Bedingung: --argc > 0: Die while-Schleife wird genau so oft durchlaufen wie es Parameter gibt.
• 2. Bedingung: **++argv == '-': Überprüft, ob der nächste Parametereintrag im Argumentvektor mit einem '-' beginnt. Beachten Sie dabei, dass der Argumentvektor immer um ein Element weitergeschoben wird.

• Parametereingabe ist korrekt, daher temp_check_valid = 1.
• Die while-Anweisung sorgt nun dafür, dass alle hinter dem '-' stehenden Buchstaben aus der Kommandozeile jetzt interpretiert werden können. temp_get_parameter wird jetzt mit jedem Buchstaben, der dem '-' nachfolgt, belegt. Beachten Sie, dass dies nur bis zum Leerzeichen erfolgt (argv[0]) und nicht darüber hinaus. Aus diesem Grund mißversteht das Programm eine derartige Eingabe: nice -c -s. -s steht in diesem Fall in argv[1]!
• Abhängig von dem eingebenen Parameter (oder von den eingegbenen Parametern) entscheidet das Programm, was zu tun ist (switch).

• Falls ein 'c' als Parameter eingegeben worden ist, startet das Programm den Versuch die angegebene Datei zu komprimieren.
• Dazu wird der Name der Quelldatei eingelesen und in file_source gespeichert, und es wird der Name der Zieldatei eingelesen und in file_target gespeichert.
• Die if-Anweisung prüft, ob zwei Dateien nach dem Parameter eingegeben worden sind. Falls nicht, erhöht das Programm die globale Fehlervariable temp_num_error um 1 und verlässt die while-Schleife.

• Sollte die Erweiterung der Zieldatei nicht der Norm entsprechen (die Funktion check_target_extension(...) gibt in diesem Fall 1 zurück), wird die while-Schleife ebenfalls verlassen.

• Die if-Schleife prüft, ob der Benutzer auch wirklich mindestens 2 Dateien hinter dem Parameter '-c' eingegeben hat.
• Ist das der Fall informiert das Programm über den Programmfortschritt, wobei zunächst die RLE-Komprimierung angewandt wird (Funktion rle_cod(char *)) und dann die Huffman-Komprimierung (Funktion control_coding(char *, char *)).
• Die RLE-Komprimierungsfunktion übernimmt die vom Benutzer eingegebene Quelldatei (file_source) und überschreibt den char * (Name der Quelldatei file_source) mit dem Namen der temporären RLE-komrimierten Datei. Wichtig! Die Quelldatei selbst wird natürlich nicht überschrieben.
• Danach übernimmt die Huffman-Komprimierung, wobei diese Funktion auch das Erstellen der Zieldatei (file_target) übernimmt.
• Die remove(char *)-Funktion entfernt die temporär erstellte Datei der RLE-Komprimierung. Für nähere Informationen zu temporären Dateien, lesen sie bitte bei den RLE-Sourcedateien weiter.

• Es folgt der Abschnitt für die Dekomprimierung der Datei.

• Belegen der char * mit den entsprechenden Parametern. file_source ist die Quelldatei und file_target ist die Zieldatei.

• Die if-Schleife überprüft, ob vom Benutzer die komprimierte Datei und die Zieldatei angegeben wurde und ob das System eine temporäre Datei anlegen konnte. Die temporäre Datei speichert die Bitfolge nach Huffman-Decodierumg ab und wird bei der RLE-Decodierung als Quelldatei hergenommen.
• Die Funktion DecompressFile(char *, char *) führt die Huffman-Decodierung durch. Sie nimmt die vom Benutzer angegebene (komprimierte) Quelldatei her (file_source) und schreibt das Ergebnis in die temporäre Datei (temp_filename).
• Die Funktion rle_dcod(char *, char *) - von den Parametern her gleicht diese Funktion der Huffman-Decodierung, sie übernimmt als ersten Parameter die Quelldatei und als zweiten Parameter die Zieldatei - führt die RLE-Decodierung durch.
• Nähere Informationen zu den Funktionen der Decodierung in den entsprechenden Quelldateien.
• Die Funktion remove(char *) ist eine Bibliotheksfunktion von ANSI-C und löscht temporär angelegte Dateien, wobei der Dateiname der temporären Datei übergeben wird.

• Falls entweder Zieldatei oder Quelldatei vom Benutzer nicht angegeben worden sind, wird eine Fehlermeldung ausgegeben und die globale Fehlervariable temp_num_error um 1 erhöht.

• Es folgt der Abschnitt für die Statistikfunktion des Programms.

• Zunächst wird der nach dem Parameter 's' eingegebene Dateinamen in file_source gespeichert.
• Danach wird mittels if-Schleife überprüft, ob der Benutzer überhaupt eine Datei eingegeben hat. Wenn nicht, wird die globale Fehlervariable wieder um 1 erhöht. break; verläßt die switch-Anweisung.

• Die Funktion start_general_statistics(char *) berechnet Kenngrößen der angegebenen Datei und gibt diese aus. Nähere Informationen in der Statistikquelldatei. Außerdem gibt die Funktion die Dateigröße zurück.
• Wenn dem Parameter 's' nur ein Parameter folgt, wird die Statistik dieser einen Datei berechnet, und damit beläßt es das Programm.
• Gibt es aber noch eine weitere Datei (die if-Schleife überprüft), wird auch die Statistik dieser Datei ausgegeben.
• Zusätzlich werden dann noch die beiden Größen der Dateien verglichen, wobei eine Warnung ausgegeben wird, wenn die Dateigröße der Zieldatei größer ist als die der Quelldatei. Dies kann gewünscht (bei der Dekompression) oder unerwünscht sein (bei der Kompression).

• Es folgt die Behandlung aller anderen (ungültigen) Parameter.

• Bei allen anderen Parametern wird eine Fehlermeldung ausgegeben und die globale Fehlervariable um 1 erhöht.

• Die Bedingung dieser if-Schleife ist dann erfüllt, wenn die Parameterangabe falsch war (wenn zB das '-' vor dem Parameter vergessen wurde). Aus diesem Grund ist es gut hier die Benutzungsinformationsfunktion usage() aufzurufen.
• Das Programm wird fehlerhaft beendet, dh. die Hauptfunktion bekommt eine 1 zurück.

• In diesem Codestück wird abhängig von der Fehleranzahl temp_num_error eine Meldung ausgegeben, wobei temp_num_error==0 bedeutet, dass kein Fehler aufgetreten ist.
• Ist kein Fehler aufgetreten, wird an die aufrufende Funktion eine 0 zurückgegeben, ansonsten eine 1.

• Es folgt die main-Funktion, die nichts anderes tut, als die Argumenteanzahl (argc) und den Argumentevektor (argv) einzulesen und an die Parameterprüffunktion weiterzugeben.

Top

Walter Scherer

• Der Dateikopf entspricht dem in unserem Projekt üblichen Vorgaben. Für die inkludierten Headerdateien bitte hier nachsehen.
• Die Headerdateien befinden sich von dieser Datei aus gesehen im übergeordneten Verzeichnis, daher ..

• Die Funktion calc_coding_percentage(double, double) berechnet das Verhältnis zwischen Größe zweiter Datei und erster Datei

• Berechnung der Code-Rate (in Prozent)

• Diese Funktion berechnet die durchschnittliche Länge des Codes
• Diese Länge ist im Array pt_array_codetable gespeichert
• Für die Struktur BitSequence bitte in huffman.h nachsehen

• run_a ist Laufvariable
• avg_code_length speichert das Endergebnis (die durchschnittliche Codelänge)
• counter speichert die Summe der Codelängen
• num_crucial_chars speichert die Anzahl der vorkommenden Zeichen

• Die for-Schleife durchläft alle 256 ASCII-Zeichen (entspricht der Position im Array)
• Die if-Schleife überprüft, ob ein Zeichen überhaupt vorkommt. Wenn nicht, wird dem Zeichen natürlich kein Code zugewiesen, dh. Code-Länge (pt_array_codetable[run_a]).length ist 0
• Kommt ein Zeichen vor, wird die Variable num_crucial_chars um 1 erhöht
• Außerdem wird die jeweilige Länge des Codes zur Gesamtlänge dazugezählt

• Diese Funktion startet die Statistikberechnung mit Bildschirmausgabe und gibt die Größe der durch den Parameter filename spezifizierten Datei zurück

• num_chars ist eine Zwischenspeicherungsvariable für die Anzahl der Zeichen
• size_file ist eine Zwischenspeicherungsvariable für die Größe der Datei filename
• get_number_of_chars(char *) besorgt sich die Anzahl der Zeichen in einer Datei
• get_size_of_file(char *, int) besorgt sich die Größe der Datei (Parameter 1)

• get_number_of_chars(char *) zählt die Zeichen in einer Datei

• temp_char bezeichnet den gerade ausgelesenen Buchstaben
• temp_number speichert die Anzahl der ausgelesenen Zeichen
• Die if-Schleife überprüft, ob das System die Datei öffnen kann (s. open_file_read_access)

• Durch die Funktion getc(FILE *) wird der Filepointer immer um ein Zeichen weitergeschoben
• Die while-Schleife wird erst am Ende der Datei verlassen
• Für jedes Zeichen wird temp_num um 1 erhöht

• Danach wird die Datei geschlossen und die Anzahl der Zeichen ausgegeben
• Außerdem liefert die Funktion die Anzahl an ausgelesenen Zeichen zurück

• Diese Funktion liefert die Größe der angegebenen Datei und berechnet die Entropie (aus diesem Grund wird auch die Zeichenanzahl übergeben)

• stat stbuf ist die Speicherstruktur für die Dateiinformationen
• Die Funktion stat(char *, &stat) belegt die Struktur mit den Dateiinformationen. Sie liefert -1 zurück, falls der Zugriff auf die angegebene Datei nicht möglich ist

• Die Funktion calc_entropy(char *, int) berechnet die Entropie der Datei, deren Name der Funktion übergeben wird

• Diese Funktion berechnet die Entropie der Datei, deren Name der Funktion übergeben wird

• run_a ist eine Laufvariable
• num_crucial_chars enthält am Ende der Funktion die Anzahl der unterschiedlichen Zeichen
• pt_array_probability wird im Laufe der Funktion mit den Zeichenwahrscheinlichkeiten - geordnet nach ASCII-Code - belegt wird (Funktion: huffman_analyse_program(char *))
• entropy ist der Entropiewert, der gleich initialisiert wird

• Das schon belegte Array mit den Wahrscheinlichkeitswerten wird in dieser for-Schleife untersucht (aus diesem Grund läuft run_a bis 256 (Maximaler ASCII-Wert))
• Die if-Schleife überprüft, ob das aktuelle Zeichen in der Datei überhaupt vorkommt, d.h. ob die Wahrscheinlichkeit eines Zeichens nicht 0 ist. Ist die Bedingung der if-Schleife erfüllt, liegt ein num_crucial_chars vor, d.h. ein in der Datei vorkommendes Zeichen. Daher wird num_crucial_chars um 1 inkrementiert
• Gleichzeitig wird die aktuelle Position im Array mit dem errechneten Entropiewert überschrieben, da die Wahrscheinlichkeiten nach der Entropieberechnung nicht mehr benötigt werden
• Die Formel der Entropie bitte in der Fachliteratur nachschlagen, es sei allerdings hier ein kleiner Hinweis angegeben: Will man den Entropiewert standardisieren ("zwischen 0 und 1 ausrechnen"), darf man nicht durch log(2.) dividieren, sondern durch log((double)num_crucial_chars). Dazu müßte man die Bestimmung der vorkommenden Zeichen jedoch vor und nicht während der Entropieberechnung durchführen
• Die Summe der einzelnen Entropiewerte bildet den gesuchten Gesamtentropiewert

• Ausgabe der Daten

• Diese Funktion öffnet die als Parameter angegebene Datei und gibt NULL bei Fehler zurück

• Es wird die C-Bibliotheksfunktion fopen(char *, char *) verwendet, die den Filepointer (hier: pt_file) auf den Beginn des Dateistreams setzt. Bei Fehler liefert die Funktion NULL zurück

Top

Walter Scherer

• Der Dateikopf entspricht dem in unserem Projekt üblichen Vorgaben. Für die inkludierten Headerdateien bitte hier nachsehen.
• Die Headerdateien befinden sich von dieser Datei aus gesehen im übergeordneten Verzeichnis, daher ..

• Die Funktion control_coding führt das Programm durch die Huffman-Komprimierung, wobei der erste Parameter die zu komprimierende Datei ist und der zweite die Zieldatei
• Diese Funktion ist der einzige Inhalt dieser Source-Datei

• pt_array_probabilities ist für die Wahrscheinlichkeiten der ASCII-Zeichen in der Quelldatei vorgesehen
• pt_root_node ist für den Wurzelknoten des Huffman-Baums reserviert
• pt_array_codetable wird den für jedes ASCII-Zeichen erstellten Code enthalten

• Die Funktion huffman_analyse_program(char *) analysiert die Quelldatei und schreibt die Zeichenwahrscheinlichkeiten geordnet nach ASCII-Code in pt_array_probabilities

• Nun wird der Huffman-Baum erstellt. Für genauere Informationen zum Thema Huffman-Codierungstheorie bitte sich im Abschnitt Info oder in der Fachliteratur zu informieren
• Die Funktion zur Erstellung des Huffman-Baumes ist CreateTree(BitSequence *), die ein Wahrscheinlichkeitsarray verlangt und den Wurzelknoten des erstellten Baumes zurück gibt
• Kann der Huffman-Baum aus irgendeinem Grund nicht erstellt werden, gibt die Funktion NULL zurück. Das wird nach dem Funktionsaufruf in der if-Schleife überprüft
• Im Fehlerfall wird - wie immer - eine Meldung ausgegeben und die globale Fehlervariable temp_num_error um 1 erhöht

• Nun wird die Codierungstabelle erstellt (die Zuweisungstabelle Zeichen-Code)
• Dazu wird die Funktion CreateCodingTable(Node *) verwendet, die aus dem Wurzelknoten des Huffman-Baumes eine Codiertabelle erstellt und diese zurückgibt
• Nach Funktionsaufruf wird überprüft, ob die Funktion korrekt ausgeführt werden konnte. Wenn nicht gibt sie NULL zurück. Eine Fehlermeldung wird ausgegeben

• Danach wird die durchschnittliche Codelänge auf Basis der Codiertabelle berechnet. Dazu wird die Funktion calc_avg_length_of_code(BitSequence *) verwendet
• Abschließend wird der Bitstream gespeichert (Funktion Parametererklärung)

• Um das Programm sauber abzuschließen, werden Huffman-Baum und Codiertabelle gelöscht (Funktionen DestroyTree(Node *) und DestroyCodingTable(BitSequence *))

Top

Walter Scherer

• Der Dateikopf entspricht dem in unserem Projekt üblichen Vorgaben. Für die inkludierten Headerdateien bitte hier nachsehen.
• Die Headerdateien befinden sich von dieser Datei aus gesehen im übergeordneten Verzeichnis, daher ..

• Diese Funktion rechnet für ein übergebenes Array mit Absolutwerten die Wahrscheinlichkeiten bezogen auf temp_counter aus

• run_a ist Laufvariable für die for-Schleife
• Die folgende for-Schleife berechnet die relative Häufigkeiten jedes Zeichens, wobei temp_counter die Gesamtanzahl der Zeichen darstellt
• Die alten Array-Einträge (absolute Zahlen) werden mit den relativen Häufigkeiten überschrieben

• Diese Funktion zählt das übergebene Zeichen und erhöht den vom Zeichen vorgegebenen Platz im Array (ASCII-Code)

• Zunächst wird die richtige Stelle im Array gesucht (pt_array_probability+temp_character). Da pt_array_probability ein - wie der Name schon vermuten läßt - Pointer ist, kann man ganz normal mit diesem Pointer rechnen. Zählt man den ASCII-Code eines Zeichens zur Startposition des Vektors, kommt man auf den richtigen Eintrag
• Der richtige Eintrag wird dann lediglich um eins erhöht, wobei der Dereferenzierungsoperator (*) vor der Berechnung pt_array_probability+temp_character. Es soll ja der Wert, auf den diese Pointer-Berechnung zeigt, um 1 erhöht werden und nicht die Adresse

• Zunächst wird die angegebene Datei geöffnet, wobei dafür die Funktion fopen(char *, char *) verwendet wird (Näheres in jeder guten C-Sprachendokumentation)
• Hat das Öffnen der Datei funktioniert, wird jedes Zeichen in der Datei überprüft (while-Schleife). Jedes Zeichen wird (samt zu befüllendem Array) der Funktion count_char(int, double *) übergeben und dort gezählt
• Das jeweilige Zeichen wird mit Hilfe der C-Funktion getc(FILE *) aus der Datei eingelesen, wobei sich diese C-Funktion bei jedem Aufruf auch um die Weiterschiebung des File-Pointers kümmert. Das eingelesene Zeichen wird zurückgeben
• Ist das Ende der Datei erreicht, gibt die Funktion die Variable EOF zurück

• Für die Funktion calc_probability(int, double *) bitte hier nachsehen
• Abschließend wird die Datei mittels C-Funktion fclose(FILE *) geschlossen und das befüllte Wahrscheinlichkeitsarray zurückgegeben

Top

Walter Scherer

• Der Dateikopf entspricht dem in unserem Projekt üblichen Vorgaben. Für die inkludierten Headerdateien bitte hier nachsehen.
• Die Headerdateien befinden sich von dieser Datei aus gesehen im übergeordneten Verzeichnis, daher ..

• Diese Funktion übersetzt den Huffman-Baum in speicherbare BitSequences (der Huffman-Baum ist bereits aufgebaut)

• Diese Funktion läuft den Baum durch und veranlaßt das Abspeichern des Baumes
• Aus programmiertechnischen Gründen gibt die Funktion am Ende des Abspeicherungsvorgangs meistens noch eine BitSequence zurück, die dann später noch berücksichtigt wird

• Diese Funktion erhält als Parameter sowohl den Dateinamen der Ursprungsdatei (file_name_source) als auch den Dateinamen der Zieldatei (file_name_target), um das Speichern der codierten Bitsequenz zu beginnen
• Außerdem werden der Wurzelknoten des Baumes (pt_RootNode) und die Codiertabelle (pt_array_codetable) als Quellen übergeben
• Der char Continue ist aus programmiertechnischen Gründen für die Funktion CompressFile(FILE *, FILE*, BitSequence *, BitSequence, char) relevant und wird in dieser Funktion nur durchgereicht

• pt_file_source bzw. pt_file_target sind Filepointer auf die Quell- bzw. Zieldatei
• BufferBitSequence wird nach Aufruf der Funktion SaveTree(FILE *, Node *, BitSequence) mit dem Rest der BitSequence (so es einen gibt) belegt
• Hinweis: In die Zieldatei wird immer nur eine Bitfolge mit Länge 8 gespeichert. Bleibt der Funktion SaveTree(FILE *, Node *, BitSequence) und ihren Subfunktionen jedoch am Schluss des Bitstreams zwischen 1 und 7 Bit inklusive über, so muss sich die Funktion CompressFile(FILE *, FILE*, BitSequence *, BitSequence, char) um die Speicherung der verbleibenden Bits kümmern
• Die Funktion SaveTree(FILE *, Node *, BitSequence) verlangt eine initialisierte BitSequence. Das erklärt die nächsten 3 Zeilen des Codes, die nichts anderes tun, als BufferBitSequence mit Code 0, Länge 0 zu initialisieren

• Anschließend wird versucht die Quelldatei zum Lesezugriff und die Zieldatei zum Schreibzugriff zu öffnen. Wichtig ist das b für "binary", um das korrekte Lesen bzw. Schreiben zu ermöglichen
• Zum Öffnen der Dateien wird die C-Bibliotheksfunktion fopen(char *, char *) verwendet, bei Interesse an dieser Funktion in geeigneter Fachliteratur Informationen einholen

• Nun wird die Funktion SaveTree(FILE *, Node *, BitSequence) mit den notwendigen Parametern aufgerufen, wobei der Rückgabewert den allerletzten Rest des codierten Bitstreams darstellt, der von der nächsten Funktion verarbeitet wird
• Für Informationen zu dieser Funktion klicken Sie hier

Top

Walter Scherer

Headerdateien

• Es wird die globale Fehlervariable temp_num_error definiert. Das extern gibt an, dass die Variable schon in einer anderen Datei definiert wurde und verhindert eine Neuanlage der Variable

• Hier werden die Funktionsprototypen für die Statistikfunktion des Programms definiert
• Die Funktionen werden aus Übersichtlichkeitsgründen hier nicht beschrieben. Klicken Sie auf den jeweiligen Link, um mehr über die Funktionen zu erfahren
• double start_general_statistics(char *)
• double get_size_of_file(char *, int)
• int get_number_of_chars(char *)
• void calc_entropy(char *, int)
• FILE *open_file_read_access(char *)
• void calc_avg_length_of_code(BitSequence *)
• void calc_coding_percentage(double, double)

Top

Walter Scherer

• Die Konstanten LEFT und RIGHT werden mit 0 bzw. 1 initialisiert, um die linken bzw. rechten Kinder eines Knotens im Huffman-Baum anschaulich und bequem ansprechen kann
• REQUESTED EXTENSION gibt vor, wie die Erweiterung der Zieldatei auszusehen hat. Ändern Sie die Erweiterung, so müssen Sie darauf achten, dass die Angabe der Länge der Erweiterung in der Zeile darunter (LENGTH_OF_EXTENSION) mit Ihrer Angabe übereinstimmt ("nice" hat 4 Buchstaben, daher Länge 4)

• Diese Struktur dient zum Darstellen der Knoten des Huffman-Baums. Sie enthält:
• cContent (Inhalt des jeweiligen Knotens)
• ldProbability (Wahrscheinlichkeit des Auftretens dieses Buchstabens (bei Blattknoten ist Buchstabe angegeben durch cContent) bzw. der Summe aller darunter liegenden Knoten, wenn Knoten kein Blattknoten ist)
• iSimpleNode (Informationsinteger: Ist Knoten ein Blattknoten, dann ist iSimpleNode 1, ansonsten 0)
• *pt_Up (Pointer auf den Vaterknoten)
• *pt_Down (Pointer auf das linke und rechte Kind des Knotens (Es handelt sich um einen Binärbaum!))
• *pt_Next (Pointer auf den Listennachbarn)
• Die Struktur bekommt einen Alias-Namen Node statt _Node

• Diese Struktur dient zum Darstellen der Bit Sequenz (des Codes). Sie enthält:
• *Code (Pointer auf die Codefolge)
• length (Länge des Codes)
• Die Struktur bekommt den Namen BitSequence

• void control_coding(char *, char *)
• void calc_probability(int, double *)
• void count_char(int, double *)
• double *huffman_analyse_program(char *)
• Node *CreateTree(double *)
• Node *CreateTreeFromFile(FILE *, BitSequence *)
• Node *CreateList(double *)
• Node *CreateNode(int, char, double, Node *, Node *, Node *, Node *)
• Node *InsertNode(Node *, Node *)
• void DestroyTree(Node *)
• void TraverseTree(Node *, char *, void (*ManipulateNode)(Node *, char *, void *), void *)
• void TraverseTreePreorder(Node *, char *, void (*ManipulateNode)(Node *, char *, void *), void *)
• void TraverseTreeforSave(Node *, char *, void (*ManipulateNode)(Node *, char *, void *), void *, FILE *)
• void TraverseTreeforRead(Node *, char *, void (*ManipulateNode)(Node *, char *, void *), void (*ManipulateNode1)(Node *pt_ActualNode, char *pt_Depth, void *pt_ExtraData, FILE *pt_file), void *, FILE *)
• void ReadLeftChildFromFile(Node *, char *, void *, FILE *)
• void ReadRightChildFromFile(Node *, char *, void *, FILE *)
• void DeleteNode(Node *, char *, void *)
• void AddNodeToCodingTable(Node *, char *, void *)
• SaveNodetoFile(Node *, char *, void *, FILE *)
• int CreateBitSequence(char *, BitSequence *)
• double PowerOf(long, int)
• int IsBitSet(int, char)
• void ShiftLeft(BitSequence *)
• int IsBitSetOfBS(BitSequence, unsigned char)
• BitSequence *CreateCodingTable(Node *)
• void DestroyCodingTable(BitSequence *)
• void CompressFile(FILE *, FILE *, BitSequence *, BitSequence, char)
• void DecompressFile(char *, char *)
• int WriteBitSequenceToFile(FILE *, BitSequence *, BitSequence *)
• char GetBitFromFile(FILE *, BitSequence *)
• char GetByteFromFile(FILE *, BitSequence *)
• int GetBitSequenceFromFile(FILE *, BitSequence *)
• BitSequence SaveTree(FILE *, Node *, BitSequence)
• void OpenFiletoSave(char *, char *, Node *, BitSequence *, char)

Top

Walter Scherer

• Diese Datei dient als zentrale Bibliothekseinbindungsdatei und wird in fast jede Source-Datei inkludiert
• Zur Erklärung der C-Headerdateien in einer ausführlichen Dokumentation nachsehen.

Top

Walter Scherer

• Diese Datei definiert die Funktionsprototypen für die Source-Datei nice_main.c
• int check_target_extension(char *)
• int check_parameters_main(int, char *[])
• void usage()

Top

Walter Scherer