Politechnika Poznańska  Wydział Maszyn Roboczych i Transportu

Instytut Maszyn Roboczych i Pojazdów Samochodowych

Wykład 16



Kompresja danych

dr inż. Michał Maciejewski

[e-mail]

Systemy informacyjno-informatyczne

w transporcie

2

Plan wykładu

• Informacja – Redundancja – Kompresja

• Typy kompresji
• Teoria informacji
• Algorytm Huffmana

Informacja

• Ogólnie

– to treść komunikatu przekazywanego za pomocą

danych

– ta sama treść może być przekazywana przy pomocy

różnych danych (znaki, mowa, wykres itp.)

• Informatyka

– podstawowa jednostka informacji to bit
– 1 bit = ilość informacji zawartej w odpowiedzi na

pytanie, na które można odpowiedzieć TAK lub NIE

– wartości bitu oznacza się cyframi dwójkowymi 1 i 0

3

Informacja

• Typy danych

– tekstowe
– numeryczne
– graficzne

• Kodowanie danych

– rozmaite formaty danych

• np. dla plików tekstowych (doc, xml, pdf, txt)

– w celu zapisu danych na komputerze (maszynach

cyfrowych) wszystkie dane są sprowadzane do
postaci binarnej

– bity pogrupowane są w bajty (8 bitów)

4

Redundancja

• Redundancja = nadmiarowość

– ilość informacji przekraczająca wymagane do rozwiązania

problemu minimum

– ilość bitów w wiadomości minus ilość bitów faktycznej

informacji

• Zastosowanie

– w celu łatwiejszego odtworzenia danych po ich częściowej

utracie czy uszkodzeniu lub też do wykrycia takiego
uszkodzania

• suma kontrolna, CRC
• macierze dysków (mirroring = RAID 1)

– dotyczy zabezpieczenia b. ważnych, strategicznych

informacji

– bazy danych – w celu przyspieszenia dostępu do

informacji pewne dane mogą być zapisane w różnych
tabelach

5

Kompresja

• Usuwanie nieprzydatnej redundancji

– Polega na zmianie sposobu zapisu informacji tak, aby

zmniejszyć redundancję i tym samym objętość
zbioru, nie zmniejszając przenoszonych informacji

– Wyrażenie tego samego zestawu informacji, ale za

pomocą mniejszej ilości bitów

– ALE: Programy kompresujące mogą dodawać

niewielkie informacje nadmiarowe, pozwalające
wykryć uszkodzenie skompresowanych danych (np.
sumy kontrolne)

• Operacją odwrotną jest dekompresja

6

7

Plan wykładu

• Informacja – Redundancja – Kompresja

• Typy kompresji

• Teoria informacji
• Algorytm Huffmana

Kompresja

• Typy kompresji

– bezstratna

• z postaci skompresowanej można odzyskać identyczną

postać pierwotną

– kompresja plików tekstowych
– kompresja danych numerycznych (choć może też

być stratna – kwantyzacja)

– kompresja obrazu

– stratna

• odzyskanie postaci pierwotnej jest niemożliwe (bądź nie

gwarantowane), jednak główne właściwości danych
zostają zachowane

– kompresja obrazu
– kompresja dźwięku

8

Kompresja

• Proszę szybko przeczytać poniższe akapity:

– Zdognie z nanjwoymszi baniadmai

perzporawdzomyni na bytyrijskch uweniretasytch nie
ma zenacznia kojnolesc ltier przy zpiasie dengao
solwa.

– Nwajzanszyeim jest, aby prieszwa i otatsnia lteria

byla na siwom mijsecu, ptzosałoe mgoą być w
niaedziłe i w dszalym cąigu nie pwinono to sawrztać
polbemórw ze zozumierniem tksetu.

– Dzijee sie tak datgelo, ze nie czamyty wyszistkch

lteir w sołwie, ale cłae sołwa od razu.

9

Kompresja

• Algorytmy kompresji

– ogólnego zastosowania

• głównie algorytmy bezstratne

– kompresja stratna zakłada pomijanie mniej

ważnych informacji, a więc zależy od typu danych

– szczególnego zastosowania

• algorytmy bezstratne

– często przeróbki algorytmów ogólnego

zastosowania

• algorytmy stratne

– kompresja audio
– kompresja video (obrazy, filmy)

10

Kompresja bezstratna

• Algorytmy

– BZIP2
– Deflate
– Huffman
– LZMA
– …

• Formaty

– zip (szerokodostępny – Windows, szybki)
– gzip (UNIX)
– rar (wolniejszy, ale skuteczniejszy od zipa)
– 7z (wolny, wysoka kompresja, silne szyfrowanie,

unicode)

– png (grafika dla WWW, następca gif)
– …

11

Kompresja bezstratna

wyniki orientacyjne (nie reprezentatywne!!)

12

Kompresja stratna

• Algorytmy

– DCT
– Falki
– MDCT
– …

• Formaty - obraz

– JPEG
– MPEG, WMV, AVI

• Formaty – dźwięk

– OGG, AC3, MP3, MPC, WMA

13

Formaty - obraz

14

JPG

TIFF/

/BMP

PNG

GIF

Kompresja stratna – redukcja ilości
barw

15

256

16

64

4

8

2

Kompresja stratna – jakość MP3

• oryginał

(*.wav)

• mp3

128 kbit/s

16

Kompresja stratna – jakość MP3

• oryginał

(*.wav)

• mp3

192 kbit/s

17

Kompresja stratna – jakość MP3

• oryginał

(*.wav)

• mp3

224 kbit/s

18

Kompresja stratna – jakość MP3

• oryginał

(*.wav)

• mp3

VBR
(=variable
bitrate)

19

Kompresja stratna

• Techniki kompresji video (MPEG)

– podpróbkowanie chrominancji
– kompensacja ruchu
– kodowanie transformatowe
– kodowanie Huffmana

• Kodeki

– K-Lite Codec Pack

• Basic

– absolutne minimum, mieści się na dyskietce

• Standard

– wszystkie popularne formaty

• Full

– jeszcze więcej kodeków, oprogramowanie do

tworzenia własnych kodeków

20

31

Plan wykładu

• Informacja – Redundancja – Kompresja
• Typy kompresji
• Teoria informacji

• Algorytm Huffmana

Kodowanie Huffmana

• Kodowanie Huffmana

– Jedna z najprostszych i łatwych w implementacji metod

kompresji bezstratnej

– Opracowana w 1952 Davida Huffmana

– Algorytm Huffmana nie należy do najefektywniejszych

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

32

Kodowanie Huffmana

• Przykład budowy słownika

– Prawdopodobieństwa

» A – 0,1
» B – 0,2
» C – 0,3
» D – 0,4

33

Kodowanie Huffmana

• Przykład budowy słownika

– Prawdopodobieństwa

» A – 0,1
» B – 0,2
» C – 0,3
» D – 0,4

– Wynik (słownik)

» A – 000
» B – 001
» C – 01
» D – 1

– Stopień kompresji

• przed:

8 bit / znak

• po (średnio):

1,9 bit / znak

(0,1*3 + 0,2*3 + 0,3*2 + 0,4*1) = 1,9

34

8/1,9=

=4,21…

Kodowanie Huffmana

• Przykład 2 (do opisu algorytmu)

35

Kodowanie Huffmana

• Tworzenie drzewa (1)

– W każdym kroku procedury kodowania Huffmana

zmniejszamy ilość uwzględnianych jeszcze symboli o
jeden poprzez połączenie dwóch symboli o
najmniejszych prawdopodobieństwach

– Dla danych z rysunku w pierwszym kroku należy

połączyć symbole E oraz F w symbol złożony „E lub
F" o prawdopodobieństwie wystąpienia 0,2

– Symbole złożone należy ustawiać w kolejnych

kolumnach (kolejne etapy) możliwie jak najwyżej

– Procedurę tę powtarzamy tak długo, aż w kolumnie

pozostaną dokładnie dwa symbole

36

Kodowanie Huffmana

• Tworzenie drzewa (2)

– W utworzonym drzewie każde dwa łączone symbole

oznaczamy arbitralnie 1 lub 0 (ostatnie elementy
każdej kolumny)

– Po zakończeniu procedury należy z otrzymanego

diagramu odczytać słowa kodowe przypisane do
poszczególnych symboli poruszając się od „korzenia”
do „liści” utworzonego drzewa

– Przykładowo symbolowi A zostaje przyporządkowane

słowo kodowe 01

– Utworzony w ten sposób słownik ma dodatkową

cechę: żaden z jego symboli kodowych nie jest
prefiksem któregokolwiek innego symbolu

37

38

Dziękuję…