Verlustfreie Kompression - Lossless compression

Die verlustfreie Komprimierung ist eine Klasse von Datenkomprimierungsalgorithmen , die eine perfekte Rekonstruktion der Originaldaten aus den komprimierten Daten ermöglicht. Im Gegensatz dazu erlaubt die verlustbehaftete Komprimierung nur die Rekonstruktion einer Annäherung der Originaldaten, allerdings in der Regel mit stark verbesserten Komprimierungsraten (und damit reduzierten Mediengrößen).

Durch den Betrieb des Schubladenprinzips kann kein verlustfreier Kompressionsalgorithmus alle möglichen Daten effizient komprimieren. Aus diesem Grund gibt es viele verschiedene Algorithmen, die entweder mit Blick auf einen bestimmten Typ von Eingabedaten oder mit bestimmten Annahmen darüber entwickelt wurden, welche Arten von Redundanz die unkomprimierten Daten wahrscheinlich enthalten werden. Daher sind die Komprimierungsraten bei von Menschen und Maschinen lesbaren Dokumenten und Code im Vergleich zu entropischen Binärdaten (zufällige Bytes) tendenziell stärker.

Die verlustfreie Datenkomprimierung wird in vielen Anwendungen verwendet. Es wird beispielsweise im ZIP- Dateiformat und im GNU- Tool gzip verwendet . Es wird auch oft als Komponente in verlustbehafteten Datenkompressionstechnologien verwendet (zB verlustfreie Mid/Side Joint Stereo Preprocessing durch MP3- Encoder und andere verlustbehaftete Audio-Encoder).

Die verlustfreie Komprimierung wird dort eingesetzt, wo es darauf ankommt, dass Original- und dekomprimierte Daten identisch sind oder Abweichungen von den Originaldaten ungünstig wären. Typische Beispiele sind ausführbare Programme, Textdokumente und Quellcode. Einige Bilddateiformate wie PNG oder GIF verwenden nur verlustfreie Komprimierung, während andere wie TIFF und MNG entweder verlustfreie oder verlustbehaftete Methoden verwenden. Verlustfreie Audioformate werden am häufigsten für Archivierungs- oder Produktionszwecke verwendet, während kleinere verlustbehaftete Audiodateien typischerweise auf tragbaren Playern verwendet werden und in anderen Fällen, in denen der Speicherplatz begrenzt ist oder eine genaue Reproduktion des Audios nicht erforderlich ist.

Verlustfreie Kompressionstechniken

Die meisten verlustfreien Komprimierungsprogramme machen zwei Dinge nacheinander: Der erste Schritt erzeugt ein statistisches Modell für die Eingabedaten und der zweite Schritt verwendet dieses Modell, um die Eingabedaten so auf Bitfolgen abzubilden, dass "wahrscheinliche" (zB häufig vorkommende) Daten erzeugt eine kürzere Ausgabe als "unwahrscheinliche" Daten.

Die primären Codieralgorithmen, die verwendet werden, um Bitfolgen zu erzeugen, sind die Huffman-Codierung (die auch vom Deflate-Algorithmus verwendet wird ) und die arithmetische Codierung . Die arithmetische Codierung erreicht für ein bestimmtes statistisches Modell nahe der bestmöglichen Kompressionsraten, die durch die Informationsentropie gegeben ist , während die Huffman-Komprimierung einfacher und schneller ist, aber bei Modellen, die mit Symbolwahrscheinlichkeiten nahe 1 umgehen, schlechte Ergebnisse liefert.

Es gibt hauptsächlich zwei Möglichkeiten, statistische Modelle zu konstruieren: In einem statischen Modell werden die Daten analysiert und ein Modell konstruiert, dann wird dieses Modell mit den komprimierten Daten gespeichert. Dieser Ansatz ist einfach und modular, hat jedoch den Nachteil, dass die Speicherung des Modells selbst teuer sein kann und dass er die Verwendung eines einzigen Modells für alle zu komprimierenden Daten erzwingt und daher bei Dateien, die heterogene Daten enthalten, schlecht funktioniert. Adaptive Modelle aktualisieren das Modell dynamisch, wenn die Daten komprimiert werden. Sowohl der Codierer als auch der Decodierer beginnen mit einem trivialen Modell, das eine schlechte Komprimierung der Anfangsdaten ergibt, aber wenn sie mehr über die Daten erfahren, verbessert sich die Leistung. Die meisten in der Praxis gebräuchlichen Kompressionsarten verwenden heute adaptive Codierer.

Verlustfreie Komprimierungsverfahren können nach der Art der Daten kategorisiert werden, die sie komprimieren sollen. Während im Prinzip jeder verlustfreie Komprimierungsalgorithmus für allgemeine Zwecke ( allgemein bedeutet, dass er jede Bitfolge akzeptieren kann) für jeden Datentyp verwendet werden kann, sind viele nicht in der Lage, eine signifikante Komprimierung für Daten zu erreichen, die nicht die Form haben, für die Sie wurden entwickelt, um zu komprimieren. Viele der für Text verwendeten verlustfreien Komprimierungstechniken funktionieren auch bei indizierten Bildern recht gut .

Multimedia

Diese Techniken machen sich die spezifischen Eigenschaften von Bildern zunutze, wie zum Beispiel das gemeinsame Phänomen zusammenhängender 2D-Bereiche mit ähnlichen Farbtönen. Jedes Pixel außer dem ersten wird durch die Differenz zu seinem linken Nachbarn ersetzt. Dies führt dazu, dass kleine Werte eine viel höhere Wahrscheinlichkeit haben als große Werte. Dies wird häufig auch auf Audiodateien angewendet und kann Dateien komprimieren, die hauptsächlich niedrige Frequenzen und geringe Lautstärken enthalten. Bei Bildern kann dieser Schritt wiederholt werden, indem die Differenz zum obersten Pixel genommen wird, und dann kann bei Videos die Differenz zum Pixel im nächsten Frame gemessen werden.

Eine hierarchische Version dieser Technik nimmt benachbarte Paare von Datenpunkten, speichert ihre Differenz und Summe und fährt auf einer höheren Ebene mit niedrigerer Auflösung mit den Summen fort. Dies wird als diskrete Wavelet-Transformation bezeichnet . JPEG2000 verwendet zusätzlich Datenpunkte aus anderen Paaren und Multiplikationsfaktoren, um sie in die Differenz einzumischen. Diese Faktoren müssen ganze Zahlen sein, damit das Ergebnis unter allen Umständen eine ganze Zahl ist. Die Werte werden also erhöht, die Dateigröße erhöht, aber die Verteilung der Werte ist hoffentlich spitzer.

Die adaptive Kodierung verwendet die Wahrscheinlichkeiten aus dem vorherigen Abtastwert bei der Tonkodierung, aus dem linken und oberen Pixel bei der Bildkodierung und zusätzlich aus dem vorherigen Frame bei der Videokodierung. Bei der Wavelet-Transformation werden auch die Wahrscheinlichkeiten durch die Hierarchie geleitet.

Historische Rechtsfragen

Viele dieser Methoden sind in Open-Source- und proprietären Tools implementiert, insbesondere LZW und seine Varianten. Einige Algorithmen sind in den Vereinigten Staaten und anderen Ländern patentiert und ihre legale Verwendung erfordert eine Lizenzierung durch den Patentinhaber. Aufgrund von Patenten auf bestimmte Arten der LZW- Komprimierung und insbesondere von Lizenzpraktiken des Patentinhabers Unisys, die von vielen Entwicklern als missbräuchlich angesehen wurden, ermutigten einige Open-Source-Befürworter die Leute, die Verwendung des Graphics Interchange Format (GIF) zum Komprimieren von Standbilddateien zugunsten von Portable zu vermeiden Network Graphics (PNG), das den LZ77- basierten Deflate-Algorithmus mit einer Auswahl domänenspezifischer Vorhersagefilter kombiniert . Die Patente auf LZW liefen jedoch am 20. Juni 2003 aus.

Viele der für Text verwendeten verlustfreien Komprimierungstechniken funktionieren auch für indizierte Bilder einigermaßen gut , aber es gibt andere Techniken, die für typischen Text nicht funktionieren und für einige Bilder (insbesondere einfache Bitmaps) nützlich sind, und andere Techniken, die die spezifischen Vorteile nutzen Eigenschaften von Bildern (wie das häufige Phänomen zusammenhängender 2D-Bereiche mit ähnlichen Farbtönen und die Tatsache, dass Farbbilder in der Regel ein Übergewicht einer begrenzten Farbpalette unter den im Farbraum darstellbaren Farben aufweisen).

Wie bereits erwähnt, ist die verlustfreie Tonkomprimierung ein etwas spezialisierter Bereich. Verlustfreie Klangkompressionsalgorithmen können die sich wiederholenden Muster nutzen, die sich in der wellenartigen Natur der Daten zeigen – im Wesentlichen verwenden sie autoregressive Modelle, um den "nächsten" Wert vorherzusagen und die (hoffentlich kleine) Differenz zwischen dem erwarteten Wert und den tatsächlichen Daten zu codieren. Wenn die Differenz zwischen den vorhergesagten und den tatsächlichen Daten (sogenannter Fehler ) dazu neigt, klein zu sein, werden bestimmte Differenzwerte (wie 0, +1, –1 usw. bei Abtastwerten) sehr häufig, was durch Codieren ausgenutzt werden kann in wenigen Ausgabebits.

Manchmal ist es von Vorteil, nur die Unterschiede zwischen zwei Versionen einer Datei (oder bei der Videokomprimierung von aufeinanderfolgenden Bildern innerhalb einer Sequenz) zu komprimieren . Dies wird Delta-Kodierung genannt (vom griechischen Buchstaben Δ , der in der Mathematik einen Unterschied bezeichnet), aber der Begriff wird normalerweise nur verwendet, wenn beide Versionen außerhalb der Komprimierung und Dekomprimierung sinnvoll sind. Während zum Beispiel der Prozess der Komprimierung des Fehlers im oben erwähnten verlustfreien Audiokompressionsschema als Delta-Kodierung von der angenäherten Schallwelle zur ursprünglichen Schallwelle beschrieben werden könnte, ist die angenäherte Version der Schallwelle in keinem anderen Kontext sinnvoll .

Verlustfreie Komprimierungsmethoden

Siehe auch: Kategorie: Verlustfreie Komprimierungsalgorithmen und Liste der verlustfreien Komprimierungsalgorithmen

Kein verlustfreier Komprimierungsalgorithmus kann alle möglichen Daten effizient komprimieren (siehe Abschnitt Einschränkungen unten für Details). Aus diesem Grund gibt es viele verschiedene Algorithmen, die entweder mit Blick auf einen bestimmten Typ von Eingabedaten oder mit bestimmten Annahmen darüber entwickelt wurden, welche Arten von Redundanz die unkomprimierten Daten wahrscheinlich enthalten werden.

Einige der gebräuchlichsten verlustfreien Komprimierungsalgorithmen sind unten aufgeführt.

Allgemeiner Zweck

Audio

Rastergrafiken

  • AVIF – AOMedia Video 1 Bilddateiformat
  • FLIF – Kostenloses verlustfreies Bildformat
  • HEIF – High Efficiency Image File Format (verlustfreie oder verlustbehaftete Komprimierung mit HEVC )
  • ILBM – (verlustfreie RLE-Komprimierung von Amiga- IFF- Bildern)
  • JBIG2 – (verlustfreie oder verlustbehaftete Komprimierung von Schwarzweißbildern)
  • JPEG 2000 – (beinhaltet verlustfreie Komprimierungsmethode über LeGall-Tabatabai 5/3 reversible Integer Wavelet-Transformation )
  • JPEG-LS – (verlustfreier/fast verlustfreier Komprimierungsstandard)
  • JPEG XL – (verlustfreie oder verlustbehaftete Komprimierung)
  • JPEG XR – früher WMPhoto und HD Photo , enthält eine verlustfreie Komprimierungsmethode
  • LDCT – Verlustfreie diskrete Kosinustransformation
  • PCX – Bildaustausch
  • PDF – Portable Document Format (verlustfreie oder verlustbehaftete Komprimierung)
  • PNG – Tragbare Netzwerkgrafiken
  • TGA – Truevision TGA
  • TIFF – Tagged Image File Format (verlustfreie oder verlustbehaftete Komprimierung)
  • WebP – (verlustfreie oder verlustbehaftete Komprimierung von RGB- und RGBA-Bildern)

3D-Grafik

  • OpenCTM – Verlustfreie Komprimierung von 3D-Dreiecksnetzen

Video

Siehe diese Liste verlustfreier Videocodecs.

Kryptographie

Kryptosysteme komprimieren oft Daten (den "Klartext") vor der Verschlüsselung für zusätzliche Sicherheit. Bei richtiger Implementierung erhöht die Komprimierung den Einzigkeitsabstand erheblich, indem Muster entfernt werden, die die Kryptoanalyse erleichtern könnten . Viele gewöhnliche verlustfreie Komprimierungsalgorithmen erzeugen jedoch Header, Wrapper, Tabellen oder andere vorhersagbare Ausgaben, die stattdessen die Kryptoanalyse erleichtern könnten. Somit müssen Kryptosysteme Kompressionsalgorithmen verwenden, deren Ausgabe diese vorhersagbaren Muster nicht enthält.

Genetik und Genomik

Genetische Kompressionsalgorithmen (nicht zu verwechseln mit genetischen Algorithmen ) sind die neueste Generation von verlustfreien Algorithmen, die Daten (typischerweise Sequenzen von Nukleotiden) komprimieren, wobei sowohl konventionelle Kompressionsalgorithmen als auch spezifische Algorithmen verwendet werden, die an genetische Daten angepasst sind. Im Jahr 2012 veröffentlichte ein Team von Wissenschaftlern der Johns Hopkins University den ersten genetischen Kompressionsalgorithmus, der für die Kompression nicht auf externe genetische Datenbanken angewiesen ist. HAPZIPPER wurde auf HapMap- Daten zugeschnitten und erreicht eine über 20-fache Komprimierung (95% Reduzierung der Dateigröße) und bietet eine 2- bis 4-fach bessere Komprimierung viel schneller als führende allgemeine Komprimierungsprogramme.

Genomische Sequenzkompressionsalgorithmen, auch bekannt als DNA-Sequenzkompressoren, untersuchen die Tatsache, dass DNA-Sequenzen charakteristische Eigenschaften haben, wie beispielsweise invertierte Wiederholungen. Die erfolgreichsten Kompressoren sind XM und GeCo. Für Eukaryoten ist XM im Komprimierungsverhältnis etwas besser, obwohl seine Rechenanforderungen für Sequenzen größer als 100 MB unpraktisch sind.

Ausführbare Dateien

Hauptartikel: Ausführbare Komprimierung

Selbstextrahierende ausführbare Dateien enthalten eine komprimierte Anwendung und einen Dekomprimierer. Wenn der Dekomprimierer ausgeführt wird, dekomprimiert er transparent und führt die ursprüngliche Anwendung aus. Dies wird besonders häufig bei der Demo- Codierung verwendet, bei der Wettbewerbe für Demos mit strikten Größenbeschränkungen ab einer Größe von 1 KB stattfinden . Diese Art der Komprimierung ist nicht strikt auf binäre ausführbare Dateien beschränkt, sondern kann auch auf Skripte wie JavaScript angewendet werden .

Verlustfreie Kompressions-Benchmarks

Verlustfreie Komprimierungsalgorithmen und ihre Implementierungen werden routinemäßig in direkten Vergleichstests getestet . Es gibt eine Reihe bekannterer Kompressionsbenchmarks. Einige Benchmarks decken nur die Datenkompressionsrate ab , so dass Gewinner in diesen Benchmarks aufgrund der langsamen Geschwindigkeit der Top-Performer möglicherweise nicht alltagstauglich sind. Ein weiterer Nachteil einiger Benchmarks besteht darin, dass ihre Datendateien bekannt sind, sodass einige Programmautoren ihre Programme möglicherweise für die beste Leistung bei einem bestimmten Datensatz optimieren. Die Gewinner dieser Benchmarks kommen oft aus der Klasse der kontextmischen Komprimierungssoftware.

Matt Mahoney führt in seiner Februar-Ausgabe 2010 der kostenlosen Broschüre Data Compression Explained zusätzlich Folgendes auf:

  • Das Calgary Corpus aus dem Jahr 1987 ist aufgrund seiner geringen Größe nicht mehr weit verbreitet. Matt Mahoney führte die Calgary Compression Challenge durch, die vom 21. Mai 1996 bis zum 21. Mai 2016 von Leonid A. Broukhis erstellt und gepflegt wurde.
  • Der Large Text Compression Benchmark und der ähnliche Hutter Prize verwenden beide einen zugeschnittenen Wikipedia- XML- UTF-8- Datensatz.
  • Der Generic Compression Benchmark, der von Matt Mahoney verwaltet wird, testet die Komprimierung von Daten, die von zufälligen Turing-Maschinen generiert werden .
  • Sami Runsas (der Autor von NanoZip) hat Compression Ratings beibehalten, einen Benchmark ähnlich dem Maximum Compression Multiple File Test, jedoch mit minimalen Geschwindigkeitsanforderungen. Es bot den Rechner, der es dem Benutzer ermöglichte, die Bedeutung von Geschwindigkeit und Kompressionsverhältnis zu gewichten. Die Top-Programme waren aufgrund der Geschwindigkeitsanforderung ziemlich unterschiedlich. Im Januar 2010 war NanoZip das Top-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 mit einem Zeitlimit von 40 Minuten. Im Dezember 2009 war NanoZip 0.07a der bestplatzierte Archiver und der beste Single File Compressor war ccmx 1.30c.

Die Website Compression Ratings veröffentlichte eine grafische Zusammenfassung der „Grenze“ in Bezug auf Kompressionsverhältnis und -zeit.

Das Compression Analysis Tool ist eine Windows-Anwendung, die es Endbenutzern ermöglicht, die Leistungsmerkmale von Streaming-Implementierungen von LZF4, Deflate, ZLIB, GZIP, BZIP2 und LZMA mit ihren eigenen Daten zu vergleichen. Es erstellt Messwerte und Diagramme, mit denen Benutzer die Komprimierungsgeschwindigkeit, Dekomprimierungsgeschwindigkeit und Komprimierungsrate der verschiedenen Komprimierungsmethoden vergleichen und untersuchen können, wie sich Komprimierungsstufe, Puffergröße und Spülvorgänge auf die Ergebnisse auswirken.

Einschränkungen

Verlustfreie Datenkomprimierungsalgorithmen können die Komprimierung nicht für alle Eingabedatensätze garantieren. Mit anderen Worten, für jeden verlustfreien Datenkomprimierungsalgorithmus gibt es einen Eingabedatensatz, der bei der Verarbeitung durch den Algorithmus nicht kleiner wird, und für jeden verlustfreien Datenkomprimierungsalgorithmus, der mindestens eine Datei verkleinert, gibt es mindestens einen Datei, die es größer macht. Dies lässt sich mit der elementaren Mathematik leicht mit einem Zählargument namens Schubladenprinzip beweisen , wie folgt:

  • 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, so dass es eine Datei F mit einer Länge von M Bits gibt, die auf etwas kürzer komprimiert wird. Sei N die Länge (in Bits) der komprimierten Version von F .
  • Da N < M ist , behält jede Datei der Länge N ihre Größe während der Komprimierung. Es sind 2 N solcher Dateien möglich. Zusammen mit F ergibt dies 2 N +1 Dateien, die alle in eine der 2 N Dateien der Länge N komprimiert werden .
  • Aber 2 N ist kleiner als 2 N +1, so dass nach dem Schubladenprinzip eine Datei der Länge N vorhanden sein muss , die gleichzeitig die Ausgabe der Kompressionsfunktion an zwei verschiedenen Eingängen ist. Diese Datei kann nicht zuverlässig dekomprimiert werden (welches der beiden Originale sollte das ergeben?), was der Annahme widerspricht, dass der Algorithmus verlustfrei war.
  • Wir müssen daher schlussfolgern, dass unsere ursprüngliche Hypothese (dass die Komprimierungsfunktion keine Datei mehr erzeugt) notwendigerweise falsch ist.

Jeder verlustfreie Komprimierungsalgorithmus, der einige Dateien kürzer macht, muss zwangsläufig einige Dateien länger machen, aber es ist nicht notwendig, dass diese Dateien sehr viel länger werden. Die meisten praktischen Komprimierungsalgorithmen bieten eine "Escape"-Funktion, die die normale Codierung für Dateien abschalten kann, die durch die Codierung länger werden würden. Theoretisch ist nur ein einziges zusätzliches Bit erforderlich, um dem Decoder mitzuteilen, dass die normale Codierung für den gesamten Eingang ausgeschaltet wurde; die meisten Codierungsalgorithmen verwenden jedoch zu diesem Zweck mindestens ein vollständiges Byte (und normalerweise mehr als eines). Deflate komprimierte Dateien müssen beispielsweise 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 wären, dann muss für jede verlustfreie Komprimierung, die die Größe einer Datei reduziert, die erwartete Länge einer komprimierten Datei (gemittelt über alle möglichen Dateien der Länge N) notwendigerweise sein größer als N. Also , wenn wir nichts über die Eigenschaften der Daten wissen wir komprimieren, können wir auch nicht komprimieren alles an. Ein verlustfreier Komprimierungsalgorithmus ist nur dann nützlich, wenn wir bestimmte Dateitypen eher komprimieren als andere; dann könnte der Algorithmus entworfen werden, um diese Datentypen besser zu komprimieren.

Die wichtigste Lehre aus dem Argument ist also nicht, dass man große Verluste riskiert, sondern lediglich, dass man nicht immer gewinnen kann. Einen Algorithmus zu wählen bedeutet immer implizit, eine Teilmenge aller Dateien auszuwählen , die sinnvollerweise kürzer wird. Dies ist der theoretische Grund, warum wir für verschiedene Arten von Dateien unterschiedliche Komprimierungsalgorithmen benötigen: Es kann keinen Algorithmus geben, der für alle Arten von Daten geeignet ist.

Der "Trick", der es verlustfreien Komprimierungsalgorithmen ermöglicht, die für die Art von Daten, für die sie entwickelt wurden, verwendet werden, um solche Dateien konsistent in eine kürzere Form zu komprimieren, besteht darin, dass die Dateien, auf die die Algorithmen wirken sollen, alle eine Form von leicht modellierbarer Redundanz aufweisen , die der Algorithmus wurde entwickelt, um zu entfernen und gehört somit zu der Teilmenge von Dateien, die dieser Algorithmus verkürzen kann, während andere Dateien nicht komprimiert oder sogar größer werden würden. Algorithmen sind im Allgemeinen ganz speziell auf einen bestimmten Dateityp abgestimmt: Beispielsweise funktionieren verlustfreie Audiokompressionsprogramme nicht gut bei Textdateien und umgekehrt.

Insbesondere können Dateien mit Zufallsdaten durch keinen denkbaren verlustfreien Datenkomprimierungsalgorithmus konsistent komprimiert werden; tatsächlich wird dieses Ergebnis verwendet, um das Konzept der Zufälligkeit in der Kolmogorov-Komplexität zu definieren .

Es ist nachweislich unmöglich, einen Algorithmus zu erstellen, der Daten verlustfrei komprimieren kann. Während es im Laufe der Jahre viele Behauptungen gab, in denen Unternehmen eine "perfekte Komprimierung" erreicht haben, bei der eine beliebige Anzahl N zufälliger Bits immer auf N  − 1 Bit komprimiert werden kann, können diese Arten von Behauptungen sicher verworfen werden, ohne auch nur auf weitere Details zu achten das angebliche Komprimierungsschema. Ein solcher Algorithmus widerspricht grundlegenden Gesetzen der Mathematik, denn wenn er existiert, könnte er wiederholt angewendet werden, um jede Datei verlustfrei auf die Länge 1 zu reduzieren.

Andererseits ist auch nachgewiesen, dass es keinen Algorithmus gibt, um festzustellen, ob eine Datei im Sinne der Kolmogorov-Komplexität inkompressibel ist . Daher ist es möglich, dass jede bestimmte Datei, selbst wenn sie zufällig erscheint, erheblich komprimiert wird, sogar einschließlich der Größe des Dekomprimierers. Ein Beispiel sind die Ziffern der mathematischen Konstanten pi , die zufällig erscheinen, aber von einem sehr kleinen Programm erzeugt werden können. Obwohl nicht festgestellt werden kann, ob eine bestimmte Datei inkomprimierbar ist, zeigt ein einfacher Satz über inkomprimierbare Zeichenfolgen , dass über 99 % der Dateien einer bestimmten Länge nicht um mehr als ein Byte komprimiert werden können (einschließlich der Größe des Dekomprimierers).

Mathematischer Hintergrund

Abstrakt kann ein Kompressionsalgorithmus als Funktion von Sequenzen (normalerweise von Oktetten) betrachtet werden. Die Komprimierung ist erfolgreich, wenn die resultierende Sequenz kürzer ist als die ursprüngliche Sequenz (und die Anweisungen für die Dekompressionskarte). Damit ein Komprimierungsalgorithmus verlustfrei ist , muss die Komprimierungsabbildung eine Injektion von "einfachen" zu "komprimierten" Bitfolgen bilden. Das Schubladenprinzip verbietet eine Bijektion zwischen der Sammlung von Folgen der Länge N und einer Teilmenge der Sammlung von Folgen der Länge N −1. Daher ist es nicht möglich, einen verlustfreien Algorithmus zu erstellen, der die Größe jeder möglichen Eingabesequenz reduziert.

Anwendungspunkte in der realen Kompressionstheorie

Konstrukteure echter Kompressionsalgorithmen akzeptieren, dass Ströme mit hoher Informationsentropie nicht komprimiert werden können, und umfassen dementsprechend Einrichtungen zum Erkennen und Behandeln dieser Bedingung. Eine offensichtliche Methode zur Erkennung besteht darin, einen Rohkomprimierungsalgorithmus anzuwenden und zu testen, ob seine Ausgabe kleiner als ihre Eingabe ist. Manchmal erfolgt die Erkennung durch Heuristiken ; Beispielsweise kann eine Komprimierungsanwendung Dateien, deren Namen auf ".zip", ".arj" oder ".lha" enden, ohne weitere raffinierte Erkennung als nicht komprimierbar betrachten. Eine übliche Methode, mit dieser Situation umzugehen, besteht darin, Eingaben oder nicht komprimierbare Teile der Eingabe in der Ausgabe zu zitieren, um den Komprimierungsaufwand zu minimieren. Das ZIP -Datenformat gibt beispielsweise die 'Kompressionsmethode' von 'Gespeichert' für Eingabedateien an, die wörtlich in das Archiv kopiert wurden.

Die Million Random Digit Challenge

Mark Nelson hat als Reaktion auf Behauptungen über "magische" Kompressionsalgorithmen, die in comp.compression auftauchen, eine 415.241 Byte lange Binärdatei mit stark entropischem Inhalt erstellt und eine öffentliche Aufforderung von 100 US-Dollar an jeden ausgegeben, ein Programm zu schreiben, das zusammen mit seiner Eingabe , wäre kleiner als seine bereitgestellten Binärdaten, könnte sie jedoch fehlerfrei rekonstruieren. Eine ähnliche Herausforderung mit $5.000 als Belohnung wurde von Mike Goldman herausgegeben.

Siehe auch

Verweise

Weiterlesen

  • Sayood, Khalid (27. Oktober 2017). Einführung in die Datenkomprimierung . The Morgan Kaufmann Series in Multimedia Information and Systems (5 Hrsg.). Morgan Kaufmann . ISBN 978-0-12809474-7. (790 Seiten)
  • Sayood, Khalid, Hrsg. (18. Dezember 2002). Lossless Compression Handbook (Communications, Networking and Multimedia) (1 ed.). Akademische Presse . ISBN 978-0-12390754-7.CS1-Wartung: ref dupliziert Standard ( Link ) (488 Seiten)

Externe Links