Kompresja bezstratna

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Kompresja bezstratna (ang. lossless compression) – metoda kompresji informacji do postaci zawierającej zmniejszoną liczbę bitów, gwarantująca możliwość odtworzenia informacji z postaci skompresowanej do identycznej postaci pierwotnej.

Generator liczb pseudolosowych (Pseudo-Random Number Generator, lub PRNG) to program lub podprogram, który na podstawie niewielkiej ilości informacji (ziarno, zarodek, ang. seed) generuje deterministycznie ciąg bitów, który pod pewnymi względami jest nieodróżnialny od ciągu uzyskanego z prawdziwie losowego źródła.Kodowanie arytmetyczne – metoda kodowania źródłowego dyskretnych źródeł sygnałów, stosowana jako jeden z systemów w bezstratnej kompresji danych. Została wynaleziona przez Petera Eliasa około 1960 roku.

Najważniejszym twierdzeniem o kompresji bezstratnej jest twierdzenie o zliczaniu.

Twierdzenie o zliczaniu (counting theorem)[ | edytuj kod]

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.

Znaki pisarskie – znaki stanowiące pismo, symbole graficzne oznaczające dźwięki mowy lub znaczenia myślowe. Ciąg znaków pisarskich nazywamy tekstem.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.

Dowód:

Załóżmy, że dana funkcja kompresuje choć jedną 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ć.

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.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).

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).


  • Podstrony: 1 [2] [3]




    Warto wiedzieć że... beta

    Kompresja stratna — metoda 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.
    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.
    Liczba losowa – liczba otrzymana jako rezultat działania określonego mechanizmu losującego (na przykład przy rzucaniu kostką do gry, tasowaniu kart, ciągnieniu losów z urny itp.). Można je także uzyskiwać za pomocą specjalnie skonstruowanych maszyn lub przy użyciu specjalnych programów komputerowych (generator liczb losowych).
    Kodowanie Shannona – metoda kodowania, którą Claude E. Shannon przedstawił jako jeden z dowodów swojego podstawowego twierdzenia o kodowaniu.
    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.
    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.

    Reklama