Donnerstag, 2018-11-15, 8:24 PM Willkommen Interessent

Video Game Developers Forum

Suche
Menü
Short News
SNpowered by ShortNews.de
News Verzeichnis
[ Neue Beiträge · Teilnehmer · Forumregeln · Suche · RSS ]
  • Seite 1 von 1
  • 1
Moderator in diesem Forum: Goblin1405  
Forum » Programmiersprachen uvm. » Programmieren allgemein » Datenkompression
Datenkompression
Goblin1405Datum: Montag, 2010-06-21, 10:43 PM | Nachricht # 1
Coder
Gruppe: Administratoren
Nachrichten: 89
Auszeichnungen: 0
Status: Offline
Datenkompression

Datenkompression oder Datenkomprimierung wird angewendet, damit weniger Speicherplatz gebraucht wird oder um die Übertragungsgeschwindigkeit zu erhöhen. Die Datenorganisation wird hierfür geändert und muss bei der schließlichen Nutzung reorganisiert werden. Man spricht vom Kodieren und Dekodieren.

Die Datenmenge wird reduziert, indem eine günstigere Repräsentation bestimmt wird, mit der sich die gleichen Informationen in kürzerer Form darstellen lassen. Diesen Vorgang übernimmt ein Kodierer, und man bezeichnet den Vorgang als Kompression bzw. Kodierung. Die Umkehrung bezeichnet man als Dekompression oder Dekomprimierung. Man spricht von einer verlustfreien Kompression (oder verlustfreien Kodierung), wenn die kodierten Daten nach Anwendung der entsprechenden Dekodiervorschrift exakt denen des Originals entsprechen. Dies ist beispielsweise bei der Kompression ausführbarer Programmdateien notwendig. Verlustbehaftet wird die Kompression oder Kodierung genannt, wenn sich die Daten im allgemeinen nicht fehlerfrei rekonstruieren lassen. Solche Verfahren werden häufig zur Bildkompression oder Audiodatenkompression eingesetzt. Werden mehrere Dateien komprimiert, können diese vorher durch ein Packprogramm zusammengefasst werden. Enthalten die Dateien Gemeinsamkeiten, so wird dadurch die Kompression verbessert.

In der Nachrichtentechnik wird das Kodieren von Nachrichten aus einer Quelle durch einen Sender als Quellenkodierung bezeichnet.

Redundanz- und Irrelevanzreduktion

Die Datenkompression wird teils durch „günstigere Repräsentation“, das heißt Vermeiden von Redundanz und Erhöhen der Entropie, teils durch Weglassen von Information erreicht. Wenn die Daten mit einem Dekompressionsverfahren wieder originalgetreu hergestellt werden, arbeitet es verlustfrei. Man spricht dann von Redundanzreduktion. Andernfalls ist es verlustbehaftet. In diesem Fall spricht man von Irrelevanzreduktion. Beide Verfahren können kombiniert werden.

Bei der verlustfreien Kompression werden die originären Daten in komprimierte Daten überführt, die die ursprünglichen Informationen vollständig enthalten. Die Überführung muss nicht eindeutig sein, aber auf jeden Fall umkehrbar. Verschiedene Kompressionsprogramme und Heuristiken können unterschiedlich hohe Kompressionsraten eines Kompressionsformates erzeugen.

Die verlustbehaftete Kompression reduziert die Information. Es wird ein Modell zugrunde gelegt, das entscheidet, welcher Anteil der Information für den Empfänger entbehrlich ist. Da eine solche Abbildung nicht mehr eindeutig ist, kann die ursprüngliche Information mittels Dekompression nicht wiederhergestellt werden.
Symmetrische und asymmetrische Kompression

Ein Verfahren zur asymmetrischen Kompression benötigt zum Kodieren (Komprimieren) einen wesentlich höheren zeitlichen Aufwand als zum Dekodieren. Im Gegensatz dazu benötigt ein symmetrisches Verfahren ungefähr gleichviel Zeit für Kompression und Dekompression.
Verfahren

Die theoretische Grundlage bildet die von Mathematikern (Claude Shannon; Andrei Kolmogorow) erarbeitete Theorie der Information und Kommunikation (Informationstheorie). Diese beschreibt den Zusammenhang zwischen Informationsgehalt einer Zeichenkette auf der Basis von Zeichen durch den Begriff der Entropie der Zeichenkette, die im Allgemeinen auf eine bestimmte, minimale Länge gebracht werden kann.

Durch geeignete Kompressionsverfahren erreicht man gute Annäherungen an die Kanalkapazität.

In neuerer Zeit gibt es umgekehrt auch Ansätze, den Informationsgehalt auf die „Nichtmehrverkürzbarkeit“ zurückzuführen (Chaitin).

Speicherung von Text

Texte, sofern sie aus Buchstaben bestehen bzw. als Zeichenketten abgespeichert sind, und somit nicht als Bild (Rastergrafik, typischerweise z. B. eine Bilddatei nach dem Einscannen eines Buches), belegen vergleichsweise wenig Speicherplatz. Dieser lässt sich durch ein Verfahren zur verlustfreien Kompression auf 20 % bis 10 % des ursprünglich von ihr benötigten Platzes reduzieren.

Beispiele:

Ausgangstext: AUCH EIN KLEINER BEITRAG IST EIN BEITRAG
Kodiertext: AUCH EIN KLEINER BEITRAG IST -4 -3

Hier wurde erkannt, dass die Wörter EIN und BEITRAG zweimal auftauchen, und dadurch angegeben, dass diese mit den gerade zurückliegenden übereinstimmen. Bei genauerer Betrachtung könnte dann auch das EIN in KLEINER entsprechend kodiert werden.

Verwandt ist die tokenbasierte Kompression. Häufig wiederkehrende Schlüsselwörter werden durch Abkürzungen, Tokens, ersetzt.

Ausgangstext: Print "Hallo"; Print "Hier"
Kodiertext: 3F "Hallo"; 3F "Hier"


Verfahren der so genannten Entropiekodierung:

* Huffman-Code (in modifizierter Form zum Beispiel für die Fax-Übertragung)
* Arithmetische Kodierung

Präkodierung

Präkodierung umfasst alle Techniken der Datenkompression, welche in Daten vorhandene statistische Abhängigkeiten ausnutzen. Diese Techniken bilden Symbole aus einem Alphabet auf Symbole eines anderen Alphabets ab bzw. unterstützen diesen Prozess. Die Anzahl der Symbole kann sich dabei verändern (im Gegensatz z. B. zu Verfahren der Dekorrelation, welche ebenfalls Korrelationen im Signal auflösen). Oft werden die Ergebnisse nochmals entropiekodiert.

Sehr verschiedene Algorithmen gehören zur Gruppe der Präkodierung: Lauflängenkodierung, Phrasenkodierung (besser bekannt als wörterbuchbasierte Kodierung wie z. B. LZ78 und LZW), Blocksortierung (auch bekannt als Burrows-Wheeler-Transformation), Quadtree-Kodierung und andere.

Heutzutage stehen viele Datenkompressionsprogramme für den Rechnereinsatz zur Verfügung.

Infos aus dem offiziellen WIKI Wikipedia® zum Thema unter der Creative Commons Lizenz. Hier der Link zur Seite und zu den Autoren: klick

LG Euer Admin

 
Forum » Programmiersprachen uvm. » Programmieren allgemein » Datenkompression
  • Seite 1 von 1
  • 1
Suche:

Our Age
Chat Box
Mini Profil


Statistik
Bookmarks
Copyright by GamesArmyLabs © 2018