Po obejrzeniu serialu HBO "Silicon Valley" zawsze interesowały mnie algorytmy kompresji. Richard Hendricks i jego algorytm kompresji do środka są oczywiście fałszywi, ale po intensywnym googlowaniu odkryłem, że w rzeczywistości istnieje taki geniusz algorytmów kompresji.
Yann Collet wynalazł algorytm kompresji LZ4 w 2011 roku. Oczywiście algorytm LZ4 nie jest tak zaawansowany jak middle out, ale jest znany z niezwyciężonej prędkości kompresji i szybszej dekompresji, gdy można zagwarantować określoną szybkość kompresji.
Nie będę tu szczegółowo opisywał oceny jego szybkości kompresji, jeśli jesteś zainteresowany, możesz przeczytać ten artykuł porównawczy:Logowanie do linku jest widoczne.
Załączony jest także adres github LZ4:Logowanie do linku jest widoczne.
Ten artykuł koncentruje się na wyjaśnieniu zasady algorytmu kompresji LZ4. Wielki bóg napisał wcześniej wyjaśnienie algorytmu LZ4:Logowanie do linku jest widoczne.Ale kiedy wcześniej się uczyłem, uznałem, że ten artykuł nie jest zbyt przyjazny dla nowicjuszy, więc zacząłem kolejny artykuł dla takich jak ja.
Jeśli podsumować to w jednym zdaniu, LZ4 to LZ77, który przechowuje słownik z tabelą skrótów o rozmiarze 16k i upraszcza wyszukiwanie.
LZ4 to bezstratny algorytm kompresji, który oferuje prędkość kompresji > 500 MB/s na rdzeń, którą można skalować za pomocą procesorów wielordzeniowych. Posiada niezwykle szybkie dekodery z prędkością kilku GB/s na rdzeń, często osiągając limity RAM w systemach wielordzeniowych.
Prędkość można dynamicznie regulować, wybierając czynnik "przyspieszenia", który zamienia stopień sprężania na wyższą prędkość. Z drugiej strony, dostępna jest również pochodna o wysokiej kompresji, LZ4_HC zwiększająca kompresję kosztem czasu CPU. Wszystkie wersje mają taką samą szybkość dekompresji.
Czym więc jest LZ77?
Kompresja i zasada LZ77
LZ77 to algorytm stosujący słownik do kompresji. Mówiąc prosto, chodzi o to, by program obserwował (patrząc w słownik), czy aktualnie widoczne dane są zdublowane z poprzednim, a jeśli tak, zapisujemy odległość (przesunięcie) i długość zduplikowanych pól, aby zastąpić zduplikowane pola i skompresować dane.
odniesienieLogowanie do linku jest widoczne.
Dla ciągu liter A A B C B B A B C, gdy odczytane jest drugie A, program zapisuje (1,1) (1 cyfrę względem poprzedniej, długość 1), a podobnie, gdy odczytane jest drugie B, program zapisuje (2,1) (odległość 2, długość 1).
Ale jeśli ciąg jest dłuższy, a program cały czas zapisuje dane do słownika, wyszukiwanie zduplikowanych pól staje się niezwykle czasochłonne, ponieważ w najgorszym przypadku program przechodzi przez cały słownik przy każdym przeczytanym nowym literze. LZ77 wykorzystuje metodę okna przesuwnego do rozwiązania tego problemu.
Podobnie jak w przypadku TCP z przesuwanym oknem, okno przesuwne może zmniejszyć obszar pamięci podręcznej, aby uniknąć przetwarzania zbyt dużej ilości danych buforowanych jednocześnie. W LZ77 słownik nie zwiększa się cały czas, lecz odrzuca pierwsze znaki dodane do słownika, gdy przekraczają maksymalny rozmiar określony przez słownik, aby zapewnić, że rozmiar słownika zawsze pozostaje na określonym maksymalnym poziomie.
Załóżmy, że długość słownika wynosi 3
| Słownik |
| A | A B C B B A B C
Wyjście (0,0,A)
| A A | B C B B A B C
Wyjście(1,1)
| A A B | C B B A B C
Wyjście (0,0,B)
A | A B C | B B A B C
Wyjście (0,0,C)
A A | B C B | B A B C
Wyjście(2,1)
Druga część okna przesuwnego to pamięć podręczna do przeszukiwania (bufor look ahead nie ma oficjalnego tłumaczenia). Pamięcią podręczną do przeszukiwania jest nieskompresowana część długości najbliższa słownikowi. Algorytm LZ77 dopasuje najdłuższy ciąg znaku w tej części znaku, który jest taki sam jak słownik. Poprzedni przykład można traktować jako bufor look ahead o wartości 1.
Załóżmy, że długość słownika wynosi 5, a rozmiar pamięci podręcznej do przeszukiwania to 3
| Słownik | Look Ahead buffer |
A | A B C B B | A B C |
Wyjście(5,3)
Najdłuższy ciąg, który pasuje, to ABC
Pełny proces kompresji:
Załóżmy, że długość słownika wynosi 5, a rozmiar pamięci podręcznej do przeszukiwania to 3
| Słownik | Look Ahead buffer |
| A A B | C B B A B C
Wyjście (0,0,A)
| A | A B C | B B A B C
Wyjście(1,1)
| A A | B C B | B A B C
Wyjście (0,0,B)
| A A B | C B B | A B C
Wyjście (0,0,C)
| A A B C | B B A | B C
Wyjście(2,1)
| A A B C B | B A B | C
Wyjście(1,1)
A | A B C B B | A B C |
Wyjście(5,3)
A A B C | B B A B C | 。。。 |
Nie ma potrzeby zapisywania słownika w pliku wyjściowym kompresora, ponieważ program dekompresyjny przywraca słownik, dopasowując jednostki wyjściowe.
Proces dekompresji
Jedną z wielkich zalet algorytmu LZ77 jest jego bardzo szybka dekompresja.
Jeśli pierwsza jednostka dopasowania to (0,0,A), to A jest wyjściowe.
Druga jednostka dopasowania to (1,1), która kopiuje poprzedni bit w ciągu wyjściowym i generuje A, jeśli długość kopii wynosi 1.
。。。
Jeśli ostatnia jednostka dopasowania to (5,3), to spójrz na 5 bitów w ciągu kopiowania wyjściowym, a jeśli długość kopii wynosi 3, to wyjdź A, B, C.
Najczasochłoniejszym elementem kompresji algorytmu LZ77 jest znalezienie najdłuższego znaku pasującego w pamięci podręcznej do przeszukiwania w słowniku. Jeśli słownik i pamięć podręczna do przeszukania są zbyt krótkie, szanse na znalezienie dopasowania są niewielkie. Dlatego LZ4 zmieniło algorytm dopasowywania dla LZ77.
Po pierwsze, słownikiem algorytmu LZ4 jest tablica skrótu. Kluczem w słowniku jest ciąg 4-bajtowy, każdy klucz odpowiada tylko jednemu slocie, a wartość w slocie to pozycja tego ciągu.
Zamiast przeszukiwać cache, LZ4 odczytuje cztery bajty naraz z pliku wejściowego, a następnie szuka slotu odpowiadającego ciągowi znaków w tablicy skrótu, który dalej nazywa się obecnym ciągiem tekstów.
Jeśli osiągnąłeś ostatnie 12 znaków, umieść je bezpośrednio w pliku wyjściowym.
Jeśli w slocie nie przypisano wartości, oznacza to, że cztery bajty pojawiają się po raz pierwszy, dodaj te cztery bajty i pozycje do tabeli skrótów i kontynuuj wyszukiwanie.
Jeśli w slocie jest przypisanie, oznacza to, że znaleźliśmy dopasowaną wartość.
Jeśli wartość w slocie plus rozmiar okna suwaka < pozycja aktualnego znaku, pozycja dopasowania przekracza rozmiar bloku, a program aktualizuje wartość w slocie skrótu do pozycji aktualnego ciągu znaków.
LZ4 sprawdzi, czy wystąpił konflikt hashów. Jeśli 4 bajty w slocie nie są takie same jak aktualny ciąg tekstu, musi wystąpić konflikt skrótów. Własny xxhash autora jest również znany ze swojej efektywności, ale konflikty są nieuniknione. W przypadku konfliktu program aktualizuje wartość w slocie skrótu do aktualnej pozycji ciągu
Na koniec możemy potwierdzić, że dopasowanie jest prawidłowe, a program będzie dalej sprawdzał, czy kolejne znaki w ciągu dopasowania są takie same. Na koniec skopiuj wszystkie znaki z końca poprzedniego poprawnego dopasowania do początku tego poprawnego dopasowania do pliku skompresowanego i dodaj sekwencję dopasowania tego poprawnego dopasowania.
Collet wywołuje odpowiadające jednostki wyjściowe przez sekwencje LZ4 i tworzą one plik skompresowany LZ4. Szczegóły są następujące:
Token ma długość 1 bajt, przy czym pierwsze 4 słowa to dosłowna długość, a ostatnie 4 słowa to długość dopasowania. Jak wspomniano wcześniej, wszystkie znaki od końca poprzedniego poprawnego dopasowania do początku tego prawidłowego dopasowania zostaną skopiowane do pliku skompresowanego, te nieskompresowane pliki są dosłowne, a ich długość to dosłowna długość.
Dosłownie następuje odchylenie. Podobnie jak w LZ77, odchylenie i długość dopasowania odnoszą się do długości bieżącego ciągu względem jego dopasowania, a długość dopasowania to długość dopasowania bieżącego ciągu do tego samego ciągu w słowniku. W dekompresji trzeba przejść przez nią, aby znaleźć ciąg do kopiowania i długość do skopiowania. Wielkość odchylenia jest stała.
Na rysunku literal length+ i match length+ oznaczają, że jeśli literal lub match length 4 słowa w tokenie nie wystarczą, będą nadal rosnąć na odpowiadających pozycjach. 4 słowa mogą reprezentować 0-15, a jeśli jest ich więcej, dodaj jeden bajt, czyli 255 do rozmiaru, aż bajt będzie mniejszy niż 255. W długości dopasowania 0 oznacza 4 bajty.
Ostatnie 12 bajtów kończy się dosłownie, bo zostało skopiowane bezpośrednio.
Przyjrzyjmy się kodowi (python jest bardziej abstrakcyjny)
Podsumowanie Mimo tego wszystkiego, wciąż nie podsumowałem, dlaczego LZ4 jest tak szybki. Najpierw porównajmy wyszukiwanie słownikowe między LZ77 a LZ4. Natywny LZ77 wyszukuje słowniki, szukając największego dopasowania w pamięci podręcznej do przeszukiwania oraz w słowniku. Jest to problem znalezienia największego identycznego ciągu w dwóch ciągach. Jeśli nie użyjemy programowania dynamicznego, to w najgorszym przypadku musimy rozważyć wszystkie podciągi jednego ciągu i dopasować je do innego. Jeśli ×używamy programowania dynamicznego, użyjemy tabeli do przechowywania najdłuższego dopasowania w dynamice, co pozwoli nam ukończyć dopasowanie tylko w przypadku O(m*n). I to tylko dla pary pamięci podręcznych i słowników. W najgorszym przypadku, jeśli nie ma dopasowań, LZ77 będzie musiał liczyć (długość całego pliku – długość pamięci podręcznej do przeszukiwania) tyle samo takich problemów z dopasowaniem. LZ4 faktycznie wykorzystuje wyższy poziom programowania dynamicznego: przechowuje 4 bajty i ich pozycje w tablicy skrótów, a następnie za każdym razem dopasowuje nowe 4 bajty danych, aby sprawdzić, czy wartości w tablicy skrótów są poprawne. Po znalezieniu poprawnej wartości dopasowania, jeśli spojrzysz na dane uzupełniające obu zestawów wartości dopasowania, możesz również znaleźć jej najdłuższe dopasowanie. Ponieważ każdy klucz tabeli skrótów LZ4 odpowiada tylko 1 slotowi, praca nad znalezieniem, dodawaniem i modyfikowaniem tabeli skrótu wymaga tylko O(1). Jeśli po dopasowaniu zostanie znalezionych więcej dopasowań, potrzebne są kolejne porównania grupowe, ale w tym czasie porównania te zastąpią więcej czasu na wyszukanie tablicy skrótującej, więc całkowity czas działania algorytmu LZ4 to tylko O(n). Muszę podziwiać piękno algorytmu Colleta! Aby algorytm był jeszcze szybszy, Collet ustawia domyślny rozmiar tabeli skrótu na 16k, co zaleca się nie przekraczać 32k, aby można było umieścić go w pamięci podręcznej L1 niemal wszystkich procesorów (Intel). Wszyscy wiedzą, że szybkość i stosunek pamięci podręcznej L1 CPU są bardzo różne, więc nie dziwi fakt, że LZ4 leci szybko, nie wspominając o tym, że równanie haszujące używane w tabeli skrótów LZ4 jest nadal najszybszym xxhash. Oczywiście taki projekt ma swoje wady. Im mniejsza tablica skrótów, tym mniej kluczy ma. Oznacza to, że pojawią się kolejne konflikty hashów, co jest nieuniknione. A więcej kolizji skrótów oznacza mniej dopasowań. Mniejsza tabela haszująca oznacza też mniejsze okno przesuwane, co oznacza, że więcej dopasowań zostanie odrzuconych, bo są zbyt daleko. Mniej zapałek oznacza mniejszy stopień sprężania, dlatego LZ4 ma mniej wyraźny stopień sprężania. Looking Forward LZ4 oferuje szeroki zakres scenariuszy aplikacji. Podobnie jak middle out był stosowany w VR w Dolinie Krzemowej, LZ4 może zwiększyć wykorzystanie przepustowości, dostarczając mniej IO, kosztem bardzo niskiego opóźnienia dzięki bardzo szybkiej kompresji. Jest też mała spekulacja, jeśli CPU ma większą pamięć podręczną na poziomie 1, czy LZ4 może zwiększyć współczynnik kompresji bez kompromisu na szybkości?
Oryginał:Logowanie do linku jest widoczne. |
Opublikowano 03.01.2022 13:54:23
|
|
|
|
