Kompresja (informatyka)

Kompresja danych () – 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ż 

 plik skompresowany
 program do kompresji plików

Linki zewnętrzne 
  (materiały dydaktyczne AGH)