LZ4 (algorytm kompresji)

LZ4

Oryginalni autorzy	Yanna Colleta
Deweloperzy	Yanna Colleta
Pierwsze wydanie	24 kwietnia 2011 ( 24.04.2011 )
Wersja stabilna	1.9.4 / 16 sierpnia 2022 ( 2022-08-16 )
Magazyn	github.com/lz4/lz4 _ _ _
Napisane w	C
System operacyjny	Międzyplatformowe
Platforma	Przenośny
Typ	Kompresja danych
Licencja	Uproszczona licencja BSD
Strona internetowa	lz4 .github .io /lz4 /

Format ramki LZ4

magiczny numer	04 22 4d 18
Typ formatu	Kompresja danych
Strona internetowa	https://github.com/lz4/lz4/blob/master/doc/lz4_Frame_format.md

LZ4 to bezstratny algorytm kompresji danych , który koncentruje się na szybkości kompresji i dekompresji. Należy do rodziny schematów kompresji zorientowanej bajtowo LZ77 .

Cechy

Algorytmy LZ4 mają na celu zapewnienie dobrego kompromisu między szybkością a współczynnikiem kompresji. Zwykle ma mniejszy (tj. gorszy) współczynnik kompresji niż podobny LZO , który z kolei jest gorszy niż algorytmy takie jak DEFLATE . Jednak prędkość kompresji LZ4 jest podobna do LZO i kilka razy szybsza niż DEFLATE, podczas gdy prędkość dekompresji jest znacznie większa niż LZO.

Projekt

LZ4 wykorzystuje tylko etap dopasowywania słowników (LZ77) iw przeciwieństwie do innych popularnych algorytmów kompresji nie łączy go z etapem kodowania entropijnego (np. kodowanie Huffmana w DEFLATE).

Algorytm LZ4 przedstawia dane jako serię sekwencji. Każda sekwencja rozpoczyna się jednobajtowym tokenem podzielonym na dwa 4-bitowe pola. Pierwsze pole reprezentuje liczbę bajtów literałów, które mają zostać skopiowane na wyjście. Drugie pole reprezentuje liczbę bajtów do skopiowania z już zdekodowanego bufora wyjściowego (gdzie 0 oznacza minimalną długość dopasowania wynoszącą 4 bajty). Wartość 15 w jednym z pól bitowych wskazuje, że długość jest większa i że do długości należy dodać dodatkowy bajt danych. Wartość 255 w tych dodatkowych bajtach wskazuje, że należy dodać jeszcze jeden bajt. Stąd dowolne długości są reprezentowane przez serię dodatkowych bajtów zawierających wartość 255. Ciąg literałów następuje po tokenie i wszelkich dodatkowych bajtach potrzebnych do wskazania długości łańcucha. Po tym następuje przesunięcie, które wskazuje, jak daleko wstecz w buforze wyjściowym należy rozpocząć kopiowanie. Dodatkowe bajty (jeśli są) długości dopasowania znajdują się na końcu sekwencji.

Kompresję można przeprowadzić w strumieniu lub w blokach. Wyższe współczynniki kompresji można osiągnąć, inwestując więcej wysiłku w znalezienie najlepszych dopasowań. Skutkuje to zarówno mniejszą mocą wyjściową, jak i szybszą dekompresją.

Realizacja

Implementacja referencyjna w C autorstwa Yanna Colleta jest objęta licencją BSD. Istnieją porty i powiązania w różnych językach, w tym Java , C# , Rust i Python . System Apache Hadoop wykorzystuje ten algorytm do szybkiej kompresji. LZ4 został również zaimplementowany natywnie w jądrze Linuksa 3.11. Implementacje FreeBSD, Illumos, ZFS w systemie Linux i ZFS-OSX systemu plików ZFS obsługują algorytm LZ4 do kompresji w locie. Linux obsługuje LZ4 dla SquashFS od 3.19-rc1. LZ4 jest również zaimplementowany w nowszym Zstd autorstwa Yanna Colleta.

• LZ4 dostępny w rozszerzonej wersji 7zip.
• Lizard (wcześniej LZ5) to ulepszona implementacja LZ4 z bardzo szybką dekompresją powyżej 1000 MB na sekundę i jest również dostępna w 7-zip-zstd.

Linki zewnętrzne

• Oficjalna strona internetowa