Projekt ======= Implementierung von Beispiel-Algorithmen ---------------------------------------- Run-Length Encoding ^^^^^^^^^^^^^^^^^^^ **Funktionsweise:** Zunächst werden alle Wiederholungen gesucht, also Sequenzen mit aufeinanderfolgenden, identischen Zeichen. Für jede Gruppe gleicher aufeinanderfolgender Zeichen wird die Anzahl der Wiederholungen gezählt. Anschließend wird statt jedes einzelnen Zeichens nur das Zeichen und die Anzahl an Wiederholungen notiert. .. literalinclude:: code/rle.py :pyobject: rle_compress **Fazit:** Die LRE-Komprimierung bietet einige Vorteile, darunter ihre einfache Implementierung und ihr Verständnis. Sie ist besonders effektiv bei der Komprimierung von Daten mit vielen aufeinanderfolgenden gleichen Zeichen und erfordert daher einen geringen Speicherbedarf für diese Art von Daten. Die Dekomprimierung von LRE-kodierten Daten ist ebenfalls sehr einfach und schnell. Allerdings hat die LRE-Komprimierung auch einige Nachteile. Sie ist bei Daten, die wenige Wiederholungen oder viele unterschiedliche Zeichen enthalten, ineffizient. Aufgrund ihrer Ineffizienz bei nicht-homogenen Daten eignet sich LRE nur für spezifische Anwendungsbereiche. Der Komprimierungsfaktor von LRE hängt stark von der Struktur der zu komprimierenden Daten ab, und sie ist kein Allzweck-Komprimierungsverfahren. Daher sollte LRE nur in Szenarien eingesetzt werden, in denen Daten mit vielen Wiederholungen vorkommen. Die Anwendungsgebiete von LRE umfassen einfache Grafiken und Bilder, insbesondere Schwarz-Weiß-Bilder, sowie die Fax-Kommunikation. In diesen Kontexten kann LRE aufgrund seiner Effizienz bei der Komprimierung von wiederkehrenden Mustern und seiner einfachen Implementierung nützlich sein. Huffman Encoding ^^^^^^^^^^^^^^^^ **Funktionsweise:** Daten sollen effizient komprimiert werden, indem häufig vorkommende Zeichen mit kurzen Binärcodes ersetzt werden und seltene Zeichen mit längeren Binärcodes codiert werden. Zuerst wird die Häufigkeit der Zeichen bestimmt und anschließend ein Huffman- Baum erstellt. Dieser ist ein binärer Baum, bei dem jeder Knoten entweder ein Blattknoten ist, der ein Zeichen und seine Häufigkeit enthält, oder ein innerer Knoten, der die Summe der Häufigkeiten seiner beiden Kindknoten speichert. Die Zeichen mit den niedrigsten Häufigkeiten finden sich in den Blattknoten. .. literalinclude:: code/huffman.py :pyobject: build_huffman_tree Jetzt müssen die Zeichen codiert werden, die codierung ergibt sich aus dem Pfad von der Wurzel zum entsprecenden Knoten des Zeichens. .. literalinclude:: code/huffman.py :pyobject: build_codes Anschließend werden die Zeichen durch die jeweilige Codierung ersetzt. .. literalinclude:: code/huffman.py :pyobject: huffman_encode **Fazit:** Die Huffman-Codierung ist ein effizientes Komprimierungsverfahren, das eine hohe Komprimierungsrate erreichen kann, insbesondere wenn einige Zeichen in der zu komprimierenden Datei häufiger vorkommen als andere. Für eine gegebene Zeichenhäufigkeitsverteilung erzeugt die Huffman-Codierung ein optimal kodiertes Bitmuster, das die durchschnittliche Länge der Codes minimiert. Da die Huffman-Codierung verlustfrei ist, können die Originaldaten exakt wiederhergestellt werden. Diese Methode ist vielseitig einsetzbar und kann auf eine Vielzahl von Datentypen angewendet werden, einschließlich Text, Bilder und Audio. Jedoch hat die Huffman-Codierung auch einige Nachteile. Die Erstellung des Huffman-Baums und der dazugehörigen Codes erfordert eine Vorverarbeitung der Daten, was zusätzliche Rechenzeit und Speicherplatz beansprucht. Da Huffman-Codes variable Längen haben, kann dies die Handhabung und Verarbeitung der kodierten Daten erschweren, insbesondere bei der Dekodierung. Zudem hängt die Effizienz der Huffman-Codierung stark von der Häufigkeitsverteilung der Zeichen ab. Bei sehr kleinen Datenmengen kann der Overhead der Huffman-Codierung die Vorteile der Komprimierung überwiegen. Trotz dieser Nachteile wird die Huffman-Codierung häufig in verschiedenen Anwendungsgebieten verwendet. Ein prominentes Beispiel ist die Bildkomprimierung in JPEG. Ebenso wird sie in der Audiokomprimierung, beispielsweise im MP3-Format, genutzt, um die Daten effizient zu reduzieren. Lempel-Ziv-Welch Algorithmus ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ **Funktionsweise:** Im Gegensatz zum Huffman Encoding verwendet der LZW ganze Zeichenketten und encodiert diese. Als erstes wird ein Wörterbuch initialisiert, dass die ersten 256 möglichen Zeichen/Bytekombinationen, die im Text vokommen könnten, enthält. Der Text wird dann Zeichen für Zeichen durchlaufen. Es wird eine Zeichenkette mit dem aktuellen Zeichen initialisiert. Wenn die aktuelle Kette im Buch gefunden wird, so wird sie um das nächste Zeichen erweitert, dies wird wiederholt, bis eine nicht vorhandene Kette gefunden wird. Diese Codierung, also die Stelle im Wörterbuch, die diese neue Kette hat, wird dann dem komprimierten Ausgabestream angefügt und zum Wörterbuch hinzugefügt. Der LZW-Algorithmus aktualisiert das Wörterbuch, indem er die neu codierte Zeichenkette hinzufügt. Das nächste Zeichen wird als neue Anfangszeichenkette für die weitere Codierung verwendet. .. literalinclude:: code/lzw.py :pyobject: lzw_compress Beispiel: Texteingabe: BABBABABA Wörterbuch .. list-table:: Wörterbuch :header-rows: 1 * - Schritt - Index - Zeichenkette * - 0. - 0 - A * - 0. - 1 - B * - 2. - 2 - BA * - 4. - 3 - AB * - 6. - 4 - BB * - 9. - 5 - BAB * - 13. - 6 - BABA Schritt markiert, wann im Beispielablauf das Wörterbuch erweitert wurde, der Index ist die Codierung. 1. B -> im Wörterbuch (WB) an Stelle (1) 2. BA -> nicht im WB, also BA hinzufügen und (1) ausgeben 3. A -> im WB an Stelle (0) 4. AB -> nicht im WB, also AB hinzufügen und (0) ausgeben 5. B -> im WB an Stelle (1) 6. BB -> nicht im WB, also BB hinzufügen und (1) ausgeben 7. B -> im WB an Stelle (1) 8. BA -> im WB an Stelle (3) 9. BAB -> nicht im WB, also BAB hinzufügen und (3) ausgeben 10. B -> im Wörterbuch (B) an Stelle (1) 11. BA -> im Wörterbuch an Stelle (3) 12. BAB -> im Wörterbuch an Stelle (5) 13. BABA-> nicht im Wörterbuch -> hinzufüguen an Stelle (6) und (5) ausgeben 14. A -> kein weiterer Buchstabe mehr verfügbar, (0) ausgeben Komprimierter Output: 1 0 1 3 5 0 **Fazit:** LZW ist ein verlustfreies Komprimierungsverfahren, bei dem die Originaldaten exakt wiederhergestellt werden können. Diese Methode ist besonders effektiv bei Textdaten und bei Daten, die sich durch wiederkehrende Muster auszeichnen, wie zum Beispiel Quellcode oder strukturierte Daten. Ein wesentlicher Vorteil von LZW gegenüber der Huffman-Codierung ist, dass keine Vorverarbeitung zur Erstellung eines Kodierbaums erforderlich ist. Dies erleichtert die Implementierung und Anwendung in verschiedenen Kontexten. Zudem ist die Dekomprimierung von LZW-kodierten Daten relativ einfach und schnell, da das Wörterbuch während der Dekomprimierung gleichzeitig aufgebaut wird. Allerdings hat LZW auch einige Nachteile. Während der Komprimierung wächst das verwendete Wörterbuch kontinuierlich, was bei sehr großen Dateien zu einem erheblichen Speicherbedarf führen kann. Außerdem kann die LZW-Komprimierung bei Daten, die keine oder nur wenige wiederkehrende Muster aufweisen, ineffizient sein. Die Implementierung des LZW-Algorithmus ist zudem komplexer als bei einfachen Komprimierungsverfahren wie der Lauf-Längen-Kodierung (RLE). Trotz dieser Nachteile wird LZW häufig in bestimmten Anwendungsgebieten verwendet. Dazu gehören insbesondere Bildformate wie GIF und TIFF sowie PDF-Dokumente, wo die Vorteile der verlustfreien Komprimierung und der effizienten Dekomprimierung besonders zur Geltung kommen. Der Performance-Vergleich ^^^^^^^^^^^^^^^^^^^^^^^^^ Um die Leistung der drei Komprimierungsverfahren zu testen, komprimieren wir drei verschiedene Texte mit allen drei Methoden und vergleichen anschließend die Größe der komprimierten Texte. Hierzu haben wir ein Python-Skript erstellt, das die Texte aus einer Datei einliest und nacheinander von allen Komprimierungsverfahren komprimieren lässt. Abschließend überprüfen wir, ob der nach der Dekomprimierung entstandene Text wieder dem Originaltext entspricht. Wir testen mit drei verschiedenen Texten: einem kurzen Text, einem langen Text und einem Text in kyrillischer Schrift. short_text.txt (1833 bytes) .. literalinclude:: code/short_text.txt Ausschnitt aus long_text.txt (9798374 bytes) .. literalinclude:: code/long_text.txt :lines: 1-5 Ausschnitt aus kyrill_text.txt (6899560 bytes) .. literalinclude:: code/kyrill_text.txt :lines: 65-69 Das Python-Skript für den Performance-Test sieht wie folgt aus: .. literalinclude:: code/performance_test.py Ergebnisse ^^^^^^^^^^ Die Ergebnisse unseres Tests sind wie folgt: **short_text.txt (1833 bytes)** .. list-table:: :header-rows: 1 * - Metric - RLE - LZW - Huffman * - Compressed Size (bytes) - 3504 - 1552 - 931 * - Compression Time (ms) - 1 - 8 - 0 * - Decompression Time (ms) - 0 - 6 - 1 * - Compression Ratio - 1.91 - 0.85 - 0.51 **long_text.txt (9798374 bytes)** .. list-table:: :header-rows: 1 * - Metric - RLE - LZW - Huffman * - Compressed Size (bytes) - 9756399 - 1375006 - 2975492 * - Compression Time (ms) - 1148 - 792 - 330 * - Decompression Time (ms) - 284 - 252 - 1529 * - Compression Ratio - 0.996 - 0.14 - 0.30 **kyrill_text.txt (6899560 bytes)** .. list-table:: :header-rows: 1 * - Metric - RLE - LZW - Huffman * - Compressed Size (bytes) - 9487980 - 1176078 - 2082318 * - Compression Time (ms) - 1010 - 623 - 408 * - Decompression Time (ms) - 241 - 243 - 1085 * - Compression Ratio - 1.38 - 0.17 - 0.30 Der Originaltext "short_text.txt" hat eine Größe von 1833 Bytes. Nach der Komprimierung mit RLE beträgt die Dateigröße 3504 Bytes, was bedeutet, dass die Datei nach der Komprimierung größer ist als vorher. Dieses Ergebnis ist nicht unerwartet, da RLE besonders effektiv bei Texten mit vielen Wiederholungen ist, was in diesem kurzen Text nicht der Fall war. Die LZW-Komprimierung hat den Text auf 1552 Bytes reduziert, was einer Reduzierung der Dateigröße um etwa 15 % entspricht. Am effektivsten war die Huffman-Codierung, die den Originaltext auf 931 Bytes komprimieren konnte, was einer Einsparung von fast 50 % entspricht. Der Originaltext "long_text.txt" hat eine Größe von 9798374 Bytes. Die RLE-Komprimierung reduzierte die Dateigröße nur minimal auf 9756399 Bytes, was einer Kompressionsrate von 0.996 entspricht. Dies zeigt, dass RLE für diesen langen Text ebenfalls ineffektiv ist. Die LZW-Komprimierung reduzierte die Größe auf 1375006 Bytes, was einer erheblichen Einsparung von etwa 86 % entspricht. Die Huffman-Komprimierung reduzierte die Dateigröße auf 2975492 Bytes, was einer Einsparung von etwa 70 % entspricht, jedoch bei einer deutlich längeren Dekompressionszeit im Vergleich zu den anderen Methoden. Der Originaltext "kyrill_text.txt" hat eine Größe von 6899560 Bytes. Auch hier führte die RLE-Komprimierung zu einer Vergrößerung der Datei auf 9487980 Bytes, was eine Kompressionsrate von 1.38 zeigt. Die LZW-Komprimierung reduzierte die Dateigröße auf 1176078 Bytes, was einer Einsparung von etwa 83 % entspricht. Die Huffman-Komprimierung reduzierte die Dateigröße auf 2082318 Bytes, was einer Einsparung von etwa 70 % entspricht. Hier war die Dekompressionszeit bei der Huffman-Komprimierung ebenfalls deutlich länger als bei den anderen Methoden. Insgesamt zeigt sich, dass die RLE-Komprimierung für diese Textdateien ineffektiv war und oft zu einer Vergrößerung der Dateigröße führte. Die LZW-Komprimierung erwies sich als sehr effektiv, insbesondere bei großen Textdateien, und konnte die Dateigröße erheblich reduzieren. Die Huffman-Komprimierung war ebenfalls effektiv, wobei sie besonders bei kleinen Texten herausragende Ergebnisse lieferte, jedoch mit einer längeren Dekompressionszeit bei großen Textdateien verbunden war. Vergleich von Bildkomprimierungsverfahren ----------------------------------------- Die folgende Tabelle und die dazugehörigen Bilder vergleichen die drei populären Bildformate: PNG, JPEG und GIF. Diese Formate unterscheiden sich in Komprimierungsart, Bildqualität, Farbhandhabung und Transparenz. Als Grundbild wurde ein ARW (oder RAW) Bild mit der Dateigröße 11.142.144 Bytes (ca.11,1 MB) verwendet. .. list-table:: Vergleich von Bildkomprimierungsformaten :widths: 25 25 25 25 :header-rows: 1 * - Eigenschaft - PNG - JPEG - GIF * - Dateigröße - 4,139,048 Bytes (ca. 4,14 MB) - 893,250 Bytes (ca. 893 KB) - 2,270,466 Bytes (ca. 2,27 MB) * - Bildqualität - Verlustfreie Komprimierung, keine sichtbaren Artefakte, ideal für Detailtreue - Verlustbehaftete Komprimierung, kann zu Artefakten führen, geeignet für moderate Kompression, Dateigröße auf Kosten der Bildqualität reduziert - Verlustfreie Komprimierung, aber begrenzt auf 256 Farben, kann zu Banding führen * - Farbhandhabung - Unterstützt bis zu 48-Bit Farbtiefe, exzellent für Farbverläufe - Unterstützt bis zu 24-Bit Farbe, ausreichend für die meisten fotografischen Zwecke - Begrenzt auf 256 Farben, ungeeignet für farbreiche Bilder * - Transparenz - Volle Alpha-Kanal-Transparenz, ideal für komplexe Bilder - Keine Transparenz unterstützt - Einfache binäre Transparenz, kann zu harten Rändern führen Bildvergleich ^^^^^^^^^^^^^^ Im Folgenden sind die Bilder in den drei Formaten zu sehen, die oben besprochen wurden. Beachten Sie die Unterschiede in der Darstellung von Farben und Details. **PNG-Format:** .. image:: code/cat_image.png :width: 200px :alt: Bild im PNG-Format **JPEG-Format:** .. image:: code/cat_image.jpeg :width: 200px :alt: Bild im JPEG-Format **GIF-Format:** .. image:: code/cat_image.gif :width: 200px :alt: Bild im GIF-Format Zusammenfassung ^^^^^^^^^^^^^^^^^^^ Wann welches Format wählen?: Für hochwertige, bearbeitbare Bilder oder Grafiken mit Transparenz ist PNG die beste Wahl. Für Fotografien und Bilder, die online geteilt werden sollen, wo Dateigröße ein wichtiger Faktor ist, ist JPEG ideal. GIF sollte für einfache Grafiken oder kleine Animationen verwendet werden, besonders wenn eine niedrige Farbtiefe ausreichend ist.