spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Man komprimiert Daten indem man Wissen über die Struktur der Daten ausnutzt, d.h. wenn du wirklich rein zufällig gleichverteile Daten hast (z.B. wenn du Zufallszahlen speichern willst) kann man kaum komprimieren.


Ein einfach zu verstehendes Beispiel ist: Run-length coding (Wird in Faxgeräten und fast allen Multimediaformaten genutzt).

Du hast eine Reihe von 1 und 0, wobei die 1 viel weniger häufig vor kommt: 0000000010001000000000000010000000000000101

statt dann alle 0'en zu speichern kannst du auch ausnutzen, dass immer viele 0'en aufeinanderfolgen und einfach speichern: Jetzt kommen 8 0'en, und dann eine 1. Danach 3 0'en und wieder eine 1. Du speicherst also nu wie viele 0'en zwischen den 1'en kommen.
8,3,13,13,1 ist dann alles was du speichern musst.


Was z.B. in ZIP Dateien benutzt wird ist ein Variable-Length Code. Das prinzip dahinter ist das folgende: Man weiß z.B. dass in deutscher Sprache das E wesentlich häufiger vorkommt als das Y. In normalen ASCII Code haben beide jedoch genau ein Byte, was eigentlich Verschwendung ist. Für das E sollte man wesentlich weniger Bits brauchen als für das Y. (ASCII enthält auch viele Sonderzeichen die noch viel seltener sind)

Das ist das was man mit der Huffman Kodierung macht. Man sortiert alle Zeichen nach ihren Wahrscheinlichkeiten und gibt denen die am häufigsten vorkommen ein kurzes Codewort, und denen die selten sind ein längeres.


PS: Was noch nicht so klar gesagt wurde: Du kannst keine einzelnen Bits schreiben, dein Computer kann noch nichtmal einzelne Bits verarbeiten. Die kleinsten Elemente die dein PC verarbeiten und in Dateien schreiben kann sind Bytes, d.h. wenn du einzelne Bits schreiben möchtest musst du das Byte so anlegen, dass es genau deine Bits enthält. "Bit Manipulation C++" sollte dir bei Google weiterhelfen.

PPS: Variable-Length Codes sind sog. Entropy Codes, da sie versuchen nur so viele Bits zu verwenden wie wirklich an Informationen in den Daten enthalten sind. http://en.wikipedia.org/wiki/Entropy_(information_theory)