Algorytm łańcucha Lempel-Ziv-Markov - Lempel–Ziv–Markov chain algorithm

Lzma ( LZMA ) to algorytm stosowany do wykonywania kompresji bezstratnej . Jest rozwijany od 1996 lub 1998 roku przez Igora Pavlova i po raz pierwszy został użyty w formacie 7z archiwizatora 7-Zip . Algorytm ten wykorzystuje schemat kompresji słownika nieco podobny do algorytmu LZ77 opublikowanego przez Abrahama Lempela i Jacoba Ziva w 1977 roku i charakteryzuje się wysokim współczynnikiem kompresji (zwykle wyższym niż bzip2 ) oraz zmiennym rozmiarem słownika kompresji (do 4 GB ), a jednocześnie utrzymywanie szybkości dekompresji zbliżonej do innych powszechnie stosowanych algorytmów kompresji.

LZMA2 to prosty format kontenera, który może zawierać zarówno nieskompresowane dane, jak i dane LZMA, prawdopodobnie z wieloma różnymi parametrami kodowania LZMA. LZMA2 obsługuje dowolnie skalowalną wielowątkową kompresję i dekompresję oraz wydajną kompresję danych, które są częściowo nieskompresowalne. Uważa się jednak, że jest niebezpieczny i mniej wydajny niż LZMA.

Przegląd

LZMA wykorzystuje algorytm kompresji słownika (wariant LZ77 z ogromnymi rozmiarami słowników i specjalną obsługą wielokrotnie używanych odległości dopasowania), którego dane wyjściowe są następnie kodowane za pomocą kodera zakresu , przy użyciu złożonego modelu do przewidywania prawdopodobieństwa każdego bitu. Możliwe są liczne kodowania i A: Słownik znaleziska kompresor mecze wykorzystaniem zaawansowanego słownika struktur danych i wytwarza strumień dosłownych symboli i odniesień frazę, która jest kodowana jeden bit na raz przez koder zakresu programowania dynamiczny algorytm służy do wybrania optymalny pod pewnymi przybliżeniami.

Przed LZMA większość modeli koderów była oparta wyłącznie na bajtach (tj. kodowały każdy bit przy użyciu tylko kaskady kontekstów do reprezentowania zależności od poprzednich bitów z tego samego bajtu). Główną innowacją LZMA jest to, że zamiast ogólnego modelu opartego na bajtach, model LZMA wykorzystuje konteksty specyficzne dla pól bitowych w każdej reprezentacji literału lub frazy: jest to prawie tak proste, jak ogólny model oparty na bajtach, ale daje znacznie lepsze kompresja, ponieważ pozwala uniknąć mieszania niepowiązanych ze sobą bitów w tym samym kontekście. Co więcej, w porównaniu z klasyczną kompresją słownika (taką jak ta używana w formatach zip i gzip ), rozmiary słowników mogą być i zwykle są znacznie większe, wykorzystując dużą ilość pamięci dostępnej w nowoczesnych systemach.

Przegląd formatu skompresowanego

W kompresji LZMA skompresowany strumień jest strumieniem bitów zakodowanych przy użyciu adaptacyjnego kodera zakresu binarnego. Strumień jest podzielony na pakiety, przy czym każdy pakiet opisuje albo pojedynczy bajt, albo sekwencję LZ77 z jej długością i odległością zakodowaną w sposób niejawny lub jawny. Każda część każdego pakietu jest modelowana z niezależnymi kontekstami, więc przewidywania prawdopodobieństwa dla każdego bitu są skorelowane z wartościami tego bitu (i powiązanych bitów z tego samego pola) w poprzednich pakietach tego samego typu. Zarówno dokumentacja lzip, jak i LZMA SDK opisują ten format strumienia.

Istnieje 7 rodzajów pakietów:

Kod spakowany (sekwencja bitowa)	Nazwa pakietu	Opis pakietu
0 + kod bajtowy	OŚWIETLONY	Pojedynczy bajt zakodowany przy użyciu adaptacyjnego kodera zakresu binarnego.
1+0 + dł. + odległość	MECZ	Typowa sekwencja LZ77 opisująca długość i odległość sekwencji.
1+1+0+0	SKRÓT	Jednobajtowa sekwencja LZ77. Odległość jest równa ostatnio używanej odległości LZ77.
1+1+0+1 + len	LONGREP[0]	Sekwencja LZ77. Odległość jest równa ostatnio używanej odległości LZ77.
1+1+1+0 + len	LONGREP[1]	Sekwencja LZ77. Odległość jest równa przedostatniej używanej odległości LZ77.
1+1+1+1+0 + len	LONGREP[2]	Sekwencja LZ77. Odległość jest równa trzeciej ostatnio używanej odległości LZ77.
1+1+1+1+1 + len	LONGREP[3]	Sekwencja LZ77. Odległość jest równa czwartej ostatnio używanej odległości LZ77.

LONGREP[*] odnosi się do pakietów LONGREP[0-3], *REP odnosi się zarówno do LONGREP, jak i SHORTREP, a *MATCH do MATCH i *REP.

Pakiety LONGREP[n] usuwają użytą odległość z listy ostatnich odległości i wstawiają ją ponownie na początku, aby uniknąć niepotrzebnego wielokrotnego wprowadzania, podczas gdy MATCH po prostu dodaje odległość na początek, nawet jeśli jest już obecna na liście, a SHORTREP i LONGREP [0] nie zmieniaj listy.

Długość jest zakodowana w następujący sposób:

Kod długości (sekwencja bitów)	Opis
0+ 3 bity	Długość zakodowana przy użyciu 3 bitów daje zakres długości od 2 do 9.
1+0+ 3 bity	Długość zakodowana przy użyciu 3 bitów daje zakres długości od 10 do 17.
1+1+ 8 bitów	Długość zakodowana przy użyciu 8 bitów daje zakres długości od 18 do 273.

Podobnie jak w LZ77, długość nie jest ograniczona odległością, ponieważ kopiowanie ze słownika jest definiowane tak, jakby kopiowanie odbywało się bajt po bajcie, zachowując stałą odległość.

Odległości są logicznie 32-bitowe, a odległość 0 wskazuje na ostatnio dodany bajt w słowniku.

Kodowanie odległości rozpoczyna się od 6-bitowego „slotu odległości”, który określa, ile dodatkowych bitów jest potrzebnych. Odległości są dekodowane jako binarna konkatenacja, od najbardziej do najmniej znaczącej, dwóch bitów w zależności od szczeliny odległości, niektórych bitów zakodowanych ze stałym prawdopodobieństwem 0,5 i niektórych bitów zakodowanych kontekstowo, zgodnie z poniższą tabelą (odległości 0–3 są kodowane bezpośrednio odległości 0-3).

6-bitowe gniazdo odległości	Najwyższe 2 bity	Naprawiono bity prawdopodobieństwa 0,5	Bity zakodowane w kontekście
0	00	0	0
1	01	0	0
2	10	0	0
3	11	0	0
4	10	0	1
5	11	0	1
6	10	0	2
7	11	0	2
8	10	0	3
9	11	0	3
10	10	0	4
11	11	0	4
12	10	0	5
13	11	0	5
14-62 (parzysty)	10	((gniazdo / 2) - 5)	4
15-63 (nieparzyste)	11	(((szczelina − 1) / 2) − 5)	4

Szczegóły algorytmu dekompresji

Wydaje się, że nie istnieje kompletna specyfikacja skompresowanego formatu języka naturalnego, poza tą, o której mowa w poniższym tekście.

Poniższy opis opiera się na kompaktowym dekoderze XZ Embedded autorstwa Lasse Collina zawartym w źródle jądra Linux, z którego można stosunkowo łatwo wywnioskować szczegóły algorytmów LZMA i LZMA2: dlatego chociaż cytowanie kodu źródłowego jako odniesienia nie jest idealne, każdy programista powinien być w stanie sprawdzić poniższe roszczenia po kilku godzinach pracy.

Kodowanie zakresu bitów

Dane LZMA są dekodowane na najniższym poziomie po jednym bicie przez dekoder odległości w kierunku dekodera LZMA.

Dekodowanie zakresu w oparciu o kontekst jest wywoływane przez algorytm LZMA przekazujący mu odniesienie do „kontekstu”, który składa się z 11-bitowej zmiennej prob bez znaku (zazwyczaj realizowanej przy użyciu 16-bitowego typu danych) reprezentującej przewidywane prawdopodobieństwo, że bit jest 0, które jest odczytywane i aktualizowane przez dekoder zakresu (i powinno być inicjowane na 2^10, co odpowiada prawdopodobieństwu 0,5).

Zamiast tego dekodowanie z ustalonym zakresem prawdopodobieństwa zakłada prawdopodobieństwo 0,5, ale działa nieco inaczej niż dekodowanie zakresu opartego na kontekście.

Stan dekodera zakresu składa się z dwóch 32-bitowych zmiennych bez znaku, zakresu (reprezentującego rozmiar zakresu) i kodu (reprezentującego zakodowany punkt w zakresie).

Inicjalizacja dekodera zakresu polega na ustawieniu zakresu na 2 ^32-1 i kodowaniu do wartości 32-bitowej od drugiego bajtu w strumieniu interpretowanym jako big-endian; pierwszy bajt w strumieniu jest całkowicie ignorowany.

Normalizacja przebiega w ten sposób:

Przesuń zakres i kod w lewo o 8 bitów
Przeczytaj bajt ze skompresowanego strumienia
Ustaw najmniej znaczące 8 bitów kodu na odczytaną wartość bajtu

Kontekstowe dekodowanie zakresu bitu przy użyciu zmiennej prawdopodobieństwa prob przebiega w następujący sposób:

Jeśli zakres jest mniejszy niż 2^24, wykonaj normalizację
Ustaw powiązanie z podłogą ( zakres / 2^11) * prob
Jeśli kod jest mniejszy niż związany :
1. Ustaw zakres na ograniczenie
2. Ustaw prob na prob + piętro((2^11 - prob ) / 2^5)
3. Zwróć bit 0
W przeciwnym razie (jeśli kod jest większy lub równy bound ):
1. Ustaw zakres na zakres - ograniczony
2. Ustaw kod na kod - związany
3. Ustaw prob na prob - piętro( prob / 2^5)
4. Zwróć bit 1

Dekodowanie bitu ze stałym prawdopodobieństwem przebiega w następujący sposób:

Jeśli zakres jest mniejszy niż 2^24, wykonaj normalizację
Ustaw zakres na podłogę ( zakres / 2)
Jeśli kod jest mniejszy niż zakres :
1. Zwróć bit 0
W przeciwnym razie (jeśli kod jest większy lub równy zakresowi ):
1. Ustaw kod na kod - zakres
2. Zwróć bit 1

Implementacja w jądrze Linuksa dekodowania ze stałym prawdopodobieństwem w rc_direct(), ze względu na wydajność, nie zawiera gałęzi warunkowej, ale zamiast tego bezwarunkowo odejmuje zakres od kodu . Wynikowy bit znaku jest używany zarówno do określenia bitu do zwrócenia, jak i do wygenerowania maski, która jest połączona z kodem i dodana do range .

Zwróć uwagę, że:

Dzielenie przez 2^11, gdy obliczenia związane i dolne są wykonywane przed mnożeniem, a nie po (najwyraźniej w celu uniknięcia konieczności szybkiej obsługi sprzętowej mnożenia 32-bitowego z wynikiem 64-bitowym)
Dekodowanie ze stałym prawdopodobieństwem nie jest ściśle równoważne z dekodowaniem zakresu opartego na kontekście z dowolną wartością prob , ponieważ dekodowanie zakresu oparte na kontekście odrzuca dolnych 11 bitów zakresu przed pomnożeniem przez prob, jak opisano powyżej , podczas gdy dekodowanie ze stałym prawdopodobieństwem odrzuca tylko ostatni kawałek

Kodowanie zakresu liczb całkowitych

Dekoder zakresu zapewnia również funkcje dekodowania drzewa bitów, odwrotnego drzewa bitów i liczb całkowitych o stałym prawdopodobieństwie, które są wykorzystywane do dekodowania liczb całkowitych i uogólniania opisanego powyżej dekodowania jednobitowego. Aby zdekodować liczby całkowite bez znaku mniejsze niż limit , dostarczana jest tablica ( limit - 1) 11-bitowych zmiennych prawdopodobieństwa, które są koncepcyjnie uporządkowane jako wewnętrzne węzły pełnego drzewa binarnego z liśćmi limitu .

Nieodwrotne dekodowanie drzewa bitowego polega na utrzymywaniu wskaźnika do drzewa zmiennych, które zaczyna się od korzenia. Dopóki wskaźnik nie wskazuje na liść, bit jest dekodowany przy użyciu zmiennej wskazywanej przez wskaźnik, a wskaźnik jest przesuwany do lewego lub prawego dziecka w zależności od tego, czy bit ma wartość 0 czy 1; gdy wskaźnik wskazuje na liść, zwracana jest liczba skojarzona z liściem.

Nieodwrotne dekodowanie drzewa bitowego odbywa się zatem od najbardziej znaczącego do najmniej znaczącego bitu, zatrzymując się, gdy możliwa jest tylko jedna wartość z prawidłowego zakresu (to koncepcyjnie pozwala na uzyskanie rozmiarów zakresu, które nie są potęgami dwójki, nawet jeśli LZMA nie korzysta tego).

Zamiast tego dekodowanie odwróconego drzewa bitowego dekoduje od najmniej znaczącego bitu do najbardziej znaczących bitów, a zatem obsługuje tylko zakresy, które są potęgami dwójki, i zawsze dekoduje tę samą liczbę bitów. Jest to równoważne wykonaniu nieodwrotnego dekodowania drzewa bitowego z mocą dwójki limit i odwróceniu ostatnich bitów log2( limit ) wyniku.

W funkcji rc_bittree w jądrze Linuksa liczby całkowite są faktycznie zwracane w zakresie [ limit , 2 * limit ) (z limitem dodanym do wartości koncepcyjnej), a zmienna o indeksie 0 w tablicy jest nieużywana, natomiast zmienna o indeksie 1 jest pierwiastkiem, a lewe i prawe indeksy potomne są obliczane jako 2 i oraz 2 i + 1. Zamiast tego funkcja rc_bittree_reverse dodaje liczby całkowite z zakresu [0, limit ) do zmiennej podanej przez wywołującego, gdzie limit jest niejawnie reprezentowany przez jego logarytm i ma własną niezależną implementację ze względu na wydajność.

Dekodowanie liczb całkowitych o stałym prawdopodobieństwie po prostu wykonuje dekodowanie bitów o stałym prawdopodobieństwie wielokrotnie, odczytując bity od najbardziej do najmniej znaczącej.

Konfiguracja LZMA

Dekoder LZMA jest konfigurowany przez bajt „właściwości” lclppb i rozmiar słownika. Wartość bajtu lclppb to lc + lp * 9 + pb * 9 * 5, gdzie:

lc to liczba starszych bitów poprzedniego bajtu, które mają być użyte jako kontekst dla kodowania literalnego (wartość domyślna używana przez LZMA SDK to 3)
lp to liczba młodszych bitów pozycji słownika do uwzględnienia w literal_pos_state (domyślna wartość używana przez LZMA SDK to 0)
pb to liczba młodszych bitów pozycji słownika do uwzględnienia w pos_state (wartość domyślna używana przez LZMA SDK to 2)

W strumieniach innych niż LZMA2 lc nie może być większe niż 8, a lp i pb nie może być większe niż 4. W strumieniach LZMA2 ( lc + lp ) i pb nie mogą być większe niż 4.

W formacie pliku 7-zip LZMA konfiguracja odbywa się za pomocą nagłówka zawierającego bajt „właściwości”, po którym następuje rozmiar 32-bitowego słownika little-endian w bajtach. W LZMA2 bajt właściwości można opcjonalnie zmienić na początku pakietów LZMA2 LZMA, podczas gdy rozmiar słownika jest określony w nagłówku LZMA2, jak opisano później.

Konteksty kodowania LZMA

Format pakietu LZMA został już opisany, a ta sekcja określa, w jaki sposób LZMA statystycznie modeluje strumienie zakodowane w LZ, czyli innymi słowy, które zmienne prawdopodobieństwa są przekazywane do dekodera zakresu w celu zdekodowania każdego bitu.

Te zmienne prawdopodobieństwa są zaimplementowane jako wielowymiarowe tablice; przed ich wprowadzeniem definiuje się kilka wartości, które są używane jako indeksy w tych wielowymiarowych tablicach.

Wartość stanu jest koncepcyjnie oparta na tym, który z wzorców w poniższej tabeli pasuje do ostatnio widzianych 2-4 typów pakietów i jest zaimplementowana jako stan automatu stanu aktualizowany zgodnie z tabelą przejść wymienioną w tabeli za każdym razem, gdy pakiet jest wyprowadzany.

Stanem początkowym jest 0, a zatem pakiety przed początkiem są uznawane za pakiety LIT.

stan	poprzednie pakiety				następny stan, gdy następny pakiet jest
	4. poprzedni	3 poprzedni	2. poprzedni	Poprzedni	OŚWIETLONY	MECZ	LONGREP[*]	SKRÓT
0		OŚWIETLONY	OŚWIETLONY	OŚWIETLONY	0	7	8	9
1		MECZ	OŚWIETLONY	OŚWIETLONY	0	7	8	9
2		LONGREP[*]	OŚWIETLONY	OŚWIETLONY	0	7	8	9
2	*MECZ	SKRÓT	OŚWIETLONY	OŚWIETLONY	0	7	8	9
3	OŚWIETLONY	SKRÓT	OŚWIETLONY	OŚWIETLONY	0	7	8	9
4			MECZ	OŚWIETLONY	1	7	8	9
5			LONGREP[*]	OŚWIETLONY	2	7	8	9
5		*MECZ	SKRÓT	OŚWIETLONY	2	7	8	9
6		OŚWIETLONY	SKRÓT	OŚWIETLONY	3	7	8	9
7			OŚWIETLONY	MECZ	4	10	11	11
8			OŚWIETLONY	LONGREP[*]	5	10	11	11
9			OŚWIETLONY	SKRÓT	6	10	11	11
10			*MECZ	MECZ	4	10	11	11
11			*MECZ	*REPREZENTANT	5	10	11	11

Wartości pos_state i literal_pos_state składają się odpowiednio z pb i lp (do 4, z nagłówka LZMA lub pakietu właściwości LZMA2) najmniej znaczących bitów pozycji słownika (liczba bajtów zakodowanych od ostatniego zerowania słownika modulo rozmiar słownika). Zauważ, że rozmiar słownika jest zwykle wielokrotnością dużej potęgi 2, więc te wartości są równoważnie opisane jako najmniej znaczące bity liczby nieskompresowanych bajtów widzianych od ostatniego resetowania słownika.

Wartość prev_byte_lc_msbs jest ustawiona na lc (do 4, z nagłówka LZMA lub pakietu właściwości LZMA2) najbardziej znaczących bitów poprzedniego nieskompresowanego bajtu.

Wartość is_REP wskazuje, czy pakiet, który zawiera długość, jest LONGREP, a nie MATCH.

Wartość match_byte to bajt, który zostałby zdekodowany, gdyby użyto pakietu SHORTREP (innymi słowy, bajt znaleziony w słowniku na ostatnio użytej odległości); jest używany tylko po pakiecie *MATCH.

literal_bit_mode to tablica 8 wartości z zakresu 0-2, po jednej dla każdej pozycji bitu w bajcie, która wynosi 1 lub 2, jeśli poprzedni pakiet był *MATCH i jest to albo najbardziej znacząca pozycja bitowa, albo bardziej znacząca bity w literale do kodowania/dekodowania są równe bitom w odpowiednich pozycjach w match_byte , podczas gdy w przeciwnym razie jest to 0; wybór między 1 lub 2 wartościami zależy od wartości bitu na tej samej pozycji w match_byte .

Dosłowny/dosłowny zestaw zmiennych może być postrzegany jako „pseudo-drzewo-bitowe” podobne do drzewa bitowego, ale z 3 zmiennymi zamiast 1 w każdym węźle, wybieranymi w zależności od wartości literal_bit_mode na pozycji bitu następnego bitu dekodować po kontekście drzewa bitowego wskazanym przez węzeł.

Twierdzenie, znalezione w niektórych źródłach, że literały po *MATCH są kodowane jako XOR wartości byte z match_byte jest niepoprawne; zamiast tego są kodowane po prostu jako ich wartość bajtowa, ale przy użyciu opisanego właśnie pseudo-drzewa bitowego i dodatkowego kontekstu wymienionego w poniższej tabeli.

Grupy zmiennych prawdopodobieństwa stosowane w LZMA to:

XZ nazwa	Nazwa LZMA SDK	Sparametryzowane przez	Używane, gdy	Tryb kodowania	Jeśli bit 0 to	Jeśli bit 1, to
is_match	IsMatch	stan , stan_poz	początek pakietu	fragment	OŚWIETLONY	*MECZ
is_rep	IsRep	stan	po sekwencji bitowej 1	fragment	MECZ	*REPREZENTANT
is_rep0	IsRepG0	stan	po sekwencji bitowej 11	fragment	KRÓTKI/ LONGREP[0]	LONGREP[1-3]
is_rep0_long	IsRep0Long	stan , stan_poz	po sekwencji bitowej 110	fragment	SKRÓT	LONGREP[0]
is_rep1	IsRepG1	stan	po sekwencji bitowej 111	fragment	LONGREP[1]	LONGREP[2/3]
is_rep2	IsRepG2	stan	po sekwencji bitowej 1111	fragment	LONGREP[2]	LONGREP[3]
dosłowny	Dosłowny	prev_byte_lc_msbs , literal_pos_state , literal_bit_mode [pozycja bitowa], kontekst drzewa bitowego	po sekwencji bitowej 0	256 wartości pseudo-drzewa bitowego	dosłowna wartość bajtów
dist_slot	PosSlot	min( długość_dopasowania , 5), kontekst drzewa bitowego	odległość: początek	64 wartości drzewa bitowego	szczelina dystansowa
dist_specjalny	SpecPos	odległość_slot , odwrócony kontekst drzewa bitowego	odległość: 4–13 szczelin dystansowych	(( odległość_szczelin >> 1) − 1)-bitowe odwrotne drzewo bitów	małe bity odległości
dist_align	Wyrównywać	odwrócony kontekst drzewa bitowego	odległość: ponad 14 przedziałów odległości, po ustalonych bitach prawdopodobieństwa	4-bitowe odwrócone drzewo bitów	małe bity odległości
len_dec.choice	LenChoice	is_REP	długość meczu: początek	fragment	2–9 długości	10+ długości
len_dec.choice2	LenChoice2	is_REP	długość dopasowania: po sekwencji bitowej 1	fragment	10-17 długość	18+ długość
len_dec.low	LenLow	is_REP , pos_state , kontekst drzewa bitowego	długość dopasowania: po sekwencji bitów 0	8 wartości drzewa bitowego	małe bity długości
len_dec.mid	LenMid	is_REP , pos_state , kontekst drzewa bitowego	długość dopasowania: po sekwencji bitowej 10	8 wartości drzewa bitowego	środkowe bity długości
len_dec.high	LenHigh	is_REP , kontekst drzewa bitowego	długość dopasowania: po sekwencji bitowej 11	256 wartości drzewa bitowego	wysokie bity długości

Format LZMA2

Kontener LZMA2 obsługuje wiele przebiegów skompresowanych danych LZMA i nieskompresowanych danych. Każdy skompresowany przebieg LZMA może mieć inną konfigurację i słownik LZMA. Poprawia to kompresję częściowo lub całkowicie nieskompresowanych plików i umożliwia wielowątkową kompresję i wielowątkową dekompresję, dzieląc plik na przebiegi, które można niezależnie skompresować lub dekompresować równolegle. Krytyka zmian LZMA2 w stosunku do LZMA obejmuje pola nagłówka nieobjęte CRC oraz niemożliwą w praktyce dekompresję równoległą.

Nagłówek LZMA2 składa się z bajtu określającego rozmiar słownika:

40 oznacza 4 GB − 1 rozmiar słownika
Nawet wartości mniejsze niż 40 wskazują na rozmiar słownika 2 ^{v /2 + 12} bajtów
Wartości nieparzyste mniejsze niż 40 oznaczają rozmiar słownika 3×2 ^{( v − 1)/2 + 11} bajtów
Wartości wyższe niż 40 są nieprawidłowe

Dane LZMA2 składają się z pakietów zaczynających się od bajtu kontrolnego o następujących wartościach:

0 oznacza koniec pliku
1 oznacza zresetowanie słownika, po którym następuje nieskompresowany fragment
2 oznacza nieskompresowany fragment bez resetowania słownika
3-0x7f to nieprawidłowe wartości
0x80-0xff oznacza porcję LZMA, w której najniższe 5 bitów jest używanych jako bit 16-20 nieskompresowanego rozmiaru minus jeden, a bit 5-6 wskazuje, co należy zresetować

Bity 5-6 dla kawałków LZMA mogą być:

0: nic się nie resetuje
1: reset stanu
2: resetowanie stanu, resetowanie właściwości za pomocą właściwości byte
3: resetowanie stanu, resetowanie właściwości za pomocą bajtu właściwości, resetowanie słownika

Resety stanów LZMA powodują reset wszystkich stanów LZMA poza słownikiem, a konkretnie:

Koder zakresu
Stan wartość
Ostatnie dystanse dla powtarzających się meczów
Wszystkie prawdopodobieństwa LZMA

Nieskompresowane kawałki składają się z:

16-bitowa wartość big-endian kodująca rozmiar danych minus jeden
Dane do skopiowania dosłownie do słownika i wyjścia

Kawałki LZMA składają się z:

16-bitowa wartość big-endian kodująca dolne 16 bitów nieskompresowanego rozmiaru minus jeden
16-bitowa wartość big-endian kodująca skompresowany rozmiar minus jeden
Bajt właściwości/lclppb, jeśli ustawiony jest bit 6 w bajcie kontrolnym
Skompresowane dane LZMA, zaczynając od 5 bajtów (z których pierwszy jest ignorowany) użytych do zainicjowania kodera zakresu (które są zawarte w skompresowanym rozmiarze)

formaty xz i 7z

Ten . Format xz , który może zawierać dane LZMA2, jest udokumentowany na tukaani.org , natomiast format pliku .7z, który może zawierać dane LZMA lub LZMA2, jest udokumentowany w pliku 7zformat.txt zawartym w LZMA SDK.

Szczegóły algorytmu kompresji

Podobnie jak w przypadku formatu dekompresyjnego, wydaje się, że nie istnieje kompletna specyfikacja języka naturalnego technik kodowania w 7-zip lub xz , inna niż ta, o której mowa w poniższym tekście.

Poniższy opis opiera się na koderze XZ for Java autorstwa Lasse Collina, który wydaje się być najbardziej czytelny spośród kilku przepisanych oryginalnego 7-zip przy użyciu tych samych algorytmów: ponownie, chociaż cytowanie kodu źródłowego jako odniesienia nie jest idealne, żaden programista powinien być w stanie sprawdzić poniższe roszczenia po kilku godzinach pracy.

Enkoder zakresu

Enkoder zakresu nie może dokonywać żadnych interesujących wyborów i można go łatwo skonstruować na podstawie opisu dekodera.

Inicjalizacja i zakończenie nie są w pełni określone; koder xz wyprowadza 0 jako pierwszy bajt, który jest ignorowany przez dekompresor i koduje dolną granicę zakresu (co ma znaczenie dla końcowych bajtów).

Koder xz wykorzystuje 33-bitową zmienną bez znaku o nazwie low (zwykle zaimplementowaną jako 64-bitową liczbę całkowitą, zainicjowaną na 0), zmienną 32-bitową bez znaku o nazwie range (zainicjowaną do 2 ³² - 1), zmienną 8-bitową bez znaku zwana pamięcią podręczną (zainicjowana na 0) i zmienną bez znaku o nazwie cache_size, która musi być wystarczająco duża, aby przechowywać nieskompresowany rozmiar (zainicjowany na 1, zwykle zaimplementowany jako 64-bitowa liczba całkowita).

W cache / cache_size zmienne są używane prawidłowo obsługiwać niesie i oznaczają liczbę określoną przez sekwencję big-endian począwszy od podręcznej wartości, a następnie cache_size 0xFF bajty, który został przesunięty z niskim rejestrze, ale nie było jeszcze napisane, ponieważ może zostać zwiększone o jeden z powodu przeniesienia.

Zauważ, że pierwszy bajt wyjściowy zawsze będzie miał wartość 0, ponieważ cache i low są inicjowane na 0, a implementacja kodera; dekoder xz ignoruje ten bajt.

Normalizacja przebiega w ten sposób:

Jeśli niski jest mniejszy niż (2^32 - 2^24):
1. Wyprowadź bajt przechowywany w pamięci podręcznej do skompresowanego strumienia
2. Output cache_size - 1 bajty z wartością 0xff
3. Ustaw pamięć podręczną na bity 24-31 lub niskie
4. Ustaw cache_size na 0
Jeśli niski jest większy lub równy 2^32:
1. Wyprowadź bajt przechowywany w pamięci podręcznej plus jeden do skompresowanego strumienia
2. Output cache_size - 1 bajty z wartością 0
3. Ustaw pamięć podręczną na bity 24-31 lub niskie
4. Ustaw cache_size na 0
Zwiększ rozmiar pamięci podręcznej
Ustaw low na najniższe 24 bity low przesunięte w lewo o 8 bitów
Ustaw zakres na zakres przesunięty w lewo o 8 bitów

Kontekstowe kodowanie zakresu bitu przy użyciu zmiennej prawdopodobieństwa prob przebiega w ten sposób:

Jeśli zakres jest mniejszy niż 2^24, wykonaj normalizację
Ustaw powiązanie z podłogą ( zakres / 2^11) * prob
Jeśli kodujesz bit 0:
1. Ustaw zakres na ograniczenie
2. Ustaw prob na prob + piętro((2^11 - prob ) / 2^5)
W przeciwnym razie (jeśli kodujesz 1 bit):
1. Ustaw zakres na zakres - ograniczony
2. Ustaw niski na niski + granica
3. Ustaw prob na prob - piętro( prob / 2^5)

Kodowanie bitu ze stałym prawdopodobieństwem przebiega w ten sposób:

Jeśli zakres jest mniejszy niż 2^24, wykonaj normalizację
Ustaw zakres na podłogę ( zakres / 2)
Jeśli kodujesz 1 bit:
1. Ustaw niski na niski + zakres

Wypowiedzenie przebiega w ten sposób:

Wykonaj normalizację 5 razy

Kodowanie drzewa bitowego odbywa się podobnie jak dekodowanie, z tym wyjątkiem, że wartości bitowe są pobierane z wejściowej liczby całkowitej do zakodowania, a nie z wyniku funkcji dekodowania bitów.

W przypadku algorytmów, które próbują obliczyć kodowanie z najkrótszym rozmiarem kodowania post-range, koder musi również podać oszacowanie tego.

Struktury danych wyszukiwania w słowniku

Koder musi być w stanie szybko zlokalizować dopasowania w słowniku. Ponieważ LZMA używa bardzo dużych słowników (potencjalnie rzędu gigabajtów) w celu poprawy kompresji, zwykłe przeskanowanie całego słownika spowodowałoby, że koder byłby zbyt wolny, aby był praktycznie użyteczny, więc do obsługi szybkiego wyszukiwania dopasowań potrzebne są zaawansowane struktury danych.

Łańcuchy haszowe

Najprostsze podejście, zwane „łańcuchami mieszającymi”, jest parametryzowane przez stałą N, która może wynosić 2, 3 lub 4, która jest zwykle wybierana tak, aby 2^(8× N ) było większe lub równe rozmiarowi słownika.

Polega na utworzeniu, dla każdego k mniejszego lub równego N , tabeli haszującej indeksowanej przez krotki k bajtów, gdzie każdy z segmentów zawiera ostatnią pozycję, w której pierwsze k bajtów zahaszowane do wartości haszującej powiązanej z tym segmentem tabeli haszującej .

Łączenie jest osiągane przez dodatkową tablicę, która przechowuje, dla każdej pozycji słownika, ostatnią widzianą poprzednią pozycję, której pierwsze N bajtów hashuje do tej samej wartości pierwszych N bajtów danej pozycji.

Aby znaleźć mecze o długości N lub wyższej, wyszukiwanie jest uruchamiana za pomocą N -sized tabeli mieszania i dalej za pomocą łańcucha tablicę hash; wyszukiwanie zatrzymuje się po przejściu określonej liczby węzłów łańcucha haszującego lub gdy łańcuchy haszujące "zawijają się", wskazując, że osiągnięto część danych wejściowych, które zostały nadpisane w słowniku.

Dopasowania o rozmiarze mniejszym niż N można znaleźć, po prostu patrząc na odpowiednią tabelę skrótów, która zawiera najnowsze takie dopasowanie, jeśli istnieje, lub ciąg znaków haszujący do tej samej wartości; w tym drugim przypadku koder nie będzie w stanie znaleźć dopasowania. Ten problem jest łagodzony przez fakt, że w przypadku odległych krótkich dopasowań użycie wielu literałów może wymagać mniej bitów, a konflikty haszujące w pobliskich ciągach znaków są stosunkowo mało prawdopodobne; używanie większych tabel mieszających lub nawet bezpośrednich tabel wyszukiwania może zmniejszyć problem kosztem wyższego współczynnika chybień pamięci podręcznej, a tym samym niższej wydajności.

Należy zauważyć, że wszystkie dopasowania muszą zostać zweryfikowane, aby sprawdzić, czy aktualne bajty pasują do tej konkretnej pozycji w słowniku, ponieważ mechanizm haszujący gwarantuje jedynie, że w przeszłości istniały znaki haszujące do indeksu tabeli haszującej (niektóre implementacje mogą nawet nie gwarantują to, ponieważ nie inicjują struktur danych).

LZMA używa łańcuchów Markowa , co sugeruje „M” w nazwie.

Drzewa binarne

Drzewo binarne podejście odzwierciedla podejście łańcuchowej skrótu, oprócz tego, że logicznie wykorzystuje binarne drzewo zamiast połączonej listy łańcuchowym.

Drzewo binarne jest utrzymywane tak, że zawsze jest zarówno drzewem wyszukiwania względem porządku leksykograficznego sufiksów, jak i kopią max dla pozycji słownika (innymi słowy, korzeń jest zawsze najnowszym łańcuchem, a dziecko nie może być dodany później niż jego rodzic): zakładając, że wszystkie ciągi są uporządkowane leksykograficznie, warunki te jednoznacznie jednoznacznie określają drzewo binarne (jest to banalnie możliwe do udowodnienia przez indukcję na wielkości drzewa).

Ponieważ ciąg do wyszukania i ciąg do wstawienia są takie same, możliwe jest zarówno przeszukiwanie słownika, jak i wstawianie (co wymaga obrócenia drzewa) w jednym przejściu drzewa.

Patricia próbuje

Niektóre stare kodery LZMA również wspierały strukturę danych opartą na próbach Patricii , ale od tego czasu takie wsparcie zostało porzucone, ponieważ uznano je za gorsze od innych opcji.

Enkoder LZMA

Kodery LZMA mogą swobodnie decydować, które dopasowanie do wyjścia lub czy mimo to ignorować obecność dopasowań i literałów wyjściowych.

Możliwość przywołania 4 ostatnio używanych odległości oznacza, że w zasadzie użycie dopasowania z odległością, która będzie potrzebna ponownie później, może być globalnie optymalna, nawet jeśli nie jest lokalnie optymalna, a w rezultacie optymalna kompresja LZMA prawdopodobnie wymaga znajomości wszystkich danych wejściowych i może wymagać algorytmów zbyt wolnych, aby można je było wykorzystać w praktyce.

Z tego powodu w praktycznych implementacjach stosuje się nieglobalną heurystykę.

Kodery xz używają wartości zwanej nice_len (domyślnie 64): gdy zostanie znalezione dowolne dopasowanie długości co najmniej nice_len , koder zatrzymuje wyszukiwanie i wyświetla je z maksymalną pasującą długością.

Szybki koder

Szybki koder XZ (pochodzący z szybkiego kodera 7-zip) jest najkrótszym koderem LZMA w drzewie źródeł xz.

Działa to tak:

Wykonywanie połączonego wyszukiwania i wstawiania w strukturze danych słownika
Jeśli jakakolwiek powtarzająca się odległość pasuje do długości co najmniej nice_len :
- Wyprowadź najczęściej używaną taką odległość z pakietem REP
Jeśli znaleziono dopasowanie o długości co najmniej nice_len :
- Wyślij go z pakietem MATCH
Ustaw mecz główny na najdłuższy mecz
Spójrz na najbliższe dopasowanie każdej długości w kolejności malejącej długości i dopóki nie będzie można dokonać wymiany:
- Zastąp mecz główny meczem, który jest o jeden znak krótszy, ale którego dystans jest mniejszy niż 1/128 od aktualnego dystansu głównego meczu
Ustaw długość głównego meczu na 1, jeśli bieżący mecz główny ma długość 2 i dystans co najmniej 128
Jeśli znaleziono powtarzające się dopasowanie, które jest krótsze o co najwyżej 1 znak niż dopasowanie główne:
- Wyślij powtórzony mecz z pakietem REP
Jeśli znaleziono powtarzające się dopasowanie, które jest krótsze o maksymalnie 2 znaki niż dopasowanie główne, a odległość głównego dopasowania wynosi co najmniej 512:
- Wyślij powtórzony mecz z pakietem REP
Jeśli znaleziono powtarzające się dopasowanie, które jest krótsze o maksymalnie 3 znaki niż dopasowanie główne, a odległość głównego dopasowania wynosi co najmniej 32768:
- Wyślij powtórzony mecz z pakietem REP
Jeśli główny rozmiar dopasowania jest mniejszy niż 2 (lub nie ma żadnego dopasowania):
- Wyprowadź pakiet LIT
Przeprowadź wyszukiwanie w słowniku następnego bajtu
Jeśli następny bajt jest krótszy o co najwyżej 1 znak od głównego dopasowania, z odległością mniejszą niż 1/128 razy odległość głównego dopasowania, a długość głównego dopasowania wynosi co najmniej 3:
- Wyprowadź pakiet LIT
Jeśli następny bajt zawiera dopasowanie co najmniej tak długo, jak mecz główny i ma mniejszą odległość niż dopasowanie główne:
- Wyprowadź pakiet LIT
Jeśli następny bajt ma dopasowanie co najmniej o jeden znak dłuższe od głównego dopasowania i takie, że 1/128 jego odległości jest mniejsze lub równe głównej odległości dopasowania:
- Wyprowadź pakiet LIT
Jeśli następny bajt ma dopasowanie o więcej niż jeden znak dłuższe niż dopasowanie główne:
- Wyprowadź pakiet LIT
Jeśli jakiekolwiek powtórzone dopasowanie jest krótsze o co najwyżej 1 znak niż dopasowanie główne:
- Wyprowadź najczęściej używaną taką odległość z pakietem REP
Wyślij główny mecz z pakietem MATCH

Normalny koder

Normalny koder XZ (pochodzący z normalnego kodera 7-zip) jest drugim koderem LZMA w drzewie źródłowym xz, w którym zastosowano bardziej wyrafinowane podejście, które próbuje zminimalizować rozmiar generowanych pakietów po kodowaniu zakresu.

W szczególności koduje fragmenty danych wejściowych przy użyciu wyniku dynamicznego algorytmu programowania, w którym podproblemy znajdują w przybliżeniu optymalne kodowanie (to z minimalnym rozmiarem kodowania post-range) podciągu o długości L, zaczynając od skompresowanego bajtu .

Wielkość części danych wejściowych przetwarzanych w algorytmie programowania dynamicznego jest określana jako maksymalna między najdłuższym dopasowaniem słownikowym a najdłuższym powtórzonym dopasowaniem znalezionym w pozycji początkowej (które jest ograniczone przez maksymalną długość dopasowania LZMA, 273); ponadto, jeśli dopasowanie dłuższe niż nice_len zostanie znalezione w dowolnym punkcie właśnie zdefiniowanego zakresu, algorytm programowania dynamicznego zatrzymuje się, wyprowadzane jest rozwiązanie podproblemu do tego punktu, wyprowadzane jest dopasowanie o wielkości nice_len i nowe programowanie dynamiczne instancja problemu jest uruchamiana w bajcie po dopasowaniu.

Kandydujące rozwiązania podproblemów są stopniowo aktualizowane za pomocą kandydujących kodowań, konstruowanych na podstawie rozwiązania dla krótszego podłańcucha o długości L', rozszerzonego o wszystkie możliwe „ogony” lub zestawy 1-3 pakietów z pewnymi ograniczeniami, które kodują dane wejściowe w pozycji L' . Po znalezieniu ostatecznego rozwiązania podproblemu obliczany jest stan LZMA i najmniej używane odległości, a następnie są wykorzystywane do odpowiedniego obliczenia rozmiarów jego rozszerzeń po zakodowaniu zakresu.

Pod koniec optymalizacji programowania dynamicznego wyprowadzane jest całe optymalne kodowanie najdłuższego rozważanego podciągu, a kodowanie jest kontynuowane przy pierwszym nieskompresowanym bajcie, który nie został jeszcze zakodowany, po zaktualizowaniu stanu LZMA i najmniej używanych odległości.

Każdy podproblem jest rozszerzony o sekwencję pakietów, którą nazywamy „ogonem”, która musi pasować do jednego z następujących wzorców:

1 pakiet	Drugi pakiet	Trzeci pakiet
każdy
OŚWIETLONY	LONGREP[0]
*MECZ	OŚWIETLONY	LONGREP[0]

Powodem nie tylko rozszerzenia o pojedyncze pakiety jest to, że podproblemy mają tylko długość podciągu jako parametr ze względu na wydajność i złożoność algorytmiczną, podczas gdy optymalne podejście do programowania dynamicznego wymagałoby również posiadania ostatnio używanych odległości i stanu LZMA jako parametru; w ten sposób rozszerzenie o wiele pakietów pozwala lepiej przybliżyć optymalne rozwiązanie, a w szczególności lepiej wykorzystać pakiety LONGREP[0].

Dla każdego podproblemu zapisywane są następujące dane (oczywiście wartości przechowywane są dla rozwiązania kandydującego z ceną minimalną ), gdzie przez „ogon” odnosimy się do pakietów rozszerzających rozwiązanie mniejszego podproblemu, które są opisane bezpośrednio w dalszej części Struktura:

Nazwa członka XZ for Java	opis
Cena £	ilość do zminimalizowania: liczba bitów post-range-coding potrzebnych do zakodowania ciągu
optPrev	nieskompresowany rozmiar podciągu zakodowanego przez wszystkie pakiety z wyjątkiem ostatniego
wsteczPoprzednia	-1 jeśli ostatni pakiet to LIT, 0-3 jeśli jest to powtórzenie przy użyciu ostatnio użytej odległości o numerze 0–3, 4 + odległość jeśli jest to MATCH (jest to zawsze 0 jeśli prev1IsLiteral jest prawdziwe, ponieważ ostatni pakiet może w takim przypadku być tylko LONGREP[0])
prev1IsDosłowny	prawda, jeśli „ogon” zawiera więcej niż jeden pakiet (w takim przypadku przedostatni to LIT)
maPoprzednia2	true jeśli "ogon" zawiera 3 pakiety (ważne tylko jeśli prev1IsLiteral jest prawdziwe)
optPrev2	nieskompresowany rozmiar podciągu zakodowanego przez wszystkie pakiety z wyjątkiem „ogonu” (ważne tylko, jeśli wartości prev1IsLiteral i hasPrev2 są prawdziwe)
wsteczPoprzednia2	-1 jeśli pierwszy pakiet w "ogonie" to LIT, 0-3 jeśli jest powtórzeniem z użyciem ostatnio użytej odległości o numerze 0-3, 4 + odległość jeśli jest to MATCH (ważne tylko jeśli prev1IsLiteral i hasPrev2 są prawdziwe)
przedstawiciele[4]	wartości 4 ostatnio użytych odległości po pakietach w rozwiązaniu (obliczone dopiero po określeniu najlepszego rozwiązania podproblemu)
stan	wartość stanu LZMA po pakietach w rozwiązaniu (obliczana dopiero po określeniu najlepszego rozwiązania podproblemu)

Należy zauważyć, że w implementacji XZ for Java elementy składowe optPrev i backPrev są ponownie wykorzystywane do przechowywania listy pakietów z pojedynczym łączem do przodu w ramach wyprowadzania ostatecznego rozwiązania.

Enkoder LZMA2

Koder XZ LZMA2 przetwarza dane wejściowe w kawałkach (do 2 MB nieskompresowanego rozmiaru lub 64 KB skompresowanego rozmiaru, w zależności od tego, która jest mniejsza), przekazując każdy fragment do kodera LZMA, a następnie decydując, czy wyprowadzić fragment LZMA2 LZMA, w tym zakodowane dane , lub aby wyprowadzić nieskompresowaną porcję LZMA2, w zależności od tego, która jest krótsza (LZMA, jak każdy inny kompresor, z konieczności rozszerza, a nie kompresuje niektóre rodzaje danych).

Stan LZMA jest resetowany tylko w pierwszym bloku, jeśli wywołujący żąda zmiany właściwości i za każdym razem, gdy wyprowadzany jest skompresowany fragment. Właściwości LZMA są zmieniane tylko w pierwszym bloku lub jeśli wywołujący żąda zmiany właściwości. Słownik jest resetowany tylko w pierwszym bloku.

Górne warstwy kodujące

Przed kodowaniem LZMA2, w zależności od dostarczonych opcji, xz może zastosować filtr BCJ, który filtruje kod wykonywalny, aby zastąpić względne przesunięcia absolutnymi, które są bardziej powtarzalne, lub filtr delta, który zastępuje każdy bajt różnicą między nim a bajtem N bajtów przed nim.

Kodowanie równoległe jest wykonywane przez podzielenie pliku na porcje, które są dystrybuowane do wątków, a ostatecznie każdy z nich jest zakodowany osobno (przy użyciu na przykład kodowania blokowego xz), co skutkuje resetowaniem słownika między porcjami w pliku wyjściowym.

Implementacja referencyjna 7-Zip

Implementacja LZMA wyodrębniona z 7-Zip jest dostępna jako LZMA SDK. Pierwotnie był on objęty podwójną licencją zarówno na licencji GNU LGPL, jak i Common Public License , z dodatkowym specjalnym wyjątkiem dla połączonych plików binarnych, ale został umieszczony przez Igora Pavlova w domenie publicznej 2 grudnia 2008 r., wraz z wydaniem wersji 4.62.

Kompresja LZMA2, która jest ulepszoną wersją LZMA, jest teraz domyślną metodą kompresji dla formatu .7z, począwszy od wersji 9.30 26 października 2012 r.

Referencyjna biblioteka kompresji LZMA o otwartym kodzie źródłowym została pierwotnie napisana w C++, ale została przeniesiona do ANSI C , C# i Java . Istnieją również zewnętrzne powiązania Pythona do biblioteki C++, a także porty LZMA do Pascal , Go i Ada .

Implementacja 7-Zip wykorzystuje kilka wariantów łańcuchów haszujących , drzew binarnych, a Patricia próbuje jako podstawę algorytmu wyszukiwania słownika.

Oprócz LZMA, SDK i 7-Zip implementują również wiele filtrów wstępnego przetwarzania, które mają na celu poprawę kompresji, począwszy od prostego kodowania delta (dla obrazów) i BCJ dla kodu wykonywalnego. Zapewnia również kilka innych algorytmów kompresji używanych w 7z.

Kod tylko do dekompresji dla LZMA zwykle kompiluje się do około 5 KB, a ilość pamięci RAM wymagana podczas dekompresji jest głównie określana przez rozmiar przesuwanego okna używanego podczas kompresji. Mały rozmiar kodu i stosunkowo niski narzut pamięci, szczególnie przy mniejszych długościach słowników i darmowym kodzie źródłowym, sprawiają, że algorytm dekompresji LZMA dobrze nadaje się do aplikacji wbudowanych .

Inne realizacje

Oprócz implementacji referencyjnej 7-Zip, poniższe obsługują format LZMA.

xz : implementacja strumieniowa zawierająca narzędzie wiersza poleceń podobne do gzip , obsługujące zarówno LZMA, jak i LZMA2 w formacie pliku xz. Dzięki swojej wysokiej wydajności (w porównaniu do bzip2 ) i małym rozmiarom (w porównaniu do gzip ) trafił do kilku programów ze świata uniksopodobnego . Do jądra Linux , dpkg i RPM systemy zawiera kod XZ, i wielu dystrybutorów oprogramowania jak kernel.org , Debian i Fedora używają teraz xz kompresji ich uwolnienia.
lzip : kolejna implementacja LZMA, głównie dla systemów uniksopodobnych, która bezpośrednio konkuruje z xz. Zawiera głównie prostszy format plików, a tym samym łatwiejsze odzyskiwanie błędów.
ZIPX : rozszerzenie formatu kompresji ZIP utworzone przez program WinZip począwszy od wersji 12.1. Może również używać różnych innych metod kompresji, takich jak BZip i PPMd .

LZHAM

LZHAM (LZ, Huffman, Arithmetic, Markov) to implementacja podobna do LZMA, która wymienia przepustowość kompresji na bardzo wysokie współczynniki i wyższą przepustowość dekompresji. Została umieszczona przez jej autora w domenie publicznej 15 września 2020 r.

Languages

In other projects