Kompresja bezstratna
Kompresja bezstratna danych to proces przekształcenia pierwotnej reprezentacji sekwencji danych w reprezentację o mniejszej liczbie bitów
Bezstratna jest kompresją nie dopuszczającą do utraty treści.
Dane po skompresowaniu i późniejszym zdekompresowaniu są identyczne. Podstawową zasadą konstrukcji algorytmów jest twierdzenie o zliczaniu.
Twierdzenie o zliczaniu
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.
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ć.
Metody kompresji bezstratnej
Kodowanie Huffmana
Jedna z najprostszych i łatwych w implementacji metod kompresji bezstratnej. Została opracowana w 1952 roku przez Amerykanina Davida Huffmana.
Algorytm Huffmana nie należy do najefektywniejszych obliczeniowo systemów bezstratnej kompresji danych, dlatego też praktycznie nie używa się go samodzielnie. Często wykorzystuje się go jako ostatni etap w różnych systemach kompresji, zarówno bezstratnej, jak i stratnej, np. MP3 lub JPEG. Pomimo że nie jest doskonały, stosuje się go ze względu na prostotę oraz brak ograniczeń patentowych. Jest to przykład wykorzystania algorytmu zachłannego
Założenia algorytmu:
- Symbolom występującym częściej odpowiadają krótsze słowa niż symbolom występującym rzadziej,
- Dwa najrzadziej występujące symbole mają w kodzie słowa kodowe tej samej długości,
- Dwa najrzadziej występujące symbole mają w kodzie słowa kodowe różniące się tylko ostatnim bitem.
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.
Ideą tego kodu jest przedstawienie ciągu wiadomości jako podprzedziału przedziału jednostkowego [0,1) wyznaczonego rekursywnie na podstawie prawdopodobieństw wystąpienia tychże wiadomości generowanych przez źródło.
Ciąg kodowy reprezentujący kodowane wiadomości jest binarnym zapisem wartości z wyznaczonego w ten sposób przedziału.
Znajdowanie tej liczby polega na zwiększaniu jej precyzji przez stopniowe zawężanie przedziału, przy użyciu prawdopodobieństwa aktualnie przetwarzanej litery.