Bezstratna kompresja

Kompresja bezstratna to klasa kompresji danych , która umożliwia doskonałą rekonstrukcję oryginalnych danych ze skompresowanych danych bez utraty informacji . Kompresja bezstratna jest możliwa, ponieważ większość rzeczywistych danych wykazuje redundancję statystyczną. Z kolei kompresja stratna pozwala na rekonstrukcję jedynie przybliżonych danych oryginalnych , chociaż zwykle ze znacznie poprawionymi współczynnikami kompresji (a tym samym zmniejszonymi rozmiarami nośników).

Działając na zasadzie szufladki , żaden algorytm kompresji bezstratnej nie jest w stanie skutecznie skompresować wszystkich możliwych danych. Z tego powodu istnieje wiele różnych algorytmów zaprojektowanych z myślą o określonym typie danych wejściowych lub z określonymi założeniami dotyczącymi rodzajów redundancji , jakie mogą zawierać nieskompresowane dane. Dlatego współczynniki kompresji są zwykle silniejsze w dokumentach i kodzie czytelnym dla ludzi i maszyn w porównaniu z entropicznymi danymi binarnymi (losowe bajty).

Bezstratna kompresja danych jest wykorzystywana w wielu aplikacjach. Na przykład jest używany w ZIP oraz w narzędziu GNU gzip . Jest również często używany jako komponent w technologiach stratnej kompresji danych (np. bezstratne stereo mid/side przez kodery MP3 i inne stratne kodery audio).

Kompresję bezstratną stosuje się w przypadkach, gdy ważne jest, aby dane oryginalne i zdekompresowane były identyczne lub gdy odchylenia od danych oryginalnych 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 , używają tylko kompresji bezstratnej, podczas gdy inne, takie jak TIFF i MNG , mogą używać metod bezstratnych lub stratnych. Bezstratne formaty audio są najczęściej wykorzystywane do celów archiwizacyjnych lub produkcyjnych, natomiast mniejsze stratne formaty audio Pliki są zwykle używane w odtwarzaczach przenośnych oraz w innych przypadkach, w których przestrzeń dyskowa jest ograniczona lub dokładna replikacja dźwięku nie jest konieczna.

Techniki

Większość programów do bezstratnej kompresji robi dwie rzeczy po kolei: pierwszy krok generuje model statystyczny dla danych wejściowych, a drugi krok używa tego modelu do odwzorowania danych wejściowych na sekwencje bitów w taki sposób, że „prawdopodobne” (tzn. często spotykane) dane da krótszy wynik niż dane „nieprawdopodobne”.

Podstawowymi algorytmami kodowania używanymi do tworzenia sekwencji bitów są kodowanie Huffmana (używane również przez algorytm deflate ) i kodowanie arytmetyczne . Kodowanie arytmetyczne osiąga współczynniki kompresji zbliżone do najlepszych możliwych dla konkretnego modelu statystycznego, co jest określone przez entropię informacyjną , podczas gdy kompresja Huffmana jest prostsza i szybsza, ale daje słabe wyniki dla modeli, które zajmują się prawdopodobieństwami symboli bliskimi 1.

Istnieją dwa podstawowe sposoby konstruowania modeli statystycznych: w modelu statycznym dane są analizowane i konstruowany jest model, który następnie jest przechowywany wraz ze skompresowanymi danymi. To podejście jest proste i modułowe, ale ma tę wadę, że sam model może być kosztowny w przechowywaniu, a także wymusza użycie jednego modelu dla wszystkich kompresowanych danych, przez co słabo działa na plikach zawierających heterogeniczne dane. Adaptacyjny modele dynamicznie aktualizują model w miarę kompresji danych. Zarówno koder, jak i dekoder zaczynają od trywialnego modelu, co skutkuje słabą kompresją danych początkowych, ale gdy dowiadują się więcej o danych, wydajność poprawia się. Większość popularnych rodzajów kompresji stosowanych w praktyce wykorzystuje obecnie kodery adaptacyjne.

Metody kompresji bezstratnej można podzielić na kategorie według typu danych, które mają kompresować. Chociaż w zasadzie każdy 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 bezstratnych technik kompresji stosowanych w przypadku tekstu sprawdza się 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 2-D o podobnych tonach. Każdy piksel oprócz pierwszego jest zastępowany różnicą w stosunku do 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 górnego piksela, a następnie w filmach można wziąć różnicę 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ą transformacją falkową . JPEG2000 dodatkowo wykorzystuje punkty danych z innych par i mnożników, aby zmieszać je z różnicą. Czynniki te muszą być liczbami całkowitymi, tak aby wynik był liczbą całkowitą we wszystkich 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. [ potrzebne źródło ]

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 są również przekazywane przez hierarchię.

Historyczne problemy prawne

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

Wiele bezstratnych technik kompresji stosowanych 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, które są przydatne w przypadku niektórych obrazów (szczególnie prostych map bitowych) oraz inne techniki wykorzystujące specyficzne właściwości obrazów (takie jak powszechne zjawisko ciągłych dwuwymiarowych obszarów o podobnych tonach oraz fakt, że kolorowe obrazy zwykle mają 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ść wyspecjalizowana dziedzina. Algorytmy bezstratnej kompresji dźwięku mogą wykorzystywać powtarzające się wzorce pokazywane przez falową naturę danych – zasadniczo wykorzystując autoregresyjne do przewidywania „następnej” wartości i kodowania (miejmy nadzieję, małej) różnicy między wartością oczekiwaną a rzeczywistymi danymi. Jeśli różnica między przewidywanymi a rzeczywistymi danymi (zwana błędem ) jest zwykle niewielka, wówczas pewne wartości różnic (takie jak 0, +1, −1 itd. w wartościach próbek) stają się bardzo częste, co można wykorzystać, kodując je 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 Δ , co 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 w wyżej wymienionym 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 .

Metody

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

szczegóły w sekcji Ograniczenia poniżej). Z tego powodu istnieje wiele różnych algorytmów zaprojektowanych z myślą o określonym typie danych wejściowych lub z określonymi założeniami dotyczącymi rodzajów redundancji, jakie mogą zawierać nieskompresowane dane.

Niektóre z najpopularniejszych algorytmów kompresji bezstratnej wymieniono poniżej.

Ogólny cel

Audio

Grafika rastrowa

Grafika 3D

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

Wideo

Zobacz listę bezstratnych kodeków wideo

Kryptografia

Systemy kryptograficzne często kompresują dane („tekst jawny”) przed zaszyfrowaniem w celu zwiększenia bezpieczeństwa. Prawidłowo zaimplementowana kompresja znacznie zwiększa dystans jednoznaczności , usuwając wzorce, które mogą ułatwić kryptoanalizę . Jednak wiele zwykłych algorytmów bezstratnej kompresji tworzy nagłówki, opakowania, tabele lub inne przewidywalne dane wyjściowe, które mogą zamiast tego ułatwić kryptoanalizę. Dlatego systemy kryptograficzne 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 algorytmów bezstratnych, 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 HapMap danych i osiąga ponad 20-krotną kompresję (zmniejszenie rozmiaru pliku o 95%), zapewniając 2- do 4-krotnie lepszą kompresję znacznie szybciej niż wiodące narzędzia do kompresji ogólnego przeznaczenia.

Algorytmy kompresji sekwencji genomowych, 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. Dla 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 pliku wykonywalnego

Samorozpakowujące się pliki wykonywalne zawierają skompresowaną aplikację i dekompresor. Po uruchomieniu dekompresor w przejrzysty sposób dekompresuje i uruchamia oryginalną aplikację. Jest to szczególnie często używane w demonstracyjnym , gdzie odbywają się konkursy na wersje demonstracyjne o ścisłych ograniczeniach rozmiaru, tak małych jak 1k . Ten typ kompresji nie jest ściśle ograniczony do binarnych plików wykonywalnych, ale może być również stosowany do skryptów, takich jak JavaScript .

Wzorce

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 w tych testach porównawczych mogą nie nadawać się do codziennego użytku ze względu na niską prędkość najlepszych wydajności. Inną wadą niektórych testów porównawczych jest to, że ich pliki danych są znane, więc niektórzy autorzy programów mogą optymalizować swoje programy w celu uzyskania najlepszej wydajności na określonym zbiorze danych. Zwycięzcy w tych testach porównawczych często pochodzą z klasy miksującego kontekst .

Matt Mahoney w swojej bezpłatnej broszurze Data Compression Explained z lutego 2010 r . dodatkowo wymienia:

  • Calgary Corpus pochodzący z 1987 roku nie jest już powszechnie używany ze względu na swoje niewielkie rozmiary. Matt Mahoney utrzymywał Calgary Compression Challenge, stworzone i utrzymywane od 21 maja 1996 do 21 maja 2016 przez Leonida A. Broukhisa.
  • Test porównawczy kompresji dużego tekstu i podobna nagroda Huttera wykorzystują przycięty zestaw danych XML UTF-8 Wikipedii .
  • Generic Compression Benchmark, prowadzony przez Matta Mahoneya, testuje kompresję danych generowanych przez losowe maszyny Turinga .
  • Sami Runsas (autor NanoZip) utrzymywał oceny kompresji, test porównawczy podobny do testu wielu plików maksymalnej kompresji, ale z minimalnymi wymaganiami dotyczącymi prędkości. Oferował kalkulator, który pozwalał użytkownikowi ocenić znaczenie szybkości i stopnia 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 .
  • Benchmark Monster of Compression autorstwa Nani Francesco Antonio przetestował kompresję na 1 Gb publicznych danych z 40-minutowym limitem czasowym. W grudniu 2009 roku najwyżej sklasyfikowanym archiwizatorem był NanoZip 0.07a, a najwyżej sklasyfikowanym kompresorem pojedynczego pliku był ccmx 1.30c.

Witryna Compression Ratings opublikowała podsumowanie wykresu „granicy” współczynnika kompresji i czasu.

Narzędzie do analizy kompresji to aplikacja systemu Windows, która umożliwia użytkownikom końcowym porównywanie charakterystyk wydajności implementacji przesyłania strumieniowego LZF4, Deflate, ZLIB, GZIP, BZIP2 i LZMA przy użyciu własnych danych. Tworzy pomiary i wykresy, za pomocą których użytkownicy mogą porównać szybkość kompresji, szybkość dekompresji i współczynnik kompresji różnych metod kompresji oraz zbadać, w jaki sposób poziom kompresji, rozmiar bufora i operacje opróżniania wpływają na wyniki.

Ograniczenia

Algorytmy bezstratnej kompresji danych (które nie dołączają etykiet identyfikatora kompresji do swoich wyjściowych zestawów danych) nie mogą zagwarantować kompresji dla wszystkich wejściowych zestawów danych. Innymi słowy, dla dowolnego algorytmu bezstratnej kompresji danych będzie istniał zbiór danych wejściowych, który nie zmniejsza się podczas przetwarzania przez algorytm, a dla dowolnego algorytmu bezstratnej kompresji danych, który zmniejsza co najmniej jeden plik, będzie co najmniej jeden plik, który powiększa. Można to łatwo udowodnić za pomocą elementarnej matematyki, używając argumentu liczenia zwanego zasadą przegródki , 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 można skompresować 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 daje to 2 N + 1 plików, które wszystkie kompresują się do jednego z 2 N plików o długości N .
  • Ale 2 N jest mniejsze niż 2 N +1, więc zgodnie z zasadą przegródki musi istnieć jakiś plik o długości N , który jest jednocześnie wyjściem funkcji kompresji na dwa różne wejścia. Tego pliku 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 stwierdzić, że nasza pierwotna hipoteza (że funkcja kompresji nie sprawia, że ​​plik jest dłuższy) jest z konieczności nieprawdziwa.

Większość praktycznych algorytmów kompresji zapewnia funkcję „ucieczki”, która może wyłączyć normalne kodowanie plików, które wydłużyłyby się w wyniku zakodowania. Teoretycznie tylko jeden dodatkowy bit jest wymagany, aby powiedzieć dekoderowi, że normalne kodowanie zostało wyłączone dla całego wejścia; jednak większość algorytmów kodowania wykorzystuje do tego celu co najmniej jeden pełny bajt (i zazwyczaj więcej niż jeden). Na przykład z opróżnianiem 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łyby jednakowo prawdopodobne, to dla każdej 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ększa niż N. Jeśli więc nie wiemy nic o właściwościach danych, które kompresujemy, równie dobrze możemy ich w ogóle nie kompresować. Algorytm bezstratnej kompresji jest przydatny tylko wtedy, gdy istnieje większe prawdopodobieństwo kompresji niektórych typów plików niż innych; wtedy algorytm można by zaprojektować tak, aby lepiej kompresował te typy danych.

Tak więc główna lekcja płynąca z tej argumentacji nie polega na tym, że ryzykuje się duże straty, ale jedynie na tym, że nie zawsze można wygrać. Wybranie algorytmu zawsze oznacza niejawne wybranie podzbioru wszystkich plików, które staną się użytecznie krótsze. To jest teoretyczny powód, dla którego musimy mieć różne algorytmy 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 do typu danych, dla których zostały zaprojektowane, na konsekwentne kompresowanie takich plików do krótszej postaci, polega na tym, że wszystkie pliki, na których algorytmy mają działać, mają jakąś formę łatwej do modelowania redundancji , która algorytm jest przeznaczony do usuwania, a zatem należy do podzbioru plików, które ten algorytm może skrócić, podczas gdy inne pliki nie zostałyby skompresowane ani nawet powiększone. Algorytmy są na ogół dość specjalnie dostrojone do określonego typu pliku: na przykład programy do bezstratnej kompresji dźwięku nie działają dobrze na plikach tekstowych i odwrotnie.

W szczególności plików losowych danych nie można spójnie skompresować żadnym możliwym algorytmem bezstratnej kompresji danych; w istocie wynik ten jest używany do zdefiniowania pojęcia losowości w złożoności Kołmogorowa .

Stworzenie algorytmu, który byłby w stanie bezstratnie skompresować dowolne dane, jest niemożliwe do udowodnienia. Chociaż przez lata pojawiło się wiele twierdzeń, że firmy osiągnęły „doskonałą kompresję”, w której dowolną liczbę N losowych bitów można zawsze skompresować 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ł, można by go wielokrotnie stosować, aby bezstratnie zredukować dowolny plik do długości 1.

Z drugiej strony udowodniono również, że nie ma algorytmu określającego, czy plik jest nieskompresowalny w sensie złożoności Kołmogorowa . W związku z tym możliwe jest, że dowolny konkretny plik, nawet jeśli wydaje się przypadkowy, może być znacznie skompresowany, nawet włączając rozmiar dekompresora. Przykładem są cyfry stałej matematycznej pi , które wydają się losowe, ale mogą być generowane przez bardzo mały program. Jednak nawet jeśli nie można określić, czy dany plik jest nieściśliwy, proste twierdzenie o nieściśliwych ciągach pokazuje, że ponad 99% plików o dowolnej długości nie może zostać skompresowanych o więcej niż jeden bajt (wliczając rozmiar dekompresora).

Tło matematyczne

Abstrakcyjnie, algorytm kompresji można postrzegać jako funkcję na sekwencjach (zwykle oktetów). Kompresja jest skuteczna, 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ę z „zwykłej” do „skompresowanej” sekwencji bitów. Zasada przegródki zabrania bijekcji między zbiorem ciągów o długości N a jakimkolwiek podzbiorem zbioru ciągów o długości N -1. Dlatego nie jest możliwe stworzenie bezstratnego algorytmu, który zmniejsza rozmiar każdej możliwej sekwencji wejściowej.

Punkty zastosowania w rzeczywistej teorii kompresji

Projektanci algorytmów rzeczywistej kompresji akceptują fakt, że strumieni o wysokiej entropii informacji nie można skompresować, i odpowiednio uwzględniają narzędzia 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 uważać pliki, których nazwy kończą się na „.zip”, „.arj” lub „.lha”, za nieskompresowalne bez bardziej wyrafinowanego wykrywania. Powszechnym sposobem radzenia sobie z tą sytuacją jest cytowanie danych wejściowych lub nieskompresowalnych części danych wejściowych w danych wyjściowych, co minimalizuje narzut związany z kompresją. Na przykład 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 wystosował publiczne wyzwanie w wysokości 100 USD dla każdego, kto napisze program, który wraz z jego danymi wejściowymi , byłby mniejszy niż dostarczone przez niego dane binarne, ale byłby w stanie odtworzyć je bez błędów. Podobne wyzwanie, z nagrodą w wysokości 5000 $, rzucił Mike Goldman.

Zobacz też

Dalsza lektura

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Lossless_compression&oldid=1138395526 ”