Verlustfreie Komprimierung ist eine Klasse der Datenkomprimierung , die es ermöglicht, die Originaldaten vollständig und ohne Informationsverlust aus den komprimierten Daten wiederherzustellen . Verlustfreie Komprimierung ist möglich, da die meisten realen Daten statistische Redundanz aufweisen . [ 1 ] Im Gegensatz dazu erlaubt verlustbehaftete Komprimierung nur die Rekonstruktion einer Annäherung an die Originaldaten , allerdings in der Regel mit deutlich verbesserten Komprimierungsraten (und damit reduzierten Speichermediengrößen).

Nach dem Schubfachprinzip kann kein verlustfreier Kompressionsalgorithmus die Größe aller möglichen Daten verkleinern: Einige Daten werden um mindestens ein Symbol oder Bit länger.

Komprimierungsalgorithmen eignen sich in der Regel gut für menschen- und maschinenlesbare Dokumente, können aber die Größe von zufälligen Daten ohne Redundanz nicht verringern . Es gibt verschiedene Algorithmen, die entweder für einen bestimmten Typ von Eingabedaten oder auf der Grundlage spezifischer Annahmen über die Art der Redundanz in den unkomprimierten Daten entwickelt wurden.

Verlustfreie Datenkomprimierung findet in vielen Anwendungen Verwendung. Beispielsweise wird sie im ZIP- Dateiformat und im GNU- Tool gzip eingesetzt . Sie dient auch häufig als Komponente in verlustbehafteten Datenkomprimierungstechnologien (z. B. verlustfreie Mid/Side-Stereo- Vorverarbeitung durch MP3- Encoder und andere verlustbehaftete Audio-Encoder). [ 2 ]

Verlustfreie Komprimierung kommt zum Einsatz, wenn es wichtig ist, dass Original- und dekomprimierte Daten identisch sind oder Abweichungen von den Originaldaten unerwünscht wären. Gängige Beispiele sind ausführbare Programme, Textdokumente und Quellcode. Einige Bilddateiformate wie PNG oder GIF verwenden ausschließlich verlustfreie Komprimierung, während andere wie TIFF und MNG sowohl verlustfreie als auch verlustbehaftete Verfahren nutzen können. Verlustfreie Audioformate werden meist für Archivierungs- oder Produktionszwecke verwendet, während kleinere, verlustbehaftete Audiodateien typischerweise auf tragbaren Abspielgeräten und in anderen Fällen zum Einsatz kommen, in denen der Speicherplatz begrenzt ist oder eine exakte Wiedergabe des Audiomaterials nicht erforderlich ist.

Techniken

Die meisten verlustfreien Komprimierungsprogramme führen zwei Schritte nacheinander aus: Im ersten Schritt wird ein statistisches Modell für die Eingabedaten erstellt, und im zweiten Schritt wird dieses Modell verwendet, um die Eingabedaten auf Bitfolgen abzubilden, sodass „wahrscheinliche“ (d. h. häufig vorkommende) Daten eine kürzere Ausgabe erzeugen als „unwahrscheinliche“ Daten.

Die wichtigsten Codierungsalgorithmen zur Erzeugung von Bitfolgen sind die Huffman-Codierung (die auch vom Deflate-Algorithmus verwendet wird ) und die arithmetische Codierung . Die arithmetische Codierung erzielt Kompressionsraten, die für ein bestimmtes statistisches Modell, das durch die Informationsentropie gegeben ist, nahezu optimal sind . Die Huffman-Komprimierung ist zwar einfacher und schneller, liefert aber schlechte Ergebnisse für Modelle mit Symbolwahrscheinlichkeiten nahe 1.

Es gibt zwei Hauptmethoden zur Erstellung statistischer Modelle: Bei einem statischen Modell werden die Daten analysiert, ein Modell erstellt und dieses anschließend zusammen mit den komprimierten Daten gespeichert. Dieser Ansatz ist einfach und modular, hat aber den Nachteil, dass die Speicherung des Modells selbst aufwendig sein kann und zudem die Verwendung eines einzigen Modells für alle zu komprimierenden Daten erzwingt. Dies führt zu einer schlechten Performance bei Dateien mit heterogenen Daten. Adaptive Modelle hingegen aktualisieren das Modell dynamisch während der Datenkomprimierung. Sowohl der Encoder als auch der Decoder beginnen mit einem einfachen Modell, was zu einer schlechten Komprimierung der anfänglichen Daten führt. Mit zunehmender Kenntnis der Daten verbessert sich die Performance jedoch. Die meisten gängigen Komprimierungsverfahren verwenden heutzutage adaptive Codierer.

Verlustfreie Komprimierungsverfahren lassen sich nach dem Datentyp kategorisieren, für den sie entwickelt wurden. Prinzipiell kann jeder universelle verlustfreie Komprimierungsalgorithmus ( universell bedeutet, dass er beliebige Bitfolgen verarbeiten kann) für jeden Datentyp verwendet werden. Viele dieser Algorithmen erzielen jedoch keine signifikante Komprimierung bei Daten, die nicht dem vorgesehenen Format entsprechen. Viele der für Text verwendeten verlustfreien Komprimierungstechniken eignen sich auch gut für indizierte Farbbilder .

Multimedia

Diese Techniken nutzen die spezifischen Eigenschaften von Bildern, wie beispielsweise das häufige Phänomen zusammenhängender zweidimensionaler Bereiche mit ähnlichen Farbtönen. Jedes Pixel außer dem ersten wird durch die Differenz zum Pixel seines linken Nachbarn ersetzt. Dadurch erhalten kleine Werte eine deutlich höhere Wahrscheinlichkeit als große. Dieses Verfahren wird oft auch auf Audiodateien angewendet und kann Dateien komprimieren, die überwiegend tiefe Frequenzen und geringe Lautstärken enthalten. Bei Bildern kann dieser Schritt wiederholt werden, indem die Differenz zum obersten Pixel berechnet wird. Bei Videos kann anschließend die Differenz zum Pixel des nächsten Frames ermittelt werden.

Die adaptive Kodierung nutzt bei der Tonkodierung die Wahrscheinlichkeiten des vorherigen Samples, bei der Bildkodierung die des linken und oberen Pixels und bei der Videokodierung zusätzlich die des vorherigen Frames. Auch bei der Wavelet-Transformation werden die Wahrscheinlichkeiten hierarchisch verarbeitet. [ 3 ]

Viele dieser Methoden sind in Open-Source- und proprietären Tools implementiert, insbesondere in LZW und seinen Varianten. Einige Algorithmen sind in den USA und anderen Ländern patentiert, und ihre rechtmäßige Nutzung erfordert eine Lizenz des Patentinhabers. Aufgrund von Patenten auf bestimmte Arten der LZW -Komprimierung und insbesondere der von vielen Entwicklern als missbräuchlich empfundenen Lizenzierungspraxis des Patentinhabers Unisys rieten einige Befürworter von Open Source davon ab, das Graphics Interchange Format (GIF) zur Komprimierung von Standbilddateien zu verwenden und stattdessen Portable Network Graphics (PNG) zu nutzen. PNG kombiniert den auf LZ77 basierenden Deflate-Algorithmus mit einer Auswahl domänenspezifischer Vorhersagefilter. Die Patente auf LZW liefen jedoch am 20. Juni 2003 aus. [ 4 ]

Viele der für Text verwendeten verlustfreien Komprimierungstechniken funktionieren auch für indizierte Bilder recht gut . Es gibt jedoch andere Techniken, die für typischen Text nicht funktionieren, aber für einige Bilder (insbesondere einfache Bitmaps) nützlich sind, sowie andere Techniken, die die spezifischen Eigenschaften von Bildern ausnutzen (wie das häufige Phänomen zusammenhängender 2D-Bereiche ähnlicher Farbtöne und die Tatsache, dass Farbbilder in der Regel einen Überschuss an Farben aus einem begrenzten Farbspektrum aufweisen, das im Farbraum darstellbar ist).

Wie bereits erwähnt, ist die verlustfreie Audiokompression ein Spezialgebiet. Verlustfreie Kompressionsalgorithmen nutzen die sich wiederholenden Muster der Wellenstruktur der Daten –im Wesentlichen mithilfe autoregressiver Modelle, um den „nächsten“ Wert vorherzusagen und die (möglicherweise geringe) Differenz zwischen dem erwarteten Wert und den tatsächlichen Daten zu kodieren. Ist die Differenz zwischen den vorhergesagten und den tatsächlichen Daten (der sogenannte Fehler ) tendenziell gering, treten bestimmte Differenzwerte (wie 0, +1, −1 usw. bei Abtastwerten) sehr häufig auf. Diese können genutzt werden, indem sie in wenigen Ausgabebits kodiert werden.

Manchmal ist es vorteilhaft, nur die Unterschiede zwischen zwei Versionen einer Datei (oder, bei der Videokomprimierung , zwischen aufeinanderfolgenden Bildern einer Sequenz) zu komprimieren. Dies wird als Delta-Codierung bezeichnet (vom griechischen Buchstaben Δ , der in der Mathematik eine Differenz symbolisiert). Der Begriff wird jedoch typischerweise nur verwendet, wenn beide Versionen außerhalb der Komprimierung und Dekomprimierung aussagekräftig sind. Beispielsweise könnte der Komprimierungsprozess des Fehlers im oben erwähnten verlustfreien Audiokomprimierungsverfahren zwar als Delta-Codierung von der approximierten zur ursprünglichen Schallwelle beschrieben werden, die approximierte Version der Schallwelle ist jedoch in keinem anderen Kontext aussagekräftig.

Methoden

Kein verlustfreier Komprimierungsalgorithmus kann alle möglichen Daten effizient komprimieren . Aus diesem Grund existieren viele verschiedene Algorithmen, die entweder für einen bestimmten Typ von Eingabedaten oder auf der Grundlage spezifischer Annahmen darüber entwickelt wurden, welche Art von Redundanz die unkomprimierten Daten wahrscheinlich enthalten.

Nachfolgend sind einige der gebräuchlichsten verlustfreien Komprimierungsalgorithmen aufgeführt.

Allgemeiner Zweck

Audio

Rastergrafiken

3D-Grafiken

  • OpenCTM – Verlustfreie Komprimierung von 3D-Dreiecksnetzen

Video

Siehe Liste der verlustfreien Videocodecs

Kryptographie

Kryptosysteme komprimieren Daten (den „Klartext“) häufig vor der Verschlüsselung, um die Sicherheit zu erhöhen. Bei korrekter Implementierung verbessert die Komprimierung die Eindeutigkeitsdistanz erheblich, indem sie Muster entfernt, die eine Kryptoanalyse erleichtern könnten . [ 9 ] Viele gängige verlustfreie Komprimierungsalgorithmen erzeugen jedoch Header, Wrapper, Tabellen oder andere vorhersehbare Ausgaben, die die Kryptoanalyse unter Umständen sogar vereinfachen. Daher müssen Kryptosysteme Komprimierungsalgorithmen verwenden, deren Ausgabe diese vorhersehbaren Muster nicht enthält.

Genetik und Genomik

Genetische Kompressionsalgorithmen (nicht zu verwechseln mit genetischen Algorithmen ) stellen die neueste Generation verlustfreier Algorithmen dar, die Daten (typischerweise Nukleotidsequenzen) mithilfe konventioneller und speziell für genetische Daten angepasster Kompressionsalgorithmen komprimieren. Im Jahr 2012 veröffentlichte ein Wissenschaftlerteam der Johns Hopkins University den ersten genetischen Kompressionsalgorithmus, der keine externen genetischen Datenbanken zur Komprimierung benötigt. HAPZIPPER wurde speziell für HapMap -Daten entwickelt und erreicht eine mehr als 20-fache Komprimierung (95 % Reduzierung der Dateigröße). Damit bietet er eine 2- bis 4-fach bessere Komprimierung deutlich schneller als führende universelle Kompressionsprogramme. [ 10 ]

Genomsequenzkomprimierungsalgorithmen, auch DNA-Sequenzkompressoren genannt, nutzen die charakteristischen Eigenschaften von DNA-Sequenzen, wie beispielsweise invertierte Wiederholungen. Die erfolgreichsten Kompressoren sind XM und GeCo. [ 11 ] Für Eukaryoten erzielt XM ein etwas besseres Kompressionsverhältnis, allerdings ist der Rechenaufwand für Sequenzen über 100 MB unpraktisch.

Ausführbare Dateien

Selbstextrahierende ausführbare Dateien enthalten eine komprimierte Anwendung und einen Dekomprimierer. Bei der Ausführung dekomprimiert der Dekomprimierer die ursprüngliche Anwendung transparent und führt sie aus. Dies wird besonders häufig beim Demo -Coding eingesetzt, wo Wettbewerbe mit strengen Größenbeschränkungen – teilweise nur 1 Kilobyte – für Demos veranstaltet werden . Diese Art der Komprimierung ist nicht ausschließlich auf Binärdateien beschränkt, sondern kann auch auf Skripte wie JavaScript angewendet werden .

Benchmarks

Verlustfreie Komprimierungsalgorithmen und ihre Implementierungen werden regelmäßig in direkten Vergleichstests geprüft . Es gibt eine Reihe bekannter Komprimierungs-Benchmarks. Einige dieser Benchmarks berücksichtigen lediglich das Datenkomprimierungsverhältnis , weshalb die besten Ergebnisse aufgrund ihrer geringen Geschwindigkeit möglicherweise nicht für den täglichen Gebrauch geeignet sind. Ein weiterer Nachteil mancher Benchmarks besteht darin, dass die verwendeten Datendateien bekannt sind. Daher optimieren manche Programmierer ihre Programme möglicherweise für die beste Leistung mit einem bestimmten Datensatz. Die besten Ergebnisse in diesen Benchmarks erzielen häufig Komprimierungssoftware, die Kontextmischung verwendet .

Matt Mahoney führt in seiner Ausgabe vom Februar 2010 der kostenlosen Broschüre „Data Compression Explained“ zusätzlich Folgendes auf: [ 12 ]

  • Das Calgary-Korpus aus dem Jahr 1987 wird aufgrund seines geringen Umfangs heute nicht mehr häufig genutzt. Matt Mahoney betreute die Calgary Compression Challenge, die von Leonid A. Broukhis vom 21. Mai 1996 bis zum 21. Mai 2016 ins Leben gerufen und gepflegt wurde.
  • Sowohl der Large Text Compression Benchmark als auch der ähnliche Hutter Prize verwenden einen gekürzten Wikipedia XML UTF-8- Datensatz.
  • Der von Matt Mahoney betreute Generic Compression Benchmark testet die Komprimierung von Daten, die von zufälligen Turingmaschinen erzeugt werden .
  • Sami Runsas (der Entwickler von NanoZip) pflegte die Compression Ratings, einen Benchmark ähnlich dem Maximum Compression Multiple File Test, jedoch mit Mindestanforderungen an die Komprimierungsgeschwindigkeit. Er bot einen Rechner an, mit dem der Benutzer die Bedeutung von Geschwindigkeit und Komprimierungsrate gewichten konnte. Die besten Programme unterschieden sich aufgrund der Geschwindigkeitsanforderungen deutlich. Im Januar 2010 war NanoZip das führende Programm, gefolgt von FreeArc , CCM , flashzip und 7-Zip .
  • Der „Monster of Compression“-Benchmark von Nania Francesco Antonio testete die Komprimierung von 1 GB öffentlicher Daten innerhalb eines Zeitlimits von 40 Minuten. Im Dezember 2009 war NanoZip 0.07a der beste Archivierer und ccmx 1.30c der beste Einzeldateikomprimierer .

Die Website Compression Ratings veröffentlichte eine grafische Zusammenfassung der „Grenze“ in Bezug auf Kompressionsverhältnis und Zeit. [ 13 ]

Silesia corpus

Das Silesia-Korpus ist eine Sammlung von Dateien , die 2003 als Alternative zum Canterbury-Korpus und zum Calgary-Korpus erstellt wurde , da Bedenken hinsichtlich deren Repräsentation moderner Dateien bestanden. Es enthält verschiedene Datentypen, darunter große Textdokumente, ausführbare Dateien und Datenbanken. [ 14 ] Es wird häufig in der Datenkomprimierungsforschung verwendet. [ 15 ]

Das Korpus besteht aus 12 Dateien mit einer Gesamtgröße von 211 MB. Die Dateien wurden so ausgewählt, dass sie Datentypen repräsentieren, die nach Ansicht des Autors im Laufe der Zeit wahrscheinlich schnell an Größe zunehmen, wie z. B. Computerprogramme und Datenbanken, sowie traditionellere Komprimierungs-Benchmarks, wie z. B. große Textdateien. [ 14 ]

Übersicht über Dateien, ihre Größen, Beschreibungen und Datentypen
Datei Größe (B) Beschreibung Datentyp
Dickens 10192446 Die Werke von Charles DickensEnglischer Text
Mozilla 51220480 Ausführbare Dateien für Mozilla 1.0 Ausführbar
Herr 9970564 MRT- Bilder 3D-Bild
nci 33553445 Eine Datenbank chemischer Strukturen Datenbank
Büro 6152192 Eine gemeinsam genutzte Bibliothek aus OpenOfficeAusführbar
osdb 10085684 Eine Beispiel -MySQL- Datenbank aus dem Open Source Database Benchmark Datenbank
Reymont 6625583 Der Text des Buches Chłopi von Władysław ReymontPDF auf Polnisch
Samba 21606400 Der Quellcode von Samba  2‐2.3 Ausführbar
sao 7251944 Der SAO-SternenkatalogBinärdatenbank
Webster 41458703 Das Webster Unabridged Dictionary von 1913HTML
XML 5345280 Gesammelte XML- Dateien XML
Röntgenaufnahme 8474240 Eine medizinische RöntgenaufnahmeBild
Gesamt211938580

Da es eine breitere und modernere Auswahl an Datentypen bietet, gilt es im Vergleich zum Calgary-Korpus als bessere Quelle für Testdaten für Kompressionsalgorithmen . [ 16 ]

Einschränkungen

Verlustfreie Datenkomprimierungsalgorithmen können keine Komprimierung für alle Eingabedatensätze garantieren. Anders ausgedrückt: Für jeden verlustfreien Datenkomprimierungsalgorithmus gibt es einen Eingabedatensatz, der sich durch die Verarbeitung mit dem Algorithmus nicht verkleinert, und für jeden verlustfreien Datenkomprimierungsalgorithmus, der mindestens eine Datei verkleinert, gibt es mindestens eine Datei, die er vergrößert. Dies lässt sich leicht mit elementarer Mathematik mithilfe eines Zählarguments, dem sogenannten Schubfachprinzip , beweisen: [ 17 ] [ 18 ]

  • Angenommen, jede Datei wird als Bitfolge beliebiger Länge dargestellt.
  • Angenommen, es gibt einen Komprimierungsalgorithmus, der jede Datei in eine Ausgabedatei umwandelt, die nicht länger als die Originaldatei ist, und dass mindestens eine Datei in eine Ausgabedatei komprimiert wird, die kürzer als die Originaldatei ist.
  • Sei M die kleinste Zahl, sodass es eine Datei F der Länge M Bit gibt, die sich zu einer kürzeren Länge komprimieren lässt. Sei N die Länge (in Bit) der komprimierten Version von F.
  • Da N < M gilt , behält jede Datei der Länge N ihre Größe bei der Komprimierung. Es gibt 2 <sup>N </sup> solcher Dateien. Zusammen mit F ergeben sich daraus 2 <sup>N +1</sup> Dateien, die alle zu einer der 2<sup> N</sup> Dateien der Länge N komprimiert werden können .
  • Da 2N kleiner als 2N + 1 ist , muss es nach dem Schubfachprinzip eine Datei der Länge N geben , die gleichzeitig das Ergebnis der Kompressionsfunktion für zwei verschiedene Eingaben ist. Diese Datei lässt sich nicht zuverlässig dekomprimieren (welche der beiden Originaldateien sollte sich daraus ergeben?), was der Annahme widerspricht, dass der Algorithmus verlustfrei war.
  • Wir müssen daher schlussfolgern, dass unsere ursprüngliche Hypothese (dass die Komprimierungsfunktion die Datei nicht verlängert) notwendigerweise falsch ist.

Die meisten praktischen Komprimierungsalgorithmen bieten eine „Escape“-Funktion, mit der die normale Codierung für Dateien deaktiviert werden kann, die durch die Codierung größer würden. Theoretisch genügt ein einziges zusätzliches Bit, um dem Decoder mitzuteilen, dass die normale Codierung für die gesamte Eingabe deaktiviert wurde. Die meisten Codierungsalgorithmen verwenden jedoch mindestens ein Byte (und typischerweise mehrere) für diesen Zweck. Beispielsweise müssen mit Deflate komprimierte Dateien nie um mehr als 5 Byte pro 65.535 Byte Eingabe anwachsen.

Wenn wir Dateien der Länge N betrachten und alle Dateien gleich wahrscheinlich sind, dann muss die erwartete Länge einer komprimierten Datei (gemittelt über alle möglichen Dateien der Länge N) bei jeder verlustfreien Komprimierung, die die Größe einer Datei reduziert, zwangsläufig größer als N sein. Wenn wir also nichts über die Eigenschaften der zu komprimierenden Daten wissen, können wir sie genauso gut gar nicht komprimieren. Ein verlustfreier Komprimierungsalgorithmus ist nur dann sinnvoll, wenn wir bestimmte Dateitypen häufiger komprimieren als andere; dann könnte der Algorithmus so entwickelt werden, dass er diese Datentypen besser komprimiert.

Die wichtigste Lehre aus dieser Argumentation ist also nicht, dass man große Verluste riskiert, sondern lediglich, dass man nicht immer gewinnen kann. Die Wahl eines Algorithmus bedeutet stets implizit, eine Teilmenge aller Dateien auszuwählen, die dadurch sinnvoll verkürzt werden. Dies ist der theoretische Grund, warum wir unterschiedliche Komprimierungsalgorithmen für verschiedene Dateitypen benötigen: Es kann keinen Algorithmus geben, der für alle Datentypen geeignet ist.

Der „Trick“, der es verlustfreien Komprimierungsalgorithmen ermöglicht, Dateien, die für den vorgesehenen Datentyp verwendet werden, konsistent zu verkürzen, besteht darin, dass die Dateien, auf die die Algorithmen angewendet werden, alle eine Form von leicht modellierbarer Redundanz aufweisen , die der Algorithmus entfernt. Dadurch gehören sie zu der Teilmenge der Dateien, die der Algorithmus verkürzen kann, während andere Dateien nicht komprimiert werden oder sogar größer werden. Algorithmen sind in der Regel sehr spezifisch auf einen bestimmten Dateityp abgestimmt: Beispielsweise funktionieren verlustfreie Audiokomprimierungsprogramme nicht gut mit Textdateien und umgekehrt.

Insbesondere können Dateien mit zufälligen Daten durch keinen denkbaren verlustfreien Datenkomprimierungsalgorithmus konsistent komprimiert werden; dieses Ergebnis wird sogar verwendet, um den Begriff der Zufälligkeit in der Kolmogorov-Komplexität zu definieren . [ 19 ]

Es ist nachweislich unmöglich, einen Algorithmus zu entwickeln, der beliebige Daten verlustfrei komprimieren kann. Obwohl im Laufe der Jahre zahlreiche Unternehmen behauptet haben, eine „perfekte Komprimierung“ erreicht zu haben, bei der eine beliebige Anzahl N von Zufallsbits stets auf N  − 1 Bits komprimiert werden kann, können solche Behauptungen getrost verworfen werden, ohne dass man sich näher mit den Details des angeblichen Komprimierungsverfahrens befasst. Ein solcher Algorithmus widerspricht fundamentalen Gesetzen der Mathematik, denn wenn er existierte, könnte er beliebig oft angewendet werden, um jede Datei verlustfrei auf die Länge 1 zu reduzieren. [ 18 ]

Andererseits wurde auch bewiesen, dass es keinen Algorithmus gibt, der mit Hilfe der Kolmogorov-Komplexität feststellen kann, ob eine Datei inkompressibel ist. [ 20 ] Daher ist es möglich, dass jede beliebige Datei, selbst wenn sie zufällig erscheint, erheblich komprimiert werden kann, sogar unter Berücksichtigung der Größe des Dekomprimierers. Ein Beispiel hierfür sind die Ziffern der mathematischen Konstante Pi , die zwar zufällig erscheinen, aber von einem sehr kleinen Programm generiert werden können. Obwohl sich nicht feststellen lässt, ob eine bestimmte Datei inkompressibel ist, zeigt ein einfacher Satz über inkompressible Zeichenketten , dass über 99 % der Dateien beliebiger Länge nicht um mehr als ein Byte komprimiert werden können (einschließlich der Größe des Dekomprimierers).

Mathematischer Hintergrund

Abstrakt betrachtet kann ein Kompressionsalgorithmus als Funktion auf Sequenzen (üblicherweise Oktetten) verstanden werden. Die Kompression ist erfolgreich, wenn die resultierende Sequenz kürzer ist als die ursprüngliche Sequenz (und die Anweisungen für die Dekompressionsabbildung). Damit ein Kompressionsalgorithmus verlustfrei ist, muss die Kompressionsabbildung eine Injektion von „unkomprimierten“ zu „komprimierten“ Bitsequenzen ermöglichen. Das Schubfachprinzip verbietet eine Bijektion zwischen der Menge der Sequenzen der Länge N und einer beliebigen Teilmenge der Menge der Sequenzen der Länge N − 1. Daher ist es nicht möglich, einen verlustfreien Algorithmus zu entwickeln, der die Größe jeder möglichen Eingabesequenz reduziert. [ 21 ]

Anwendungsgebiete in der realen Kompressionstheorie

Reale Entwickler von Komprimierungsalgorithmen akzeptieren, dass Datenströme mit hoher Informationsentropie nicht komprimiert werden können und integrieren daher Mechanismen zur Erkennung und Behandlung dieses Problems. Eine naheliegende Methode ist die Anwendung eines einfachen Komprimierungsalgorithmus und die Prüfung, ob die Ausgabedatei kleiner als die Eingabedatei ist. Manchmal erfolgt die Erkennung heuristisch ; beispielsweise kann eine Komprimierungsanwendung Dateien, deren Namen auf „.zip“, „.arj“ oder „.lha“ enden, ohne weitere Erkennung als nicht komprimierbar einstufen. Eine gängige Methode zur Behandlung dieser Situation ist das Ausblenden der Eingabe oder nicht komprimierbarer Teile der Eingabe in die Ausgabe, um den Komprimierungsaufwand zu minimieren. Beispielsweise legt das ZIP- Datenformat die Komprimierungsmethode „Gespeichert“ für Eingabedateien fest, die unverändert in das Archiv kopiert wurden. [ 22 ]

Siehe auch

Referenzen

  1. ^ „Unit 4 Lab 4: Data Representation and Compression“ . BJC.EDC.org . S. 6. Abgerufen am 9. April 2022 .
  2. ^ Price, Andy (3. März 2022). „Verlustfreies Streaming – die Zukunft von hochauflösendem Audio“ . Audio Media International . Abgerufen am 25. Oktober 2025 .
  3. Unser , M .; Blu, T. (2003). „Mathematische Eigenschaften der JPEG2000-Wavelet-Filter“ (PDF) . IEEE Transactions on Image Processing . 12 (9): 1080–1090 . Bibcode : 2003ITIP...12.1080U . doi : 10.1109/ TIP.2003.812329 . PMID 18237979 . 
  4. ^ „LZW Patentinformationen“ . Über Unisys . Unisys. Archiviert vom Original am 2. Juni 2009.
  5. ^ Sullivan, Gary (8.–12. Dezember 2003). „Allgemeine Merkmale und Designüberlegungen für die temporale Subband-Videocodierung“ . ITU-T . Video Coding Experts Group . Abgerufen am 13. September 2019 .
  6. ^ Bovik, Alan C. (2009). The Essential Guide to Video Processing . Academic Press . S. 355. ISBN 9780080922508Die
  7. ^ Ahmed, Nasir ; Mandyam, Giridhar D.; Magotra, Neeraj (17. April 1995). Rodriguez, Arturo A.; Safranek, Robert J.; Delp, Edward J. (Hrsg.). „DCT-basiertes Verfahren zur verlustfreien Bildkomprimierung“. Digital Video Compression: Algorithms and Technologies 1995. 2419. International Society for Optics and Photonics: 474–478 . Bibcode : 1995SPIE.2419..474M . doi : 10.1117/12.206386 .
  8. Komatsu , K.; Sezaki, K. (1998). „Reversible diskrete Kosinustransformation“. Proceedings der IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '98 (Kat.-Nr. 98CH36181) . Bd. 3 , S.  1769–1772 . doi : 10.1109/ICASSP.1998.681802 . ISBN 0-7803-4428-6Die
  9. ^ Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (16. Oktober 1996). Handbuch der angewandten Kryptographie . CRC Press. ISBN 978-1-4398-2191-6Die
  10. ^ Chanda, P.; Elhaik, E.; Bader, JS (2012). „HapZipper: Das Teilen von HapMap-Populationen ist jetzt einfacher“ . Nucleic Acids Res . 40 (20): e159. doi : 10.1093/nar/gks709 . PMC 3488212. PMID 22844100 .  
  11. ^ Pratas, D.; Pinho, AJ; Ferreira, PJSG (2016). Effiziente Komprimierung genomischer Sequenzen (PDF) . Datenkomprimierungskonferenz. Snowbird, Utah.
  12. ^ Mahoney, Matt (2010). „Datenkomprimierung erklärt“ (PDF) . S.  3–5 .
  13. ^ „Zusammenfassung“ . 1. September 2016. Archiviert vom Original am 1. September 2016.
  14. ^ a b Deorowicz, Sebastian. Universelle verlustfreie Datenkompressionsalgorithmen (PDF) (Dissertation). Schlesische Technische Universität. S.  93–95 . Archiviert vom Original (PDF) am 28. August 2024.
  15. ^ Maulidina, Alysha Puti; Wijaya, Rachel Anastasia; Mazel, Kimberly; Astriani, Maria Seraphina (2024). „Vergleichende Studie von Datenkompressionsalgorithmen: Zstandard, zlib & LZ4“. Science, Engineering Management and Information Technology . Communications in Computer and Information Science. 2198 : 394–406 . doi : 10.1007/978-3-031-72284-4_24 . ISBN 978-3-031-72283-7Die
  16. ^ Gupta, Apoorv; Bansal, Aman; Khanduja, Vidhi (22. Februar 2017). „Moderne verlustfreie Kompressionsverfahren: Überblick, Vergleich und Analyse“. Zweite Internationale Konferenz für Elektrotechnik, Computer- und Kommunikationstechnologien (ICECCT) 2017. IEEE. S.  1–8 . doi : 10.1109/ICECCT.2017.8117850 . ISBN 978-1-5090-3239-6Die
  17. ^ Sayood 2002 , S. 41.
  18. ^ a b Bell, Tim (2015). „Überraschende Informatik“. Informatik in Schulen. Lehrpläne, Kompetenzen und Wettbewerbe . Lecture Notes in Computer Science. Band 9378. S.  1–11 . doi : 10.1007/978-3-319-25396-1_1 . ISBN 978-3-319-25395-4DieSiehe insbesondere S. 8–9 .
  19. ^ Sayood 2002 , S. 38.
  20. ^ Li, Ming; Vitányi, Paul (1993). Eine Einführung in die Kolmogorov-Komplexität und ihre Anwendungen . New York: Springer. P. 102. ISBN 0-387-94053-7Satz 2.6 Die Funktion ist nicht partiell rekursiv.
  21. ^ Joshi, Mark (2015). „Das Schubfachprinzip“. Beweismuster . S.  19–23 . doi : 10.1007/978-3-319-16250-8_3 . ISBN 978-3-319-16249-2Die
  22. ^ ".ZIP-Dateiformatspezifikation" . PKWARE, Inc. Kapitel V, Abschnitt J.

Weiterführende Literatur