Kann man Daten verlustlos komprimieren?

3 Antworten

Vom Fragesteller als hilfreich ausgezeichnet

Zwei Ansätze:

  • Lauflängen-Kodierung: Wenn viele aufeinanderfolgende Zeichen gleich sind, speichert man nur eines und die dazugehörige Anzahl.
  • Wenn die Daten keine zufälligen Bitfolgen sind, sondern bestimmte Muster aufweisen, kann man die häufiger auftretenden Folgen mit weniger Bits kodieren als die selteneren. Das geschieht z.B. bei der Huffmann-Kodierung. Im Deutschen sind z.B. e,r,n häufige Buchstaben, x,y dagegen selten. Das gleiche gilt für Buchstabenkombinationen: Das q kommt praktisch nur als qu vor, das sch ist auch häufig. sxy ist dagegen nie zu finden. Das kann man nutzen um eine Tabelle der häufigsten Silben zu kodieren und so zu sortieren, dass die häufigsten die wenigsten Bits benötigen.

Beide Methoden kann man kombinieren. Bei einem Foto, das nur unterschiedliche Rottöne enthält, kann man z.B. zunächst die Durchschnittsfarbe berechnen und dann die Unterschiede jedes einzelnen Pixels dazu. Diese Unterschiede werden weniger Bits benötigen, als die Originalwerte.

Ein klassisches und effektives Mittel zum komprimieren ist die Huffmann-Codierung. Der kommt unter anderem bei der Komprimierung zip mit zum Einsatz.

An deiner Zeichenkette könntest du z.B. sehen, dass die Folge 01 gleich 2 mal vor kommt. Du könntest also folgende Kodierung machen:

0 => 01
10 => 00
110 =>10
111 => 11

Die Kodierung ist eindeutig und würde dir für eine andere Kombination ein längeres Ergebnis liefern, aber das ist OK.

Die Grundidee von Komprimierung ist, Muster zu erkennen und zu vereinfachen, oder redundante Teile zu entfernen. Das kann über verschiedene Arten gehen. Bei Musik kannst du z.B. statt jedes digitale Sample für rechts und links vollständig separat zu speichern, die Differenzen zum vorherigen Wert speichern - die in der Regel als deutlich kleinere Binärzahl gespeichert werden können.

Ja, das kann man schon. Es kommt aber auf die zu verwendeten Daten an, wieweit diese die vorhandenen Möglichkeiten ausschöpfen. Wenn man nur reinen Text hat, werden kaum die Hälfte der Möglichkeiten wirklich genutzt. Bei reinen Zahlen mit Leerzeichen und Vorzeichen werden nur rund 5 % der vorhandenen Möglichkeiten genutzt, womit man sehr hohe Kompressionsraten erreichen kann. Ausführbare Programme kommen dagegen wegen ihrer hohen Anteile an binären Werten zu so hohen Nutzung der Möglichkeiten, dass die Daten durch das Komprimieren sogar mehr werden können. Das Komprimierprogramm erkennt dies aber und übernimmt dann die Daten 1:1. Die verwendeten Algorithmen sind sehr ausgeklügelt und deshalb auch von Hersteller zu Hersteller unterschiedlich leistungsfähig. Im Prinzip werden die Daten in Zeichenfolgen von unterschiedlicher Länge aufgeteilt, die jeweils bestmöglich komprimiert werden können. So ergibt sich für jedes Datenvolumen ein statistischer Wert der Komprimierung.

Was möchtest Du wissen?