bzip2 - bzip2

„Bzip” przekierowuje tutaj. Dla domeny białkowej, patrz domena bZIP .

bzip2
Bzip2-logo.svg
Pierwotny autor (autorzy) Julian Seward
Deweloper(zy) Mark Wielaard, Federico Mena , Micah Snyder
Pierwsze wydanie 18 lipca 1996 ; 25 lat temu ( 18.07.1996 )
Wersja stabilna
1.0.8 / 13 lipca 2019 ; 2 lata temu ( 2019-07-13 )
Magazyn 1.0: https://sourceware.org/git/bzip2.git
1.1+: https://gitlab.com/bzip2/bzip2/
System operacyjny Wieloplatformowy
Rodzaj Kompresja danych
Licencja Licencja podobna do BSD
Strona internetowa oprogramowanie źródłowe .org /bzip2 /
bzip2
Rozszerzenie nazwy pliku
.bz2
Rodzaj mediów internetowych
application/x-bzip2
Kod typu Bzp2
Jednolity identyfikator typu (UTI) publiczne.archiwum.bzip2
magiczny numer BZh
Opracowany przez Julian Seward
Rodzaj formatu Kompresja danych
Otwarty format ? tak

bzip2 to darmowy program do kompresji plików o otwartym kodzie źródłowym , który wykorzystuje algorytm Burrows-Wheeler . Kompresuje tylko pojedyncze pliki i nie jest archiwizatorem plików . Został opracowany przez Juliana Sewarda i utrzymywany przez Marka Wielaarda i Micaha Snydera.

Historia

Seward dokonał pierwszego publicznego wydania bzip2 w wersji 0.15 w lipcu 1996 roku. Stabilność i popularność kompresora rosły w ciągu następnych kilku lat, a Seward wydał wersję 1.0 pod koniec 2000 roku. Po dziewięcioletniej przerwie w aktualizowaniu projektu od 2010 roku , 4 czerwca 2019 r. Federico Mena zaakceptował opiekę nad projektem bzip2. Od czerwca 2021 opiekunem jest Micah Snyder.

Realizacja

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) danych początkowych.
  2. Transformacja Burrowsa-Wheelera (BWT) lub sortowanie blokowe.
  3. Przejście na przód (MTF).
  4. Kodowanie run-length (RLE) wyniku MTF.
  5. Kodowanie Huffmana .
  6. Wybór między wieloma stołami Huffmana.
  7. Jednoargumentowe kodowanie base-1 wyboru tabeli Huffmana.
  8. Kodowanie delta (Δ) długości bitów kodu Huffmana.
  9. Rozrzedzona tablica bitowa pokazująca, które symbole są używane.

Dowolna sekwencja od 4 do 255 kolejnych zduplikowanych symboli jest zastępowana przez pierwsze 4 symbole i powtórzenie o długości od 0 do 251. Zatem sekwencja AAAAAAABBBBCCCDjest zastępowana przez AAAA\3BBBB\0CCCD, gdzie \3i \0reprezentują odpowiednio wartości bajtów 3 i 0. Ciągi symboli są zawsze transformowane po 4 kolejnych symbolach, nawet jeśli długość ciągu jest ustawiona na zero, aby transformacja była odwracalna.

W najgorszym przypadku może to spowodować ekspansję o 1,25, a w najlepszym redukcję do <0,02. Podczas gdy specyfikacja teoretycznie pozwala na kodowanie przebiegów o długości 256–259, enkoder referencyjny nie wygeneruje takiego wyjścia.

Autor bzip2 stwierdził, że krok RLE był historycznym błędem i miał na celu jedynie ochronę oryginalnej implementacji BWT przed przypadkami patologicznymi.

Transformacja Burrowsa-Wheelera to odwracalne sortowanie blokowe, które jest rdzeniem bzip2. Blok jest całkowicie samowystarczalny, z buforami wejściowymi i wyjściowymi o tej samej wielkości — w bzip2 limit operacyjny dla tego etapu wynosi 900 kB. W przypadku sortowania blokowego tworzona jest (pojęciowa) macierz, w której wiersz i zawiera cały bufor, obrócony tak, aby zaczynał się od i-tego symbolu. Po rotacji wiersze macierzy są sortowane w kolejności alfabetycznej (numerycznej). Przechowywany jest 24-bitowy wskaźnik oznaczający pozycję początkową, gdy blok jest nieprzekształcony. W praktyce nie jest konieczne konstruowanie pełnej macierzy; sortowanie odbywa się raczej za pomocą wskaźników dla każdej pozycji w buforze. Bufor wyjściowy to ostatnia kolumna macierzy; zawiera on cały bufor, ale jest tak uporządkowany, że prawdopodobnie zawiera duże serie identycznych symboli.

Przekształcenie przejścia na przód ponownie nie zmienia rozmiaru przetwarzanego bloku. Każdy z symboli używanych w dokumencie jest umieszczany w tablicy. Kiedy symbol jest przetwarzany, jest zastępowany przez jego lokalizację (indeks) w tablicy i ten symbol jest tasowany na początek tablicy. Efektem jest to, że bezpośrednio powtarzających się znaków są zastępowane przez zera symboli (długie ciągi jakiegokolwiek dowolnego symbolu tak stać przebiegi zera symboli), a inne symbole są odwzorowane według lokalnej 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 do symboli, które często pojawiają się ponownie, w wyniku tego strumień danych zawiera wiele symboli w niskim zakresie liczb całkowitych, z których wiele jest identycznych (różne powtarzające się symbole wejściowe mogą w rzeczywistości mapować na ten sam symbol wyjściowy). Takie dane można bardzo wydajnie zakodować dowolną starszą metodą kompresji.

Długie ciągi zer na wyjściu transformacji przejścia do przodu (pochodzące z powtarzających się symboli na wyjściu BWT) są zastępowane sekwencją dwóch specjalnych kodów, RUNA i RUNB, które reprezentują długość przebiegu jako Liczba binarna. Rzeczywiste zera nigdy nie są kodowane w danych wyjściowych; samotne zero staje się RUNA. (W rzeczywistości ten krok jest wykonywany w tym samym czasie, co MTF; ilekroć MTF wygeneruje zero, zamiast tego zwiększa licznik, aby następnie zakodować za pomocą RUNA i RUNB.)

Sekwencja 0, 0, 0, 0, 0, 1byłaby reprezentowana jako RUNA, RUNB, 1; RUNA, RUNBreprezentuje 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ż900 000  bajtów ). Długość przebiegu jest zakodowana w ten sposób: przypisując wartości miejsca 1 pierwszemu bitowi, 2 drugiemu, 4 trzeciemu itd. w sekwencji pomnóż każdą wartość miejsca w miejscu RUNB przez 2 i dodaj wszystkie wynikowe wartości miejsca (zarówno dla wartości RUNA, jak i RUNB) razem. Jest to podobne do bijektywnej numeracji o podstawie 2 . Tak więc sekwencja RUNA, RUNBdaje 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

Ten proces zastępuje symbole o stałej długości w zakresie 0–258 kodami o zmiennej długości w oparciu o częstotliwość używania. Częściej używane kody są krótsze (2–3 bity), podczas gdy rzadkie kody mogą mieć do 20 bitów. Kody są starannie dobierane, aby nie można było pomylić sekwencji bitów 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. Ze względu na połączony wynik kodowania MTF i RLE w poprzednich dwóch krokach, nigdy nie ma potrzeby jawnego odwoływania się do pierwszego symbolu w tabeli MTF (byłoby to zero w zwykłym MTF), oszczędzają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 (domyślnie powtarzających się 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).

Kilka stołów Huffmana o identycznych rozmiarach może być używanych z blokiem, jeśli zysk z ich używania jest większy niż koszt włączenia dodatkowego stołu. Mogą być obecne co najmniej 2 do 6 tabel, przy czym najodpowiedniejsza tabela jest ponownie wybierana przed każdym przetworzeniem 50 symboli. Ma to tę zaletę, że ma bardzo responsywną dynamikę Huffmana bez konieczności ciągłego dostarczania nowych stołów, co byłoby wymagane w DEFLATE . Kodowanie run-length w poprzednim kroku ma na celu zadbanie o kody, które mają odwrotne prawdopodobieństwo użycia wyższe niż najkrótszy kod Huffmana w użyciu.

Jeśli używanych jest wiele tabel Huffmana, wybór każdej tabeli (ponumerowanej od 0 do 5) jest dokonywany z listy bitem zakończonym zerem o długości od 1 do 6 bitów. Wybór odbywa się na liście tabel MTF . Korzystanie z tej funkcji skutkuje maksymalnym rozszerzeniem o około 1,015, ale generalnie mniej. Ta ekspansja prawdopodobnie zostanie znacznie przyćmiona przez zaletę wyboru bardziej odpowiednich tabel Huffmana, a częsty przypadek dalszego korzystania z tej samej tabeli Huffmana jest reprezentowany jako pojedynczy bit. Zamiast kodowania jednoargumentowego jest to w rzeczywistości ekstremalna forma drzewa Huffmana, w którym każdy kod ma połowę prawdopodobieństwa poprzedniego kodu.

Długość bitów kodu Huffmana jest wymagana do rekonstrukcji każdej z używanych kanonicznych tabel 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 na podstawie tej wartości. W powszechnym przypadku jeden bit jest używany na symbol w tabeli, a najgorszy przypadek — od długości 1 do długości 20 — wymagałby około 37 bitów. W wyniku wcześniejszego kodowania MTF długość kodu zaczynała się od 2–3 bitów (bardzo często używane kody) i stopniowo wzrastała, co oznacza, że ​​format delta jest dość wydajny, wymagając około 300 bitów (38 bajtów) na pełną tabelę Huffmana .

Mapa bitowa służy do pokazania, które symbole są używane w bloku i powinny być uwzględnione 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ący zakres ASCII od 32 do 126. Przechowywanie 256 bitów zerowych byłoby nieefektywne, gdyby były 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 bitmapa zajmuje od 32 do 272 bitów pamięci (4–34 bajty). Dla kontrastu, algorytm DEFLATE wykazałby brak symboli przez zakodowanie symboli jako mających zerową długość bitową z kodowaniem długości serii i dodatkowym kodowaniem Huffmana.

Format pliku

Nie istnieje żadna formalna specyfikacja dla bzip2, chociaż nieformalna specyfikacja została odtworzona z implementacji referencyjnej.

Ogólnie rzecz biorąc, .bz2strumień składa się z 4-bajtowego nagłówka, po którym następuje zero lub więcej skompresowanych bloków, po których bezpośrednio następuje znacznik końca strumienia zawierający 32-bitowe CRC dla całego przetworzonego strumienia w postaci zwykłego tekstu. Skompresowane bloki są wyrównane bitowo i nie występuje dopełnienie. 

.magic:16                       = 'BZ' signature/magic number
.version:8                      = 'h' for Bzip2 ('H'uffman coding), '0' for Bzip1 (deprecated)
.hundred_k_blocksize:8          = '1'..'9' block-size 100 kB-900 kB (uncompressed)

.compressed_magic:48            = 0x314159265359 (BCD (pi))
.crc:32                         = checksum for this block
.randomised:1                   = 0=>normal, 1=>randomised (deprecated)
.origPtr:24                     = starting pointer into BWT for after untransform
.huffman_used_map:16            = bitmap, of ranges of 16 bytes, present/not present
.huffman_used_bitmaps:0..256    = bitmap, of symbols used, present/not present (multiples of 16)
.huffman_groups:3               = 2..6 number of different Huffman tables in use
.selectors_used:15              = number of times that the Huffman tables are swapped (each 50 symbols)
*.selector_list:1..6            = zero-terminated bit runs (0..62) of MTF'ed Huffman table (*selectors_used)
.start_huffman_length:5         = 0..20 starting bit length for Huffman deltas
*.delta_bit_length:1..40        = 0=>next symbol; 1=>alter length
                                                { 1=>decrement length;  0=>increment length } (*(symbols+2)*groups)
.contents:2..∞                  = Huffman encoded data stream until end of block (max. 7372800 bit)

.eos_magic:48                   = 0x177245385090 (BCD sqrt(pi))
.crc:32                         = checksum for whole stream
.padding:0..7                   = align to whole byte

Ze względu na kompresję RLE pierwszego stopnia (patrz wyżej), maksymalna długość tekstu jawnego, jaką może zawierać pojedynczy blok bzip2 o wielkości 900 kB, wynosi około 46 MB (45 899 236 bajtów). Może się tak zdarzyć, jeśli cały tekst jawny składa się wyłącznie z powtarzających się wartości ( .bz2plik wynikowy w tym przypadku ma długość 46 bajtów). Jeszcze mniejszy plik o wielkości 40 bajtów można uzyskać, używając danych wejściowych zawierających wyłącznie wartości 251, pozorny współczynnik kompresji 1147480.9:1.

Skompresowane bloki w bzip2 mogą być dekompresowane niezależnie, bez konieczności przetwarzania wcześniejszych bloków. Oznacza to, że pliki bzip2 mogą być dekompresowane równolegle, co czyni go dobrym formatem do użycia w aplikacjach big data z frameworkami obliczeniowymi klastrów, takimi jak Hadoop i Apache Spark .

Efektywność

bzip2 kompresuje większość plików skuteczniej niż starsze algorytmy kompresji LZW ( .Z ) i Deflate ( .zip i .gz ), ale jest znacznie wolniejszy. LZMA jest generalnie bardziej oszczędny niż bzip2 kosztem jeszcze wolniejszej kompresji przy znacznie szybszej dekompresji.

bzip2 kompresuje dane w blokach o rozmiarze od 100 do 900 kB i używa transformacji Burrowsa-Wheelera do konwersji często powtarzających się sekwencji znaków na ciągi identycznych liter. Następnie stosuje transformację typu move-to-front i kodowanie Huffmana . Przodek bzip2, bzip, używał kodowania arytmetycznego zamiast Huffmana. Zmiana została dokonana z powodu ograniczenia patentu na oprogramowanie .

Wydajność bzip2 jest asymetryczna, ponieważ dekompresja jest stosunkowo szybka. Motywowana dużym czasem procesora wymaganym do kompresji, w 2003 roku stworzono zmodyfikowaną wersję o nazwie pbzip2, która wspierała wielowątkowość , dając niemal liniową poprawę szybkości na komputerach wieloprocesorowych i wielordzeniowych. Od maja 2010 ta funkcjonalność nie została włączona do głównego projektu.

Podobnie jak gzip, bzip2 jest tylko kompresorem danych. Nie jest to archiwizator, taki jak tar lub ZIP; sam program nie ma możliwości obsługi wielu plików, szyfrowania lub dzielenia archiwów, ale zgodnie z tradycją UNIX , do tych zadań opiera się na oddzielnych zewnętrznych narzędziach, takich jak tar i GnuPG .

grep-Na bzgrepnarzędzie pozwala bezpośrednio przeszukując sprężonego tekstu bez konieczności rozpakować zawartość pierwszego.

Zobacz też

Bibliografia

Zewnętrzne linki