Algorytmy kompresji: opis, podstawowe techniki, charakterystyka

Kompresja jest szczególnym przypadkiem kodowania, którego główną cechą jest to, że wynikowy kod jest mniejszy od oryginału. Proces polega na znalezieniu powtórzeń w sekwencjach informacji, a następnie zapisaniu tylko jednej obok liczby powtórzeń. Tak więc, na przykład, jeśli sekwencja pojawia się w pliku jako "AAAAA" zajmująca 6 bajtów, zostanie zapisana jako "6A", która zajmuje tylko 2 bajty, w algorytmie kompresji RLE.

Historia powstania procesu

Kod Morse`a wynaleziony w 1838 roku był pierwszym znanym przypadkiem kompresji danych. Później, gdy w 1949 roku komputery mainframe zaczęły zdobywać popularność, Claude Shannon i Robert Fano wynaleźli kodowanie, nazwane przez autorów Shannon-Fano. Szyfrowanie to przypisuje kody do znaków w zbiorze danych zgodnie z teorią prawdopodobieństwa.

Dopiero w latach siedemdziesiątych, wraz z pojawieniem się Internetu i pamięci masowej online, wprowadzono pełnoprawne algorytmy kompresji. Kody Huffmana były dynamicznie generowane z danych wejściowych. Kluczowa różnica między kodowaniem Shannona-Fano a kodowaniem Huffmana polega na tym, że w tym pierwszym drzewo prawdopodobieństwa było budowane od dołu do góry, tworząc nieoptymalny wynik, natomiast w tym drugim drzewo prawdopodobieństwa było budowane od góry do dołu.

W 1977 roku Abraham Lempel i Jacob Ziv opublikowali swoją nowatorską metodę LZ77, która wykorzystuje bardziej zmodernizowany słownik. W 1978 roku ten sam zespół autorów opublikował ulepszony algorytm kompresji LZ78. Który wykorzystuje nowy słownik, który analizuje dane wejściowe i generuje słownik statyczny, a nie dynamiczny z wersji 77.

Formy wykonania kompresji

Kompresja jest wykonywana przez program, który wykorzystuje wzór lub algorytm określający, jak zmniejszyć wielkość danych. Na przykład, reprezentowanie ciągu bitów za pomocą mniejszego ciągu 0 i 1 przy użyciu słownika lub formuły konwersji.

Kompresja może być tak prosta jak. Czyli na przykład, jako usunięcie wszystkich niechcianych znaków, wstawiając pojedynczy kod powtarzający, aby wskazać linię powtórzenia i zastępując ciąg bitów mniejszym. Algorytm kompresji plików może zmniejszyć plik tekstowy nawet o 50% lub znacznie więcej.

W przypadku transmisji, proces realizowany jest w bloku transmisyjnym, zawierającym dane nagłówkowe. Gdy informacje są wysyłane lub odbierane przez Internet, archiwizowane indywidualnie lub razem z innymi dużymi plikami, mogą być przesyłane w formacie ZIP, GZIP lub innym "Zmniejszona" format.

Zalety algorytmów kompresji:

1. Znacząco zmniejsza przestrzeń magazynową. Przy współczynniku kompresji 2:1, plik o rozmiarze 20 megabajtów (MB) zajmie 10 MB miejsca. W rezultacie administratorzy sieci wydają mniej pieniędzy i czasu na przechowywanie baz danych.
2. Optymalizacja wydajności tworzenia kopii zapasowych.
3. Ważna metoda redukcji danych.
4. Prawie każdy plik może być skompresowany, ale ważne jest, aby wybrać odpowiednią technologię dla danego typu pliku. W przeciwnym razie pliki mogą być "zmniejszona", ale całkowity rozmiar nie ulegnie zmianie.

Stosowane są dwa rodzaje metod kompresji - algorytmy kompresji bezstratnej i stratnej. Pierwszy przywraca plik do jego pierwotnego stanu bez utraty ani jednego bitu informacji w nieskompresowanym pliku. Drugi - jest typowym podejście do plików wykonywalnych, tekstu i arkuszy kalkulacyjnych, w których utrata słów lub liczb spowodowałaby zmianę informacji.

Kompresja stratna trwale usuwa bity danych, które są zbędne, nieistotne lub niezauważalne. Jest to przydatne w przypadku grafiki, audio, wideo i obrazów, gdzie usunięcie niektórych bitów ma niewielki lub żaden zauważalny wpływ na prezentację treści.

Algorytm kompresji Huffmana

Ten proces, który może być wykorzystany do "do zmniejszenia " lub szyfrowanie.

Polega ona na przypisaniu każdemu powtarzającemu się znakowi kodów o różnej długości bitów, im więcej takich powtórzeń, tym większy stopień kompresji. Aby zrekonstruować oryginalny plik, trzeba znać przydzielony kod i jego długość bitową. Podobnie, użyj programu do szyfrowania plików.

Algorytmy kompresji danych

1. Oblicz ile razy każdy znak powtarza się w pliku dla "zmniejszyć".
2. Utwórz listę połączoną z informacjami o znakach i częstotliwości.
3. Wykonaj sortowanie listy od najmniejszego do największego w zależności od częstotliwości.
4. Przekształć każdy element listy na drzewo.
5. Połącz drzewa w jedno, przy czym dwa pierwsze tworzą nowe.
6. Dodaj częstotliwości każdej gałęzi do nowego elementu drzewa.
7. W odpowiednim miejscu na liście wstawia się nowy, zgodnie z sumą uzyskanych częstotliwości.
8. Przypisać nowy kod binarny do każdego znaku. W przypadku wykonania gałęzi zerowej do kodu dodawane jest zero, a w przypadku pierwszej gałęzi - jeden.
9. Plik jest ponownie zakodowany zgodnie z nowymi kodami.
10. Na przykład charakterystyka algorytmów kompresji dla krótkiego tekstu:"ata la jaca a la estaca"
11. Policz, ile razy pojawia się każdy znak i utwórz listę powiązaną:` (5), a (9), c (2), e (1), j (1), l (2), s (1), t (2)
12. Kolejność według częstotliwości od najniższej do najwyższej: e (1), j (1), s (1), c (2), l (2), t (2), `` (5), a (9)

Jak widać, tworzony jest węzeł główny drzewa, następnie przypisywane są kody.

I pozostaje tylko upakować bity w grupy po osiem, czyli w bajty:

Tylko osiem bajtów, a oryginalny tekst miał 23.

Demonstracja biblioteki LZ77

Rozważmy algorytm LZ77 na przykład tekstu"howtogeek". Jeśli powtórzysz to trzy razy, zmienia się to w następujący sposób.

Następnie, gdy będzie chciał odczytać tekst z powrotem, zastąpi każdą instancję (h) przez "howtogeek", wracając do oryginalnego zdania. Pokazuje to algorytm bezstratnej kompresji danych, ponieważ wprowadzone dane są takie same jak otrzymane.

Jest to idealny przykład, gdzie większość tekstu jest skompresowana z kilkoma znakami. Na przykład słowo "ten" zostanie skompresowane, nawet jeśli pojawi się w słowach takich jak "ten", "ich" i "ten". Dzięki powtarzającym się słowom, można uzyskać ogromne współczynniki kompresji. Na przykład tekst ze słowem "howtogeek" powtórzonym 100 razy ma rozmiar trzech kilobajtów, a po skompresowaniu zajmie tylko 158 bajtów, czyli z 95% "zmniejszenie".

Jest to oczywiście dość skrajny przykład, ale wyraźnie pokazuje właściwości algorytmów kompresji. W ogólnej praktyce jest to 30-40% przy formacie tekstowym ZIP. Algorytm LZ77, dotyczy wszystkich danych binarnych, nie tylko tekstu, choć ten ostatni jest łatwiejszy do skompresowania ze względu na powtarzalność słów.

Dyskretna transformacja kosinusowa obrazów

Kompresja wideo i audio działa zupełnie inaczej. W przeciwieństwie do tekstu, gdzie stosowane są algorytmy kompresji bezstratnej i żadne dane nie są tracone, w przypadku obrazów "kurczący się" Im wyższy %, tym większe straty. Prowadzi to do tych okropnie wyglądających plików JPEG, które ludzie w kółko ściągają, wymieniają i robią zrzuty ekranu.

Większość obrazów, zdjęć i innych rzeczy przechowuje listę liczb, z których każda reprezentuje pojedynczy piksel. JPEG zapisuje je za pomocą algorytmu kompresji obrazu zwanego dyskretną transformatą kosinusową. Reprezentuje on zbiór fal sinusoidalnych dodanych do siebie z różnymi natężeniami.

Ta metoda wykorzystuje 64 różne równania, a następnie kodowanie Huffmana, aby jeszcze bardziej zmniejszyć rozmiar pliku. Algorytm kompresji obrazu, taki jak ten, daje szalenie wysoki stopień kompresji i zmniejsza go z kilku megabajtów do kilku kilobajtów, w zależności od wymaganej jakości. Większość zdjęć jest skompresowana, aby zaoszczędzić czas pobierania, zwłaszcza dla użytkowników telefonów komórkowych o słabej transmisji.

Wideo działa nieco inaczej niż obrazy. Zazwyczaj algorytmy kompresji grafiki wykorzystują tak zwaną "kompresję międzyramkową", która oblicza zmiany pomiędzy każdą klatką i zapisuje je. Na przykład, jeśli w ogóle względnie nieruchomy obraz, który zajmuje kilka sekund w filmie, to byłoby "zmniejszona" w jeden. Kompresja międzyramkowa zapewnia cyfrową telewizję i wideo internetowe. Bez tego wideo ważyłoby setki gigabajtów, czyli więcej niż przeciętny dysk twardy w 2005 roku.

kompresja dźwięku działa bardzo podobnie do kompresji tekstu i obrazu. Podczas gdy JPEG usuwa z obrazu szczegóły, które nie są widoczne dla ludzkiego oka, kompresja audio robi to samo dla dźwięków. MP3 wykorzystuje bitrate, który waha się od 48 i 96 kbps (niższy poziom) przez 128 i 240 kbps (całkiem dobry) do 320 kbps (dźwięk wysokiej jakości), a różnicę można usłyszeć tylko w wyjątkowo dobrych słuchawkach. Istnieją bezstratne kodeki dla dźwięku, FLAC jest głównym i używa kodowania LZ77 dla bezstratnego dźwięku.

Formaty "redukcje" tekst

Zakres bibliotek dla tekstu obejmuje głównie algorytm bezstratnej kompresji danych, poza skrajnymi przypadkami dla danych zmiennoprzecinkowych. Większość kodeków kompresji zawiera "redukcja" LZ77, Huffman i kodowanie arytmetyczne. Są one stosowane po innych narzędziach, aby wycisnąć jeszcze kilka punktów procentowych kompresji.

Przebiegi wartości są kodowane jako znak, po którym następuje przebieg długości. Możesz prawidłowo przywrócony oryginalny stream. Jeśli długość serii<= 2 znaki, ma sens po prostu pozostawienie ich bez zmian, takich jak na końcu strumienia z "bb".

W niektórych rzadkich przypadkach dodatkowe oszczędności uzyskuje się poprzez zastosowanie konwersji z użyciem algorytmów kompresji stratnej do fragmentów treści przed zastosowaniem metody bezstratnej. Ponieważ w tych konwersjach pliki nie mogą być przywrócone do stanu pierwotnego, te "procesy" zarezerwowane dla dokumentów tekstowych. Które nie ucierpią z powodu utraty informacji, np. obcięcie liczb zmiennoprzecinkowych do tylko dwóch znaczących miejsc po przecinku.

Obecnie większość systemów kompresji tekstu działa poprzez łączenie różnych transformacji danych w celu osiągnięcia maksymalnego wyniku. Sensem każdego kroku w systemie jest wykonanie konwersji, aby następny krok mógł kontynuować efektywną kompresję. Suma tych kroków daje mały plik, który może być odzyskany bezstratnie. Istnieją dosłownie setki formatów i systemów kompresji, z których każdy ma zalety i wady dla różnych typów danych.

Schematy HTTP: DEFLATE i GZIP

Obecnie w Internecie powszechnie stosowane są dwa algorytmy kompresji tekstu HTTP: DEFLATE i GZIP.

DEFLATE - normalnie łączy dane, używając LZ77, kodowania Huffmana. GZIP - plik używa wewnętrznie DEFLATE wraz z kilkoma ciekawymi blokadami, heurystyką filtrowania, nagłówkami i sumą kontrolną. Ogólnie rzecz biorąc, dodatkowa blokada i heurystyka przy użyciu GZIP daje lepsze współczynniki kompresji niż sam DEFLATE.

Protokoły danych nowej generacji - SPDY i HTTP2.0, obsługują kompresję nagłówka GZIP, więc większość serwerów internetowych nadal będzie z niej korzystać w przyszłości.

Większość programistów po prostu przesyła nieskompresowane treści i polega na serwerze internetowym, aby "zmniejszenie" dane na bieżąco. Daje to doskonałe rezultaty i łatwy w użyciu algorytm kompresji obrazu. Domyślnym ustawieniem na wielu serwerach jest GZIP na warstwie 6, a najwyższy poziom to 9. Jest to celowo zaprojektowane, aby umożliwić serwerom szybszą kompresję danych kosztem większego pliku wyjściowego.

Formaty BZIP2 i LZMA, które tworzą bardziej zwarte formy niż GZIP, ale dekompresują się szybciej.

LZMA można uznać za dalekiego krewnego GZIP. Obie zaczynają się od popularny słownik LZ, a następnie system kodowania statystycznego. Jednak lepsza zdolność LZMA do kompresji małych plików leży w jego "zaawansowanych algorytmach dopasowania i oknach LZ".

Wstępne przetwarzanie dokumentów

W przypadku kompresji jakościowej wykonywany jest dwuetapowy proces:

• Zminimalizuj krok;
• krok bezstratny.

Minifikacja to zmniejszenie rozmiaru danych tak, aby można je było wykorzystać bez przetwarzania, wymazanie wielu niepotrzebnych rzeczy z pliku bez zmiany jego składni. Tak więc bezpiecznie jest usunąć większość spacji z Jscript, zmniejszając rozmiar bez zmiany składni. Minifikacja jest wykonywana podczas procesu budowania. Albo jako etap ręczny, albo jako część zautomatyzowanego łańcucha montażowego.

Istnieje wiele programów realizujących podstawowe algorytmy kompresji, wśród nich:

1. Winzip to bezstratny format zapisu szeroko stosowany dla dokumentów, obrazów lub aplikacji. Jest to dość prosty program, który kompresuje każdy z plików z osobna, pozwalając na odtworzenie każdego z nich bez konieczności czytania reszty. Tym samym zwiększając wydajność procesu.
2. 7zip - darmowy menedżer bardzo wydajnego i prostego algorytmu kompresji danych. Dzięki formatowi plików 7z, który poprawia standard ZIP o 50%. Wspiera innych najczęściej spotykany formaty takie jak RAR, ZIP, CAB, GZIP i ARJ, więc nie ma problemów z używaniem z dowolnym skompresowanym plikiem i integruje się z menu kontekstowym w systemie Windows.
3. GZIP jest jednym z najbardziej znanych kompresorów przeznaczonych dla Linuksa. Biorąc pod uwagę jego sukces na tej platformie, został on sfinalizowany dla Windowsa. Jedną z głównych zalet gzip jest to, że używa on algorytmu DEFLATE (połączenie LZ77 i kodowania Huffmana).
4. WinRAR - program kompresujący i wielofunkcyjny dekompresor danych. Jest to niezastąpione narzędzie do oszczędzania miejsca na dysku i czasu transferu podczas wysyłania i odbierania plików przez Internet lub do tworzenia kopii zapasowych. Służy do kompresji wszelkiego rodzaju dokumentów lub programów, dzięki czemu zajmują one mniej miejsca na dysku i mogą być szybciej przechowywane lub przesyłane przez sieć. Jest to pierwszy kompresor, który implementuje 64-bitowe zarządzanie plikami, co pozwala mu na obsługę dużych wolumenów, ograniczonych jedynie przez system operacyjny.

Minifikatory CSS

Istnieje wiele minifikatorów CSS. Niektóre z dostępnych opcji to:

• online CSS Minifier;
• freeformatter.com/css-minifier;
• cleancss.com/css-minify;
• cnvyr.io;
• minifikator.org;
• css-minifier.com.

Główna różnica między tymi narzędziami polega na tym, jak głębokie są ich procesy minifikacji. W ten sposób uproszczone filtry optymalizacji tekstu usuwają zbędne spacje i tablice. Zaawansowana optymalizacja obejmuje zastąpienie "AntiqueWhite" przez " # FAEBD7 ", ponieważ forma szesnastkowa w pliku jest krótsza, oraz wymuszenie użycia dolnego znaku rejestru GZIP.

Bardziej agresywne metody CSS oszczędzają miejsce, ale mogą wymagania dotyczące przerw CSS. Większość z nich nie ma więc możliwości zautomatyzowania, a twórcy dokonują wyboru między wielkością a stopniem ryzyka.

W rzeczywistości istnieje nowy trend do tworzenia innych wersji z języków CSS, aby pomóc autorowi kodu bardziej efektywnie jako dodatkowa korzyść, pozwalając kompilatorowi produkować mniej kodu CSS.

Zalety i wady kompresji

Główne korzyści z kompresji to zmniejszenie ilości sprzętu do przechowywania danych, czasu transferu i szerokości pasma.

Wymaga mniej pamięci, a metoda ta prowadzi do obniżenia kosztów pamięci dyskowej lub półprzewodnikowej. Wymaga mniejszego czasu transmisji dla niskiej szerokości pasma.

Główną wadą kompresji jest wpływ na wydajność wynikający z wykorzystania zasobów procesora i pamięci na proces, a następnie dekompresję.

Wielu producentów zaprojektowało systemy, które starają się zminimalizować wpływ intensywnej kompresji na koszty obliczeniowe. Jeśli jest wykonywany przed zapisem danych na dysk, system może odciążyć ten proces, aby zaoszczędzić zasoby systemowe. Na przykład IBM używa osobnej karty akceleracji sprzętowej do obsługi kompresji w niektórych systemach pamięci masowej klasy korporacyjnej.

Jeśli dane są kompresowane po zapisaniu na dysku lub po przetworzeniu, kompresja będzie działać w tle, aby zmniejszyć wpływ na wydajność maszyny. Chociaż kompresja po przetworzeniu skraca czas odpowiedzi dla każdego wejścia i wyjścia (I/O), nadal zużywa pamięć i cykle procesora oraz wpływa na liczbę operacji przetwarzanych przez system pamięci masowej. Ponadto, ponieważ dane muszą być początkowo zapisane na dysku lub w pamięci flash bez kompresji, oszczędność pamięci fizycznej nie jest tak duża, jak w przypadku danych osadzonych "redukcja".

Przyszłość nigdy nie jest pewna, ale na podstawie obecnych trendów można dokonać pewnych przewidywań dotyczących tego, co stanie się z technologią kompresji danych. Algorytmy mieszania kontekstów, takie jak PAQ i jego warianty, zaczęły zdobywać popularność i mają tendencję do osiągania najwyższych współczynników "zmniejszenie". Choć zwykle powolny.

Wraz z wykładniczym wzrostem prędkości sprzętu zgodnie z prawem Moore`a, procesy mieszania kontekstów prawdopodobnie będą się rozwijać. Ponieważ koszty prędkości są pokonywane przez szybki sprzęt dzięki wysokim współczynnikom kompresji. Algorytm, który PAQ starał się udoskonalić, nazywa się "Częściowe dopasowanie Przewidywanie ścieżki". Lub PPM.

Wreszcie, algorytm łańcucha Lempel-Ziv-Markov (LZMA) konsekwentnie wykazywał doskonały kompromis między szybkością a wysokim stopniem kompresji i prawdopodobnie w przyszłości stworzy więcej wariantów. Będzie on wiodący, ponieważ jest już akceptowany w wielu konkurencyjnych formatach kompresji, np. 7-Zip.

Innym potencjalnym kierunkiem rozwoju jest wykorzystanie kompresji wyliczania podciągów (CSE), która jest obiecującą technologią i nie ma jeszcze wielu implementacji programowych.