Das ZIP-Datenkompressionsverfahren

Letztmalig dran rumgefummelt: 05.07.26 00:30:19

	Zip & Co - ZIP ist übrigens die Abkürzung für „Zigzag Inline Package", deutsch so etwas wie „zeilenweise im Zickzack gefaltetes (Daten-)Paket". Es wurde 1989 von Phil Katz geschrieben, der es als PKZIP (Phil Katz's Zip) vertrieb. Zip ist so bis heute der meistverbreitete Standard zur verlustfreien Datenkomprimierung. Andere bekannte Komprimierer sind ARJ (nach seinem Erfinder Archiver von Robert Jung" genannt) und RAR (auch nach dem Erfinder "Eugene Roshal Archiver" benannt).
	1. Problembeschreibung 2.  Informationsgehalt von Zeichen und Zeichengruppen 3. Häufigkeitsverteilung von Zeichen 4. Bits reduzieren - egal, WIE!!! 5. Präfixe, Fano-Bedingung - +++ START +++ Stop+++ 6. Weiterführende Literatur 7. Linkliste zum Thema 8. Verwandte Themen
	Probleme & Problemlösungsverfahren   Logo für den ZIP-Algorithmus inhaltlich auf korrektem Stand - evtl. partiell unvollständig ;-) Wissen für Fortgeschrittene der Informatik Informatik-Profi-Wissen
	Quellen: Abenteuer Informatik Seite 121 ff. Technische und Theoretische Informatik  Seite ???
	ANSI-Code UNICODE Mit sechsundzwanzig Zeichen lässt sich die ganze Welt beschreiben!Abger es sollen nur so wenig wie mögliche Bits zur Speicherung oder Übertragung eingesetzt werden. Geht das überhaupt??? ASCII-Code-Tabelle ASCII- bis UNICODE
	die großen Acht Zeichenzähler Bi- und Trigramme suchen Frequenzanalyse vielseitiger Codewandlere ... 10 Zeichen genügen!!! ENIRASTD ENIRATHU ENIRSTAD ENIRSTAH ENIRSTAL ENIRSATU ENIRTSAH ENISARTU ENISATRD ENISRATD ENISRTUA ENISRTAU ENISTRAD ENISRATH ENRIADST ENRIASDT ENRISTAD ENRISATD ENRISATH ENRISDAT ENRITSAH ENRISATD ENRISATU ENRISHUA die Häufigkeitsverteilung bleibt beim CÄSAR-Chiffre ja erhalten - also analysieren wir diese einmal ... ... hier auch das Programm mit kleinen Macken - aber für unsere Zwecke durchaus hinreichend ;-) Bi- & Trigramme suchen Programm zum Auszähllen von Bi- und Trigrammen Frequenzanalyse   Codewandler Programm Codewandler (als EXE funktionieren nicht alle Codes) Programm Codewandler als ZIP-Archiv - zum Start Project1.exe das Verfahren beruht auf der Tatsache, "... dass die _ehn haeu_i_sten _u_hsta_en i_ Deuts_hen bereits drei _ierte_ des _esa_ttextes _i_den."
	Sechs Bit tiefe Zeichentabelle - der ASCII sieben und der ANSI-Code hat acht Bit Sechs Bit tiefe Zeichentabelle - Auslesen von Daten     Sechs Bit Code-Baum Binärbaum für Sechs-Bit-Code DIYS im CorelDraw 11.0-Format Sechs Bit Code-Baum - das Vorgehen beim Auslesen Binärbaum für Sechs-Bit-Code Reader DIYS im CorelDraw 11.0-Format P mit Bittiefe sechs würde zu: 000101 Jeder Tiefenstrich nach rechts repräsentiert genau ein Bit mit den Werten "0" oder "1" Pfeil mit Richtung oben - schreibe 0 Pfeil mit Richtung unten - schreibe 1

1. Problembeschreibung

	Bei der Datenkomprimierung werden redundante oder unnötige Informationen in einer Datei reduziert. Dadurch benötigt die Datei weniger Speicherplatz auf der Festplatte und lässt sich im Internet oder über Netzwerke wesentlich schneller übertragen. e
	unser vereinfachter ASCII-Codesatz als binärer Baum unser vereinfachter ASCII-Codesatz in ein DELPHI 6.0-Programm gegossen unser vereinfachter ASCII-Decoder in ein DELPHI 6.0-Programm gegossen  unser vereinfachter ASCII-Codesatz unser vereinfachter ASCII-Codesatz als binärer Baum zum selbst ausdecodieren   Binärbaum für vereinfachten ASCII-Code -Binärbaum für vereinfachten ASCII-Code im CorelDraw11.0-Format Binärbaum für vereinfachten ASCII-Code in Software Binärbaum für vereinfachten ASCII-Code als startbare EXE-Datei Binärbaum für vereinfachten ASCII-Code als ZIP-Archiv   Binärbaum für vereinfachten ASCII-Code in Software Binärbaum für vereinfachten ASCII-Code als startbare EXE-Datei Binärbaum für vereinfachten ASCII-Code als ZIP-Archiv ACHTUNG: funktioniert nur mit dem nebenstehenden ZIP-Codierer!!! Zeichen Code Zeichen Code Zeichen Code Zeichen Code SPACE 00000 H 01000 P 10000 X 11000 A 00001 I 01001 Q 10001 Y 11001 B 00010 J 01010 R 10010 Z 11010 C 00011 K 01011 S 10011 . 11011 D 00100 L 01100 T 10100 , 11100 E 00101 M 01101 U 10101 : 11101 F 00110 N 01110 V 10110 - 11110 G 00111 O 01111 W 10111 # 11111 Binärbaum für vereinfachten ASCII-Code im DIYS-Format Binärbaum für vereinfachten ASCII-Code DIYS im CorelDraw 11.0-Format
	AGATGCCGTTACGA wird nun zu: 0000100111000011010000111000110001100111101001010000001000110011100001 also 70 Bit
	GTCCAGAATTGATCCACGTTCCCAGTGATTCGTCGATTGCTTACCGTATGCCTGAGTCAGCAGTAGTTCATCCTAGGCCTACTAGCGATCAGGTACAT (99 Eingabezeichen) wird nun zu: 001111010000011000110000100111000010000110100101000011100001101000001100011000010001100111101001010000011000110001100001001111010000111000011010010100 000110011110100000110011100001101001010000111000111010010100000010001100011001111010000001101000011100011000111010000111000010011110100000110000100111 000110000100111101000000100111101001010000011000011010000011000111010000001001110011100011000111010000001000111010000001001110001100111000011010000011 0000100111001111010000001000110000110100 also 490 Bit
	Arbeitstexte   Auswertung  ... hier einige Arbeitstexte zum Ausprobieren   der Originaltext in der Software bringt es mit 5 Bit-Codierung für alle Zeichen auf 8945 Bit - gesucht sind Möglichkeiten, die Anzahl der Zielbits zu reduzieren ohne dass Informationen verloren gehen die erste Komprimierungsvariante bringt 7738 Bit in der Zielbitmenge - das sind  86,506 %
	Nachfafolgend tasten wir uns an Möglichkeiten aber auch auftretende Probleme heran, welche zum Ziel hben, den zu übertragenden Bitstrom wesentlich zu reduzieren ohne dabei Informationen zu verlieren.
	unser reduzierter ASCII-Codesatz als binärer Baum unser vereinfachter ASCII-Codesatz in ein DELPHI 6.0-Programm gegossen unser vereinfachter ASCII-Codesatz Ergebnisanalyse Binärbaum für reduzierten ASCII-Code -Binärbaum für reduzierten ASCII-Code im CorelDraw11.0-Format Binärbaum für reduzierhten ASCII-Code in Software Binärbaum für vereinfachten ASCII-Code als startbare EXE-Datei Binärbaum für vereinfachten ASCII-Code als ZIP-Archiv Zeichen Code A 00 C 01 G 11 T 11 Vorteil: die Zeichenfolgen ruduzieren sich um jeweils 2 Bit für jedes Zeichen Nachteil: der Zeichenvorrat ist auf 4 Zeichen beschränkt
	AGATGCCGTTACGA (14 Eingabezeichen) werden nun zu: 00 01 00 11 01 01 01 01 11 11 00 01 01 00 also 42 Bit
	AGTCCAGAATTGATCCACGTTCCCAGTGATTCGTCGATTGCTTACCGTATGCCTGAGTCAGCAGTAGTTCATCCTAGGCCTACTAGCGATCAGGTACAT (99 Eingabezeichen) werden nun zu: 00 01 11 01 01 00 01 00 00 11 11 01 00 11 01 01 00 01 01 11 11 01 01 01 00 01 11 01 00 11 11 01 01 11 01 01 00 11 11 01 01 11 11 00 01 01 01 11 00 11 01 01 01 11 01 00 01 11 01 00 01 01 00 01 11 00 01 11 11 01 00 11 01 01 11 00 01 01 01 01 11 00 01 11 00 01 01 01 00 11 01 00 01 01 11 00 01 00 11 also 198 Bit
	Fazit: verschlüsseln kann ich aber dabei Bits einsparen geht nicht, da das komplette Bitmuster zur Identifizierung der Zeichen benötigt wird.

2. Informationsgehalt von Zeichen und Zeichengruppen

	Unter Annahme der Tatsache, dass wir nicht die Kaprekartiefe, sondern die Regelmäßigkeit der Wiederkehr der einzelnen Werte selbiger suchen, fällt die Aufgabe heute typischerweise in den Bereich der nicht entscheidbaren Probleme. Und diese Beschreibung selbst zu finden, dürfte dann schon in die Klasse der komplexen Probleme fallen.
	Klartext ohne Konsonanten - 145 Zeichen fehlen Klartext ohne Vokale - etwa gleiche Anzahl Zeichen fehlen Klartext   Klartext ohne Konsonanten Klartext ohne Vokale Klartext Vokale außer auslautend haben also gar keinen Informationsgehalt für die Sprache - sie verbinden nur Konsonantengruppen

3. Häufigkeitsverteilung von Zeichen

	Das Grundprinzip besteht darin, systematisch mit den kleinstmöglichen Werten in den kleinstmöglichen Boxen die Gegenstände abzulegen und anschließend systematisch kleinere Gesamtwerte durch größere volumengleich zu ersetzen, Nachfolgend eine Idee, welche erst einmal nicht schlecht aussieht!
	unser vereinfachter ASCII-Codesatz mit Bitgruppen nach Häufigkeitsverteilung - auf den ersten Blick perfekt - aber was sagt der Zweite? unser vereinfachter ASCII-Codesatz unser vereinfachter ASCII-Codesatz als binärer Baum zum selbst ausdecodieren unser vereinfachter ASCII-Codesatz in ein DELPHI 6.0-Programm gegossen SPACE und E mit 3 Bit codieren N, I, S und R mit vier Bit codieren A bis G mit fünf Bit darstellen die verbleibenden Zeichen mit 6 Bit Grundidee: die oft benötigten Zeichen bekommen kürzere Bitgruppen Problem: Erkennen, wann eine Bitgruppe beendet ist und die neue beginnt SPACE: 000 L 00101 V 001000 E 001 C 00110 J 001001 N 0000 G 00111 Y 001010 I 0001 M 000000 X 001011 S 0010 O 000001 . 001100 R 0011 B 000010 , 001101 A 00000 W 000011 Q 001110 T 00001 F 000100 : 001111 D 00010 K 000101 - 010000 H 00011 Z 000110 # 010001 U 00100 P 000111     Zeichen Häufigkeit Zeichen Häufigkeit Zeichen Häufigkeit Zeichen Häufigkeit SPACE 18,50 % D 4,14 % B 1.54 % Y 0.03 % E 14,17 % H 3,88 % W 1,54 % X 0,02 % N 7,96 % U 3,54 % F 1,35 % . 0,02 % I 6,15 % L 2,80 % K 0,99 % , 0,02 % S 5,92 % C 2,49 % Z 0,92 % Q 0,02 % R 5,70 % G 2,45 % P 0,64 % : 0,01 % A 5,30 % M 2,06 % V 0,55 % - 0,01 % T 5,01 % O 2,04 % J 0,22 % # 0,01 % Binärbaum für vereinfachten ASCII-Code im DIYS-Format Binärbaum für vereinfachten ASCII-Code DIYS im CorelDraw 11.0-Format   Binärbaum für vereinfachten ASCII-Code in Software Binärbaum für vereinfachten ASCII-Code als startbare EXE-Datei Binärbaum für vereinfachten ASCII-Code als ZIP-Archiv
	HANS ZOG EIN TUECHLEIN AUS DER TASCHE, WICKELTE DEN KLUMPEN HINEIN, SETZTE IHN AUF DIE SCHULTER UND MACHTE SICH AUF DEN WEG NACH HAUS.
	Arbeitstexte   Auswertung  ... hier einige Arbeitstexte zum Ausprobieren   der Originaltext in der Sotware bringt es mit 5 Bit-Cdierung für alle Zeichen auf 8945 Bit - gesucht sind Möglichkeiten, die Anzahl der Zielbits zu reduzieren ohne dass Informationen verloren gehen die erste Komprimierungsvariante bringt 7738 Bit in der Zielbitmenge - das sind  86,506 % Problem: der Bitstrom kann nicht wieder in den Originaltextgewandelt werden, da keine Kennung vorhanden ist, wann eine neue Bitgruppe startet - jede kann ja 3, 4, 5 oder 6 Bit lang sein die zweite Komprimierungsvariante bringt 7732 (der Doppelpunkt musste entfallen - der war aber im Originaltext einmal enthalten, auch das #-Zeichen ist nicht mehr dabei, aber im Text hier nicht enthalten) Bit in der Zielbitmenge - das sind  86,643 %
	Fazit: verschlüsseln kann ich und dabei Bits einsparen entsprechend der Häufigkeit strukturiert klappt auch. Und wenn alle Texte die gleiche Verteilung hätten, könnte ich auch die Zeichengruppen eindeutig erkennen. Dem ist aber nicht so, und damit kann ich zwar kopmprimieren, aber nicht wieder dekomprimieren.

4. Bits reduzieren - egal, WIE!!!

	Das Grundprinzip besteht immer noch darin, systematisch die am häufigsten vorkommenden Zeichen durch mäglichst kleine Bitgruppen zu ersetzen, aber diese beim wieder einlesen 100 %ig genau zurück zu erhalten.
	unser vereinfachter ASCII-Codesatz mit Bitgruppen nach Häufigkeitsverteilung unser vereinfachter ASCII-Codesatz unser vereinfachter ASCII-Codesatz als binärer Baum zum selbst ausdecodieren unser vereinfachter ASCII-Codesatz in ein DELPHI 6.0-Programm gegossen   SPACE und E mit 3 Bit codieren N, I, S und R mit vier Bit codieren A bis G mit fünf Bit darstellen die verbleibenden Zeichen mit 6 Bit Grundidee: die oft benötigten Zeichen bekommen kürzere Bitgruppen Präfix-Bittgruppen machen das Erkennen der neuen Bitfolge möglich Problem: mit 2 Präfibits und vier Codelängen sind maximal 30 Zeichen möglich SPACE: 000 L 10101 V 111000 E 001 C 10110 J 111001 N 0100 G 10111 Y 111010 I 0101 M 110000 X 111011 S 0110 O 110001 . 111100 R 0111 B 110010 , 111101 A 10000 W 110011 Q 111110 T 10001 F 110100 - 111111 D 10010 K 110101     H 10011 Z 110110     U 10100 P 110111     Zeichen Häufigkeit Zeichen Häufigkeit Zeichen Häufigkeit Zeichen Häufigkeit SPACE 18,50 % D 4,14 % B 1.54 % Y 0.03 % E 14,17 % H 3,88 % W 1,54 % X 0,02 % N 7,96 % U 3,54 % F 1,35 % . 0,02 % I 6,15 % L 2,80 % K 0,99 % , 0,02 % S 5,92 % C 2,49 % Z 0,92 % Q 0,02 % R 5,70 % G 2,45 % P 0,64 % : 0,01 % A 5,30 % M 2,06 % V 0,55 % - 0,01 % T 5,01 % O 2,04 % J 0,22 % # 0,01 % Binärbaum für vereinfachten ASCII-Code im DIYS-Format Binärbaum für vereinfachten ASCII-Code DIYS im CorelDraw 11.0-Format   Binärbaum für vereinfachten ASCII-Code in Software Binärbaum für vereinfachten ASCII-Code als startbare EXE-Datei Binärbaum für vereinfachten ASCII-Code als ZIP-Archiv Binärbaum für vereinfachten ASCII-Code in Software Binärbaum für vereinfachten ASCII-Code als startbare EXE-Datei Binärbaum für vereinfachten ASCII-Code als ZIP-Archiv
	HANS ZOG EIN TUECHLEIN AUS DER TASCHE, WICKELTE DEN KLUMPEN HINEIN, SETZTE IHN AUF DIE SCHULTER UND MACHTE SICH AUF DEN WEG NACH HAUS.
	Fazit: hier nun habe ich den Lösungsansatz, welcher zum gewünschten Erfolg führt. Grundlage beim Decodieren ist nun, dass die Bitgruppen eine Zwei-Bit Gruppenkennung haben. Damit lassen sich vier Gruppen einteilen und je nach Häfigkeitszuordnung verschieden lange Bitgruppen organisieren und trotzdem eindeutig erkennen.

5. Präfixe, Fano-Bedingung - +++ START +++ Stop+++

6. Weiterführende Literatur

	Datenkompression vom Fachmann

7. Links zum Thema

	http://www.mathematische-basteleien.de/kaprekarzahl.htm

8. Verwandte Themen

	Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.
	das 8-Damen-Problem das Cliquenproblem das Dominoproblem das Entscheidbarkeitsproblem das Erfüllbarkeitsproblem die Fibonacci-Zahlen das Wortproblem das Hamiltonproblem das K-Farben-Problem das Flaggenproblem das Halteproblem das Königsberger Brückenproblem das Philosophenproblem das Teilsummensummenproblem das Post'sche Korrespondenz-Problem das Rucksackprolem (Knapsackproblem) das Rundreiseproblem - aber: beachte die Mächtigkeit! das Springerproblem die Türme von Hanoi - mit hoher Anzahl von Scheiben wird das Problem praktisch nicht lösbar - 64 ist bereits enorm hoch das Knotenüberdeckungsproblem The Busy Beaver-Problem das Spannbaumproblem der Maze-Running-Algorithmus das Schachspiel Greedy Algorithm das Maximalflussproblem das Syntheseproblem   das k-Next-Neighbor-Problem   Schwarmintelligenz ... fehlererkennende Algorithmen -  ISBN-Nummer das Binärbaumproblem geometrischen Probleme Dijkstra-Algorithmus Fermat'sches Problem FERMAT's letzter Satz   ZIP-Algorithmus   Bresenham-Algorithmus   der Huffman-Code LZW-Kompression   Quadratsummen-Problem   die glücklichen & traurigen Zahlen   Smarandache-Wellin-Zahlen der austarierte Baum   Trunkierbare Primzahlen   FERMAT'scher Großer Satz   Eulerkreis
	Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost am 7. Juni 2026 um 16.44 Uhr