Hi,
mich interessiert, wie dateien z. B. gezipte werden können.

Ich könnte mir vorstellen, dass zum beispiel gleiche Bytes, die hintereinander stehen durch durch den Wert und die Anzahl beschrieben werden, aber eben das versteh ich nicht, weil in einer Datei Bytes und nur Bytes mit einem Wert von 0..255 stehen können. Wie kann dann der Entzipper wissen, wann der oben beschriebene Fall vorliegt?

Oder vielleicht wird das ja auch ganz anders gemacht.

Würde mich freuen, wenn mir jemand helfen kann...

Es gibt da so einige Möglichkeiten. Z.B. Enthropiekodierung. Du weist ja, wie eine ANSI-Tabelle aussieht. Jetzt steht aber in der Spalte mit den Zahlen nicht mehr 8 Bit-Gruppen sondern Gruppen zu 2 - 4 Bits, je nach Häufigkeit. HUFFMAN-CODE. Das hat nur den Nachteil, dass du irgendwo den Huffman-Baum abspeichern musst, und der zieht massig Platz.
Eine Methode der Textkomprimierung ist zum Beispiel die Referenzierung. Das sieht dann so aus:

wird zu

Die ganzen -3 im zweiten Code sind die Referenzen zu "drei Worte vorher". Wie du bemerkt hast, steht "ein" zweimal da. Ja, weil einmal ist es ja groß geschrieben. Wir wollen ja verlustfrei komprimieren. Das andere gibt es auch, die verlustbehaftete Komprimation. Wird z.B. bei Fotos angewendet (digitalen, natürlich) und das gibt dann sog. Artefakte. Die sieht man aber erst bei sehr starker Vergrößerung.
Es gibt aber noch anderes. Wiki macht dich schlau.
Tschö,
nullplan

Das hab ich mir gedacht, dass es so oder so ähnlich geht.
Aber was ich nicht verstehe: was ist wenn in der Quell-Datei steht

Ein Vertrag ist ein -3 -3 -3 -3,aber nur unter Ferengi.

Wenn die datei dann enpackt wird kommt ja was falsches raus!

Die Komprimierung einer Datei läuft immer Byteweise ab.

Am besten kann man da LZ77 hernehmen (was die Grundlage vieler heutiger Algorithmen bietet):

Gegeben sei ABCABCABC

Die ersten zwei Zeichen können nicht komprimiert werden
--> A übertragen --> A merken
--> AB --> Eintrag unbekannt --> Neuen Eintrag anlegen (AB, 256), A senden, B merken
--> BC --> Eintrag unbekannt --> Neuen Eintrag anlegen (BC, 257), B senden, C merken
--> CA --> Eintrag unbekannt --> Neuen Eintrag anlegen (CA, 258), C senden, A merken
--> AB --> Eintrag bekannt --> Keinen Eintrag anlegen, nichts senden --> 256 merken
--> ABC --> Eintrag unbekannt --> Neuen Eintrag anlegen (ABC, 259) ID256 senden, C merken
--> CA --> Eintrag bekannt --> Keinen Eintrag anlegen, nichts senden --> 258 merken
--> CAB --> Eintrag unbekannt --> Neuen Eintrag anlegen (CAB, 260) ID258 senden, B merken
--> BC --> Eintrag bekannt --> Keinen Eintrag anlegen, nichts senden --> 257 merken
--> Text zu ende: Gemerkte ID257 senden

Beim dekodieren funktioniert das genauso ... LZ77 wird meist noch mit Huffmann-kodierung kombiniert, um die Darstellung der IDs im Text eindeutiger zu machen und trotzdem Platz zu sparen ...

Näheres steht z.B. aber auch in der Wiki...

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

bokaj hat folgendes geschrieben:

Das hab ich mir gedacht, dass es so oder so ähnlich geht. Aber was ich nicht verstehe: was ist wenn in der Quell-Datei steht Ein Vertrag ist ein -3 -3 -3 -3,aber nur unter Ferengi. Wenn die datei dann enpackt wird kommt ja was falsches raus!

Nee, die geschichte mit den -3 steht in der Zip. Vielleicht war die überschrift verwirrend. Also, der Unzipper betrachtet die Zip und sieht dort:

• "Ein " -> schreibe ich in Zieldatei, Id -1
  
• "Vertrag " -> schreibe ich in zieldatei, dekrementiere ID von Ein zu -2, setze ID -1
  
• "ist " -> schreibe ich in Zieldatei, dekrementiere vordere IDs um eins, setze ID -1
  
• "ein " -> schreibe ich in Zieldatei, dekrementiere vordere IDs um eins, setze ID -1
  
• -3 -> Momentanes Wort von -3: "Vertrag " -> schreibe ich in Zieldatei, dekrementiere vordere IDs
  
• -3 -> Momentanes Wort von -3: "ist " -> schreibe ich in Zieldatei, dekrementiere vordere IDs
  
• usw.
  

@BenBE: Dieses LZ777 sieht ganz gut aus. Ich bau mir gerade einen eigenen Zipper (mit eigenem Format), da kann ich ja den Algo verfeinern (Momentan nur Huffman-Code, und nichtmal der richtig). Danke für den Tipp.
Tschö,
nullplan

@nullplan: Was inimmste? Static Huffmann oder Adaptives Huffmann (Also Baum vorher berechnen oder on-the-fly)? Ich hab's mal geschafft für ne Z80-CPU die Komprimierung mit <2KB RAM auszuführen ... (Wobei die 2KB nicht mal linear lagen). An der Dekomprimierung bin ich dann gescheitert ... (bzw. hab's nicht weiter verfolgt).

Ansonsten kannst Du Dir auch mal die Fließkomma-Kodierung anschauen (die basiert auf Intervall-Schachtelung und holt noch ein wenig mehr als Adaptives Huffmann raus). Hab's aber selber noch nicht implementieren können (weder Zeit, noch Lust, noch Muße zu gehabt *g*)

Aber all das findest Du auch in der Wiki unter dem Stichwort (verlustfreie) Komprimierung ...

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Hab mal ne Frage.
Soweit ich weis werden die "Schlüssel" in einer Art "Wörterbuch" mit in die Datei gespeichert.
Könnte man nicht stattdessen ein Wörterbuch mit dem Zip Programm mitliefern?

Ist sowohl für Adaptives Huffman als auch LZ77 nicht nötig, da das "Wörterbuch" beim Packen und Entpacken allein aus den Informationen der Datei erstellt werden kann.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

@BenBE: In Anbetracht der Tatsache, dass ein Huffmann-Baum mit (in worst case) 256 Blättern massig Speicherplatz zieht, nutze ich nur einen Huffman-Baum pro Output-File. Mein Format soll nämlich mal ganze Dateisysteme (Ordner nebst unterordnern) komprimieren können. Was adaptive Huffmans sind, weis ich nicht: Ich mache den Baum nach einer Häufigkeitstabelle, die ich erstelle, indem ich byteweise durch alle Dateien hüpfe und in einem Array[0 .. 255] of longword das Element der Nummer des gerade gelesenen Bytes inkrementiere. (Ja, ich nulliere das Array vorher.) Alle Elemente, die nach der Schleife noch 0 sind, werden zur Erstellung des Baumes außer acht gelassen. Und dann kommen die Erstellungsregeln. (Ordne den Baum nach Häufigkeiten, beim kleinsten beginnend. Verknüpfe die zwei obersten Teilbäume. Mach das, bis es nur noch einen Baum gibt.)
Ich glaube, ich ändere das noch mal. Ich habe nach adaptive huffman gegoogelt und eine ziemlich gute Quelle gefunden. Ein paar Flussdiagramme nach Pascal übersetzen und etwas denken sollte nicht das Problem werden.
Tschö,
nulplan