Verlustfreie Kompression

Verlustfreie Kompression ist eine Klasse von Datenkompression Dadurch können die ursprünglichen Daten perfekt aus den komprimierten Daten ohne Verlust von rekonstruiert werden Information. Verlustlose Komprimierung ist möglich, da die meisten realen Daten eine statistische Redundanz aufweisen.[1] Im Gegensatz, Verlustige Komprimierung ermöglicht die Rekonstruktion nur einer Annäherung des Originals Daten, wenn auch normalerweise mit stark verbesserter Druckraten (und daher reduzierte Mediengrößen).

Durch Betrieb der Pigeonhole -PrinzipKein verlustfreier Komprimierungsalgorithmus kann alle möglichen Daten effizient komprimieren. Aus diesem Grund existieren viele verschiedene Algorithmen, die entweder mit einem bestimmten Typ Eingabedaten oder mit bestimmten Annahmen über welche Arten von entworfen wurden Redundanz Die unkomprimierten Daten enthalten wahrscheinlich. Daher sind die Komprimierungsverhältnisse in der Regel bei menschlichen und maschinenlesbaren Dokumenten und Code im Vergleich zu entropischen Binärdaten (zufällige Bytes) stärker.[2]

Verlustlose Datenkomprimierung wird in vielen Anwendungen verwendet. Zum Beispiel wird es in der verwendet POSTLEITZAHL Dateiformat und in der GNU Werkzeug gzip. Es wird auch häufig als Komponente innerhalb der Verlustdatenkomprimierungstechnologien verwendet (z. B. verlustlos Mid/Side -Gelenk -Stereoanlage Vorverarbeitung durch MP3 Encoder und andere verlustige Audio -Encoder).[3]

Verlustlose Komprimierung wird in Fällen verwendet, in denen es wichtig ist, dass das Original und die dekomprimierten Daten identisch sind oder in denen Abweichungen von den ursprünglichen Daten ungünstig wären. Typische Beispiele sind ausführbare Programme, Textdokumente und Quellcode. Einige Bilddateiformate wie Png oder GIFVerwenden Sie nur verlustfreie Komprimierung, während andere mögen Tiff und Mng Kann entweder verlustlose oder verlustige Methoden anwenden. Verlustloser Audio Formate werden am häufigsten für Archivierungs- oder Produktionszwecke verwendet, während sie kleiner sind Verlustiger Audio Dateien werden in der Regel für tragbare Spieler verwendet und in anderen Fällen, in denen der Speicherplatz begrenzt ist oder die genaue Replikation des Audios nicht erforderlich ist.

Techniken

Die am meisten verlustfreien Komprimierungsprogramme tun zwei Dinge in Sequenz: Der erste Schritt erzeugt a Statistisches Modell Für die Eingabedaten verwendet der zweite Schritt dieses Modell, um Eingabedaten in Bitsequenzen so zuzuordnen, dass "wahrscheinliche" Daten (d. H. Häufig aufgetretene) Daten zu einer kürzeren Ausgabe als "unwahrscheinliche" Daten erzeugt.

Die primären Codierungsalgorithmen zur Erzeugung von Bitsequenzen sind Huffman -Codierung (Auch von der verwendet Deflate -Algorithmus) und arithmetische Kodierung. Die arithmetische Codierung erreicht Kompressionsraten nahe am besten für ein bestimmtes statistisches Modell, das durch die angegeben ist Informationsentropie, während die Huffman -Komprimierung einfacher und schneller ist, aber schlechte Ergebnisse für Modelle liefert, die sich mit Symbolwahrscheinlichkeiten in der Nähe von 1 befassen.

Es gibt zwei Hauptmethoden, um statistische Modelle zu konstruieren: in a statisch Modell, die Daten werden analysiert und ein Modell erstellt, dann wird dieses Modell mit den komprimierten Daten gespeichert. Dieser Ansatz ist einfach und modular, hat jedoch den Nachteil, dass das Modell selbst teuer zu speichern sein kann und dass es die Verwendung eines einzelnen Modells für alle zu komprimierten Daten erzwingt und so bei Dateien, die heterogene Daten enthalten, schlecht abschneidet. Adaptiv Modelle aktualisieren das Modell dynamisch, wenn die Daten komprimiert werden. Sowohl der Encoder als auch der Decoder beginnen mit einem trivialen Modell, was zu einer schlechten Komprimierung der Anfangsdaten führt. Wenn sie jedoch mehr über die Daten erfahren, verbessert sich die Leistung. Die beliebtesten Komprimierungsarten, die in der Praxis verwendet werden, verwenden jetzt adaptive Codierer.

Verlustlose Komprimierungsmethoden können nach der Art der Daten kategorisiert werden, die sie für die Komprimierung ausgelegt sind. Während im Prinzip jeder allgemeine verlustfreie Kompressionsalgorithmus (allgemeiner Zweck Dies bedeutet, dass sie für jede Art von Daten eine Bitstring akzeptieren können. Viele können keine signifikante Komprimierung für Daten erzielen, die nicht von der Form sind, für die sie zum Komprimieren konzipiert wurden. Viele der verlustfreien Komprimierungstechniken, die für Text verwendet werden indizierte Bilder.

Multimedia

Diese Techniken nutzen die spezifischen Eigenschaften von Bildern wie das gemeinsame Phänomen von zusammenhängenden 2-D-Bereichen ähnliche Töne. Jedes Pixel, aber der erste wird durch den Unterschied zu seinem linken Nachbarn ersetzt. Dies führt zu kleinen Werten mit einer viel höheren Wahrscheinlichkeit als große Werte. Dies wird häufig auch auf Sounddateien angewendet und kann Dateien komprimieren, die hauptsächlich niedrige Frequenzen und niedrige Volumina enthalten. Für Bilder kann dieser Schritt wiederholt werden, indem der Unterschied zum oberen Pixel und dann in Videos der Unterschied zum Pixel im nächsten Rahmen aufgenommen werden kann.

Eine hierarchische Version dieser Technik erfordert benachbarte Datenpunkte, speichert ihre Differenz und Summe und wird auf einer höheren Ebene mit niedrigerer Auflösung mit den Summen fortgesetzt. Das nennt man Diskrete Wavelet -Transformation. JPEG2000 Verwendet zusätzlich Datenpunkte von anderen Paaren und Multiplikationsfaktoren, um sie in den Unterschied zu mischen. Diese Faktoren müssen Ganzzahlen sein, so dass das Ergebnis unter allen Umständen eine ganze Zahl ist. Die Werte werden also erhöht und erhöht die Dateigröße, aber hoffentlich wird die Werteverteilung mehr ihren Höhepunkt erreicht.

Die adaptive Codierung verwendet die Wahrscheinlichkeiten aus der vorherigen Stichprobe in der Schallcodierung, vom linken und oberen Pixel in der Bildcodierung und zusätzlich aus dem vorherigen Frame in der Videocodierung. Bei der Wavelet -Transformation werden auch die Wahrscheinlichkeiten durch die Hierarchie weitergegeben.

Historische Rechtsfragen

Viele dieser Methoden werden in Open-Source- und proprietären Tools, insbesondere LZW und seinen Varianten, implementiert. Einige Algorithmen sind in der patentiert Vereinigte Staaten und andere Länder und ihre rechtliche Verwendung erfordern die Lizenzierung durch den Patentinhaber. Wegen Patenten auf bestimmte Arten von LZW Komprimierung und insbesondere Lizenzpraktiken von Patentinhabern Unisys, die viele Entwickler als missbräuchlich angesehen haben, ermutigten einige Open -Source -Befürworter die Menschen, die Verwendung der Verwendung zu vermeiden Grafik -Austauschformat (GIF) zum Komprimieren von Standbildedateien zugunsten von Tragbare Netzwerkgrafiken (PNG), das die kombiniert LZ77-basierend Deflate -Algorithmus mit einer Auswahl von domänenspezifischen Vorhersagefiltern. Die Patente auf LZW ließen jedoch am 20. Juni 2003 ab.[4]

Viele der verlustfreien Komprimierungstechniken, die für Text verwendet werden indizierte BilderEs gibt jedoch andere Techniken, die für typische Text nicht funktionieren, die für einige Bilder (insbesondere einfache Bitmaps) nützlich sind, und andere Techniken, die die spezifischen Eigenschaften von Bildern ausnutzen (wie das gemeinsame Phänomen von zusammenhängenden 2-D-Bereichen von Ähnliche Töne und die Tatsache, dass Farbbilder normalerweise ein Überwiegen einer begrenzten Farbpalette aus den im Farbraum darstellbaren Farben haben).

Wie bereits erwähnt, ist eine verlustfreie Klangkomprimierung ein etwas spezialisierter Bereich. Verlustlose Schallkomprimierungsalgorithmen können die Wiederholungsmuster nutzen, die durch die wellenähnliche Natur der Daten gezeigt werden-im Wesentlichen verwendet autoregressiv Modelle zur Vorhersage des "nächsten" Wertes und der Codierung der (hoffentlich kleinen) Differenz zwischen dem erwarteten Wert und den tatsächlichen Daten. Wenn der Unterschied zwischen den vorhergesagten und den tatsächlichen Daten (genannt die Error) ist in der Regel klein, dann werden bestimmte Differenzwerte (wie 0, +1, –1 usw. auf Stichprobenwerte) sehr häufig, was durch Codierung in wenigen Ausgangsbits ausgenutzt werden kann.

Es ist manchmal vorteilhaft, nur die Unterschiede zwischen zwei Versionen einer Datei zu komprimieren (oder in Video-Kompression, von aufeinanderfolgenden Bildern innerhalb einer Sequenz). Das nennt man Delta -Codierung (Aus dem griechischen Brief Δ, was in der Mathematik einen Unterschied bezeichnet), aber der Begriff wird normalerweise nur verwendet, wenn beide Versionen externe Komprimierung und Dekompression aussagekräftig sind. Während beispielsweise der Prozess der Komprimierung des Fehlers im oben genannten verlustfreien Audiokomprimierungsschema als Delta-Codierung von der angenähte Schallwelle zur ursprünglichen Schallwelle beschrieben werden könnte, ist die angenähte Version der Schallwelle in einem anderen Kontext nicht aussagekräftig .

Methoden

Siehe auch: Kategorie: Verlustlose 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 einem bestimmten Typ von Eingabedaten oder mit spezifischen Annahmen darüber ausgelegt sind, welche Art von Redundanz die unkomprimierten Daten wahrscheinlich enthalten sind.

Einige der häufigsten verlustfreien Komprimierungsalgorithmen sind unten aufgeführt.

Allgemeiner Zweck

Audio

Rastergrafiken

  • Avif - Aomedia Video 1 Bilddateiformat
  • Flif - kostenloses verlustfreies Bildformat
  • Heif - Bilddateiformat mit hoher Effizienz (verlustfreie oder verlustige Komprimierung, Verwendung HEVC)
  • ILBM - (Verlustlose RLE -Kompression von Amiga IFF Bilder)
  • JBIG2 - (verlustfreie oder verlustige Kompression von B & W -Bildern)
  • JPEG 2000 - (beinhaltet eine verlustlose Komprimierungsmethode über Le Gall -Tabatabai 5/3[5][6][7] Reversible Ganzzahl Wavelet -Transformation)
  • JPEG-LS -(Verlustlos/nahezu verlustfreier Kompressionsstandard)
  • JPEG XL - (verlustfreie oder verlustige Kompression)
  • JPEG XR - früher Wmphoto und HD -Fotobeinhaltet eine verlustfreie Komprimierungsmethode
  • LDCT - Verlustlos Diskrete Cosinus -Transformation[8][9]
  • PCX - Bildaustausch
  • PDF - Tragbares Dokumentformat (verlustfreie oder verlustige Komprimierung)
  • Png - tragbare Netzwerkgrafiken
  • TGA - Truevision TGA
  • Tiff - Tagged Image -Dateiformat (verlustfreie oder verletzte Komprimierung)
  • Webp - (verlustfreie oder verlustige Komprimierung von RGB- und RGBA -Bildern)

3D -Grafik

  • Openenck - Verlustlose Kompression von 3D -Dreiecksnetzen

Video

Sehen Liste der verlustfreien Video -Codecs

Kryptographie

Kryptosysteme häufig komprimieren Daten (der "Klartext") Vor Verschlüsselung für zusätzliche Sicherheit. Bei ordnungsgemäßer Implementierung erhöht die Komprimierung das erheblich Einheitliche Entfernung durch Entfernen von Mustern, die erleichtern könnten Kryptanalyse.[10] Viele gewöhnliche verlustfreie Komprimierungsalgorithmen erzeugen jedoch Header, Wrapper, Tabellen oder andere vorhersehbare Ausgaben, die stattdessen die Kryptanalyse erleichtern könnten. Daher müssen Kryptosysteme Komprimierungsalgorithmen verwenden, deren Ausgabe diese vorhersehbaren Muster nicht enthält.

Genetik und Genomik

Genetik -Komprimierungsalgorithmen (nicht mit Verwirrung mit genetische Algorythmen) sind die neueste Generation von verlustfreien Algorithmen, die Daten (typischerweise Sequenzen von Nukleotiden) unter Verwendung herkömmlicher Komprimierungsalgorithmen und spezifischen Algorithmen komprimieren, die an genetische Daten angepasst sind. Im Jahr 2012 veröffentlichte ein Team von Wissenschaftlern der Johns Hopkins University den ersten genetischen Komprimierungsalgorithmus, der sich nicht auf externe genetische Datenbanken zur Komprimierung stützt. Hapzipper war auf zu maßgeschneidert Hapmap Daten und erreicht eine über 20-fache Komprimierung (95% Reduzierung der Dateigröße) und bietet 2- bis 4-fach eine bessere Komprimierung viel schneller als die führenden allgemeinen Komprimierungsversorgungsunternehmen.[11]

Genomische Sequenzkomprimierungsalgorithmen, auch als DNA -Sequenzkompressoren bekannt, untersuchen die Tatsache, dass DNA -Sequenzen charakteristische Eigenschaften wie umgekehrte Wiederholungen aufweisen. Die erfolgreichsten Kompressoren sind XM und GECO.[12] Zum Eukaryoten XM ist im Komprimierungsverhältnis etwas besser, obwohl für Sequenzen, die größer als 100 MB sind, ihre Rechenanforderungen unpraktisch sind.

Ausführbare

Hauptartikel: Ausführbare Komprimierung

Self-Extracing-ausführbare Bereiche enthalten eine komprimierte Anwendung und einen Dekompressor. Bei der Ausführung dekomprimiert der Dekompressor transparent und führt die ursprüngliche Anwendung aus. Dies wird besonders oft in verwendet Demo Codierung, wo Wettbewerbe für Demos mit strengen Größengrenzen abgehalten werden, so klein wie 1k. Diese Art der Komprimierung ist nicht streng auf binäre ausführbare Ausführungen beschränkt, kann aber auch auf Skripte angewendet werden, wie z. JavaScript.

Benchmarks

Verlustlose Komprimierungsalgorithmen und ihre Implementierungen werden routinemäßig in Kopf zu Kopf getestet Benchmarks. Es gibt eine Reihe bekannteren Kompressionsbenchmarks. Einige Benchmarks decken nur die ab DatenkomprimierungsverhältnisDaher können die Gewinner in diesen Benchmarks aufgrund der langsamen Geschwindigkeit der Top -Performer für den täglichen Gebrauch ungeeignet sein. Ein weiterer Nachteil einiger Benchmarks ist, dass ihre Datendateien bekannt sind, sodass einige Programmautoren ihre Programme für die beste Leistung in einem bestimmten Datensatz optimieren können. Die Gewinner dieser Benchmarks stammen oft aus der Klasse von Kontextmischung Kompressionssoftware.

Matt MahoneyIn seiner Februar 2010 Ausgabe der kostenlosen Broschüre Datenkomprimierung erläutertlistet zusätzlich Folgendes auf:[13]

  • Das Calgary Corpus Das Ausgang von 1987 wird aufgrund seiner geringen Größe nicht mehr weit verbreitet. Matt Mahoney behielt die Calgary Compression Challenge, die vom 21. Mai 1996 bis 21. Mai 2016 von Leonid A. Broukhis erstellt und gepflegt wurde.
  • Der große Benchmark der Textkompression[14] und das ähnliche Hutter -Preis Beide verwenden eine Trimmen Wikipedia Xml UTF-8 Datensatz.
  • Der generische Kompressionsbenchmark,[15] Aufrechterhalten von Matt Mahoney Tests Komprimierung von Daten, die durch zufällig generiert wurden Turing -Maschinen.
  • Sami Runsas (der Autor von Nanozip) hat die Komprimierungsbewertungen beibehalten, ein Benchmark ähnlich dem maximalen Komprimierung mehrerer Dateitest, jedoch mit minimalen Geschwindigkeitsanforderungen. Es bot dem Taschenrechner, der es dem Benutzer ermöglichte, die Bedeutung des Geschwindigkeits- und Komprimierungsverhältnisses zu gewichten. Die Top -Programme waren aufgrund des Geschwindigkeitsbedarfs ziemlich unterschiedlich. Im Januar 2010 war das Top -Programm Nanozip, gefolgt von Freearc, CCM, Flashzip und 7-Zip.
  • Das Monster der Kompressionsbenchmark von Nania Francesco Antonio testete die Komprimierung auf 1 GB öffentliche Daten mit einer Zeitlimit von 40 Minuten. Im Dezember 2009 war der Top -Archiver Nanozip 0,07A und der oberste Einzeldateikompressor CCMX 1,30C.

Auf der Website der Komprimierungsbewertungen veröffentlichte eine Tabellenzusammenfassung der "Frontier" in Komprimierungsverhältnis und Zeit.[16]

Das Kompressionsanalyse -Tool[17] ist eine Windows -Anwendung, mit der Endbenutzer die Leistungsmerkmale von Streaming -Implementierungen von LZF4, Deflate, ZLIB, GZIP, BZIP2 und LZMA unter Verwendung ihrer eigenen Daten verbieten können. Es erzeugt Messungen und Diagramme, mit denen Benutzer die Komprimierungsgeschwindigkeit, die Dekompressionsgeschwindigkeit und das Komprimierungsverhältnis der verschiedenen Komprimierungsmethoden vergleichen können, und um zu untersuchen, wie sich die Komprimierungsstufe, die Puffergröße und die Spülung die Ergebnisse auswirken.

Einschränkungen

Verlustlose Datenkomprimierungsalgorithmen (die keine Komprimierungs -ID -Bezeichnungen an ihre Ausgangsdatensätze anschließen) können die Komprimierung für alle Eingabedatensätze nicht garantieren. Mit anderen Worten, für jeden verlustfreien Datenkomprimierungsalgorithmus wird es einen Eingabedatensatz geben, der beim Verarbeiten vom Algorithmus nicht kleiner wird, und für jeden verlustfreien Datenkomprimierungsalgorithmus, der mindestens eine Datei kleiner macht, gibt es mindestens einen Datei, die es größer macht. Dies wird leicht bei der elementaren Mathematik unter Verwendung eines Zählarguments bezeichnet Pigeonhole -Prinzip, folgendermaßen:[18][19]

  • Angenommen, jede Datei wird als eine Zeichenfolge einer beliebigen 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 kürzere Ausgabedatei komprimiert wird als die ursprüngliche Datei.
  • Lassen M Seien Sie die geringste Zahl, so dass es eine Datei gibt F mit Länge M Bits, die zu etwas Kürzerem komprimiert werden. Lassen N die Länge (in Bits) der komprimierten Version von sein F.
  • Da N<M, jeder Längendatei N Hält seine Größe während der Kompression. Da sind 2N Solche Dateien möglich. Zusammen mit Fdas macht 2N+1 Dateien, die alle zu einem der 2 komprimierenN Längendateien N.
  • Aber 2N ist kleiner als 2N+1, also muss es nach dem Pigeonhole -Prinzip eine Längedatei geben N Das ist gleichzeitig die Ausgabe der Komprimierungsfunktion auf zwei verschiedenen Eingängen. Diese Datei kann nicht zuverlässig dekomprimiert werden (welcher der beiden Originale sollte diesergeben?), Was der Annahme widerspricht, dass der Algorithmus verlustlos war.
  • Wir müssen daher zu dem Schluss kommen, dass unsere ursprüngliche Hypothese (dass die Komprimierungsfunktion keine Datei länger macht) notwendigerweise nicht wahr ist.

Die meisten praktischen Komprimierungsalgorithmen bieten eine "Escape" -Funktion, mit der die normale Codierung für Dateien deaktiviert werden kann, die länger werden würden, wenn sie codiert werden. Theoretisch ist nur ein einziges zusätzliches Bit erforderlich, um dem Decoder mitzuteilen, dass die normale Codierung für die gesamte Eingabe ausgeschaltet wurde. Die meisten Codierungsalgorithmen verwenden jedoch zu diesem Zweck mindestens ein vollständiges Byte (und in der Regel mehr als eine). Zum Beispiel, Deflate Komprimierte Dateien müssen nie um mehr als 5 Bytes pro 65.535 Bytes Eingabe wachsen.

Wenn wir Dateien mit Länge n berücksichtigen, wenn alle Dateien gleich wahrscheinlich waren, muss für eine verlustfreie Komprimierung, die die Größe einer Datei verringert sein größer als N. Wenn wir also nichts über die Eigenschaften der Daten wissen, die wir komprimieren, können wir sie auch überhaupt nicht komprimieren. Ein verlustfreier Komprimierungsalgorithmus ist nur dann nützlich, wenn wir bestimmte Arten von Dateien eher komprimieren als andere. Dann könnte der Algorithmus so ausgelegt sein, dass diese Arten von Daten besser komprimiert werden.

Die Hauptstunde aus dem Argument ist also nicht, dass man große Verluste riskiert, sondern nur, dass man nicht immer gewinnen kann. Ein Algorithmus zu wählen bedeutet immer implizit, a zu wählen Teilmenge von allen Dateien, die zweckmäßig kürzer werden. Dies ist der theoretische Grund, warum wir für verschiedene Arten von Dateien unterschiedliche Komprimierungsalgorithmen benötigen: Es gibt keinen Algorithmus, der für alle Arten von Daten gut ist.

Der "Trick", der verlustfreie Komprimierungsalgorithmen ermöglicht, die für die Art der Daten verwendet werden, für die sie entwickelt wurden, um solche Dateien konsistent zu komprimieren Redundanz Dass der Algorithmus entfernen ist und daher zu der Teilmenge der Dateien gehört, die dieser Algorithmus kürzer machen kann, während andere Dateien nicht komprimiert oder sogar größer werden. Algorithmen sind im Allgemeinen ganz spezifisch auf eine bestimmte Art von Datei abgestimmt: Beispielsweise funktionieren verlustlose Audiokomprimierungsprogramme nicht gut in Textdateien und umgekehrt.

Insbesondere Dateien von zufällig Daten können nicht durch einen denkbaren verlustfreien Datenkomprimierungsalgorithmus konsistent komprimiert werden. In der Tat wird dieses Ergebnis verwendet definieren das Konzept der Zufälligkeit in Kolmogorov -Komplexität.[20]

Es ist nachweislich unmöglich, einen Algorithmus zu erstellen, der Daten verliertlos komprimieren kann. Während es in den Jahren von Unternehmen, die eine "perfekte Komprimierung" erzielten, in denen eine willkürliche Zahl "perfekte Komprimierung" erreicht hat, gab es zwar viele Behauptungen N von zufälligen Bits können immer komprimiert werden N- 1 Bit, diese Arten von Ansprüchen können sicher verworfen werden, ohne dass sich weitere Details zum angeblichen Komprimierungsschema ansehen. Ein solcher Algorithmus widerspricht den grundlegenden Gesetzen der Mathematik, da er, wenn er existierte, wiederholt angewendet werden könnte, um eine Datei verlängertlos auf Länge 1 zu reduzieren.[19]

Andererseits wurde es auch nachgewiesen[21] dass es keinen Algorithmus gibt, um festzustellen, ob eine Datei im Sinne von inkompressiv ist Kolmogorov -Komplexität. Daher ist es möglich, dass eine bestimmte Datei, auch wenn sie zufällig erscheint, erheblich komprimiert werden kann, auch einschließlich der Größe des Dekompressors. Ein Beispiel sind die Ziffern der mathematischen Konstante Pi, die zufällig erscheinen, aber durch ein sehr kleines Programm generiert werden können. Obwohl nicht festgelegt werden kann, ob eine bestimmte Datei inkompressibel ist, a Einfacher Satz über inkompressible Saiten zeigt, dass über 99% der Dateien einer bestimmten Länge nicht durch mehr als ein Byte (einschließlich der Größe des Dekompressors) komprimiert werden können.

Mathematischer Hintergrund

Abstrakt, a Kompressionsalgorithmus kann als als angesehen werden Funktion auf Sequenzen (normalerweise von Oktetten). Die Komprimierung ist erfolgreich, wenn die resultierende Sequenz kürzer ist als die ursprüngliche Sequenz (und die Anweisungen für die Dekompressionskarte). Für einen Komprimierungsalgorithmus zu sein VerlustlosDie Komprimierungskarte muss eine bilden Injektion Von "einfachen" bis "komprimierten" Bitsequenzen. Das Pigeonhole -Prinzip verbietet eine Bijektion zwischen der Sammlung von Längesequenzen N und jede Teilmenge der Sammlung von Längesequenzen N–1. Daher ist es nicht möglich, einen verlustfreien Algorithmus zu erzeugen, der die Größe jeder möglichen Eingangssequenz verringert.[22]

Anwendungsstellen in der realen Komprimierungstheorie

Echte Komprimierungsalgorithmus -Designer akzeptieren, dass Ströme mit hoher Informationsentropie nicht komprimiert werden können, und entsprechend Einrichtungen zum Erkennen und Umgang mit diesem Zustand. Eine offensichtliche Erkennungsmethode besteht darin, einen Rohkomprimierungsalgorithmus anzuwenden und zu testen, ob sein Ausgang kleiner als der Eingang ist. Manchmal erfolgt die Erkennung von Heuristik; Beispielsweise kann eine Komprimierungsanwendung Dateien berücksichtigen, deren Namen in ".zip", ".arj" oder ".lha" ohne eine anspruchsvollere Erkennung unkompliziert sind. Eine häufige Art, diese Situation zu behandeln, besteht darin, Eingänge oder unkommerhafte Teile der Eingabe im Ausgang zu zitieren, wodurch der Kompressionsaufwand minimiert wird. Zum Beispiel die Postleitzahl Das Datenformat gibt die "Komprimierungsmethode" von "gespeichert" für Eingabedateien an, die in das Archivverbatim kopiert wurden.[23]

Die millionenfach zufällige Zifferherausforderung

Mark Nelson hat als Reaktion auf Ansprüche von "Magic" -Komprimierungsalgorithmen, die in Comp.compression erscheinen , wäre kleiner als seine bereitgestellten Binärdaten, aber in der Lage sein, sie ohne Fehler wiederherzustellen.[24] Eine ähnliche Herausforderung mit 5.000 US -Dollar als Belohnung wurde von Mike Goldman herausgegeben.[25]

Siehe auch

Verweise

  1. ^ "Einheit 4 Lab 4: Datendarstellung und Komprimierung, Seite 6". bjc.edc.org. Abgerufen 9. April, 2022.
  2. ^ "Achten Sie auf Ärger - Image Rars". Abgerufen 27. September, 2021.
  3. ^ Preis, Andy (3. März 2022). "Verlustloses Streaming - Die Zukunft von High Res Audio". Audio Media International.
  4. ^ "LZW -Patentinformationen". Über Unisys. Unisys. Archiviert von das Original am 2. Juni 2009.
  5. ^ Sullivan, Gary (8. bis 12. Dezember 2003). "Allgemeine Merkmale und Konstruktionsüberlegungen für die zeitliche Subband -Videocodierung". Itu-t. Videocodierungsexperten Gruppe. Abgerufen 13. September, 2019.
  6. ^ Usser, M.; Blu, T. (2003). "Mathematische Eigenschaften der JPEG2000 -Wavelet -Filter" (PDF). IEEE -Transaktionen zur Bildverarbeitung. 12 (9): 1080–1090. Bibcode:2003itip ... 12.1080U. doi:10.1109/Tipp.2003.812329. PMID 18237979. S2CID 2765169. Archiviert von das Original (PDF) am 13. Oktober 2019.
  7. ^ Bovik, Alan C. (2009). Die wesentliche Anleitung zur Videoverarbeitung. Akademische Presse. p. 355. ISBN 9780080922508.
  8. ^ Ahmed, Nasir; Mandyam, Giridhar D.; Magotra, Neeraj (17. April 1995). "DCT-basiertes Schema für verlustfreie Bildkomprimierung". Digitale Videokomprimierung: Algorithmen und Technologien 1995. Internationale Gesellschaft für Optik und Photonik. 2419: 474–478. Bibcode:1995spie.2419..474m. doi:10.1117/12.206386. S2CID 13894279.
  9. ^ Komatsu, K.; Sezaki, Kaoru (1998). "Reversible diskrete Cosinus -Transformation". Proceedings der IEEE International Conference für Akustik, Sprach- und Signalverarbeitung von 1998, ICASSP '98 (Kat. Nr. 98CH36181). 3: 1769–1772 Vol.3. doi:10.1109/ICASSP.1998.681802. ISBN 0-7803-4428-6. S2CID 17045923.
  10. ^ Alfred J. Menezes; Paul C. Van Oorschot; Scott A. Vanstone (16. Oktober 1996). Handbuch der angewandten Kryptographie. CRC Press. ISBN 978-1-4398-2191-6.
  11. ^ Chanda, P.; Elhaik, E.; Bader, J.S. (2012). "Hapzipper: Teilen von Hapmap -Populationen wurde einfach einfacher". Nukleinsäuren Res. 40 (20): 1–7. doi:10.1093/nar/gks709. PMC 3488212. PMID 22844100.
  12. ^ Pratas, D.; Pinho, A. J.; Ferreira, P. J. S. G. (2016). "Effiziente Komprimierung genomischer Sequenzen". Datenkomprimierungskonferenz (PDF). Snowbird, Utah.
  13. ^ Matt Mahoney (2010). "Datenkomprimierung erklärt" (PDF). S. 3–5.
  14. ^ "Großer Textkomprimierung Benchmark". Mattmahoney.net.
  15. ^ "Generisches Kompressionsbenchmark". Mattmahoney.net.
  16. ^ Visualisierung des Komprimierungsverhältnisses und der Zeit
  17. ^ "Komprimierungsanalyse -Tool". Kostenlose Werkzeuge. Noemax Technologies.
  18. ^ Sayood 2002, p. 41.
  19. ^ a b Bell, Tim (28. September - 1. Oktober 2015). "Überraschende Informatik". 8. Internationale Konferenz über Informatik in Schulen: Situation, Entwicklung und Perspektiven. Vorlesungsnotizen in Informatik. Springer. 9378: 8–9. doi:10.1007/978-3-319-25396-1. ISBN 978-3-319-25396-1. S2CID 26313283. Abgerufen 24. August, 2021.
  20. ^ Sayood 2002, p. 38.
  21. ^ Li, Ming; Vitányi, Paul (1993). Eine Einführung in die Komplexität von Kolmogorov und ihre Anwendungen. New York: Springer. p. 102. ISBN 0-387-94053-7. Satz 2.6 Die Funktion ist nicht teilweise rekursiv.
  22. ^ Joshi, Mark S. (18. März 2015). "Kapitel 3 - Das Pigeonhole -Prinzip". Beweismuster. Springer. p. 21. doi:10.1007/978-3-319-16250-8_3. ISBN 978-3-319-16250-8. Abgerufen 24. August, 2021.
  23. ^ ".Zip Dateiformatspezifikation". PKware, Inc. Kapitel V, Abschnitt J.
  24. ^ Nelson, Mark (20. Juni 2006). "Die millionenfach zufällige Digit Challenge überprüft".
  25. ^ Craig, Patrick. "Die 5000 -Dollar -Komprimierungsherausforderung". Abgerufen 8. Juni, 2009.

Weitere Lektüre

  • Sayood, Khalid (27. Oktober 2017). Einführung in die Datenkomprimierung. Die Morgan Kaufmann -Serie in Multimedia -Informationen und -Systemen (5 ed.). Morgan Kaufmann. ISBN 978-0-12809474-7. (790 Seiten)
  • Sayood, Khalid, hrsg. (18. Dezember 2002). Verlustloses Komprimierungshandbuch (Kommunikation, Netzwerk und Multimedia) (1 ed.). Akademische Presse. ISBN 978-0-12390754-7. (488 Seiten)

Externe Links