Kompresja danych ( ang. data compression) – polega na zmianie sposobu zapisu informacji tak, aby zmniejszyć redundancję i tym samym objętość 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, które nas interesują, zostają zachowane, np. jeśli kompresowany jest obrazek, nie występują w postaci odtworzonej widoczne różnice w stosunku do oryginału. Pomimo to może się już nie nadawać zbyt dobrze np. 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
• LZ78 , LZW , LZMW , LZAP
• LZMA
• 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ż

• Dekompresja
• Kompresja bezstratna
• Kompresja stratna
• Program do kompresji plików