Algorytmy kompresji danych

Question

Zastanawiam się, czy ktoś ma listę algorytmów kompresji danych. Zasadniczo nic nie wiem o kompresji danych i miałem nadzieję dowiedzieć się więcej o różnych algorytmach i zobaczyć, które z nich są najnowsze i które jeszcze nie zostały opracowane na wielu układach ASIC.

Mam nadzieję, że do realizacji ASIC kompresji danych, który jest niezależny od typu danych pochodzących w (audio, wideo, zdjęć, itp.)

Jeśli moje pytanie jest zbyt otwarty zakończony, proszę dać mi znać i zrewiduję. Dziękujemy

Answer 1

Istnieje mnóstwo algorytmów kompresji. To, czego potrzebujesz, to bezstratny algorytm kompresji. Bezstratny algorytm kompresji kompresuje dane w taki sposób, że można je zdekompresować, aby osiągnąć dokładnie to, co podano przed kompresją. Przeciwieństwem byłby algorytm kompresji stratnej. Kompresja stratna może usunąć dane z pliku. Obrazy PNG używają bezstratnej kompresji, podczas gdy obrazy JPEG mogą i często wykorzystują kompresję stratną.

Niektóre z najbardziej znanych algorytmów kompresji obejmują:

• RLE
• Huffman
• LZ77

archiwa ZIP użyć kombinacji kodowania Huffmana i LZ77 dać szybką kompresję i czasy dekompresji i dość dobre kompresja ra tios.

LZ77 jest w dużym stopniu uogólnioną formą RLE i często przynosi znacznie lepsze wyniki.

Huffman pozwala najbardziej powtarzającym się bajtom reprezentować najmniejszą liczbę bitów. Wyobraźmy sobie plik tekstowy, który wyglądał tak:

aaaaaaaabbbbbcccdd 

Typowa implementacja Huffman skutkowałoby poniższej mapie:

Bits Character 
    0   a 
    10   b 
110   c 
1110   d 

Więc plik zostanie sprężony do tego:

00000000 10101010 10110110 11011101 11000000 
             ^^^^^ 
           Padding bits required 

18 bajtów zejść do 5. Oczywiście tabela musi być zawarta w pliku. Ten algorytm działa lepiej z większą ilością danych: P

Alex Allain ma a nice article na algorytmie kompresji Huffmana, jeśli Wiki nie jest wystarczający.

Możesz poprosić o więcej informacji. Ten temat jest dość szeroki.

Answer 2

Algorytm LZW lub Lempel Ziv to wielka bezstratna. Pseudokod tutaj: http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lzw.html

Answer 3

Istnieje bardzo dużo algorytmów kompresji danych. Jeśli szukasz czegoś encyklopedycznego, polecam Salomonowi i wsp., Który jest mniej więcej tak obszerny, jak ci się wydaje (i ma dobre rozdziały dotyczące zasad i praktyki kompresji danych). dobrze).

Moje najlepsze przypuszczenie jest takie, że kompresja ASIC jest zwykle zaimplementowana dla konkretnej aplikacji lub jako wyspecjalizowany element SoC, a nie jako samodzielny układ kompresji. Wątpię też, że szukanie "najnowszego i najlepszego" formatu kompresji jest sposobem na osiągnięcie tego celu - oczekiwałbym, że standaryzacja, dojrzałość i przydatność do określonego celu będą ważniejsze.

Answer 4

Mój artykuł A Survey Of Architectural Approaches for Data Compression in Cache and Main Memory Systems (permalink here) recenzuje wiele algorytmów kompresji, a także techniki ich używania w nowoczesnych procesorach. Przegląda zarówno algorytmy/techniki kompresji klasy komercyjnej, jak i komercyjnej, więc możesz znaleźć taki, który nie został jeszcze zaimplementowany w ASIC.

Answer 5

Oto niektóre algorytmy bezstratne (można doskonale odzyskania danych źródłowych przy użyciu poniższych):

• kodu Huffmana
• LZ78 (i LZW zmienności)
• LZ77
• kodowania arytmetycznego
• Sequitur
• prognozowanie z częściowym dopasowaniem (ppm)

Wiele dobrze znanych formatów, takich jak warianty użycia png lub gif lub ich kombinacje.

Z drugiej strony istnieją również algorytmy stratne (kompromisowa dokładność kompresji danych, ale często działa całkiem dobrze).

Aby dowiedzieć się więcej o kompresji danych, polecam https://www.elsevier.com/books/introduction-to-data-compression/sayood/978-0-12-809474-7. Jest to bardzo przystępny tekst wprowadzający. Trzecia edycja dostępna w pdf online.