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 (kompresja bezstratna, która jest odwracalna).
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) Zstd Brotli
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 oraz standardowe testowe obrazy do porównywania algorytmów kompresji Calgary Corpus Canterbury Corpus Silesia Corpus Lenna
Zobacz też
plik skompresowany program do kompresji plików
Bibliografia Dominik M. Matusiak, "A Review of Classical Lossless Data Compression Algorithms and Their Contemporary Relevance", Biuletyn WAT 74 (2): 31-40, 2025
Linki zewnętrzne (materiały dydaktyczne AGH)