Kompresja bezstratna - Lossless compression

Kompresja bezstratna to klasa algorytmów kompresji danych , która umożliwia doskonałą rekonstrukcję oryginalnych danych ze skompresowanych danych. W przeciwieństwie do tego kompresja stratna pozwala na odtworzenie jedynie przybliżenia oryginalnych danych, choć zwykle ze znacznie lepszymi współczynnikami kompresji (a tym samym zmniejszonymi rozmiarami nośników).

Zgodnie z zasadą szufladki żaden algorytm bezstratnej kompresji nie jest w stanie skutecznie skompresować wszystkich możliwych danych. Z tego powodu istnieje wiele różnych algorytmów zaprojektowanych z myślą o konkretnym typie danych wejściowych lub o określonych założeniach dotyczących tego, jakie rodzaje nadmiarowości mogą zawierać nieskompresowane dane. Dlatego współczynniki kompresji są zwykle wyższe w dokumentach i kodzie czytelnym dla człowieka i maszyny w porównaniu z entropicznymi danymi binarnymi (losowymi bajtami).

W wielu aplikacjach stosowana jest bezstratna kompresja danych. Na przykład jest używany w formacie pliku ZIP oraz w narzędziu GNU gzip . Jest również często używany jako składnik w technologiach stratnej kompresji danych (np. bezstratne wstępne przetwarzanie dźwięku środkowego/bocznego przez kodery MP3 i inne stratne kodery audio).

Kompresja bezstratna jest stosowana w przypadkach, gdy ważne jest, aby oryginalne i zdekompresowane dane były identyczne lub gdy odchylenia od oryginalnych danych byłyby niekorzystne. Typowymi przykładami są programy wykonywalne, dokumenty tekstowe i kod źródłowy. Niektóre formaty plików graficznych, takie jak PNG lub GIF , wykorzystują wyłącznie kompresję bezstratną, podczas gdy inne, takie jak TIFF i MNG, mogą używać metod bezstratnych lub stratnych. Bezstratne formaty audio są najczęściej używane do celów archiwizacji lub produkcji, podczas gdy mniejsze stratne pliki audio są zwykle używane w odtwarzaczach przenośnych oraz w innych przypadkach, gdy przestrzeń dyskowa jest ograniczona lub dokładna replikacja dźwięku jest niepotrzebna.

Bezstratne techniki kompresji

Większość programów do kompresji bezstratnej wykonuje kolejno dwie rzeczy: pierwszy krok generuje model statystyczny dla danych wejściowych, a drugi krok wykorzystuje ten model do mapowania danych wejściowych na sekwencje bitowe w taki sposób, aby „prawdopodobne” (np. często spotykane) dane da krótsze dane wyjściowe niż „nieprawdopodobne” dane.

Podstawowymi algorytmami kodowania używanymi do tworzenia sekwencji bitowych są kodowanie Huffmana (używane również przez algorytm deflate ) i kodowanie arytmetyczne . Kodowanie arytmetyczne osiąga współczynniki kompresji bliskie najlepszemu możliwemu dla konkretnego modelu statystycznego, który jest określony przez entropię informacji , podczas gdy kompresja Huffmana jest prostsza i szybsza, ale daje słabe wyniki dla modeli, które radzą sobie z prawdopodobieństwem symboli bliskim 1.

Istnieją dwa podstawowe sposoby konstruowania modeli statystycznych: w modelu statycznym dane są analizowane i konstruowany jest model, a następnie ten model jest przechowywany wraz ze skompresowanymi danymi. Takie podejście jest proste i modułowe, ale ma tę wadę, że sam model może być kosztowny w przechowywaniu, a także wymusza stosowanie jednego modelu dla wszystkich kompresowanych danych, przez co działa słabo na plikach zawierających dane heterogeniczne. Modele adaptacyjne dynamicznie aktualizują model podczas kompresji danych. Zarówno koder, jak i dekoder zaczynają od trywialnego modelu, co skutkuje słabą kompresją danych początkowych, ale im więcej dowiadują się o danych, wydajność się poprawia. Najpopularniejsze rodzaje kompresji stosowane w praktyce wykorzystują obecnie kodery adaptacyjne.

Metody kompresji bezstratnej można podzielić na kategorie w zależności od typu danych, które są przeznaczone do kompresji. Chociaż, w zasadzie, dowolny algorytm bezstratnej kompresji ogólnego przeznaczenia ( ogólnego przeznaczenia, co oznacza, że ​​może akceptować dowolny ciąg bitów) może być używany do dowolnego typu danych, wiele z nich nie jest w stanie osiągnąć znaczącej kompresji danych, które nie mają formy, dla której zostały zaprojektowane do kompresji. Wiele technik kompresji bezstratnej używanych w przypadku tekstu działa również dość dobrze w przypadku obrazów indeksowanych .

Multimedialne

Techniki te wykorzystują specyficzne cechy obrazów, takie jak powszechne zjawisko ciągłych obszarów 2D o podobnych tonach. Każdy piksel oprócz pierwszego jest zastępowany różnicą względem jego lewego sąsiada. Prowadzi to do tego, że małe wartości mają znacznie większe prawdopodobieństwo niż duże wartości. Jest to często stosowane również do plików dźwiękowych i może kompresować pliki zawierające głównie niskie częstotliwości i niski poziom głośności. W przypadku obrazów ten krok można powtórzyć, biorąc różnicę do najwyższego piksela, a następnie w przypadku filmów można uzyskać różnicę w stosunku do piksela w następnej klatce.

Hierarchiczna wersja tej techniki pobiera sąsiednie pary punktów danych, przechowuje ich różnicę i sumę, a na wyższym poziomie z niższą rozdzielczością kontynuuje sumowanie. Nazywa się to dyskretną transformatą falkową . JPEG2000 dodatkowo wykorzystuje punkty danych z innych par i mnożników, aby połączyć je w różnicę. Czynniki te muszą być liczbami całkowitymi, aby wynik był liczbą całkowitą w każdych okolicznościach. Tak więc wartości są zwiększane, zwiększając rozmiar pliku, ale miejmy nadzieję, że rozkład wartości jest bardziej szczytowy.

Kodowanie adaptacyjne wykorzystuje prawdopodobieństwa z poprzedniej próbki w kodowaniu dźwięku, z lewego i górnego piksela w kodowaniu obrazu oraz dodatkowo z poprzedniej klatki w kodowaniu wideo. W transformacji falkowej prawdopodobieństwa również przechodzą przez hierarchię.

Historyczne zagadnienia prawne

Wiele z tych metod jest zaimplementowanych w narzędziach open-source i własnościowych, w szczególności LZW i jego wariantach. Niektóre algorytmy są opatentowane w Stanach Zjednoczonych i innych krajach, a ich legalne użycie wymaga licencji właściciela patentu. Ze względu na patenty na niektóre rodzaje kompresji LZW , a w szczególności na praktyki licencyjne właściciela patentu Unisys, które wielu programistów uważało za nadużycie, niektórzy zwolennicy oprogramowania open source zachęcali ludzi do unikania używania formatu wymiany grafiki (GIF) do kompresji plików obrazów na rzecz przenośnego Grafika sieciowa (PNG), która łączy algorytm deflate oparty na LZ77 z wyborem filtrów predykcji specyficznych dla domeny. Jednak patenty na LZW wygasły 20 czerwca 2003 r.

Wiele technik kompresji bezstratnej używanych w przypadku tekstu działa również dość dobrze w przypadku obrazów indeksowanych , ale istnieją inne techniki, które nie działają w przypadku typowego tekstu, przydatne w przypadku niektórych obrazów (zwłaszcza prostych bitmap) oraz inne techniki, które wykorzystują specyficzny cechy charakterystyczne obrazów (takie jak powszechne zjawisko ciągłych obszarów dwuwymiarowych o podobnych tonach oraz fakt, że obrazy kolorowe mają zwykle przewagę ograniczonego zakresu kolorów spośród tych, które można przedstawić w przestrzeni kolorów).

Jak wspomniano wcześniej, bezstratna kompresja dźwięku to dość wyspecjalizowany obszar. Algorytmy bezstratnej kompresji dźwięku mogą wykorzystywać powtarzające się wzorce wynikające z falowego charakteru danych – zasadniczo wykorzystując modele autoregresyjne do przewidywania „następnej” wartości i kodowania (miejmy nadzieję, niewielkiej) różnicy między wartością oczekiwaną a rzeczywistymi danymi. Jeśli różnica między przewidywanymi a rzeczywistymi danymi (tzw. błędem ) wydaje się być niewielka, wtedy pewne wartości różnic (takie jak 0, +1, -1 itd. na wartościach próbek) stają się bardzo częste, co można wykorzystać poprzez ich zakodowanie w kilku bitach wyjściowych.

Czasami korzystne jest skompresowanie tylko różnic między dwiema wersjami pliku (lub, w przypadku kompresji wideo , kolejnych obrazów w sekwencji). Nazywa się to kodowaniem delta (od greckiej litery Δ , która w matematyce oznacza różnicę), ale termin ten jest zwykle używany tylko wtedy, gdy obie wersje mają znaczenie poza kompresją i dekompresją. Na przykład, podczas gdy proces kompresji błędu we wspomnianym powyżej schemacie bezstratnej kompresji dźwięku można opisać jako kodowanie delta od przybliżonej fali dźwiękowej do oryginalnej fali dźwiękowej, przybliżona wersja fali dźwiękowej nie ma znaczenia w żadnym innym kontekście .

Bezstratne metody kompresji

Zobacz też: Kategoria: Algorytmy kompresji bezstratnej i Lista algorytmów kompresji bezstratnej

Żaden algorytm kompresji bezstratnej nie jest w stanie efektywnie skompresować wszystkich możliwych danych (szczegóły w sekcji Ograniczenia poniżej). Z tego powodu istnieje wiele różnych algorytmów zaprojektowanych z myślą o konkretnym typie danych wejściowych lub o określonych założeniach dotyczących tego, jakie rodzaje nadmiarowości mogą zawierać nieskompresowane dane.

Poniżej wymieniono niektóre z najczęstszych algorytmów kompresji bezstratnej.

Ogólny cel

Audio

Grafika rastrowa

  • AVIF – AOMedia Video 1 Format pliku obrazu
  • FLIF – bezpłatny bezstratny format obrazu
  • HEIF – format pliku obrazu o wysokiej wydajności (kompresja bezstratna lub stratna, przy użyciu HEVC )
  • ILBM – (bezstratna kompresja RLE obrazów Amiga IFF )
  • JBIG2 – (bezstratna lub stratna kompresja obrazów czarno-białych)
  • JPEG 2000 – (zawiera bezstratną kompresję za pomocą odwracalnej transformacji falkowej LeGall-Tabatabai 5/3 )
  • JPEG-LS – (standard kompresji bezstratnej/prawie bezstratnej)
  • JPEG XL – (kompresja bezstratna lub stratna)
  • JPEG XR – dawniej WMPhoto i HD Photo , zawiera bezstratną metodę kompresji
  • LDCT – bezstratna dyskretna transformata kosinusowa
  • PCX – wymiana obrazów
  • PDF – Portable Document Format (kompresja bezstratna lub stratna)
  • PNG – przenośna grafika sieciowa
  • TGA – Truevision TGA
  • TIFF – Tagged Image File Format (kompresja bezstratna lub stratna)
  • WebP – (bezstratna lub stratna kompresja obrazów RGB i RGBA)

Grafika 3D

  • OpenCTM – bezstratna kompresja siatek trójkątów 3D

Wideo

Zobacz tę listę bezstratnych kodeków wideo.

Kryptografia

Kryptosystemy często kompresują dane („tekst jawny”) przed szyfrowaniem, aby zwiększyć bezpieczeństwo. Prawidłowo zaimplementowana kompresja znacznie zwiększa dystans jednorodności , usuwając wzorce, które mogą ułatwić kryptoanalizę . Jednak wiele zwykłych algorytmów kompresji bezstratnej generuje nagłówki, opakowania, tabele lub inne przewidywalne dane wyjściowe, które mogą ułatwić kryptoanalizę. Dlatego kryptosystemy muszą wykorzystywać algorytmy kompresji, których dane wyjściowe nie zawierają tych przewidywalnych wzorców.

Genetyka i genomika

Algorytmy kompresji genetycznej (nie mylić z algorytmami genetycznymi ) to najnowsza generacja bezstratnych algorytmów, które kompresują dane (zwykle sekwencje nukleotydów) przy użyciu zarówno konwencjonalnych algorytmów kompresji, jak i specyficznych algorytmów dostosowanych do danych genetycznych. W 2012 roku zespół naukowców z Johns Hopkins University opublikował pierwszy algorytm kompresji genetycznej, który nie opiera się na zewnętrznych genetycznych bazach danych do kompresji. HAPZIPPER został dostosowany do danych HapMap i osiąga ponad 20-krotną kompresję (zmniejszenie rozmiaru pliku o 95%), zapewniając od 2 do 4 razy lepszą kompresję znacznie szybciej niż wiodące narzędzia do kompresji ogólnego zastosowania.

Algorytmy kompresji sekwencji genomowej, znane również jako kompresory sekwencji DNA, badają fakt, że sekwencje DNA mają charakterystyczne właściwości, takie jak odwrócone powtórzenia. Najbardziej udanymi kompresorami są XM i GeCo. W przypadku eukariontów XM ma nieco lepszy współczynnik kompresji, chociaż dla sekwencji większych niż 100 MB jego wymagania obliczeniowe są niepraktyczne.

Pliki wykonywalne

Główny artykuł: Kompresja wykonywalna

Samorozpakowujące się pliki wykonywalne zawierają skompresowaną aplikację i dekompresor. Po uruchomieniu dekompresor w sposób przezroczysty dekompresuje i uruchamia oryginalną aplikację. Jest to szczególnie często używane w kodowaniu demo , gdzie odbywają się konkursy dla wersji demonstracyjnych o ścisłych limitach rozmiaru, wynoszących zaledwie 1k . Ten rodzaj kompresji nie jest ściśle ograniczony do plików wykonywalnych binarnych, ale można go również zastosować do skryptów, takich jak JavaScript .

Bezstratne testy porównawcze kompresji

Algorytmy kompresji bezstratnej i ich implementacje są rutynowo testowane w bezpośrednich testach porównawczych . Istnieje wiele bardziej znanych testów porównawczych kompresji. Niektóre testy porównawcze obejmują tylko współczynnik kompresji danych , więc zwycięzcy tych testów mogą nie nadawać się do codziennego użytku ze względu na niską prędkość osiąganych przez najlepszych graczy. Inną wadą niektórych testów jest to, że ich pliki danych są znane, więc niektórzy twórcy programów mogą optymalizować swoje programy w celu uzyskania najlepszej wydajności na określonym zestawie danych. Zwycięzcy tych testów często pochodzą z klasy oprogramowania do kompresji kontekstu .

Matt Mahoney w swoim wydaniu z lutego 2010 bezpłatnej broszury „ Data Compression Explained” dodatkowo wymienia następujące informacje:

  • Calgary Corpus sięga 1987 roku nie jest już powszechnie stosowane ze względu na jego niewielkie rozmiary. Matt Mahoney utrzymywał Calgary Compression Challenge, stworzony i utrzymywany od 21 maja 1996 do 21 maja 2016 przez Leonida A. Broukhisa.
  • Zarówno Big Text Compression Benchmark, jak i podobna Nagroda Huttera używają przyciętego zestawu danych XML UTF-8 z Wikipedii .
  • Generic Compression Benchmark, utrzymywany przez Matta Mahoneya, testuje kompresję danych generowanych przez losowe maszyny Turinga .
  • Sami Runsas (autor NanoZip) utrzymywał ocenę kompresji, test porównawczy podobny do testu wielu plików maksymalnej kompresji, ale z minimalnymi wymaganiami dotyczącymi szybkości. Oferował kalkulator, który pozwalał użytkownikowi ocenić znaczenie szybkości i współczynnika kompresji. Najlepsze programy były dość różne ze względu na wymagania dotyczące szybkości. W styczniu 2010 roku najpopularniejszym programem był NanoZip , a następnie FreeArc , CCM , flashzip i 7-Zip .
  • Test porównawczy Monster of Compression autorstwa Nani Francesco Antonio przetestował kompresję na 1 GB danych publicznych z 40-minutowym limitem czasu. W grudniu 2009 r. najwyżej notowanym archiwizatorem był NanoZip 0,07a, a najwyżej notowanym kompresorem pojedynczego pliku ccmx 1.30c.

Witryna internetowa Compression Ratings opublikowała podsumowanie wykresu „granicy” pod względem współczynnika kompresji i czasu.

Narzędzie do analizy kompresji to aplikacja systemu Windows, która umożliwia użytkownikom końcowym testowanie charakterystyki wydajności implementacji strumieniowych LZF4, Deflate, ZLIB, GZIP, BZIP2 i LZMA przy użyciu ich własnych danych. Tworzy pomiary i wykresy, za pomocą których użytkownicy mogą porównać szybkość kompresji, szybkość dekompresji i stopień kompresji różnych metod kompresji oraz zbadać, jak poziom kompresji, rozmiar bufora i operacje płukania wpływają na wyniki.

Ograniczenia

Algorytmy bezstratnej kompresji danych nie mogą zagwarantować kompresji dla wszystkich zestawów danych wejściowych. Innymi słowy, dla dowolnego algorytmu bezstratnej kompresji danych będzie zestaw danych wejściowych, który nie ulegnie zmniejszeniu podczas przetwarzania przez algorytm, a dla dowolnego algorytmu bezstratnej kompresji danych, który zmniejszy co najmniej jeden plik, będzie co najmniej jeden plik, który powiększa. Można to łatwo udowodnić za pomocą elementarnej matematyki przy użyciu argumentu liczenia zwanego zasadą szufladki , w następujący sposób:

  • Załóżmy, że każdy plik jest reprezentowany jako ciąg bitów o dowolnej długości.
  • Załóżmy, że istnieje algorytm kompresji, który przekształca każdy plik w plik wyjściowy, który nie jest dłuższy niż plik oryginalny, oraz że co najmniej jeden plik zostanie skompresowany do pliku wyjściowego, który jest krótszy niż plik oryginalny.
  • Niech M będzie najmniejszą liczbą taką, że istnieje plik F o długości M bitów, który skompresuje się do czegoś krótszego. Niech N będzie długością (w bitach) skompresowanej wersji F .
  • Ponieważ N < M , każdy plik o długości N zachowuje swój rozmiar podczas kompresji. Możliwych jest 2 N takich plików. Wraz z F , to sprawia, 2 N +1 pliki wszystkich kompres do jednej z 2 N plików o długości N .
  • Ale 2 N jest mniejsze niż 2 N +1, więc zgodnie z zasadą szufladki musi istnieć jakiś plik o długości N, który jest jednocześnie wyjściem funkcji kompresji na dwóch różnych wejściach. Pliku tego nie można wiarygodnie zdekompresować (który z dwóch oryginałów powinien to dać?), co jest sprzeczne z założeniem, że algorytm był bezstratny.
  • Musimy zatem dojść do wniosku, że nasza pierwotna hipoteza (że funkcja kompresji nie powoduje już braku pliku) jest z konieczności nieprawdziwa.

Każdy bezstratny algorytm kompresji, który skraca niektóre pliki, musi koniecznie wydłużać niektóre pliki, ale nie jest konieczne, aby te pliki stały się znacznie dłuższe. Większość praktycznych algorytmów kompresji zapewnia funkcję „ucieczki”, która może wyłączyć normalne kodowanie plików, które stałyby się dłuższe wskutek zakodowania. Teoretycznie wystarczy jeden dodatkowy bit, aby poinformować dekoder, że normalne kodowanie zostało wyłączone dla całego wejścia; jednak większość algorytmów kodowania używa do tego celu co najmniej jednego pełnego bajtu (i zazwyczaj więcej niż jednego). Na przykład skompresowane pliki deflate nigdy nie muszą rosnąć o więcej niż 5 bajtów na 65 535 bajtów danych wejściowych.

W rzeczywistości, jeśli weźmiemy pod uwagę pliki o długości N, jeśli wszystkie pliki były jednakowo prawdopodobne, to dla jakiejkolwiek bezstratnej kompresji, która zmniejsza rozmiar jakiegoś pliku, oczekiwana długość skompresowanego pliku (uśredniona ze wszystkich możliwych plików o długości N) musi koniecznie być większe niż N. Jeśli więc nie wiemy nic o właściwościach danych, które kompresujemy, równie dobrze możemy w ogóle ich nie kompresować. Algorytm kompresji bezstratnej jest przydatny tylko wtedy, gdy istnieje większe prawdopodobieństwo, że skompresujemy niektóre typy plików niż inne; wtedy algorytm mógłby być zaprojektowany tak, aby lepiej skompresować tego typu dane.

Zatem główna lekcja z tej argumentacji nie polega na tym, że ryzykuje się duże straty, ale po prostu, że nie zawsze można wygrać. Wybór algorytmu zawsze oznacza pośrednio wybranie podzbioru wszystkich plików, które staną się użytecznie krótsze. To jest teoretyczny powód, dla którego potrzebujemy różnych algorytmów kompresji dla różnych rodzajów plików: nie może być żadnego algorytmu, który byłby dobry dla wszystkich rodzajów danych.

„Sztuczka”, która pozwala algorytmom bezstratnej kompresji, używanym na typie danych, dla którego zostały zaprojektowane, konsekwentnie kompresować takie pliki do krótszej postaci, polega na tym, że pliki, na których algorytmy mają działać, mają pewną formę łatwej do modelowania nadmiarowości, która algorytm jest przeznaczony do usuwania, a zatem należeć do podzbioru plików, które ten algorytm może skrócić, podczas gdy inne pliki nie zostałyby skompresowane, a nawet większe. Algorytmy są zazwyczaj dość specjalnie dostrojone do konkretnego typu pliku: na przykład programy do bezstratnej kompresji dźwięku nie działają dobrze z plikami tekstowymi i na odwrót.

W szczególności pliki losowych danych nie mogą być konsekwentnie kompresowane przez jakikolwiek wyobrażalny algorytm bezstratnej kompresji danych; w rzeczywistości wynik ten jest używany do zdefiniowania pojęcia losowości w złożoności Kołmogorowa .

Stworzenie algorytmu, który może bezstratnie skompresować dowolne dane, jest niemożliwe do udowodnienia. Chociaż przez lata było wiele twierdzeń, że firmy osiągnęły „doskonałą kompresję”, w której dowolna liczba N losowych bitów może być zawsze skompresowana do N  -1 bitów, tego rodzaju twierdzenia można bezpiecznie odrzucić, nawet nie patrząc na żadne dalsze szczegóły dotyczące rzekomy schemat kompresji. Taki algorytm jest sprzeczny z podstawowymi prawami matematyki, ponieważ gdyby istniał, mógłby być stosowany wielokrotnie do bezstratnej redukcji dowolnego pliku do długości 1.

Z drugiej strony udowodniono również, że nie istnieje algorytm pozwalający określić, czy plik jest niekompresowalny w sensie złożoności Kołmogorowa . Dlatego możliwe jest, że każdy konkretny plik, nawet jeśli wydaje się losowy, może zostać znacznie skompresowany, nawet uwzględniając rozmiar dekompresora. Przykładem są cyfry stałej matematycznej pi , które pojawiają się losowo, ale mogą być generowane przez bardzo mały program. Jednak nawet jeśli nie można określić, czy dany plik jest niekompresowalny, proste twierdzenie o nieskompresowanych łańcuchach pokazuje, że ponad 99% plików o dowolnej długości nie może być skompresowanych o więcej niż jeden bajt (łącznie z rozmiarem dekompresora).

Tło matematyczne

Abstrakcyjnie, algorytm kompresji może być postrzegany jako funkcja na sekwencjach (zwykle oktetów). Kompresja jest udana, jeśli wynikowa sekwencja jest krótsza niż oryginalna sekwencja (i instrukcje dotyczące mapy dekompresji). Aby algorytm kompresji był bezstratny , mapa kompresji musi tworzyć iniekcję od „zwykłych” do „skompresowanych” sekwencji bitowych. Zasada szufladki zabrania bijekcji między zbiorem sekwencji o długości N a dowolnym podzbiorem zbioru sekwencji o długości N- 1. Dlatego nie jest możliwe stworzenie bezstratnego algorytmu, który zmniejszy rozmiar każdej możliwej sekwencji wejściowej.

Punkty zastosowania w rzeczywistej teorii kompresji

Projektanci algorytmów rzeczywistej kompresji akceptują fakt, że strumienie o wysokiej entropii informacji nie mogą być skompresowane, i w związku z tym zawierają urządzenia do wykrywania i obsługi tego stanu. Oczywistym sposobem wykrywania jest zastosowanie surowego algorytmu kompresji i sprawdzenie, czy jego wyjście jest mniejsze niż wejście. Czasami wykrywanie odbywa się za pomocą heurystyki ; na przykład aplikacja do kompresji może uznać, że pliki, których nazwy kończą się na „.zip”, „.arj” lub „.lha”, są nieskompresowalne bez bardziej zaawansowanego wykrywania. Typowym sposobem radzenia sobie z tą sytuacją jest cytowanie danych wejściowych lub nieskompresowanych części danych wejściowych w danych wyjściowych, minimalizując narzut kompresji. Na przykład format danych zip określa „metodę kompresji” „Przechowywane” dla plików wejściowych, które zostały dosłownie skopiowane do archiwum.

Wyzwanie miliona losowych cyfr

Mark Nelson, w odpowiedzi na twierdzenia o „magicznych” algorytmach kompresji pojawiających się w comp.compression, skonstruował plik binarny o wielkości 415 241 bajtów o wysoce entropicznej zawartości i wysłał każdemu publiczne wezwanie do napisania programu, który wraz z jego danymi wejściowymi zapłacił 100 USD. , byłby mniejszy niż podane przez niego dane binarne, ale byłby w stanie odtworzyć je bez błędów. Podobne wyzwanie, z nagrodą w wysokości 5000 dolarów, wystawił Mike Goldman.

Zobacz też

Bibliografia

Dalsza lektura

Zewnętrzne linki