wie funktioniert die Dateikomprimierung?
-
das wär mal ne frage von mir, ich würde nämlich gern ein programm schreiben, welches x dateien packt und dann in ein eigenes dateiformat steckt.
der grobalgorithmus ist mir klar
für jede zu packende Datei:
streams der sourcefile öffnen
Datei komprimieren
header schreiben
header+datei ans ende der Zieldatei schreiben
source datei schließen.verfeinerung: header schreiben
name der datei eintragen
größe der Datei eintragen
(anzahl der durchgänge der komprimierung eintragen)Datei komprimieren:
???also was mich dabei intressiert ist die technik welche dahinter steckt.
Werden beim komprimieren einfach nur bitfolgen durch andere(kürzere) ersetzt?
oder wird was ganz andres gemacht?
-
http://www-user.tu-chemnitz.de/~mfie/compproj/
http://directory.google.com/Top/Computers/Algorithms/Compression/Erstmal genug Lesestoff ...
-
Wenn dir das nicht reicht, google mal nach Huffman Algorithmus
-
ist der huffmann algorithmus denn der, welcher heute maßgeblich genutzt wird?
in den quellen von Bashar(1. link) wurde der algorithmus nicht so hochgelobt
-
RLE-Kompression ist auch recht interessant und
wird von einigen Grafikformaten verwenden.
RLE ist zum Anfang auch um einiges leichter zu
programmieren als die ganzen LZW Verianten.Bye Peter.
-
erstmal ganz rein aus der sicht der informatik gesehen, kann man keine dateien kleiner machen, da du eine bestimmte daten mit einem bestimmten informationsgehalt nicht einfach kürzen kannst, da sonst informationen verloren gehen würden. beim packen ist man darauf angewiesen, dass die daten eine bestimmte verteilung bzw. redundanz aufweisen, d.h. entweder sind bestimmte zeiche besonders oft vertreten und werden deshalb durch kürzere bits repräsentiert (huffmann algo) oder man fasst die redundanten Daten zusammen (RLE/LZW algo).
deshalb kann man z.b. auch keine gepackten daten noch mal großartig packen, da in gepackten daten bereits eine relative gleichverteilung und äußerst geringe redundanz vorliegt.
-
otze schrieb:
ist der huffmann algorithmus denn der, welcher heute maßgeblich genutzt wird?
Huffman wird z.B. als Hilfsalgorithmus bei der JPEG-Komprimierung verwendet. Allein macht er nicht soviel her, da er nur nach Zeichenhäufigkeiten geht und ein «schief» verteiltes Alphabet geraderückt. Aber viele andere Kompressionsalgorithmen hinterlassen eine schiefe Verteilung, die man am Ende für ein paar Extra-Prozente nochmal Huffman-komprimiert.
-
@todo: Was ist Verlustbehafteten verfahren (MP3, JPEG, ...)?
-
da spielt ja nicht nur komprimierung an sich einen rolle, schließlich kannst du aus MP3s usw. keine unkomprimierte file mehr herstellen, die die gleiche qualität bzw. die gleichen informationen beinhaltet! das steht im krassen gegensatz zu "richtigen" komprimierungs-algorithmen, da bei diesen verfahren alle bits 1:1 wiederhergestellt werden. bei mpeg,jpeg,mp3...-codecs werden nur teile aller informationen herausgenommen (also z.b. nur jedes zweite sample usw.) und mit einer auf diesen daten-/informationstyp ausgelegten/optimierten verfahrensweise komprimiert. wobei hier in den meisten fällen auch wieder dinge wie RLE zum tragen kommen. (speziell bei Bildern/JPEGs ist man ja auf redundanz bzw. vorher extra hergestellte redundanz (die sich dann in pixeligen bildern äußert) angewiesen)
-
todo schrieb:
bei mpeg,jpeg,mp3...-codecs werden nur teile aller informationen herausgenommen
Bei JPEG wird AFAIK zuerst jeder 8x8-Pixel-Block in den Frequenzbereich transformiert (diskrete Cosinus-Transformation), dann werden die höheren Frequenzanteile abgeschnitten (bzw. die DCT nur bis zu einer bestimmten Maximalfrequenz durchgeführt -- das ist der verlustbehaftete Part), alles zusammengeschoben (auf den Part gibts witzigerweise ein Patent) und am Ende nochmal Huffman-komprimiert.
Aber der OP hatte ziemlich sicher nach verlustfreien Kompressionsverfahren gefragt
-
Zu langsam.
-
wenn du aus mehr informationen weniger machst (also diese von dir beschriebene frequenz-transformation) dann passt das schon auf meine von dir zitierte aussage
verlustfrei bei audio ist z.b. FLAC unter linux
-
Helium schrieb:
Zu langsam.
was ist zu langsam??
-
Ich.
Hatte erst etwas ähnliches, wie Bashar geschreiben.
-
da hab ich hier was cooles gefunden:
http://www.neumahr.de/study/mpeg_audio.pdf
http://www.informatik.uni-trier.de/~kessler/bvsem/bildkompression.pdfkomplett deutsch
-
danke für die infos
aber Bashar hat recht, ich suche nach einer verlustfreien Datenkompression für daten(also keine Medien wie Filme bilder usw),und hab mich erstmal doch für das Huffmannsche verfahren entschieden, einfach weil der Rest erstmal zu komplex ist
später kann man ja ne andre Kompression vorschalten, das dürfte nicht so das große problem sein nun hab ich noch ne kleine verständnisfrage, was die Komprimierungstechniken angeht, welche mit schlüsseln arbeiten:
wenn ich nach dem LZW verfahren arbeite,werden ja zuerst die standardzeichen
von 0-255 in Zahlenverweise umgewandelt,und dann werden, wenn ich das richtig verstanden hab, alle weiteren verweise aus diesen Grundverweisen aufgebaut.
Wo ist da die Platzersparnis? die Standardzeichen(also typ char) sind 8 bit groß.Eine Zahl muss aber genauso groß sein,um in der Lage zu sein, alle standardzeichen zu speichern.Da ist doch keine platzersparnis möglich, denn demnach müsste ja ein Verweis für 2 Buchstaben vom bereich 257-65536 gehen, um alle Möglichkeiten(die sicher vorkommen werden) zu speichern.Und das währen wieder 16 Bit-genausoviel wie die beiden Zeichen verbrauchen.Da ist doch keine Platzersparnis möglich..oder etwa doch?
-
Wieso? Ein Eintrag kann doch auch "TGGC ist der Held" enthalten. Allerdings wird dieser Ausdruck nirgend gespeichert, da er sich von alleine wärend des Komprimierens und Dekomprimierens ergibt.