Kompresja danych

Ten artykuł od 2021-02 zawiera treści, przy których brakuje odnośników do źródeł. Należy dodać przypisy do treści niemających odnośników do źródeł. Dodanie listy źródeł bibliograficznych jest problematyczne, ponieważ nie wiadomo, które treści one uźródławiają. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Kompresja danych (ang. data compression) – zmiana sposobu zapisu informacji w celu zmniejszenia redundancji i tym samym objętości zbioru. Innymi słowy chodzi o wyrażenie tego samego zestawu informacji, lecz za pomocą mniejszej liczby bitów.

Działaniem przeciwnym do kompresji jest dekompresja.

Kompresja stratna i bezstratna

Kompresja dzieli się na bezstratną – w której z postaci skompresowanej można odzyskać identyczną postać pierwotną oraz stratną – w której takie odzyskanie jest niemożliwe, jednak główne właściwości zostają zachowane. Np. jeśli kompresowany jest obrazek, nie widać znaczących różnic w stosunku do oryginału. Pomimo to może się już nie nadawać do dalszej przeróbki czy do wydruku, gdyż w tych zastosowaniach wymaga się zachowania innych właściwości.

Algorytmy kompresji dzieli się na algorytmy zastosowania ogólnego oraz algorytmy do danego typu danych. Z definicji nie istnieją algorytmy kompresji stratnej zastosowania ogólnego, ponieważ dla różnych typów danych konieczne jest zachowanie różnych właściwości. Na przykład kompresja dźwięku używa specjalnego modelu psychoakustycznego, który nie ma sensu w zastosowaniu do obrazu, poza bardzo ogólnymi przesłankami dotyczącymi sposobu postrzegania rzeczywistości przez człowieka.

Większość algorytmów bezstratnych to algorytmy zastosowania ogólnego oraz ich drobne przeróbki, dzięki którym lepiej działają z określonymi typami danych. Nawet drobne poprawki mogą znacząco polepszyć wyniki dla pewnych typów danych.

Algorytmy kompresji stratnej często jako ostatniej fazy używają kompresji bezstratnej. W takim przypadku poprzednie fazy mają za zadanie nie tyle kompresować, ile przygotować dane do łatwiejszej kompresji.

Modele prawdopodobieństw

Algorytmy kompresji używają pewnych modeli prawdopodobieństwa. Są generalnie 2 systemy: modele statyczne i modele adaptywne.

Modele statyczne, jeśli nie są znane z góry, są przesyłane przed właściwymi danymi. Koszt przesłania takiego modelu jest bardzo duży i wymusza stosowanie wyłącznie bardzo prostych modeli. To powoduje, że modele statyczne rzadko są stosowane. Kompresory są tutaj zwykle znacznie bardziej złożone niż dekompresory.

Modele adaptywne są tworzone w miarę przetwarzania danych. Kompresor i dekompresor używają tego samego algorytmu do nanoszenia zmian na model w miarę napływania danych. W tym przypadku złożoność kompresorów i dekompresorów jest zwykle, choć nie zawsze, podobna. Wadą modeli adaptywnych jest to, że na początku model ten znacznie odbiega od optymalnego. Jednak możliwość stosowania modeli o dowolnej złożoności, możliwość używania różnych modeli do różnych obszarów kompresowanych danych oraz brak potrzeby przesyłania modelu sprawia, że właściwie całkowicie wyparły one modele statyczne.

Czasami, np. w algorytmie PNG, stosowane są modele pośrednie.

Algorytmy kompresji bezstratnej

• Kodowanie Huffmana
• Kodowanie arytmetyczne
• Kodowanie Shannona, Shannona-Fano
• LZ77, LZSS, LZP, LZX
• LZ78, LZW, LZMW, LZAP
• LZMA
• LHA
• PNG
• RLE
• PPM
• Deflate
• Bzip2 (oparty m.in. o transformaty Burrowsa-Wheelera i Move To Front)

Algorytmy wykorzystywane w kompresji stratnej

• Kodowanie predykcyjne (DPCM, ADPCM)
• Kodowanie transformatowe
• Kodowanie podpasmowe
• Kompresja falkowa
• Kwantyzacja wektorowa
• Matching pursuit
• Kompresja fraktalna
• Kodowanie parametryczne

Systemy kompresji stratnej obrazu

• JPEG
• JPEG2000
• MPEG-1, MPEG-2, MPEG-4
• H.261, H.263
• Quicktime
• Windows Media Video (wmv)
• RealVideo

Systemy kompresji stratnej dźwięku

• Vorbis (Ogg)
• A/52 (AC3)
• MP1, MP2, MP3
• AAC
• Musepack (mpc)
• Windows Media Audio (wma)
• ATRAC (używany w Minidisc)

Standardowe zestawy danych do testowania algorytmów kompresji

• Calgary Corpus
• Lenna

Zobacz też

Zobacz hasło kompresja w Wikisłowniku

• plik skompresowany
• program do kompresji plików

Linki zewnętrzne

• Standardowe Techniki Kompresji. dsp.agh.edu.pl. [zarchiwizowane z tego adresu (2013-12-04)]. (materiały dydaktyczne AGH)