Kompresja bezstratna - Polski Serwis Naukowy

Kompresja bezstratna (ang. lossless compression) – ogólna nazwa metod kompresji informacji do postaci zawierającej zmniejszoną liczbę bitów, pod warunkiem że metoda ta gwarantuje możliwość odtworzenia informacji z postaci skompresowanej do identycznej postaci pierwotnej.

Najważniejszym twierdzeniem o kompresji bezstratnej jest:

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.

Run-Length Encoding (RLE, kodowanie długości serii) — prosta metoda bezstratnej kompresji danych, której działanie polega na opisywaniu ciągów tych samych liter (bitów, bajtów, symboli, pikseli itp.) za pomocą licznika powtórzeń (długości ciągu), a dokładniej przez pary: licznik powtórzeń litery, litera.

Twierdzenie o zliczaniu (counting theorem)

Niemożliwe jest skonstruowanie funkcji przekształcającej odwracalnie każdą informację na informację (czyli funkcji kompresji bezstratnej), która nie wydłuża jakiejś informacji o przynajmniej 1 bit, chyba że nie kompresuje ona żadnej informacji.

Słownik – zbiór słów lub wyrażeń ułożonych i opracowanych według jakiejś zasady. Dzieli się na artykuły hasłowe ułożone w porządku alfabetycznym, rzadko tematycznym.

LZMW - algorytm kompresji słownikowej będący modyfikacją algorytmu LZW, zaproponowany w 1985 roku przez V. Millera i M. Wegmana w artykule Variations on a theme by Ziv and Lempel.

Dowód:

Załóżmy, że dana funkcja kompresuje choć jedną dowolną wiadomość do długości N bitów z dowolnej większej długości. Jest X wiadomości o długości nie większej od N bitów. Jeśli żadna z wiadomości zawierających nie więcej niż N bitów nie została wydłużona, to w wyniku otrzymujemy przynajmniej X+1 wiadomości o długości nie większej niż N bitów. Ponieważ X jest skończone to X+1>X, a więc jest to sprzeczne z założeniem, że takich wiadomości jest X. Co należało udowodnić.

LZ78 – słownikowa metoda bezstratnej kompresji danych. Została opracowana w 1978 roku przez Jacoba Ziva i Abrahama Lempela i opisana w IEEE Transactions on Information Theory, w artykule pt. "Compression of individual sequences via variable-rate encoding" (str. 530-536).

Kompresja stratna — metody zmniejszania liczby bitów potrzebnych do wyrażenia danej informacji, które nie dają gwarancji, że odtworzona informacja będzie identyczna z oryginałem. Dla niektórych danych algorytm kompresji stratnej może odtworzyć informację w sposób identyczny.

Skonstruowanie funkcji, która wydłuża o nie więcej niż 1 bit jest trywialne. Dla dowolnej funkcji f(x), niech f'(x) będzie:

dla f(x) zawierającego mniej bitów niż x: f'(x)=<0,f(x)>

dla f(x) zawierającego więcej bitów niż x: f'(x)=<1,x>

dla f(x) zawierającego tyle samo bitów co x: f'(x)=<0,f(x)> lub f'(x)=<1,x> (nie ma to znaczenia)

Algorytmy kompresji bezstratnej

Algorytmy kompresji bezstratnej dobrze kompresują "typowe" dane, czyli takie w których występuje znaczna nadmiarowość informacji (redundancja).

Kodek jest skrótem od "koder/dekoder", co oznacza urządzenie lub program zdolny do przekształcania strumienia danych lub sygnału. Kodeki mogą zmienić strumień danych w formę zakodowaną (często w celu transmisji, składowania lub zaszyfrowania) lub odzyskać (odkodować) strumień danych z formy zakodowanej, by umożliwić ich odtwarzanie bądź obróbkę. Kodeki są często używane w wideokonferencjach oraz strumieniowaniu obrazu lub dźwięku.

PPM (ang. Prediction by partial matching – przewidywanie przez częściowe dopasowanie) to adaptacyjny algorytm kompresji danych oparty na kontekstowym modelowaniu statystycznym oraz predykcji. Algorytm PPM wykorzystuje układ symboli w strumieniu danych do przewidywania kolejnego symbolu. Zwykle predykcja opiera się na tworzeniu statystycznego rankingu występowania symboli. Pewna liczba poprzednich symboli wykorzystywanych w danym kroku do predykcji (n) jest określana jako rząd modelu PPM, który oznacza się jako PPM(n). Istnieją warianty algorytmu, w których rząd modelu nie jest z góry narzucany oznaczane jako PPM*. Jeżeli przewidywanie nie może zostać dokonane w oparciu o model o rzędzie n-tym to jego rząd jest zmniejszany o jeden. Proces jest powtarzany aż do uzyskania poprawnej predykcji lub, gdy strumień danych został wyczerpany. W tym momencie wykonywana jest ustalona predykcja.

Pewne rodzaje danych są bardzo trudne lub niemożliwe do skompresowania:

strumienie liczb losowych (niemożliwe do skompresowania)

strumienie liczb pseudolosowych (trudne do skompresowania, choć teoretycznie łatwe)

dane skompresowane za pomocą tego samego lub innego algorytmu (w praktyce trudne)

Najczęściej używane metody kompresji bezstratnej można podzielić na słownikowe i statystyczne, choć wiele metod lokuje się pośrodku:

LZP (P od predykacja) - metoda kompresji opracowana w 1996 roku przez Charlesa Blooma, będąca modyfikacją algorytmu LZ77, wykorzystująca kontekstowość danych - pewne ciągi występują z większym prawdopodobieństwem w sąsiedztwie innych. Mówiąc obrazowo, jeśli wcześniej po ciągu abc wystąpił ciąg def, i znów pojawił się ciąg abc, to jest szansa, że następnym ciągiem będzie def.

Redundancja (łac. redundantia – powódź, nadmiar, zbytek), inaczej nadmiarowość w stosunku do tego, co konieczne lub zwykłe. Określenie może odnosić się zarówno do nadmiaru zbędnego lub szkodliwego, niecelowo zużywającego zasoby, jak i do pożądanego zabezpieczenia na wypadek uszkodzenia części systemu.

metody słownikowe poszukują dokładnych wystąpień danego ciągu znaków, np. zastępują 'the ' krótszą ilością bitów niż jest potrzebna na zakodowanie 4 niezwiązanych znaków. Jednak znajomość symbolu 'the ' nie pociąga za sobą usprawnień w kompresowaniu 'they' czy 'then'.

metody statystyczne używają mniejszej ilości bitów dla częściej występujących symboli, w przypadku praktycznie wszystkich oprócz najprostszych metod, prawdopodobieństwa zależą od kontekstu. A więc np. dla 'h' występującego po 't' używają mniejszej ilości bitów niż dla innych znaków w tym kontekście.

Twierdzenie o zliczaniu (counting theorem)

Algorytmy kompresji bezstratnej

Popularne metody

Zobacz też

Linki zewnętrzne