mfranczak.pl

Algorytmy kompresji stratnej i bezstratnej

Kompresja danych – polega na zmianie sposobu zapisu informacji tak, aby zmniejszyć objętość zbioru. Innymi słowy chodzi o wyrażenie tego samego zestawu informacji, lecz za pomocą mniejszej liczby bitów.

Można obliczyć współczynnik kompresji

R=(Vk/Vnk)*100% <- wzór na to jak bardzo zmniejszyły sie dane w stosunku do oryginalnych

R=(1-Vk/Vnk)*100% <- ile miejsca zaoszczędziliśmy

Vk – dane skompresowane (w bajtach)
Vnk – dane nieskompresowane (w bajtach)

Rodzaje kompresji:
1. kompresja bezstratna
2. kompresja stratna

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 stratnej
Bazują na niedoskonałościach ludzkich zmysłów. Ludzkie oko nie dostrzega niewielkich zmian w zmianach kolorów albo w jednej chwili nie słyszymy wszystkich dźwięków. Algorytmy kompresji stratnej po porostu usuwają te informacje których w danej chwili nie widzimy albo nie słyszymy. Objętość pliku stosując kompresję stratną można zmniejszyć nawet dziesięciokrotnie.

Algorytmy kompresji bezstratnej dzielimy na statyczne i słownikowe.

Algorytmy statyczne bazują na takich faktach że np. znaki w tekście występują z różną częstotliwością.
W kodzie ASCII każdy znak zajmuję 8 bitów czyli 1 Bajt. Gdyby podzielić znaki na te które w polskich słowach występują częściej i rzadziej a nawet bardzo rzadko i przydzielić im odpowiednią długość bitów moglibyśmy zaoszczędzić dużo więcej miejsca. np.:
polskim literom które często występują w wyrazach przydzielimy po 3 bity a tym które występują rzadziej np. 8 bitów.
Prawda jest taka aby każdy znak dało się jednoznacznie zidentyfikować mogą wystąpić takie znaki których długość przekroczy 8 bitów ale całość kompresji i tak okaże się bardziej efektywna niż brak kompresji.Najczęstszym stosowanych przykładem kodowania który opiera się właśnie na  tej metodzie to kod Morse’a.

Kodowanie Huffmana

jedna z najprostszych i łatwych w implementacji metod kompresji bezstratnej. Została opracowana w 1952 roku przez Amerykanina Davida Huffmana.