bzip2 (Polski)

Bzip2 wykorzystuje kilka warstw technik kompresji ułożonych jedna na drugiej, które występują w następującej kolejności podczas kompresji i odwrotnej kolejności podczas dekompresji:

1. Kodowanie run-length (RLE) początkowych danych.
2. Transformacja Burrowsa-Wheelera (BWT) lub sortowanie blokowe.
3. Transformacja Move-to-front (MTF).
4. Kodowanie długości przebiegu (RLE) wyniku MTF.
5. Kodowanie Huffmana.
6. Wybór między wieloma tabelami Huffmana.
7. Jednoargumentowe kodowanie base-1 wyboru tabeli Huffmana.
8. Kodowanie delta (Δ) długości bitów kodu Huffmana.
9. Rzadka tablica bitowa pokazująca, które symbole są używane.

Początkowe kodowanie długości seriiEdytuj

Dowolna sekwencja od 4 do 255 kolejnych zduplikowanych symboli jest zastępowana przez pierwsze 4 symbole i długość powtórzenia od 0 do 251. Zatem sekwencja AAAAAAABBBBCCCD jest zastępowane przez AAAA\3BBBB\0CCCD, gdzie \3 i \0 reprezentują odpowiednio wartości bajtów 3 i 0. Sekwencje symboli są zawsze przekształcane po 4 kolejnych symbolach, nawet jeśli długość biegu jest ustawiona na zero, aby zachować odwracalność transformacji.

W najgorszym przypadku może spowodować rozszerzenie o 1,25, aw w najlepszym przypadku redukcja do < 0,02. Chociaż specyfikacja teoretycznie pozwala na zakodowanie ciągów o długości 256–259, koder odniesienia nie wygeneruje takiego wyjścia.

Autor bzip2 stwierdził, że krok RLE był historycznym błędem i był przeznaczony tylko aby chronić oryginalną implementację BWT przed patologicznymi przypadkami.

Burrows-Wheeler transformEdit

To jest odwracalne sortowanie blokowe, które jest podstawą bzip2. Blok jest całkowicie samowystarczalny, a bufory wejściowe i wyjściowe pozostają tej samej wielkości – w bzip2 limit operacyjny dla tego stopnia wynosi 900 kB. Dla sortowania blokowego tworzona jest (pojęciowa) macierz, w której wiersz i zawiera cały bufor, obróconą, aby rozpocząć od i-tego symbolu. Po obróceniu wiersze macierzy są sortowane w kolejności alfabetycznej (numerycznej). Przechowywany jest 24-bitowy wskaźnik oznaczający pozycję początkową, gdy blok nie jest transformowany. W praktyce nie jest konieczne tworzenie pełnej macierzy; raczej sortowanie jest wykonywane przy użyciu wskaźników dla każdej pozycji w buforze. Bufor wyjściowy to ostatnia kolumna macierzy; zawiera cały bufor, ale uporządkowany tak, że prawdopodobnie będzie zawierał duże serie identycznych symboli.

Transformacja Move-to-frontEdit

Ponownie, ta transformacja nie zmienia rozmiaru przetwarzanego bloku. Każdy z symboli używanych w dokumencie jest umieszczony w tablicy. Kiedy symbol jest przetwarzany, jest zastępowany przez swoją lokalizację (indeks) w tablicy i ten symbol jest tasowany na początek tablicy. Efekt jest taki, że natychmiastowo powtarzające się symbole są zastępowane symbolami zerowymi (długie ciągi dowolnego dowolnego symbolu stają się w ten sposób ciągami symboli zerowych), podczas gdy inne symbole są odwzorowywane zgodnie z ich lokalną częstotliwością.

Wiele „naturalnych” danych zawiera identyczne symbole, które powtarzają się w ograniczonym zakresie (dobrym przykładem jest tekst). Ponieważ transformacja MTF przypisuje niskie wartości symbolom, które często pojawiają się ponownie, powoduje to strumień danych zawierający wiele symboli w dolnym zakresie liczb całkowitych, z których wiele jest identycznych (różne powtarzające się symbole wejściowe mogą faktycznie mapować na ten sam symbol wyjściowy). Takie dane mogą być bardzo wydajnie zakodowane za pomocą dowolnej starszej metody kompresji.

Kodowanie długości przebiegu MTF resultEdit

Długie ciągi zer na wyjściu transformacji move to front ( które pochodzą z powtarzających się symboli na wyjściu BWT) są zastępowane sekwencją dwóch specjalnych kodów, RUNA i RUNB, które przedstawiają długość przebiegu jako liczbę binarną. Rzeczywiste zera nigdy nie są kodowane na wyjściu; samotne zero staje się RUNĄ. (Ten krok jest faktycznie wykonywany w tym samym czasie co MTF; kiedykolwiek MTF generuje zero, zamiast tego zwiększa licznik, aby następnie zakodować za pomocą RUNA i RUNB.)

Sekwencja 0, 0, 0, 0, 0, 1 byłby reprezentowany jako RUNA, RUNB, 1; RUNA, RUNB reprezentuje wartość 5, jak opisano poniżej. Kod długości przebiegu kończy się osiągnięciem innego normalnego symbolu. Ten proces RLE jest bardziej elastyczny niż początkowy krok RLE, ponieważ jest w stanie zakodować dowolnie długie liczby całkowite (w praktyce jest to zwykle ograniczone rozmiarem bloku, więc ten krok nie koduje serii większej niż 900000 bajtów). Długość przebiegu jest kodowana w następujący sposób: przypisując wartości pozycji 1 do pierwszego bitu, 2 do drugiego, 4 do trzeciego itd. W sekwencji, pomnóż każdą wartość miejsca w miejscu RUNB przez 2 i dodaj wszystkie wynikowe wartości miejsc (zarówno dla wartości RUNA, jak i RUNB) razem. Jest to podobne do numeracji bijektywnej o podstawie 2.Zatem sekwencja RUNA, RUNB daje w wyniku wartość (1 + 2 × 2) = 5. Jako bardziej skomplikowany przykład:

RUNA RUNB RUNA RUNA RUNB (ABAAB) 1 2 4 8 16 1 4 4 8 32 = 49

Huffman codingEdit

Ten proces zastępuje symbole o stałej długości z zakresu 0–258 kodami o zmiennej długości w oparciu o częstotliwość ich używania. Częściej używane kody są krótsze (2–3 bity), podczas gdy rzadkie kody mogą mieć maksymalnie 20 bitów. Kody są starannie dobierane, aby żadna sekwencja bitów nie mogła być pomylona z innym kodem.

Szczególnie interesujący jest kod końca strumienia. Jeśli w nieskompresowanych danych jest n różnych bajtów (symboli), kod Huffmana będzie składał się z dwóch kodów RLE (RUNA i RUNB), n – 1 kodów symboli i jednego kodu końca strumienia. Z powodu połączonego wyniku kodowania MTF i RLE w poprzednich dwóch krokach, nigdy nie ma potrzeby jawnego odwoływania się do pierwszego symbolu w tabeli MTF (w zwykłej MTF byłoby zero), zapisując w ten sposób jeden symbol na koniec. znacznik strumienia (i wyjaśniający, dlaczego tylko n – 1 symboli jest zakodowanych w drzewie Huffmana). W skrajnym przypadku, gdy w nieskompresowanych danych używany jest tylko jeden symbol, w drzewie Huffmana nie będzie żadnych kodów symboli, a cały blok będzie składał się z RUNA i RUNB (niejawnie powtarzającego pojedynczy bajt) oraz końca – znacznik strumienia o wartości 2.

0: RUNA, 1: RUNB, 2–257: wartości bajtów 0–255, 258: koniec strumienia, zakończenie przetwarzania (może wynosić zaledwie 2).

Wiele tabel HuffmanaEdytuj

Kilka tabel Huffmana o identycznej wielkości może być używanych z blokiem, jeśli zysk z ich używania jest większy niż koszt włączenia dodatkowej tabeli. Mogą być obecne co najmniej 2 i do 6 tabel, przy czym najbardziej odpowiednia tabela jest wybierana ponownie przed każdymi 50 przetwarzanymi symbolami. Ma to tę zaletę, że ma bardzo responsywną dynamikę Huffmana bez konieczności ciągłego dostarczania nowych tabel, jak byłoby to wymagane w DEFLATE. Kodowanie run-length w poprzednim kroku zostało zaprojektowane tak, aby zadbać o kody, których odwrotne prawdopodobieństwo użycia jest wyższe niż najkrótszy używany kod Huffmana.

Jednoargumentowe kodowanie wyboru tabeli HuffmanaEdit

Jeśli używanych jest wiele tablic Huffmana, wybór każdej tabeli (ponumerowanej od 0 do 5) jest dokonywany z listy przez ciąg bitów zakończony zerem o długości od 1 do 6 bitów. Wybór następuje na liście tabel MTF. Korzystanie z tej funkcji skutkuje maksymalnym rozszerzeniem o około 1,015, ale generalnie mniej. To rozszerzenie może być znacznie przesłonięte zaletą wyboru bardziej odpowiednich tabel Huffmana, a typowy przypadek dalszego używania tej samej tabeli Huffmana jest reprezentowany jako pojedynczy bit. Zamiast kodowania jednoargumentowego, w rzeczywistości jest to skrajna forma drzewa Huffmana, w której każdy kod ma połowę prawdopodobieństwa poprzedniego kodu.

Kodowanie deltaEdytuj

Długość bitów kodu Huffmana jest wymagane do zrekonstruowania każdej z używanych kanonicznych tablic Huffmana. Każda długość bitu jest przechowywana jako zakodowana różnica w stosunku do długości bitu poprzedniego kodu. Bit zerowy (0) oznacza, że poprzednia długość bitu powinna zostać zduplikowana dla bieżącego kodu, podczas gdy jeden bit (1) oznacza, że należy odczytać kolejny bit i zwiększyć lub zmniejszyć długość bitu w oparciu o tę wartość.

W typowym przypadku pojedynczy bit jest używany na symbol w tabeli, a najgorszy przypadek – przejście od długości 1 do długości 20 – wymagałoby około 37 bitów. W wyniku wcześniejszego kodowania MTF długości kodu zaczynałyby się od 2–3 bitów (bardzo często używane kody) i stopniowo rosły, co oznacza, że format delta jest dość wydajny, wymagając około 300 bitów (38 bajtów) na pełną tablicę Huffmana .

Sparse bit arrayEdit

Bitmapa jest używana do pokazania, które symbole są używane wewnątrz bloku i powinny być zawarte w drzewach Huffmana. Dane binarne prawdopodobnie wykorzystują wszystkie 256 symboli reprezentowanych przez bajt, podczas gdy dane tekstowe mogą wykorzystywać tylko niewielki podzbiór dostępnych wartości, być może obejmując zakres ASCII między 32 a 126. Przechowywanie 256 bitów zerowych byłoby nieefektywne, gdyby były one w większości nieużywane. Stosowana jest metoda rzadka: 256 symboli jest podzielonych na 16 zakresów i tylko wtedy, gdy symbole są używane w tym bloku, zawiera 16-bitową tablicę. Obecność każdego z tych 16 zakresów jest wskazywana przez dodatkową 16-bitową tablicę z przodu.

Całkowita mapa bitowa zajmuje od 32 do 272 bitów pamięci (4-34 bajty). Dla kontrastu, algorytm DEFLATE pokazałby brak symboli przez zakodowanie symboli jako mające zerową długość bitową z kodowaniem run-length i dodatkowym kodowaniem Huffmana.