Kompresja w Big Data: Typy i Techniki

\

Wprowadzenie

Ten artykuł omówi kompresję w kontekście Big Data, obejmując typy i metody kompresji. Wyjaśnię również, dlaczego i kiedy należy używać każdego typu i metody.

\

Czym jest kompresja?

Według ogólnej definicji angielskiej, kompresja odnosi się do zmniejszania czegoś, aby zajmowało mniejszą przestrzeń. W informatyce kompresja to proces zmniejszania danych do mniejszego rozmiaru. Dane w tym przypadku mogą być reprezentowane w plikach tekstowych, audio, wideo itp. Pomyśl o tym jak o wszystkim, co przechowujesz na dysku twardym komputera, jako o danych reprezentowanych w różnych formatach. Aby podać bardziej techniczną definicję, kompresja to proces kodowania danych w celu użycia mniejszej liczby bitów.

\ Istnieje wiele powodów kompresji danych. Najbardziej powszechnym i intuicyjnym powodem jest oszczędność miejsca do przechowywania. Inne powody wynikają z tego, że dane są mniejsze. Korzyści z pracy z mniejszymi danymi obejmują:

1. Szybszy czas przesyłania danych: Skompresowane dane mają mniejszy rozmiar i wymagają mniej czasu na przesłanie ze źródła do miejsca docelowego.
2. Zmniejszone zużycie przepustowości: Ten powód jest silnie związany z zaletą szybszego przesyłania danych. Skompresowane dane zużywają mniej przepustowości sieci, zwiększając tym samym przepustowość i zmniejszając opóźnienia.
3. Poprawiona wydajność systemów cyfrowych, które w dużym stopniu polegają na danych: Jest to widoczne w systemach, które polegają na przetwarzaniu danych. Systemy te wykorzystują kompresję w celu poprawy wydajności poprzez zmniejszenie objętości danych, które należy przetworzyć. Należy pamiętać, że może to być specyficzne dla systemu i będzie zależeć od zastosowania odpowiedniej techniki kompresji. Techniki kompresji zostaną omówione w dalszej części tego artykułu.
4. Efektywność kosztowa: Usługi w chmurze pobierają opłaty za przechowywanie danych. Dzięki wykorzystaniu mniejszej przestrzeni dyskowej wprowadzane są oszczędności kosztów, szczególnie w systemach Big Data.

\ Inne powody kompresji zależą od różnych technik i formatów kompresji. Niektóre algorytmy szyfrowania mogą być używane jako metoda kompresji. W ten sposób obejmuje to warstwę bezpieczeństwa dla wcześniej omówionych powodów kompresji danych. Dodatkowo, używanie powszechnych formatów kompresji zapewnia kompatybilność i możliwość rozszerzania do systemów zewnętrznych w celach integracyjnych.

\ Warto zauważyć, że powody kompresji brzmią również jak korzyści. Jednak kompresja nie jest pozbawiona kompromisów. Jednym z powszechnych kompromisów kompresji jest potrzeba dekompresji, która może być problematyczna dla systemów o ograniczonych zasobach. Inne kompromisy zależą od techniki kompresji i rodzaju używanych danych.

\

Typy kompresji

Aby omówić różne techniki używane do kompresji danych, najpierw podzielę kompresję na 2 główne kategorie. Ten artykuł następnie omówi techniki istotne dla każdej kategorii. Kompresję można ogólnie podzielić na kompresję stratną i bezstratną.

\ Jak nazwy już sugerują, techniki kompresji stratnej to techniki, które nie zachowują pełnej wierności danych. Mówiąc prościej, niektóre dane są odrzucane, ale nie na tyle, aby to, co reprezentują dane, stało się nierozpoznawalne. Dlatego kompresja stratna może oferować bardzo wysoki poziom kompresji w porównaniu do kompresji bezstratnej, która zostanie wkrótce przedstawiona.

\ Cechą kompresji stratnej jest to, że jest nieodwracalna, tj. po otrzymaniu skompresowanego pliku nie można przywrócić surowych danych z ich oryginalną wiernością. Niektóre pliki i formaty plików nadają się do kompresji stratnej. Jest ona zwykle używana dla obrazów, dźwięku i wideo. Na przykład obrazy w formacie JPEG dobrze nadają się do kompresji, a kompresując obraz JPEG, twórca lub edytor może wybrać, ile strat wprowadzić.

\ Z drugiej strony, kompresja bezstratna jest odwracalna, co oznacza, że po kompresji wszystkie dane są zachowane i w pełni przywracane podczas dekompresji. Oznacza to, że kompresja bezstratna nadaje się do plików tekstowych, a w świecie hurtowni danych i domów danych byłaby to jedyny istotny typ do wykorzystania. Niektóre formaty plików audio (FLAC i ALAC) i obrazów (GIF, PNG itp.) dobrze działają z tym typem kompresji.

Wybór metody

Nie ma ogólnie najlepszej metody kompresji. W wyborze odpowiedniej metody biorą udział różne czynniki w każdym przypadku z osobna. Aby to zilustrować przykładami, inżynier danych w branży finansowej pracujący nad przechowywanymi danymi tabelarycznymi będzie zazwyczaj używał kompresji bezstratnej ze względu na wpływ brakujących danych na tworzenie dokładnych raportów. Alternatywnie, kompresja stratna może być właściwym rozwiązaniem w optymalizacji strony internetowej z wieloma obrazami poprzez kompresowanie obrazów i zmniejszanie elementów do załadowania, czyniąc stronę lżejszą. Dlatego kluczowe jest przeprowadzenie oceny w celu określenia najbardziej odpowiedniej metody kompresji zgodnej z wymaganiami biznesowymi.

Techniki kompresji

Ta sekcja obejmie tylko powszechne techniki kompresji zarówno dla kompresji stratnej, jak i bezstratnej. Należy pamiętać, że nie jest to w żaden sposób wyczerpujące. Ponadto omawiane techniki mogą mieć niewielkie odmiany w celu poprawy ich wydajności, co jest poparte różnymi badaniami.

Techniki kompresji bezstratnej

Trzy powszechne techniki bezstratne to kodowanie długości serii (RLE), kodowanie Huffmana i techniki Lempel-Ziv-Welch.

\ Kodowanie długości serii: RLE opiera się na kodowaniu danych w taki sposób, że zastępuje sekwencje powtarzających się danych pojedynczym elementem danych i liczbą tego elementu danych. Jest skuteczne dla długich serii powtarzających się danych. Również zestawy danych, które mają wymiary (pola) posortowane od niskiego poziomu do wysokiego poziomu kardynalności, korzystają z RLE.

\ Na przykład, weź prosty ciąg jak AAAAABBCDDD. RLE kompresuje dane do A(5)B(2)C(1)D(3). Aby być bardziej praktycznym, weź tabelę na obrazku poniżej.

\ Rysunek 1 - przed RLE. Ważne jest, aby zaobserwować, że poziom kardynalności rośnie w polach od lewej do prawej

Rysunek 2 - Po RLE

Ponieważ RLE zależy od serii powtarzających się pól, a w drugim przykładzie kardynalności i kolejności sortowania danych, rekord Mouse w kolumnie przedmiotów nie może być skompresowany tylko do Mouse (3), ponieważ poprzednia kolumna dzieli wszystkie wartości na IT, Mouse i HR, Mouse. Niektóre formaty plików są kompatybilne z RLE, takie jak formaty plików bitmapowych jak TIFF, BMP itp. Pliki Parquet również obsługują RLE, co czyni je bardzo przydatnymi w nowoczesnych domach danych wykorzystujących przechowywanie obiektów jak S3 lub GCS.

\ Kodowanie Huffmana: Opiera się na modelowaniu statystycznym, które przypisuje kody o zmiennej długości do wartości w surowych danych na podstawie częstotliwości, z jaką występują w surowych danych. Reprezentacja tego modelowania może być nazywana drzewem Huffmana, które jest podobne do drzewa binarnego. To drzewo jest następnie używane do utworzenia kodu Huffmana dla każdej wartości w surowych danych. Algorytm priorytetowo koduje najczęstsze wartości w najmniejszej możliwej liczbie bitów.

\ Weźmy te same dane użyte w przykładzie RLE AAAAABBCDDD. Odpowiednie drzewo Huffmana wygląda tak.

\ Drzewo Huffmana

Z drzewa widzimy, że litera A jest reprezentowana przez 0, podobnie D jest reprezentowane przez 10. W porównaniu do liter B: 111 i C:110, obserwujemy, że A i D są reprezentowane przez mniej bitów. Jest tak, ponieważ mają wyższą częstotliwość; stąd algorytm Huffmana reprezentuje je przez konstrukcję mniejszą liczbą bitów. Wynikowe skompresowane dane stają się 00000111111110101010.

\ Kodowanie Huffmana używa reguły prefiksu, która stwierdza, że kod reprezentujący znak nie powinien być obecny w prefiksie żadnego innego kodu. Na przykład, prawidłowy kod Huffmana nie może mieć liter c i d reprezentowanych za pomocą C: 00 i D: 000, ponieważ reprezentacja C jest prefiksem D.

\ Aby zobaczyć to w akcji, Computer Science Field Guide ma Generator drzewa Huffmana, z którym możesz poeksperymentować.

\ Kodowanie Lempel–Ziv–Welch: Zostało stworzone przez Abrahama Lempela, Jacoba Ziva i Terry'ego Welcha w 1984 roku i jest nazwane od twórców, oczywiście 😅. Podobnie jak RLE i kodowanie Huffmana, LZW dobrze działa z danymi, które zawierają wiele powtarzających się danych. Algorytm LZW jest oparty na słowniku i tworzy słownik zawierający pary klucz-wartość często spotykanych wzorców w surowych danych. Taki słownik może być również określany jako tabela kodów. Używając ilustracji do wyjaśnienia, jak działa ta technika, weźmy nasze surowe dane reprezentowane przez ABBABABABA. Po przejściu przez algorytm przy użyciu konfiguracji A-Z jako możliwych wartości, wynikowa tabela kodów wygląda następująco:

\ Tabela kodów LZW

Z powyższej tabeli kodów istnieje para klucz-wartość dla wszystkich liter A-Z oraz pary klucz-wartość dla wzorców takich jak AB, BB, BA i ABA. Dzięki krótszej reprezentacji tych wzorców algorytm LZW może kompresować surowe dane, kodując je na mniej bitów. Stąd, używając tabeli kodów wygenerowanej z tego wejścia, skompresowana wersja to 0 1 1 26 29 28. Kluczowe jest zauważenie spacji w skompresowanych danych. Można o nich myśleć jak o końcu znaku, aby dekoder nie interpretował 1,0 jako 10, ponieważ oznaczają one różne rzeczy.

\ LZW jest zwykle ogólnego przeznaczenia i szeroko stosowany dzisiaj. Jest zintegrowany z wieloma systemami operacyjnymi opartymi na Unix/Linux za komendą powłoki compress. Również powszechne formaty plików kompatybilne z LZW to GIF, TIFF i PDF. Inne zastosowania kompresji LZW można zobaczyć w dziedzinie przetwarzania języka naturalnego, jak omówiono w tym artykule na temat tokenizacji w NLP.

\ RLE, kodowanie Huffmana i kodowanie LZW to tylko powszechne przykłady. Techniki kompresji bezstratnej wykraczają poza te trzy (3) opisane powyżej. Inne techniki obejmują DEFLATE, który używa kombinacji kodowania Huffmana i LZW - konkretnie LZ77.

Techniki kompresji stratnej

W tej sekcji przyjrzymy się dwóm typom kompresji stratnej. Przypominamy, że kompresja stratna wprowadza stratę do oryginalnych danych, co oznacza, że nie wszystkie dane są zachowane.

\ Dyskretna transformata kosinusowa (DCT): Ta metoda kompresji jest używana głównie w plikach audio, obrazów i wideo i jest również powszechnie nazywana kompresją blokową. Używa funkcji matematycznej - funkcji kosinusowej, jak sama nazwa wskazuje - do konwersji bloków oryginalnych danych na częstotliwości. Bloki danych to zwykle macierz 8x8, 4x4 i tak dalej, w tej kolejności wielkości.

\ Kompresja pojawia się podczas radzenia sobie z wysokimi częstotliwościami występującymi w danych, gdy surowe dane są przekształcane w dziedzinę częstotliwości przy użyciu funkcji matematycznej. Ogólny proces używania DCT do kompresji to:

• Podział surowych danych na fragmenty. Na przykład w kompresji obrazu może to być 8x8 pikseli.
• Zastosowanie funkcji matematycznej do konwersji fragmentów danych na częstotliwości. To spowoduje powstanie pewnych wysokich częstotliwości i niskich częstotliwości.
• Wysokie częstotliwości są następnie zmniejszane lub usuwane w zależności od akceptowalnego stopnia straty, który jest się gotów wprowadzić. To jest miejsce, gdzie naprawdę staje się kompresją stratną.
• Aby przekonwertować z powrotem na reprezentowalne dane, wszystkie pozostałe częstotliwości są przepuszczane przez odwrotną dyskretną transformatę kosinusową - IDCT - w celu przywrócenia danych z częstotliwości.

\ DCT jest szeroko stosowany w różnych dziedzinach dzisiaj, nie tylko w kompresji, ale także w przetwarzaniu sygnałów. Powszechne formaty plików kompatybilne z DCT to JPEG (obrazy), MP3 (audio) i MPEG (wideo). Dodatkowo, DCT może osiągnąć wysokie współczynniki kompresji, co czyni go odpowiednim dla systemów cyfrowych z wieloma obrazami, jak strony internetowe w Internecie.

\ Kompresja fraktalna: Fraktal to samopowtarzający się nieskończony wzór, który powtarza się w różnych skalach. Gdy jest oglądany z dowolnego punktu na skali, wzór wygląda podobnie. Ponieważ wzory są podobne w dowolnej skali, kompresja fraktalna zmniejsza skalę „dużych" fraktali, aby zmniejszyć rozmiar danych.

\ Przykłady fraktali

Kompresja fraktalna została wprowadzona przez Michaela Barnsleya w latach 80. XX wieku. Ogólny pomysł wykorzystujący obraz polega na tym, że jeśli obraz zawiera kilka części, które wyglądają podobnie, dlaczego przechowywać je dwa razy? Aby to zrobić, kompresja fraktalna wykonuje następujące czynności:

• Dzieli obraz na nieprzekrywające się bloki znane jako bloki zakresu. Mogą to być bloki zakresu 8x8, 16x16 pikseli itp.
• Skanuje obraz w poszukiwaniu samopowtarzających się wzorców (wzorców fraktalnych). Używając bloków zakresu, algorytm znajduje większe sekcje obrazu, które są podobne do tych bloków zakresu. Te większe sekcje są nazywane blokami domeny.
• Funkcja transformacji jest następnie stosowana do bloku domeny, aby przybliżyć bloki zakresu. Te funkcje transformacji to funkcje matematyczne, takie jak skalowanie, translacja, rotacja itp. Mogą być również nazywane transformacjami. Te transformacje są nazywane kodami fraktalnymi w odniesieniu do kompresji fraktalnej.
• Dane są następnie kodowane do tych funkcji transformacji. Zamiast przechowywać dane piksel-piksel, przechowywane są transformacje. Te transformacje są regułami opisującymi, jak zrekonstruować obraz z bloków domeny.

\ Za pomocą kodów fraktalnych obraz jest rekonstruowany przy użyciu procesu iteracyjnego. Ten proces może być kosztowny obliczeniowo, ale kompresja fraktalna może osiągnąć wysoki współczynnik kompresji w porównaniu do innych technik kompresji. Ze względu na jej poleganie na samopowtarzających się wzorach, działałaby lepiej na danych, które mają takie samopowtarzające się wzory. Przykładami byłyby fotografie krajobrazowe (obrazy natury) i obrazy DNA.

\ Istnieją inne techniki kompresji stratnej, takie jak dyskretna transformata falkowa, kwantyzacja. Te techniki są zwykle używane w plikach obrazów, audio i wideo i nadają się do niektórych typów lub formatów plików - JPEG, MP3 - dla każdego typu pliku.

\ Kompresja stratna ma ogólnie wyższe współczynniki kompresji niż kompresja bezstratna i czasami oczekuje, że użytkownik zna ilość straty do wprowadzenia wcześniej. Istotne jest podkreślenie, że wybór metody i techniki kompresji zależy od kilku czynników. W centrum tych czynników znajduje się format danych i pożądany rezultat.

TL;DR

Ogólnie rzecz biorąc, ten post omawia kompresję w świecie danych. Opiera się mocno na istniejącej wiedzy w informatyce i teorii informacji. Kompresować oznacza zmniejszyć objętość zajmowaną przez podmiot, a w dziedzinie danych objętość odnosi się do przestrzeni dyskowej. Kompresja w systemach cyfrowych ma wiele zalet, gdy jest wykonywana prawidłowo. Oczywiste jest, że zmniejsza przestrzeń i daje możliwość przechowywania większej ilości danych. Inne zalety obejmują szybszą transmisję, mniejsze zużycie przepustowości i ogólną poprawę wydajności wspomnianego systemu. Pamiętaj, to jest wtedy, gdy jest wykonywane prawidłowo.

\ Aby wykorzystać zalety kompresji, kluczowe jest wiedzieć, jaki typ zastosować. Kompresja to albo kompresja stratna, albo bezstratna. Kompresja stratna wprowadza stratę w oryginalnych danych, która jest zwykle nieodwracalna, podczas gdy kompresja bezstratna kompresuje dane i zachowuje wszystkie informacje zawarte w oryginalnych danych. Ponadto istnieje dyskurs na temat hybrydowych typów kompresji, ale myślę, że kombinacja stratnej i bezstratnej to po prostu stratna. Daj mi znać, co myślisz w komentarzach.

\ Na koniec wprowadzono różne techniki dla kompresji zarówno stratnej, jak i bezstratnej. Lista technik i wyjaśnień tych technik nie jest ani wyczerpująca, ani kompleksowa. Uważam je tylko za dobry początek w daniu ci pojęcia o tym, jak działa każda technika. Podsumowując, dodałem dodatkowe zasoby, aby pomóc ci zbadać dalej i czytać głębiej o kompresji w big data.

Dodatkowe zasoby

Wideo: Podstawy Data Lake - kodowanie RLE z Parquet w praktyce

Artykuł: Przegląd technik kompresji danych

Artykuł: techniki kompresji bezstratnej

Zwięzłe wprowadzenie do kompresji danych autorstwa Davida Salomona

Artykuł: Studium różnych technik kompresji danych

Post na blogu: Kompresja w otwartych formatach plików

Artykuł: Otwarte formaty plików

Artykuł: Kompresja w bazach danych

Kompresja stratna dla danych genomowych (RNA)

\