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
Algorytmy wykorzystywane w kompresji stratnej
Systemy kompresji stratnej obrazu
Systemy kompresji stratnej dźwięku
Standardowe zestawy danych do testowania algorytmów kompresji
Zobacz też