• dom
  •  > 
  • Android
  •  > 
  • Przegląd metod kompresji danych. Kompresja danych

Przegląd metod kompresji danych. Kompresja danych

"Kompresja danych"

Cechą charakterystyczną większości typów danych jest ich redundancja. Stopień redundancji danych zależy od rodzaju danych. Przykładowo dla danych wideo stopień redundancji jest kilkukrotnie większy niż dla danych graficznych, z kolei stopień redundancji danych graficznych jest większy niż stopień redundancji danych tekstowych. Kolejnym czynnikiem wpływającym na stopień redundancji jest przyjęty system kodowania. Przykładem systemów kodujących mogą być zwykłe języki komunikacji, które są niczym innym jak systemami kodowania pojęć i pomysłów na wyrażanie myśli. Ustalono zatem, że kodowanie danych tekstowych w języku rosyjskim daje średnio o 20-25% większą redundancję niż kodowanie podobnych danych w języku angielskim.

W przypadku ludzi nadmiarowość danych jest często kojarzona z jakością informacji, ponieważ nadmiarowość zwykle poprawia zrozumiałość i postrzeganie informacji. Jednak w przypadku przechowywania i przesyłania informacji za pomocą technologii komputerowej redundancja odgrywa negatywną rolę, ponieważ prowadzi do wzrostu kosztów przechowywania i przesyłania informacji. Problem ten staje się szczególnie istotny w przypadku przetwarzania ogromnych wolumenów informacji przy niewielkiej ilości nośników danych. W związku z tym stale pojawia się problem ograniczenia redundancji lub kompresji danych. Jeśli do gotowych plików stosuje się metody kompresji danych, często zamiast terminu „kompresja danych” używa się terminu „archiwizacja danych”; skompresowana wersja danych nazywa się archiwum, A oprogramowanie, które implementują metody kompresji, nazywane są archiwiści.

W zależności od obiektu, w którym znajdują się dane do kompresji:

    Kompresja (archiwizacja) plików: stosowana w celu zmniejszenia rozmiaru plików podczas przygotowania ich do transmisji kanałami komunikacyjnymi lub do transportu na nośnikach zewnętrznych o małej pojemności;

    Kompresja folderów (archiwizacja): stosowana w celu zmniejszenia objętości folderów przed długotrwałym przechowywaniem, np. w celach archiwalnych. kopia zapasowa;

    Kompresja dysku (zagęszczanie): stosowana w celu zwiększenia efektywności wykorzystania przestrzeni dyskowej poprzez kompresję danych podczas ich zapisywania na nośniku pamięci (zwykle przy użyciu systemu operacyjnego).

Istnieje wiele praktycznych algorytmów kompresji danych, ale wszystkie opierają się na trzech teoretycznych sposobach ograniczenia nadmiarowości danych. Pierwszy sposób to zmiana zawartości danych, drugi to zmiana struktury danych, a trzeci to jednoczesna zmiana zarówno struktury, jak i zawartości danych.

Jeżeli kompresja danych zmienia ich zawartość, wywoływana jest metoda kompresji nieodwracalny, co oznacza, że ​​podczas przywracania (przywracania) danych z archiwum informacje nie są przywracane całkowicie. Metody takie są często nazywane metodami kompresji z kontrolowaną stratą. Oczywiste jest, że metody te można stosować tylko w przypadku typów danych, w przypadku których utrata części treści nie prowadzi do istotnego zniekształcenia informacji. Do tego typu danych zaliczają się dane wideo, audio i graficzne. Metody kompresji z kontrolowaną stratą zapewniają znacznie wyższe współczynniki kompresji, ale nie można ich zastosować do danych tekstowych. Przykłady formatów kompresji stratnej obejmują:

    JPEG – dla danych graficznych;

    MPG - dla danych wideo;

    MP3 – dla danych audio.

Jeżeli kompresja danych zmienia jedynie strukturę danych, wówczas wywoływana jest metoda kompresji odwracalny. W takim przypadku możliwe jest całkowite przywrócenie informacji z archiwum. Metody kompresji odwracalnej można zastosować do dowolnego typu danych, ale zapewniają one mniejszą kompresję niż metody kompresji nieodwracalnej. Przykłady formatów kompresji bezstratnej:

    GIF, TIFF – dla danych graficznych;

    AVI – dla danych wideo;

    ZIP, ARJ, RAR, CAB, LH - dla dowolne typy dane.

Istnieje wiele różnych praktycznych metod kompresji bezstratnej, które mają różną skuteczność różne rodzaje danych i różnych woluminów. Metody te opierają się jednak na trzech algorytmach teoretycznych:

    algorytm RLE (kodowanie długości przebiegu);

    algorytmy z grupy KWE (KeyWord Encoding);

    Algorytm Huffmana.

Algorytm RLE

Algorytm RLE opiera się na idei identyfikacji powtarzających się sekwencji danych i zastąpienia ich prostszą strukturą, która określa kod danych i współczynnik powtarzalności. Przykładowo, podajmy następującą sekwencję danych podlegających kompresji:

1 1 1 1 2 2 3 4 4 4

Algorytm RLE proponuje jego zastąpienie następująca struktura: 1 4 2 2 3 1 4 3, gdzie pierwsza liczba w każdej parze liczb to kod danych, a druga to współczynnik powtarzalności. Jeżeli do przechowywania każdego elementu danych sekwencji wejściowej zostanie przydzielony 1 bajt, wówczas cała sekwencja zajmie 10 bajtów pamięci, natomiast sekwencja wyjściowa (wersja skompresowana) zajmie 8 bajtów pamięci. Współczynnik kompresji, który charakteryzuje stopień kompresji, można obliczyć za pomocą wzoru:

gdzie Vx to ilość pamięci wymagana do przechowywania wyjściowej (wynikowej) sekwencji danych, Vn to wejściowa sekwencja danych.

Im niższy stopień kompresji, tym skuteczniejsza metoda kompresji. Oczywiste jest, że algorytm RLE zapewni lepszy efekt kompresji, gdy powtarzająca się sekwencja danych będzie dłuższa. W przypadku omówionego powyżej przykładu, jeśli sekwencja wejściowa będzie wyglądać następująco: 1 1 1 1 1 1 3 4 4 4, to stopień kompresji wyniesie 60%. Pod tym względem większą wydajność algorytmu RLE osiąga się przy kompresji danych graficznych (szczególnie w przypadku obrazów monochromatycznych).

Algorytmy grupy KWE

Algorytm kompresji słów kluczowych opiera się na zasadzie kodowania jednostek leksykalnych w grupach bajtów o stałej długości. Przykładem elementu leksykalnego może być zwykłe słowo. W praktyce powtarzające się ciągi symboli dobiera się do roli jednostek leksykalnych i koduje się je za pomocą łańcucha symboli (kodu) o krótszej długości. Wynik kodowania umieszczany jest w tabeli, tworząc tzw. słownik.

Istnieje sporo implementacji tego algorytmu, wśród których najczęstsze to algorytm Lempla-Ziva (algorytm LZ) i jego modyfikacja, algorytm Lempla-Ziv-Welcha (algorytm LZW). Słownik w ten algorytm to potencjalnie nieskończona lista wyrażeń. Algorytm rozpoczyna się od prawie pustego słownika zawierającego tylko jeden zakodowany ciąg znaków, tzw. ciąg NULL. Podczas odczytywania kolejnego znaku sekwencji danych wejściowych jest on dodawany do bieżącego wiersza. Proces trwa do bieżąca linia pasuje do jakiegoś wyrażenia ze słownika. Ale prędzej czy później bieżąca linia przestaje odpowiadać jakiejś frazie słownikowej. W punkcie, w którym bieżąca linia reprezentuje ostatnie dopasowanie słownikowe plus właśnie przeczytany znak komunikatu, koder generuje kod składający się z indeksu dopasowania i następnego znaku, który przerwał dopasowanie linii. Do słownika dodawana jest nowa fraza, składająca się z indeksu dopasowania i następującego po nim znaku. Następnym razem, gdy to zdanie pojawi się w wiadomości, można z niego zbudować dłuższą frazę, co zwiększa stopień kompresji informacji.

Algorytm LZW zbudowany jest wokół tabeli fraz (słownika), która zamienia ciągi znaków skompresowanej wiadomości na kody o stałej długości. Tabela posiada tzw. właściwość zaliczki, czyli dla każdej frazy w słowniku składającej się z określonej frazy w i symbolu K, do słownika wpisana jest także fraza w. Jeżeli wszystkie części słownika zostaną całkowicie wypełnione, kodowanie przestaje być adaptacyjne (kodowanie odbywa się w oparciu o frazy już istniejące w słowniku).

Algorytmy kompresji tej grupy są najskuteczniejsze w przypadku dużych danych tekstowych, natomiast są nieskuteczne w przypadku małych plików (ze względu na konieczność zapisywania słownika).

Algorytm Huffmana

Algorytm Huffmana opiera się na idei kodowania grup bitowych. W pierwszej kolejności przeprowadzana jest analiza częstotliwościowa sekwencji danych wejściowych, czyli ustalana jest częstotliwość występowania każdego znalezionego w niej znaku. Następnie symbole są sortowane według malejącej częstotliwości występowania.

Podstawowa idea jest następująca: im częściej znak występuje, tym mniej bitów jest kodowany. Wynik kodowania jest wprowadzany do słownika wymaganego do dekodowania. Spójrzmy na prosty przykład ilustrujący działanie algorytmu Huffmana.

Niech będzie podany tekst, w którym litera „A” pojawia się 10 razy, litera „B” – 8 razy, „C” – 6 razy, „D” – 5 razy, „E” i „F” – po 4 razy . Następnie w tabeli 1 przedstawiono jedną z możliwych opcji kodowania z wykorzystaniem algorytmu Huffmana.

Tabela 1.

Częstotliwość występowania

Kod bitowy

Jak widać z tabeli 1, rozmiar tekstu wejściowego przed kompresją wynosi 37 bajtów, natomiast po kompresji 93 bity, czyli około 12 bajtów (bez długości słownika). Stopień kompresji wynosi 32%. Algorytm Huffmana jest uniwersalny, można nim kompresować dane dowolnego typu, jednak w przypadku małych plików jest nieskuteczny (ze względu na konieczność zapisywania słownika).

W praktyce oprogramowanie do kompresji danych syntetyzuje te trzy „czyste” algorytmy, ponieważ ich skuteczność zależy od rodzaju i objętości danych. Tabela 2 przedstawia popularne formaty kompresji i odpowiadające im programy archiwizujące stosowane w praktyce.

Tabela 2.

Format kompresji

System operacyjny MSDOS

System operacyjny Windows

Program do archiwizacji

Program do rozpakowywania

Program do archiwizacji

Program do rozpakowywania

Ponadto nowoczesne archiwizatory zapewniają użytkownikowi pełen zakres usług do pracy z archiwami, z których główne to:

    utworzenie nowego archiwum;

    dodawanie plików do istniejącego archiwum;

    rozpakowywanie plików z archiwum;

    tworzenie archiwów samorozpakowujących;

    tworzenie rozproszonych archiwów o stałym rozmiarze dla małych nośników danych;

    zabezpieczanie archiwów hasłami przed nieuprawnionym dostępem;

    przeglądanie zawartości plików w różnych formatach bez uprzedniego rozpakowywania;

    szukać plików i danych wewnątrz archiwum;

    sprawdzanie obecności wirusów w archiwum przed rozpakowaniem;

    wybór i regulacja stopnia sprężania.

Pytania kontrolne

1. Jakie czynniki wpływają na stopień redundancji danych? 2. Co to jest archiwum? Jakie narzędzia programowe nazywane są archiwizatorami? 3. Dlaczego metody kompresji zmieniające zawartość danych nazywane są nieodwracalnymi? 4. Podaj przykłady formatów kompresji stratnej. 5. Jaka jest przewaga odwracalnych metod kompresji nad nieodwracalnymi? A co z wadą? 6. Jaka jest zależność pomiędzy stopniem sprężania a efektywnością metody sprężania? 7. Jaka jest główna idea algorytmu RLE? 8. Jaka jest główna idea algorytmów grupy KWE? 9. Jaka jest główna idea algorytmu Huffmana? 10. Jakie znasz archiwizatory oprogramowania? Krótko je opisz.

    Informatyka. Kurs podstawowy. / wyd. S.V.Simonowicz. - Petersburg, 2000

    A.P. Miklyaev, Podręcznik użytkownika IBM PC, wydanie 3 M.:, „Solon-R”, 2000, 720 s.

    Simonovich S.V., Evseev G.A., Murakhovsky V.I. Kupiłeś komputer: kompletny przewodnik dla początkujących zawierający pytania i odpowiedzi . - M.: KSIĄŻKA AST-PRESS; Inforcom-Press, 2001.- 544 s.: il. (1000 napiwków).

    Kovtanyuk Yu.S., Solovyan S.V. Instrukcja samokształcenia do pracy komputer osobisty- K.:Junior, 2001.- 560 s., il.

Razem z promotorem przygotowujemy małą monografię na temat przetwarzania obrazu. Postanowiłem przedstawić społeczności Habra rozdział poświęcony algorytmom kompresji obrazu. Ponieważ ciężko zmieścić cały rozdział w jednym poście, zdecydowałam się podzielić go na trzy posty:
1. Metody kompresji danych;
2. Bezstratna kompresja obrazu;
3. Stratna kompresja obrazu.
Poniżej możesz przeczytać pierwszy wpis z tej serii.

Obecnie istnieje duża liczba algorytmów kompresji bezstratnej, które można podzielić na dwie duże grupy:
1. Algorytmy strumieniowe i słownikowe. Do tej grupy zaliczają się algorytmy z rodziny RLE (run-length encoding), LZ* itp. Cechą wszystkich algorytmów z tej grupy jest to, że podczas kodowania nie jest wykorzystywana informacja o częstotliwości występowania symboli w komunikacie, ale informacje o sekwencjach napotkanych wcześniej.
2. Algorytmy kompresji statystycznej (entropii). Ta grupa algorytmów kompresuje informacje, wykorzystując nieregularną częstotliwość występowania różnych znaków w wiadomości. Algorytmy w tej grupie obejmują algorytmy arytmetyczne i kodowania prefiksowego (z wykorzystaniem Shannona-Fanno, Huffmana, siecznych drzew).
Algorytmy przetwarzania informacji można zaliczyć do osobnej grupy. Algorytmy z tej grupy nie kompresują bezpośrednio informacji, ale ich zastosowanie znacznie ułatwia dalszą kompresję za pomocą algorytmów strumieniowych, słownikowych i entropijnych.

Algorytmy strumieniowe i słownikowe

Kodowanie długości przebiegu

Run-Length Encoding (RLE) to jeden z najprostszych i najpopularniejszych algorytmów kompresji danych. W tym algorytmie ciąg powtarzających się znaków jest zastępowany znakiem i liczbą jego powtórzeń.
Na przykład ciąg „AAAAAA”, który wymaga przechowywania 5 bajtów (zakładając, że bajt jest przydzielony do przechowywania jednego znaku), można zastąpić ciągiem „5A” składającym się z dwóch bajtów. Oczywiście algorytm ten jest tym skuteczniejszy, im dłuższa jest seria powtórzeń.

Główną wadą tego algorytmu jest jego wyjątkowo niska skuteczność w przypadku sekwencji niepowtarzających się znaków. Na przykład, jeśli weźmiemy pod uwagę sekwencję „ABABAB” (6 bajtów), to po zastosowaniu algorytmu RLE zmieni się ona w „1A1B1A1B1A1B” (12 bajtów). Aby rozwiązać problem niepowtarzających się znaków, istnieją różne metody.

Najbardziej prosta metoda polega na następującej modyfikacji: bajt kodujący liczbę powtórzeń musi przechowywać informację nie tylko o liczbie powtórzeń, ale także o ich obecności. Jeśli pierwszy bit ma wartość 1, to kolejnych 7 bitów wskazuje liczbę powtórzeń odpowiedniego znaku, a jeśli pierwszy bit ma wartość 0, to kolejnych 7 bitów wskazuje liczbę znaków, które należy pobrać bez powtórzeń. Jeśli za pomocą tej modyfikacji zakodujemy „ABABAB”, otrzymamy „-6ABABAB” (7 bajtów). Jest oczywiste, że proponowana technika może znacząco zwiększyć efektywność algorytmu RLE na niepowtarzających się ciągach znaków. Implementację proponowanego podejścia pokazano na Listingu 1:

  1. typ
  2. funkcja RLEEncode(InMsg: ShortString): TRLEEncodedString;
  3. MatchFl: wartość logiczna;
  4. MatchCount: krótka int;
  5. Zakodowany ciąg: TRLEEncodedString;
  6. N, i: bajt;
  7. zaczynać
  8. N:=0;
  9. SetLength(EncodedString, 2 * długość(InMsg) ) ;
  10. podczas gdy długość (InMsg) >= 1 do
  11. zaczynać
  12. MatchFl : = (długość(InMsg) > 1 ) i (InMsg[ 1 ] = InMsg[ 2 ] ) ;
  13. Liczba dopasowań: = 1;
  14. podczas (MatchCount<= 126 ) and (MatchCount < length(InMsg) ) and ((InMsg[ MatchCount] = InMsg[ MatchCount + 1 ] ) = MatchFl) do
  15. MatchCount: = MatchCount + 1;
  16. jeśli MatchFl to
  17. zaczynać
  18. N:=N+2;
  19. EncodedString[N - 2]: = MatchCount + 128;
  20. EncodedString[N - 1]: = ord(InMsg[1]) ;
  21. w przeciwnym razie
  22. zaczynać
  23. jeśli MatchCount<>długość (InMsg), a następnie
  24. MatchCount: = MatchCount - 1;
  25. N : = N + 1 + Liczba dopasowań;
  26. EncodedString[N - 1 - MatchCount] : = - MatchCount + 128 ;
  27. for i: = 1 do MatchCount
  28. EncodedString[ N - 1 - MatchCount + i] : = ord (InMsg[ i] ) ;
  29. koniec ;
  30. usuń(InMsg, 1, MatchCount) ;
  31. koniec ;
  32. SetLength(Zakodowany ciąg, N) ;
  33. RLEEncode := Zakodowany ciąg;
  34. koniec ;

Dekodowanie skompresowanej wiadomości jest bardzo proste i sprowadza się do pojedynczego przejścia przez skompresowaną wiadomość, patrz Listing 2:
  1. typ
  2. TRLEEncodedString = tablica bajtów;
  3. funkcja RLEDecode(InMsg: TRLEEncodedString): ShortString;
  4. Liczba powtórzeń: krótka int;
  5. i, j: słowo ;
  6. OutMsg: Krótki ciąg;
  7. zaczynać
  8. OutMsg: = "";
  9. ja := 0;
  10. podczas gdy ja< length(InMsg) do
  11. zaczynać
  12. PowtórzCount: = InMsg[ i] - 128;
  13. ja: = ja + 1;
  14. jeśli PowtórzCount< 0 then
  15. zaczynać
  16. PowtórzCount:= mięśnie brzucha (RepeatCount) ;
  17. dla j: = i do i + RepeatCount - 1 do
  18. OutMsg: = OutMsg + chr (InMsg[ j] ) ;
  19. i : = i + Liczba powtórzeń;
  20. w przeciwnym razie
  21. zaczynać
  22. dla j : = 1 do PowtórzCount do
  23. OutMsg: = OutMsg + chr (InMsg[ i] ) ;
  24. ja: = ja + 1;
  25. koniec ;
  26. koniec ;
  27. RLEDecode := OutMsg;
  28. koniec ;

Drugą metodą zwiększenia wydajności algorytmu RLE jest zastosowanie algorytmów transformacji informacji, które nie dokonują bezpośredniej kompresji danych, ale doprowadzają je do postaci wygodniejszej do kompresji. Jako przykład takiego algorytmu rozważymy permutację BWT, nazwaną na cześć twórców transformaty Burrowsa-Wheelera. Permutacja ta nie zmienia samych znaków, a jedynie zmienia ich kolejność w ciągu, natomiast powtarzające się podciągi po zastosowaniu permutacji zbierane są w gęste grupy, które są znacznie lepiej skompresowane przy użyciu algorytmu RLE. Bezpośrednia konwersja BWT sprowadza się do następujących kroków:
1. Dodanie do oryginalnego ciągu specjalnego znaku końca linii, który nie występuje nigdzie indziej;
2. Uzyskanie wszystkich permutacji cyklicznych oryginalnego ciągu;
3. Sortowanie otrzymanych ciągów znaków w porządku leksykograficznym;
4. Zwrócenie ostatniej kolumny wynikowej macierzy.
Implementację tego algorytmu pokazano na Listingu 3.
  1. konst
  2. EOMsg = "|" ;
  3. funkcja BWTEncode(InMsg: ShortString): ShortString;
  4. OutMsg: Krótki ciąg;
  5. OstatniChar:ANSIChar;
  6. N, ja: słowo ;
  7. zaczynać
  8. InMsg: = InMsg + EOMsg;
  9. N : = długość(InMsg) ;
  10. ShiftTable[1]: = InMsg;
  11. dla i : = 2 do N zrobić
  12. zaczynać
  13. LastChar: = InMsg[ N] ;
  14. InMsg: = LastChar + copy(InMsg, 1, N - 1) ;
  15. ShiftTable[ i] : = InMsg;
  16. koniec ;
  17. Sortuj(Tabela Shift) ;
  18. OutMsg: = "";
  19. dla i: = 1 do N zrobić
  20. OutMsg: = OutMsg + ShiftTable[ i] [ N] ;
  21. BWTEncode := OutMsg;
  22. koniec ;

Najłatwiej wyjaśnić tę transformację na konkretnym przykładzie. Weźmy ciąg „ANANAS” i umówmy się, że końcem ciągu będzie znak „|”. Wszystkie permutacje cykliczne tego ciągu oraz wynik ich sortowania leksykograficznego podano w tabeli. 1.

Te. Wynikiem bezpośredniej konwersji jest ciąg „|NNAAAC”. Łatwo zauważyć, że ciąg ten jest skompresowany znacznie lepiej niż oryginalny za pomocą algorytmu RLE, ponieważ zawiera długie podciągi powtarzających się liter.
Podobny efekt można uzyskać stosując inne przekształcenia, jednak zaletą transformacji BWT jest to, że jest ona odwracalna, chociaż transformacja odwrotna jest bardziej skomplikowana niż transformacja bezpośrednia. Aby przywrócić oryginalny ciąg, należy wykonać następujące kroki:
Utwórz pustą macierz o rozmiarze n*n, gdzie n jest liczbą znaków w zakodowanej wiadomości;
Wypełnij pustą kolumnę znajdującą się najbardziej po prawej stronie zakodowaną wiadomością;
Sortuj wiersze tabeli w porządku leksykograficznym;
Powtarzaj kroki 2-3, dopóki są puste kolumny;
Zwróć ciąg znaków kończący się znakiem końca linii.

Zaimplementowanie konwersji odwrotnej na pierwszy rzut oka nie jest trudne, a jedną z opcji implementacji pokazano na Listingu 4.

  1. konst
  2. EOMsg = "|" ;
  3. funkcja BWTDecode(InMsg: ShortString): ShortString;
  4. OutMsg: Krótki ciąg;
  5. ShiftTable: tablica ShortString;
  6. N, i, j: słowo ;
  7. zaczynać
  8. OutMsg: = "";
  9. N : = długość(InMsg) ;
  10. UstawDługość(Tabela Przesunięć, N + 1) ;
  11. dla i : = 0 do N zrobić
  12. Tabela Przesunięć[i]: = "";
  13. dla i: = 1 do N zrobić
  14. zaczynać
  15. dla j := 1 do N zrobić
  16. ShiftTable[j]: = InMsg[j] + ShiftTable[j];
  17. Sortuj(Tabela Shift) ;
  18. koniec ;
  19. dla i: = 1 do N zrobić
  20. jeśli ShiftTable[i] [N] = EOMsg to
  21. OutMsg: = Tabela Przesunięć[ i] ;
  22. usuń(OutMsg, N, 1 ) ;
  23. BWTDecode := OutMsg;
  24. koniec ;

Jednak w praktyce wydajność zależy od wybranego algorytmu sortowania. Trywialne algorytmy o złożoności kwadratowej będą oczywiście miały bardzo negatywny wpływ na wydajność, dlatego zaleca się stosowanie wydajnych algorytmów.

Po posortowaniu tabeli uzyskanej w kroku siódmym należy wybrać z tabeli wiersz kończący się znakiem „|”. Łatwo zauważyć, że jest to jedyna linia. To. Przyjrzeliśmy się transformacji BWT na konkretnym przykładzie.

Podsumowując, można powiedzieć, że główną zaletą grupy algorytmów RLE jest prostota i szybkość działania (w tym szybkość dekodowania), a główną wadą jest nieefektywność w przypadku niepowtarzających się zestawów znaków. Zastosowanie specjalnych permutacji zwiększa wydajność algorytmu, ale także znacznie wydłuża czas działania (zwłaszcza dekodowania).

Kompresja słownikowa (algorytmy LZ)

Grupa algorytmów słownikowych, w odróżnieniu od algorytmów z grupy RLE, koduje nie liczbę powtórzeń znaków, ale napotkane wcześniej ciągi znaków. Podczas działania rozważanych algorytmów tworzona jest dynamicznie tabela zawierająca listę już napotkanych sekwencji i odpowiadających im kodów. Ta tabela jest często nazywana słownikiem, a odpowiadająca jej grupa algorytmów nazywana jest słownikiem.

Poniżej opisano najprostszą wersję algorytmu słownikowego:
Zainicjuj słownik ze wszystkimi znakami pojawiającymi się w ciągu wejściowym;
Znajdź w słowniku najdłuższą sekwencję (S), która pasuje do początku zakodowanej wiadomości;
Wydrukuj kod znalezionej sekwencji i usuń go z początku zakodowanej wiadomości;
Jeżeli wiadomość nie została osiągnięta, przeczytaj kolejny znak i dodaj Sc do słownika, przejdź do kroku 2. W przeciwnym razie wyjdź.

Na przykład nowo zainicjowany słownik dla frazy „CUCKOOKOOKUSHONKOOKUPILAKAHOOD” pokazano w tabeli. 3:

W procesie kompresji słownik zostanie uzupełniony o sekwencje znalezione w wiadomości. Proces aktualizacji słownika przedstawiono w tabeli. 4.

W opisie algorytmu celowo pominięto opis sytuacji, w której słownik jest całkowicie zapełniony. W zależności od wariantu algorytmu możliwe jest różne zachowanie: całkowite lub częściowe wyczyszczenie słownika, zatrzymanie uzupełniania słownika lub rozszerzenie słownika z odpowiednim zwiększeniem pojemności kodu. Każde z tych podejść ma pewne wady. Przykładowo zatrzymanie uzupełniania słownika może doprowadzić do sytuacji, w której słownik przechowuje sekwencje, które występują na początku kompresowanego ciągu, ale nie występują później. Jednocześnie czyszczenie słownika może prowadzić do usunięcia częstych sekwencji. Większość stosowanych implementacji podczas wypełniania słownika zaczyna monitorować poziom kompresji, a gdy spadnie on poniżej pewnego poziomu, słownik jest przebudowywany. Następnie rozważymy najprostszą implementację, która zatrzymuje aktualizację słownika, gdy jest on pełny.

Najpierw zdefiniujmy słownik jako rekord przechowujący nie tylko napotkane podciągi, ale także liczbę podciągów przechowywanych w słowniku:

Wcześniej napotkane podciągi są przechowywane w tablicy Words, a ich kodem są numery podsekwencji w tej tablicy.
Zdefiniujemy także funkcje wyszukiwania w słowniku i dodawania do słownika:

  1. konst
  2. MAX_DICT_LENGTH = 256 ;
  3. funkcja FindInDict(D: TDictionary; str: ShortString): liczba całkowita;
  4. r:liczba całkowita;
  5. i:liczba całkowita;
  6. fl:boolean;
  7. zaczynać
  8. r: = - 1;
  9. jeśli D. WordCount > 0 to
  10. zaczynać
  11. i := D. WordCount;
  12. fl := fałsz;
  13. podczas gdy (nie fl) i (i >= 0 ) tak
  14. zaczynać
  15. ja: = ja - 1;
  16. fl : = D. Słowa [ i] = str;
  17. koniec ;
  18. koniec ;
  19. jeśli fl to
  20. r := ja;
  21. FindInDict: = r;
  22. koniec ;
  23. procedura AddToDict(var D: TDictionary; str: ShortString) ;
  24. zaczynać
  25. jeśli D. WordCount< MAX_DICT_LENGTH then
  26. zaczynać
  27. D. Liczba Słów : = D. Liczba Słów + 1 ;
  28. SetLength(D. Words, D. WordCount) ;
  29. D. Słowa [ D. WordCount - 1 ] : = str;
  30. koniec ;
  31. koniec ;

Korzystając z tych funkcji, proces kodowania według opisanego algorytmu można zrealizować w następujący sposób:
  1. funkcja LZWEncode(InMsg: ShortString): TEncodedString;
  2. OutMsg: TEncodedString;
  3. tmpstr: Krótki ciąg;
  4. D: TSłownik;
  5. i, N: bajt;
  6. zaczynać
  7. SetLength(OutMsg, długość(InMsg) ) ;
  8. N:=0;
  9. InitDict(D) ;
  10. podczas gdy długość (InMsg) > 0 zrobić
  11. zaczynać
  12. tmpstr: = InMsg[ 1] ;
  13. while (FindInDict(D, tmpstr) >= 0 ) i (długość(InMsg) > długość(tmpstr) do
  14. tmpstr: = tmpstr + InMsg[długość(tmpstr) + 1] ;
  15. jeśli FindInDict(D, tmpstr)< 0 then
  16. usuń(tmpstr, długość(tmpstr) , 1 ) ;
  17. OutMsg[ N] : = FindInDict(D, tmpstr) ;
  18. N:=N+1;
  19. usuń(InMsg, 1, długość(tmpstr) ) ;
  20. jeśli długość (InMsg) > 0, to
  21. AddToDict(D, tmpstr + InMsg[ 1 ] ) ;
  22. koniec ;
  23. SetLength(OutMsg, N) ;
  24. LZWEncode := OutMsg;
  25. koniec ;

Wynikiem kodowania będzie liczba słów w słowniku.
Proces dekodowania sprowadza się do bezpośredniego dekodowania kodów i nie ma potrzeby przenoszenia utworzonego słownika, wystarczy, że podczas dekodowania słownik zostanie zainicjowany w taki sam sposób, jak podczas kodowania. Następnie słownik zostanie całkowicie przywrócony bezpośrednio podczas procesu dekodowania poprzez połączenie poprzedniego podciągu i bieżącego symbolu.

Jedyny problem może wystąpić w następującej sytuacji: gdy konieczne jest zdekodowanie podciągu, którego jeszcze nie ma w słowniku. Łatwo zauważyć, że jest to możliwe tylko wtedy, gdy konieczne jest wyodrębnienie podciągu, który należy dodać w bieżącym kroku. Oznacza to, że podciąg spełnia wzorzec cSc, tj. zaczyna się i kończy tym samym znakiem. W tym przypadku cS jest podciągiem dodanym w poprzednim kroku. Rozważana sytuacja jest jedyną, w której konieczne jest zdekodowanie linii, która nie została jeszcze dodana. Biorąc powyższe pod uwagę, możemy zaproponować następującą opcję dekodowania skompresowanego ciągu:

  1. funkcja LZWDecode(InMsg: TEncodedString): ShortString;
  2. D: TSłownik;
  3. OutMsg, tmpstr: ShortString;
  4. i: bajt;
  5. zaczynać
  6. OutMsg: = "";
  7. tmpstr: = "";
  8. InitDict(D) ;
  9. dla i : = 0 do długości (InMsg) - 1 do
  10. zaczynać
  11. jeśli InMsg[ i] >= D. WordCount to
  12. tmpstr : = D. Słowa [ InMsg [ i - 1 ] ] + D. Słowa [ InMsg [ i - 1 ] ] [ 1 ]
  13. w przeciwnym razie
  14. tmpstr: = D. Słowa [InMsg[ i] ] ;
  15. OutMsg: = OutMsg + tmpstr;
  16. jeśli i > 0, to
  17. AddToDict(D, D. Words [InMsg[ i - 1 ] ] + tmpstr[ 1 ] ) ;
  18. koniec ;
  19. LZWDecode := OutMsg;
  20. koniec ;

Zaletami algorytmów słownikowych jest większa efektywność kompresji w porównaniu do RLE. Należy jednak zrozumieć, że faktyczne wykorzystanie tych algorytmów wiąże się z pewnymi trudnościami wdrożeniowymi.

Kodowanie entropijne

Kodowanie z wykorzystaniem drzew Shannona-Fano

Algorytm Shannona-Fano jest jednym z pierwszych opracowanych algorytmów kompresji. Algorytm opiera się na idei reprezentowania częstszych znaków za pomocą krótszych kodów. Ponadto kody otrzymane za pomocą algorytmu Shannona-Fano mają właściwość przedrostka: tj. żaden kod nie jest początkiem żadnego innego kodu. Właściwość prefix zapewnia, że ​​kodowanie jest jeden do jednego. Algorytm konstruowania kodów Shannona-Fano przedstawiono poniżej:
1. Podziel alfabet na dwie części, tak aby całkowite prawdopodobieństwa symboli były jak najbliżej siebie.
2. Dodaj 0 do kodu przedrostka pierwszej części znaków, dodaj 1 do kodu przedrostka drugiej części znaków.
3. Dla każdej części (która zawiera co najmniej dwa znaki) wykonaj rekurencyjnie kroki 1-3.
Pomimo swojej względnej prostoty algorytm Shannona-Fano nie jest pozbawiony wad, z których najważniejszą jest nieoptymalne kodowanie. Chociaż podział na każdym etapie jest optymalny, algorytm nie gwarantuje optymalnego wyniku jako całości. Weź pod uwagę np. następna linia: "AAABVGDEZH". Odpowiednie drzewo Shannona-Fano i otrzymane na jego podstawie kody przedstawiono na ryc. 1:

Bez zastosowania kodowania wiadomość zajmie 40 bitów (pod warunkiem, że każdy znak będzie zakodowany na 4 bitach), a przy zastosowaniu algorytmu Shannona-Fano 4*2+2+4+4+3+3+3=27 bitów. Wolumen wiadomości spadł o 32,5%, ale poniżej pokażemy, że wynik ten można znacząco poprawić.

Kodowanie za pomocą drzew Huffmana

Algorytm kodowania Huffmana, opracowany kilka lat po algorytmie Shannona-Fano, również posiada właściwość prefiksacji, a dodatkowo udowodnioną minimalną redundancję, co decyduje o jego niezwykle szerokim rozkładzie. Aby uzyskać kody Huffmana, użyj następującego algorytmu:
1. Wszystkie znaki alfabetu są reprezentowane jako wolne węzły, a waga węzła jest proporcjonalna do częstotliwości występowania znaku w wiadomości;
2. Ze zbioru wolnych węzłów wybiera się dwa węzły o minimalnej wadze i tworzony jest nowy węzeł (rodzic) o wadze równej sumie wag wybranych węzłów;
3. Wybrane węzły usuwane są z wolnej listy, a utworzony na ich podstawie węzeł nadrzędny dodawany jest do tej listy;
4. Kroki 2-3 powtarza się, aż na wolnej liście znajdzie się więcej niż jeden węzeł;
5. Na podstawie skonstruowanego drzewa każdemu znakowi alfabetu przypisany jest kod prefiksowy;
6. Wiadomość jest kodowana otrzymanymi kodami.

Rozważmy ten sam przykład, co w przypadku algorytmu Shannona-Fano. Drzewo Huffmana i kody otrzymane dla komunikatu „AAAABVGDEJ” przedstawiono na rys. 2:

Łatwo policzyć, że objętość zakodowanej wiadomości będzie wynosić 26 bitów, czyli mniej niż w algorytmie Shannona-Fano. Osobno warto zauważyć, że ze względu na popularność algorytmu Huffmana istnieje obecnie wiele opcji kodowania Huffmana, w tym kodowanie adaptacyjne, które nie wymaga transmisji częstotliwości symboli.
Wśród wad algorytmu Huffmana znaczną część stanowią problemy związane ze złożonością implementacji. Używanie symboli zmiennych rzeczywistych do przechowywania częstotliwości wiąże się z utratą precyzji, dlatego w praktyce często stosuje się zmienne całkowite, ale ponieważ Waga węzłów macierzystych stale rośnie, prędzej czy później następuje przepełnienie. Zatem pomimo prostoty algorytmu jego poprawna implementacja może w dalszym ciągu sprawiać pewne trudności, szczególnie w przypadku dużych alfabetów.

Kodowanie siecznymi drzewami funkcyjnymi

Kodowanie za pomocą funkcji siecznych to opracowany przez autorów algorytm pozwalający na uzyskanie kodów prefiksowych. Algorytm opiera się na idei konstrukcji drzewa, którego każdy węzeł zawiera sieczną funkcję. Aby dokładniej opisać algorytm, konieczne jest wprowadzenie kilku definicji.
Słowo to uporządkowana sekwencja m bitów (liczba m nazywana jest pojemnością słowa).
Literał sieczny to para postaci cyfra-cyfra. Na przykład literał (4,1) oznacza, że ​​bit 4 słowa musi wynosić 1. Jeżeli warunek literału jest spełniony, to literał uważa się za prawdziwy, w przeciwnym razie jest on fałszywy.
Sekans k-bitowy to zbiór k literałów. Jeśli wszystkie literały są prawdziwe, to sama funkcja sieczna jest prawdziwa, w przeciwnym razie jest fałszywa.

Drzewo jest skonstruowane w taki sposób, że każdy węzeł dzieli alfabet na możliwie najbliższe części. Na ryc. Rysunek 3 pokazuje przykład siecznego drzewa:

Drzewo funkcji siecznych w ogólnym przypadku nie gwarantuje optymalnego kodowania, ale zapewnia niezwykle wysoka prędkość działają ze względu na prostotę obsługi w węzłach.

Kodowanie arytmetyczne

Kodowanie arytmetyczne jest jednym z najbardziej popularnych skuteczne sposoby kompresja informacji. W przeciwieństwie do algorytmu Huffmana, kodowanie arytmetyczne umożliwia kodowanie wiadomości z entropią mniejszą niż 1 bit na znak. Ponieważ Większość algorytmów kodowania arytmetycznego jest chroniona patentami; poniżej zostaną opisane jedynie podstawowe idee.
Załóżmy, że używany alfabet zawiera N symboli a_1,…,a_N, o częstotliwościach odpowiednio p_1,…,p_N. Wtedy algorytm kodowania arytmetycznego będzie wyglądał następująco:
Przyjmij jako roboczy półokres

Kompresja pustych przestrzeni

Zagęszczanie białych przestrzeni można opisać bardziej ogólnie jako „usuwanie tego, co nas nie interesuje”. Chociaż ta metoda jest punkt techniczny Chociaż wizja jest techniką kompresji stratnej, nadal jest użyteczna w przypadku wielu typów reprezentacji danych, które spotykamy w świecie rzeczywistym. Na przykład, mimo że HTML jest znacznie łatwiejszy do odczytania w edytorze tekstu, podczas dodawania wcięć i odstępy między wierszami, żadna z tych „białych znaków” nie ma żadnego wpływu na renderowanie dokumentu HTML w przeglądarce internetowej. Jeśli wiesz na pewno, że dany dokument HTML jest przeznaczony wyłącznie dla przeglądarki internetowej (lub jakiegoś robota/agenta wyszukiwania), dobrym pomysłem może być usunięcie wszystkich białych znaków, aby dokument przesyłał się szybciej i zajmował mniej miejsca do przechowywania. Wszystko, co usuwamy podczas kompresji pustych przestrzeni, w rzeczywistości nie przenosi żadnego obciążenia funkcjonalnego.

W przypadku przedstawionego przykładu z opisywanego raportu można usunąć jedynie niewielką część informacji. Linia symboli „=” wzdłuż górnej krawędzi raportu nie zawiera żadnej treści funkcjonalnej; to samo dotyczy znaków „-” w liczbach i spacji między liczbami. Wszystko to jest przydatne dla osoby czytającej oryginalny raport, ale nie ma żadnego znaczenia, jeśli uznamy te znaki za „dane”. To, co usuwamy, nie jest dokładnie „pustą przestrzenią” w tradycyjnym sensie, ale zasadniczo nią jest.

Kompresja pustych przestrzeni jest niezwykle „tania” z punktu widzenia implementacji. To tylko kwestia odczytania strumienia danych i wykluczenia kilku konkretnych wartości ze strumienia wyjściowego. W wielu przypadkach etap „rozpakowywania” w ogóle nie jest dostępny. Jednak nawet gdybyśmy chcieli odtworzyć coś zbliżonego do oryginalnego strumienia danych, wymagałoby to jedynie niewielkiej ilości zasobów procesora lub pamięci. Odzyskane dane niekoniecznie będą takie same jak dane oryginalne; zależy to od tego, jakie zasady i ograniczenia były zawarte w oryginale. strona HTML, wpisane przez osobę w edytorze tekstu, będzie prawdopodobnie zawierać spacje ułożone według pewnych zasad. To samo dotyczy zautomatyzowanych narzędzi, które często tworzą „rozsądne” wcięcia i odstępy w kodzie HTML. W przypadku prezentowanego w naszym przykładzie sztywnego formatu raportu nie ma powodu, dla którego pierwotna reprezentacja nie mogłaby zostać odtworzona przez jakiś „program rozpakowujący formatowanie”.

Kodowanie grupowe

Kodowanie grupowe (RLE) to najprostsza z powszechnie stosowanych metod kompresji bezstratnej. Podobnie jak zmniejszanie pustych przestrzeni, nie wymaga koszty specjalne, zwłaszcza do dekodowania. Ideą tej metody jest to, że wiele reprezentacji danych składa się głównie z ciągów powtarzających się bajtów. Nasz przykładowy raport jest jednym z takich widoków danych. Rozpoczyna się ciągiem powtarzających się znaków „=” i zawiera wiersze składające się wyłącznie ze spacji rozsiane po całym raporcie. Zamiast reprezentować każdy znak własnym bajtem, metoda RLE polega (czasami lub zawsze) na określeniu liczby powtórzeń, po której następuje podanie znaku, który ma być odtwarzany tyle razy.

Jeżeli w przetwarzanym formacie danych dominują powtarzające się bajty, właściwym i skutecznym może być zastosowanie algorytmu, w którym jeden lub więcej bajtów wskazuje liczbę powtórzeń, po których następuje powtarzający się znak. Jeśli jednak masz ciągi znaków o długości jednostkowej, ich zakodowanie zajmie dwa (lub więcej) bajty. Innymi słowy, jeden znak ASCII „X” strumienia wejściowego może wymagać wyjściowego strumienia bitów o wartości 00000001 01011000 . Z drugiej strony, zakodowanie stu kolejnych znaków „X” wymagałoby tej samej liczby bitów: 01100100 01011000 , co jest dość wydajne.

Różne warianty RLE często selektywnie wykorzystują bajty do wskazania liczby powtórzeń, podczas gdy pozostałe bajty po prostu reprezentują same siebie. W tym celu należy zarezerwować co najmniej jedną wartość jednobajtową, którą w razie potrzeby można usunąć z wyjścia. Na przykład z naszego przykładowego raportu dotyczącego numeru telefonu wiemy, że wszystkie informacje w strumieniu wejściowym składają się z prostych Znaki ASCII. W szczególności wszystkie takie znaki mają pierwszy bit wartości ASCII równy 0. Możemy użyć tego pierwszego bitu ASCII, aby wskazać, że bajt wskazuje liczbę powtórzeń, a nie zwykły znak. Następnych siedem bitów bajtu iteratora można wykorzystać do wskazania liczby powtórzeń, a następny bajt może zawierać powtarzany znak. Na przykład możemy przedstawić ciąg „YXXXXXXXXX” w następujący sposób:

„Y” Iter(8) „X” 01001111 10001000 01011000

Przykład ten nie wyjaśnia, w jaki sposób odrzucać wartości bajtów iteratora, ani nie zapewnia możliwości użycia więcej niż 127 powtórzeń pojedynczego znaku. Jednak w razie potrzeby różne odmiany RLE rozwiązują te problemy.

Kodowanie Huffmana

Kodowanie Huffmana traktuje tablicę symboli jako cały zestaw danych. Kompresję osiąga się poprzez znalezienie „wag” każdego znaku w zestawie danych. Niektóre znaki są używane częściej niż inne, dlatego w kodowaniu Huffmana zakłada się, że częste znaki powinny być kodowane w mniejszej liczbie bitów niż mniej popularne znaki. Istnieć różne opcje kodowanie Huffmana, ale pierwotna (i najczęściej stosowana) wersja polega na znalezieniu najczęstszego znaku i zakodowaniu go pojedynczym bitem, np. 1. A jeśli w zakodowanej sekwencji występuje 0, oznacza to, że w tym miejscu znajduje się inny znak zakodowany z dużą liczbą bitów.

Wyobraźmy sobie, że do zakodowania naszego przykładu użyliśmy kodowania Huffmana (zakładając, że raport poddaliśmy już kompresji białych znaków). Moglibyśmy uzyskać następujący wynik:

Tabela 2. Wyniki kodowania Huffmana

Kodowanie Symbol 1 7 010 2 011 3 00000 4 00001 5 00010 6 00011 8 00100 9 00101 0 00111 1

Oryginalny zestaw znaków (składający się z liczb) można łatwo zakodować (bez kompresji) jako sekwencje 4-bitowe (nibble). Poniższe kodowanie Huffmana w najgorszym przypadku użyje do 5 bitów znaków, co jest oczywiście gorsze niż kodowanie półbajtowe. Jednak w najlepszym przypadku wszystko, co jest wymagane, to 1 fragment; wiadomo, że najczęściej będzie używany ten najlepszy przypadek (ponieważ jest to symbol, który pojawia się najczęściej w danych). Moglibyśmy więc zakodować konkretny numer telefonu w ten sposób:

772 7628 --> 1 1 010 1 00010 010 00011

Jeśli numer telefonu zostałby zakodowany przy użyciu półbajtów, reprezentacja numeru telefonu zajęłaby 28 bitów, ale w naszym przypadku kodowanie zajmuje 19 bitów. W przykładzie dodano spacje tylko w celu lepszego zrozumienia; ich obecność w zakodowanych symbolach nie jest wymagana, ponieważ zawsze można na podstawie tabeli kodów określić, czy osiągnięto koniec zakodowanego symbolu, czy nie (jednak nadal konieczne jest śledzenie aktualnej pozycji w danych ).

Kodowanie Huffmana jest nadal bardzo „tanie” do dekodowania pod względem czasu procesora. Wymaga jednak przeszukania książki kodowej, więc może nie być tak „tani” jak RLE. Kodowanie Huffmana jest dość drogie, ponieważ wymaga pełnego skanowania danych i zbudowania tabeli częstotliwości symboli. W niektórych przypadkach, gdy stosuje się kodowanie Huffmana, odpowiedni jest „skrót”. Standardowe kodowanie Huffmana jest stosowane do określonego kodowanego zestawu danych, przy czym najpierw następuje wynik, po którym następuje tabela symboli. Jeśli jednak przesyłany jest nie pojedynczy zestaw danych, ale cały format z tymi samymi wzorcami występowania znaków, wówczas można zastosować globalną tablicę Huffmana. Mając taką tabelę, możemy zakodować wyszukiwania w naszych plikach wykonywalnych, co sprawi, że kompresja i dekompresja będą znacznie „tańsze” (pomijając początkowe globalne próbkowanie i kodowanie). Na przykład, jeśli wiemy, że nasz zbiór danych będzie prozą język angielski, to częstotliwości występowania liter są dobrze znane i stałe dla różnych zbiorów danych.

Kompresja przy użyciu algorytmu Lempela-Ziva

Prawdopodobnie najbardziej znaczącą metodą kompresji bezstratnej jest algorytm Lempela-Ziva. W tym artykule porozmawiamy o wariancie LZ78, ale LZ77 i inne warianty działają w podobny sposób. Ideą algorytmu LZ78 jest zakodowanie strumieniowej sekwencji bajtów przy użyciu jakiejś dynamicznej tabeli. Na początku kompresji strumienia bitów tablica LZ jest wypełniana rzeczywistym zestawem znaków wraz z kilkoma pustymi miejscami. Algorytm wykorzystuje tabele różne rozmiary, ale w tym przykładzie z numerami telefonów (z kompresją pustych przestrzeni) używana jest tabela złożona z 32 elementów (wystarczająca dla ten przykład, ale może nie wystarczyć w przypadku innych typów danych). Najpierw wypełniamy pierwsze dziesięć miejsc znakami użytego alfabetu (cyframi). Po nadejściu nowych bajtów najpierw pobierana jest wartość tabeli odpowiadająca najdłuższej pasującej sekwencji, a następnie sekwencja o długości N+1 jest zapisywana w następnym dostępnym slocie. W najgorszym przypadku użyjemy 5 bitów zamiast 4 dla pojedynczego znaku, ale w większości przypadków możemy obejść się przy 5 bitach dla kilku znaków. Spójrzmy na przykład działania tego algorytmu (slot tabeli jest wskazany w nawiasy kwadratowe):

7 --> Szukaj: 7 znaleziono --> nic do dodania --> kontynuuj wyszukiwanie 7 --> Szukaj: 77 nie znaleziono --> dodaj „77” do --> wyświetl =00111 2 --> Szukaj: 72 nie znaleziono znaleziono --> dodaj „72” do --> wyświetl =00111 7 --> Szukaj: 27 nie znaleziono --> dodaj „27” do --> wyświetl =00010 6 --> Szukaj: 76 nie znaleziono --> dodaj „76” do --> wyświetl =00111 2 --> Szukaj: 62 nie znaleziono --> dodaj „62” do --> wyświetl =00110 8 --> Szukaj: 28 nie znaleziono --> dodaj „28” do --> wyjście =00010

Jak dotąd nie uzyskaliśmy z tego żadnej korzyści, ale przejdźmy do następnego numeru telefonu:

7 --> Szukaj: 87 nie znaleziono --> dodaj „87 do --> wyświetl =00100 7 --> Szukaj: 77 znaleziono --> nic do dodania --> kontynuuj wyszukiwanie 2 --> Szukaj: 772 nie znaleziono - -> dodaj „772” do --> wyjście =01011 8 --> Szukaj: 28 znaleziono --> nic do dodania --> kontynuuj wyszukiwanie 6 --> Szukaj: 286 nie znaleziono --> dodaj „286” do --> wyjście =10000 ....

Powyższe operacje powinny wystarczyć do zademonstrowania działania modelu. Chociaż nie osiągnięto jeszcze zauważalnej kompresji, można już zauważyć, że ponownie wykorzystaliśmy sloty 11 i 16, kodując dwa symbole, każdy z jednym symbolem wyjściowym. Ponadto zgromadziliśmy już niezwykle użyteczną sekwencję bajtów 772 w gnieździe 18, która następnie będzie wielokrotnie pojawiać się w strumieniu.

Algorytm LZ78 wypełnia jedną tabelę symboli (prawdopodobnie) użytecznymi wpisami, następnie zapisuje tę tabelę, czyści ją i rozpoczyna nową. W takiej sytuacji tablica 32 znaków może nie wystarczyć, gdyż zostanie wyczyszczona zanim będziemy mogli wielokrotnie używać sekwencji typu 772 i tym podobnych. Jednak przy pomocy małej tabelki łatwiej jest zobrazować działanie algorytmu.

W typowych zbiorach danych warianty metody Lempela-Ziva osiągają znacznie więcej wysokie szanse kompresji niż metody Huffmana i RLE. Z drugiej strony warianty metody Lempela-Ziva zużywają znaczne zasoby na iteracje, a ich tabele mogą zajmować dużo miejsca w pamięci. Większość istniejących narzędzia i biblioteki kompresyjne wykorzystują kombinację metod Lempela-Ziva i Huffmana.

Prawidłowe określenie problemu

Wybierając odpowiedni algorytm, można osiągnąć znaczne korzyści nawet w porównaniu z bardziej zoptymalizowanymi, ale nieodpowiednimi metodami. Podobny właściwy wybór prezentacja danych jest często ważniejsze niż wybór metody kompresji (które zawsze stanowią pewnego rodzaju późniejszą optymalizację wymaganych funkcji). Prosty przykładowy zbiór danych przedstawiony w tym artykule stanowi doskonałą ilustrację sytuacji, w której ponowne przemyślenie problemu jest lepszym rozwiązaniem niż użycie każdy podanych metod kompresji.

Należy jeszcze raz przyjrzeć się problemowi, jaki stwarzają dane. Ponieważ nie jest to zbiór danych ogólnych i istnieją ku temu jasne przesłanki, problem można sformułować na nowo. Wiadomo, że jest maksymalnie 30 000 numerów telefonów (od 7720000 do 7749999), z czego część jest aktywna, a część nie. Nie stoimy przed zadaniem przedstawienia pełnej reprezentacji wszystkiego aktywne numery. Musimy tylko wskazać użycie wartości logicznej, aktywne ten numer albo nie. Myśląc o problemie w ten sposób, możemy po prostu przydzielić 30 000 bitów w pamięci i pamięci i użyć każdego bitu do wskazania aktywności (tak lub nie) odpowiedniego numeru telefonu. Kolejność bitów w mapie bitowej może odpowiadać numerom telefonów, posortowanym rosnąco (od najniższej do najwyższej).

Takie rozwiązanie oparte na bitmapie jest idealne ze wszystkich punktów widzenia. Do reprezentowania zbioru danych potrzeba dokładnie 3750 bajtów; różne metody kompresji będą wykorzystywać różną głośność w zależności od liczby numerów telefonów w zestawie i efektywności kompresji. Jeśli jednak 10 000 z 30 000 możliwych numerów telefonów jest aktywnych i nawet jeśli skuteczna metoda kompresja wymaga kilku bajtów na numer telefonu, wtedy bitmapa zdecydowanie wygrywa. Jeśli chodzi o wymagania procesora, bitmapa jest nie tylko lepsza od którejkolwiek z omawianych metod kompresji, ale jest także lepsza normalna metoda reprezentacja numerów telefonów jako ciągi znaków (bez kompresji). Przechodzenie przez bitmapę i zwiększanie aktualnego licznika numerów telefonów może odbywać się sprawnie nawet przy wbudowanej pamięci podręcznej nowoczesnych procesorów.

Od tego prosty przykład Można zrozumieć, że nie każdy problem ma tak idealne rozwiązanie, jak to omówione powyżej. Wiele problemów wymaga znacznych ilości pamięci, przepustowości, pamięci masowej i zasobów procesora; w większości takich przypadków techniki kompresji mogą złagodzić lub zmniejszyć te wymagania. Ale ważniejszym wnioskiem jest to, że przed użyciem technik kompresji powinieneś dokładnie sprawdzić, czy wybrałeś właściwą koncepcję do reprezentowania danych.

Poświęcony pamięci Claude'a Shannona.

Cechą charakterystyczną większości typów danych jest ich redundancja. Stopień redundancji danych zależy od rodzaju danych. Przykładowo dla danych wideo stopień redundancji jest kilkukrotnie większy niż dla danych graficznych, z kolei stopień redundancji danych graficznych jest większy niż stopień redundancji danych tekstowych. Kolejnym czynnikiem wpływającym na stopień redundancji jest przyjęty system kodowania. Przykładem systemów kodujących mogą być zwykłe języki komunikacji, które są niczym innym jak systemami kodowania pojęć i pomysłów na wyrażanie myśli. Ustalono zatem, że kodowanie danych tekstowych w języku rosyjskim daje średnio o 20-25% większą redundancję niż kodowanie podobnych danych w języku angielskim.

W przypadku ludzi nadmiarowość danych jest często kojarzona z jakością informacji, ponieważ nadmiarowość zwykle poprawia zrozumiałość i postrzeganie informacji. Jednak w przypadku przechowywania i przesyłania informacji za pomocą technologii komputerowej redundancja odgrywa negatywną rolę, ponieważ prowadzi do wzrostu kosztów przechowywania i przesyłania informacji. Problem ten staje się szczególnie istotny w przypadku przetwarzania ogromnych wolumenów informacji przy niewielkiej ilości nośników danych. W związku z tym stale pojawia się problem ograniczenia redundancji lub kompresji danych. Jeśli do gotowych plików stosuje się metody kompresji danych, często zamiast terminu „kompresja danych” używa się terminu „archiwizacja danych”; skompresowana wersja danych nazywa się archiwum i oprogramowanie implementujące metody kompresji nazywane są archiwiści.

W zależności od obiektu, w którym znajdują się dane do kompresji:

1. Kompresja (archiwizacja) plików: stosowana w celu zmniejszenia rozmiaru plików podczas przygotowania ich do transmisji kanałami komunikacyjnymi lub do transportu na nośnikach zewnętrznych o małej pojemności;

2. Kompresja (archiwizacja) folderów: stosowana w celu zmniejszenia objętości folderów przed długotrwałym przechowywaniem, np. podczas tworzenia kopii zapasowych;

3. Kompresja (zagęszczanie) dysków: stosowana w celu zwiększenia efektywności wykorzystania przestrzeni dyskowej poprzez kompresję danych podczas ich zapisu na nośnik pamięci (zwykle przy użyciu systemu operacyjnego).

Istnieje wiele praktycznych algorytmów kompresji danych, ale wszystkie opierają się na trzech teoretycznych sposobach ograniczenia nadmiarowości danych. Pierwszy sposób to zmiana zawartości danych, drugi to zmiana struktury danych, a trzeci to jednoczesna zmiana zarówno struktury, jak i zawartości danych.

Jeżeli kompresja danych zmienia ich zawartość, wywoływana jest metoda kompresji nieodwracalny, co oznacza, że ​​podczas przywracania (przywracania) danych z archiwum informacje nie są przywracane całkowicie. Metody takie są często nazywane metodami kompresji z kontrolowaną stratą. Oczywiste jest, że metody te można stosować tylko w przypadku typów danych, w przypadku których utrata części treści nie prowadzi do istotnego zniekształcenia informacji. Do tego typu danych zaliczają się dane wideo, audio i graficzne. Metody kompresji z kontrolowaną stratą zapewniają znacznie wyższe współczynniki kompresji, ale nie można ich zastosować do danych tekstowych. Przykłady formatów kompresji stratnej obejmują:


· JPEG – dla danych graficznych;

· MPG – dla danych wideo;

· MP3 – dla danych audio.

Jeżeli kompresja danych zmienia jedynie strukturę danych, wówczas wywoływana jest metoda kompresji odwracalny. W takim przypadku możliwe jest całkowite przywrócenie informacji z archiwum. Metody kompresji odwracalnej można zastosować do dowolnego typu danych, ale zapewniają one mniejszą kompresję niż metody kompresji nieodwracalnej. Przykłady formatów kompresji bezstratnej:

· GIF, TIFF – dla danych graficznych;

· AVI – dla danych wideo;

· ZIP, ARJ, RAR, CAB, LH - dla dowolnych typów danych.

Tabela 2 przedstawia popularne formaty kompresji i odpowiadające im programy archiwizujące stosowane w praktyce.

Nowoczesne archiwizatory

Programy specjalne

Wykład 6

Archiwizatory to programy służące do tworzenia archiwów. Archiwa służą do przechowywania danych w wygodnej, kompaktowej formie. Dane to zazwyczaj pliki i foldery. Z reguły dane są najpierw poddawane kompresji lub pakowaniu. Dlatego prawie każdy archiwizator jest także programem do kompresji danych. Z drugiej strony dowolny program do kompresji danych można uznać za archiwizator. Wydajność kompresji jest najważniejsza cecha archiwiści. Rozmiar zależy od tego utworzone archiwa. Im mniejsze archiwum, tym mniej miejsca potrzeba do jego przechowywania. Transmisja wymaga mniejszej przepustowości kanału transmisyjnego lub zajmuje mniej czasu. Zalety archiwów są oczywiste, biorąc pod uwagę, że rozmiar danych jest zmniejszony 2 i 5 razy.

Kompresja danych jest stosowana bardzo szeroko. Można powiedzieć, że niemal wszędzie. Na przykład, Dokumenty PDF z reguły zawierają skompresowane informacje. Sporo plików wykonywalnych Pliki EXE sprasowane specjalnymi pakerami. Rodzajem archiwów są wszelkiego rodzaju pliki multimedialne (GIF, JPG, MP3, MPG).

Główną wadą archiwów jest niemożność dostęp bezpośredni do danych. Należy je najpierw wyodrębnić z archiwum lub rozpakować. Jednak operacja rozpakowywania, podobnie jak pakowania, wymaga pewnych działań zasoby systemowe. To nie jest natychmiastowa operacja. Dlatego też w archiwach wykorzystuje się głównie stosunkowo rzadko wykorzystywane dane. Na przykład do przechowywania kopii zapasowych lub plików instalacyjnych.

W tej chwili jest wielu archiwistów. Różnią się częstością występowania i skutecznością. Niektóre interesujące archiwizatory nie są znane szerokiemu gronu potencjalnych użytkowników. Szczególnie interesująca jest ocena i porównanie wydajności kompresji popularnych archiwizatorów.

Opracowano wiele różnych metod, ich modyfikacji i podtypów kompresji danych. Współcześni archiwiści zwykle korzystają z kilku metod jednocześnie. Możemy wyróżnić kilka podstawowych.

Kodowanie długości przebiegu (RLE – skrót od kodowania długości przebiegu)

Bardzo prosta metoda. Kolejna seria identycznych elementów danych jest zastępowana przez dwa znaki: element i liczbę jego wystąpień. Szeroko stosowany jako dodatek i metoda pośrednia. Jako samodzielna metoda stosowana jest np formacie graficznym BMP.

Metoda słownikowa (LZ – skrót od Lempel Ziv – nazwiska autorów)

Najpopularniejsza metoda. Używany jest słownik składający się z ciągów danych lub słów. Podczas kompresji słowa te są zastępowane ich kodami ze słownika. W najpowszechniejszej implementacji jest to sam słownik oryginalny blok dane.



Głównym parametrem metody słownikowej jest rozmiar słownika. Im większe słownictwo, tym większa skuteczność. Jednak w przypadku danych heterogenicznych jest to nadmierne duży rozmiar może być szkodliwe, ponieważ w przypadku nagłej zmiany typu danych słownik zostanie wypełniony nieistotnymi słowami. Aby ta metoda kompresji działała efektywnie, wymagana jest dodatkowa pamięć. W przybliżeniu o rząd wielkości większy niż jest to potrzebne dla oryginalnych danych słownikowych. Istotną zaletą metody słownikowej jest prosta i szybka procedura rozpakowywania. Nie jest wymagana dodatkowa pamięć. Funkcja ta jest szczególnie istotna, jeśli wymagany jest szybki dostęp do danych.

Metoda entropijna (Huffman – kodowanie Huffmana, Kodowanie arytmetyczne – kodowanie arytmetyczne)

W tej metodzie elementy danych występujące częściej są kodowane podczas kompresji przy użyciu krótszego kodu, a rzadziej występujące elementy danych są kodowane przy użyciu dłuższego kodu. Ze względu na to, że kodów krótkich jest znacznie więcej, całkowity rozmiar okazuje się mniej niż oryginał.

Szeroko stosowany jako metoda dodatkowa. Jako samodzielna metoda stosowana jest np. w formacie graficznym JPG.

Metoda modelowania kontekstowego (CM – skrót od kontekstowego modelowania – modelowanie kontekstowe)

W tej metodzie budowany jest model danych źródłowych. Podczas kompresji kolejnego elementu danych model ten generuje jego przewidywanie lub prawdopodobieństwo. Zgodnie z tym prawdopodobieństwem element danych jest kodowany metodą entropii. Jak dokładniej model będzie pasował do oryginalnych danych, tym dokładniejsze będą prognozy i tym krótsze będą kodowane elementy danych.

Budowa wydajnego modelu wymaga dużej ilości pamięci. Podczas rozpakowywania trzeba zbudować dokładnie ten sam model. Dlatego wymagania dotyczące prędkości i głośności pamięć o dostępie swobodnym do pakowania i rozpakowywania są prawie takie same. W tej chwili metody modelowania kontekstowego pozwalają nam uzyskać najlepszy stopień kompresji, ale mają wyjątkowo niską prędkość.

PPM (PPM – przewidywanie przez częściowe dopasowanie)

Jest to specjalny podtyp modelowania kontekstowego. Prognozy dokonywane są na podstawie pewna ilość poprzednie elementy danych. Głównym parametrem jest kolejność modelu, która określa tę liczbę elementów. Im wyższy porządek modelu, tym wyższy współczynnik kompresji, ale do przechowywania danych modelu potrzeba więcej pamięci RAM. Jeśli nie ma wystarczającej ilości pamięci RAM, wówczas taki model przy dużym zamówieniu wykazuje słabe wyniki. Metoda PPM jest szczególnie skuteczna w przypadku kompresji danych tekstowych.

Transformacje wstępne lub filtrowanie

Metody te nie służą do kompresji, ale do przedstawienia informacji w formie dogodnej do dalszej kompresji. Na przykład nieskompresowane dane multimedialne charakteryzują się płynne zmiany poziom sygnału. Dlatego stosuje się dla nich transformację delta, gdy zamiast wartości bezwzględnej przyjmuje się wartość względną. Istnieją filtry do tekstu, pliki wykonywalne, bazy danych i inne.

Metoda sortowania blokowego (BWT – skrót od Burrows Wheeler Transform – według nazwisk autorów)

Jest to specjalny typ lub grupa przekształceń bazujących na sortowaniu. Transformacji tej można poddać niemal każde dane. Sortowanie odbywa się po blokach, więc dane są najpierw dzielone na części. Głównym parametrem jest rozmiar sortowanego bloku. Aby rozpakować dane, musisz wykonać prawie te same kroki, co przy pakowaniu. Dlatego wymagania dotyczące szybkości i pamięci RAM są prawie takie same. Archiwcy, którzy korzystają Ta metoda, zwykle wykazują dużą prędkość i współczynnik kompresji danych tekstowych.

Ciągłe bloki lub tryb ciągły (tryb ciągły - tryb ciągły)

W przypadku wielu metod kompresji początkowa część danych lub pliku jest słabo zakodowana. Na przykład w metodzie słownikowej słownik jest pusty. W metodzie modelowania kontekstowego model nie jest budowany. Gdy liczba plików jest duża, a ich rozmiar mały, ogólny współczynnik kompresji ulega znacznemu pogorszeniu z powodu tych początkowych sekcji. Aby temu zapobiec podczas przełączania na następny plik, informacje uzyskane na podstawie poprzednie pliki. Podobny efekt można osiągnąć prosta prezentacja pliki źródłowe jako jeden ciągły plik.

Ta metoda jest stosowana w wielu archiwizatorach i ma istotna wada. Aby rozpakować dowolny plik, należy rozpakować także pliki znajdujące się na początku archiwum. Jest to konieczne do prawidłowego wypełnienia słownika lub zbudowania modelu. Istnieje również opcja pośrednia, gdy stosowane są ciągłe bloki o stałym rozmiarze. Straty przy kompresji są minimalne, ale wystarczy wyodrębnić jeden plik, który jest na końcu duże archiwum, należy rozpakować tylko jeden ciągły blok, a nie całe archiwum.

Segmentacja

We wszystkich metodach kompresji przy zmianie typu danych samo przejście jest kodowane bardzo słabo. Słownik staje się nieistotny, model jest skonfigurowany na inne dane. W takich przypadkach stosuje się segmentację. Jest to wstępny podział na jednorodne części. Części te są następnie kodowane indywidualnie lub w grupach.