ZESPÓŁ LABORATORIÓW TELEMATYKI TRANSPORTU
ZAKŁAD TELEKOMUNIKACJI W TRANSPORCIE
WYDZIAŁ TRANSPORTU
POLITECHNIKI WARSZAWSKIEJ
LABORATORIUM
Telekomunikacji Kolejowej
INSTRUKCJA DO ĆWICZENIA NR 5
Kompresja danych
© TwTWTPW, DO UŻYTKU WEWNĘTRZNEGO
Warszawa 2013
Ćw. nr 5 – Kompresja danych 2013-11-09
Laboratorium Telekomunikacji Kolejowej
Zakład Telekomunikacji w Transporcie Wydziału Transportu Politechniki Warszawskiej
1
1.
Cel ćwiczenia
Celem ćwiczenia jest prezentacja procesu kompresji danych, na przykładzie obróbki
plików o różnej zawartości – różnej naturze danych.
Zakres ćwiczenia obejmuje obserwację, ocenę oraz rejestrację podstawowych dla
procesu kompresji danych parametrów, a w szczególności:
- współczynnik kompresji,
- rozkład statystyczny danych w zbiorze,
- entropia zbioru,
- teoretyczna minimalna wielkość pliku po kompresji,
- teoretyczny maksymalny współczynnik kompresji,
- sprawność kompresji popularnych programów archiwizujących.
2.
Wykaz wykorzystanych przyrządów i oprogramowania
- komputer PC z systemem Windows 98/NT/2000/XP,
- programy kompresujące:
A – WinZIP,
B – WinRAR,
C – WinACE.
- program Kompresja danych do analizy statystycznej plików (rys. 3.1),
- program graficzny IrfanView do kompresji JPG,
- zestaw plików poddawanych kompresji (patrz p. 5).
3.
Program Kompresja danych
Program
przeznaczony
jest
do
wyznaczania
podstawowych
własności
probabilistycznych dowolnych zbiorów danych. Do jego podstawowych funkcji należy:
- odczyt dowolnego zbioru danych,
- określenie wielkości zbioru danych (w bajtach),
- określenie częstości występowania wszystkich znaków we wskazanym zbiorze
danych i przedstawienie ich w postaci graficznej (histogramu),
Ćw. nr 5 – Kompresja danych 2013-11-09
Laboratorium Telekomunikacji Kolejowej
Zakład Telekomunikacji w Transporcie Wydziału Transportu Politechniki Warszawskiej
2
- eksport (zapis) wykresu w postaci pliku BMP,
- obliczenie entropii wejścia zbioru danych,
- wyznaczenie teoretycznej minimalnej wielkości zbioru wyjściowego (po
kompresji),
- wyznaczenie teoretycznego maksymalnego współczynnika kompresji dla danego
zbioru danych.
Rys. 3.1 Program Kompresja danych do analizy statystycznej plików
Obsługa programu jest bardzo prosta, a jego instalacja przebiega w typowy dla systemu
Windows sposób (setup.exe, katalog programu, itd.). Po naciśnięciu klawisza Otwórz pojawia
się typowe dla Windows okno dialogu. Wskazujemy dowolny plik danych, którego statystykę
zamierzamy określić. Program przystępuje do analizy pliku, a przebieg procesu
sygnalizowany jest zmianami zapełnienia paska postępu, u dołu okna programu. Po
zakończeniu analizy program, po lewej stronie okna, wyświetla wykres częstości
występowania poszczególnych znaków w pliku danych. Poniżej prezentowane są wszystkie
odczytane i obliczone dane: ścieżka pliku danych, jego rozmiar, entropia wejścia, teoretyczna
minimalna wielkość zbioru wyjściowego i teoretyczny maksymalny współczynnik kompresji
dla tego zbioru. Obliczana wielkość prawdopodobieństwa (pole Prawd.) służy jedynie celom
kontrolnym – powinna zawsze wynosić „1,00”, w przypadku różnicy większej niż 0,01 należy
powiadomić prowadzącego.
Ćw. nr 5 – Kompresja danych 2013-11-09
Laboratorium Telekomunikacji Kolejowej
Zakład Telekomunikacji w Transporcie Wydziału Transportu Politechniki Warszawskiej
3
Po kliknięciu na jedno z pól koloru w ramce Kolor wykresu następuje przeniesienie
wykresu z lewej strony okna na prawą, z jednoczesną zmianą jego koloru na wskazany.
Wygodnie, dla celów późniejszej analizy, jest przypisać określony kolor dla określonego typu
danych wejściowych, np. czarny dla zbioru nie skompresowanego, czerwony dla ZIP, itd. Po
naciśnięciu klawisza Zapisz pojawia się typowe dla Windows okno dialogu. Określamy
położenie (ścieżkę) i nazwę pliku BMP, w którym zostanie zapisany wykres. UWAGA!!!
Zapisywany jest wykres z prawej strony okna programu, a więc po przypisaniu mu koloru
wykresu. Wykres ten jest wyświetlany nadal po otwarciu kolejnego zbioru danych, aż do
kolejnego wyboru koloru wykresu. Takie rozwiązanie pozwala już na bieżąco kontrolować
przebieg ćwiczenia i porównywać wykresy kolejnych plików danych. Wykresy zapisywane są
w rozdzielczości dostosowanej do programu przeznaczonego dla wykonania sprawozdania.
Klawisz Eksplorator służy do wywołania Eksploratora Windows z poziomu, którego
łatwo dokonuje się operacji kompresji zbiorów.
4.
Wprowadzenie teoretyczne
Kompresja jest tanim (może nawet najtańszym) sposobem/procesem zmniejszenia
objętości danych wejściowych (źródłowych), w taki sposób, aby zajmowały one jak najmniej
miejsca. Dekompresją nazywamy proces odwrotny do kompresji, polegający na odtworzeniu
z danych wyjściowych (skompresowanych) danych wejściowych. W zależności od rodzaju
kompresji dane odtworzone (zdekompresowane) odpowiadają danym wejściowym w 100%
(kompresja bezstratna) lub jedynie z pewnym przybliżeniem (kompresja stratna). Kompresja
bezstratna stosowana jest wszędzie tam, gdzie zmiana nawet jednego bitu danych może
wywołać negatywne skutki - np. w plikach wykonywalnych EXE, dokumentach DOC,
arkuszach XLS. Kompresja stratna stosowana jest tam, gdzie dopuszczalne jest powstanie
różnicy między danymi wejściowymi a odtworzonymi, głównie w kompresji obrazów i
dźwięków - np. JPEG, MPEG, MP3. Pośrednim skutkiem kompresji może być wzrost
szybkości transmisji danych – mniejsza ilość danych zostanie przecież przesłana w krótszym
czasie niż większa przy wykorzystaniu tego samego pasma transmisyjnego. Tym samym
kompresja danych stała się jednym z fundamentalnych zagadnień transmisji danych, w
niektórych przypadkach umożliwiając wręcz jej realizację – np. w transmisji obrazu.
Realizacja kompresji możliwa jest dzięki tzw. redundancji (nadmiarowości) informacji
zawartej w danych źródłowych oraz dzięki różnym zależnościom w strukturze danych. Każdą
kompresję charakteryzuje tzw. współczynnik kompresji k, wyrażony wzorem (4.1):
Ćw. nr 5 – Kompresja danych 2013-11-09
Laboratorium Telekomunikacji Kolejowej
Zakład Telekomunikacji w Transporcie Wydziału Transportu Politechniki Warszawskiej
4
%
100
we
wy
we
L
L
L
k
(4.1)
gdzie:
we
L - rozmiar danych wejściowych,
wy
L
- rozmiar danych wyjściowych.
Wielkość współczynnika kompresji może zmieniać się od 0 do 100% i zależy od
przyjętego algorytmu (metody) kompresji oraz od zawartości zbioru. O ile pierwsza
przyczyna nie wymaga komentarza, to druga może nie być już tak oczywista. Metody
kompresji danych ogólnie dzielimy na obliczeniowe i statystyczne. Obliczeniowe dokonują
kompresji poprzez mniej lub bardziej złożone obliczenia matematyczne, których bazą jest
zbiór danych wejściowych. Nie poszukują jednak powiązań między samymi danymi.
Statystyczne zaś dostosowują algorytm kompresji do zawartości zbioru danych wejściowych,
częstości występowania poszczególnych elementów, znaków, symboli, fraz, itp. W ogólnym
ujęciu metody statystyczne dają zawsze lepsze rezultaty (większe współczynniki kompresji)
niż obliczeniowe. Wymagają jednak określenia częstości występowania poszczególnych
elementów zbioru wejściowego, a więc wymagają znajomości całego zbioru danych
wejściowych przed rozpoczęciem procesu kompresji. Fakt ten dyskwalifikuje je z zastosowań
w transmisji danych, gdzie na ogół występuje strumień a nie zbiór danych. Problem ten
rozwiązano poprzez połączenie metod obliczeniowych i statystycznych w metody, które
„przewidują” charakter strumienia danych na podstawie analizy jego wcześniej odebranej
części. Dzięki współczynnikowi kompresji możemy w prosty sposób określić podatność
zbioru wejściowego na kompresję – większy współczynnik kompresji, to większa podatność i
odwrotnie. Jest to jednak możliwe już po procesie kompresji. Ponieważ wielkość
współczynnika kompresji może zależeć od przyjętej metody kompresji, to nie można
wykluczyć, że przy zastosowaniu innego algorytmu jego wartość uległaby zwiększeniu, a
rozmiar danych wyjściowych dalszemu zmniejszeniu. Przydatna byłaby, więc możliwość
oceny podatności zbioru danych wejściowych na kompresję jeszcze przed rozpoczęciem
zasadniczego procesu kompresji. Jest to możliwe dzięki tzw. entropii wejścia
(współczynnikowi chaosu zbioru), określającej właśnie podatność na kompresję i obliczanej
ze wzoru (4.2):
Ćw. nr 5 – Kompresja danych 2013-11-09
Laboratorium Telekomunikacji Kolejowej
Zakład Telekomunikacji w Transporcie Wydziału Transportu Politechniki Warszawskiej
5
i
n
i
i
we
z
P
z
P
E
2
1
log
(4.2)
gdzie:
i
z
P
- prawdopodobieństwo występowania znaku z
i
,
2
log - logarytm o podstawie 2, podstawa 2 wynika z binarnego, 0 lub 1 systemu kodowania,
n
- ilość różnych znaków, np. 256 dla kodu 8-bitowego.
Dodatkowo z własności prawdopodobieństwa wynika, że musi być spełniony warunek
(4.3) dla którego suma prawdopodobieństw występowania wszystkich znaków P(z
i
) musi być
równa jedności:
1
1
n
i
i
z
P
(4.3)
Łatwo zauważyć, że obliczona wartość entropii ma bardzo duże znaczenie praktyczne:
Entropia duża (duża przypadkowość danych, chaos, losowość):
maksimum informacji,
minimum podatności na kompresję.
Entropia mała (uporządkowanie danych, wyraźna przewaga części danych):
mniej informacji,
większa podatność na kompresję.
Entropia zdążająca do minimum (przewaga jednych danych, brak innych):
minimum informacji,
maksymalna podatność na kompresję.
Obliczona entropia wejścia pozwala nie tylko na ocenę podatności zbioru wejściowego
na kompresję. Dzięki niej można też w prosty sposób obliczyć (4.4) teoretyczny minimalny
rozmiar danych wyjściowych (po kompresji) za pomocą metody probabilistycznej – opartej
na rozkładzie statystycznym źródła:
l
E
L
L
we
we
min
(4.4)
Ćw. nr 5 – Kompresja danych 2013-11-09
Laboratorium Telekomunikacji Kolejowej
Zakład Telekomunikacji w Transporcie Wydziału Transportu Politechniki Warszawskiej
6
gdzie:
we
L - rozmiar danych wejściowych,
we
E - entropia wejścia,
l – podstawa kodowania (pojedynczych) danych np. 8 bitów dla kodu ASCII
Stąd, równie łatwo, można wyliczyć (4.5) teoretyczny maksymalny współczynnik
kompresji:
%
100
min
max
we
we
L
L
L
k
(4.5)
Kompresja jest tym bardziej wydajna (mniejszy zbiór danych wyjściowych), im
bardziej rozmiar danej reprezentującej konkretny znak jest zbliżony do entropii wejścia. W
roku 1948 Claude E. Shannon udowodnił, że nie można wygenerować krótszego kodu
(używając metod probabilistycznych), niż wyznacza sama entropia. Inaczej mówiąc, nie
można opracować metody kompresji, która byłaby jeszcze bardziej wydajna i dawałaby
mniejszy zbiór danych wyjściowych od ich wyznaczonego teoretycznego minimalnego
rozmiaru L
min
. W praktyce przeważająca większość metod probabilistycznych nie jest w
stanie nawet dorównać wartości L
min
. Należy jednak pamiętać, że większość powszechnie
wykorzystywanych współczesnych metod kompresji jedynie w części swojego działania
wykorzystuje statystykę zbioru, która stanowi bazę do dalszych działań.
5.
Uwagi praktyczne
Większość obserwacji i operacji dokonywana jest przy wykorzystaniu jedynie
Eksploratora Windows, programu laboratoryjnego Kompresja danych, programu graficznego
IrfanView oraz programów kompresujących (patrz p. 2). Oprócz nich w ćwiczeniu występuje
zestaw plików, które poddawane są kompresji:
Ćw. nr 5 – Kompresja danych 2013-11-09
Laboratorium Telekomunikacji Kolejowej
Zakład Telekomunikacji w Transporcie Wydziału Transportu Politechniki Warszawskiej
7
UWAGA!!! Istnieje kilka zestawów o identycznych nazwach ww. plików, więc lepiej
wykonywać ćwiczenie samodzielnie i nie opierać się na wcześniejszych opracowaniach (patrz
regulamin)!
Podczas kompresji plików graficznych BMP do formatu JPG należy zawsze i za
każdym razem otworzyć źródłowy plik BMP i dopiero go skompresować.
Dla zwiększenia przejrzystości instrukcji przyjęto wykorzystanie prostych skrótów
graficznych:
- zapisz dane do pliku na dysku,
- pytanie, na które odpowiedź musi znaleźć się w sprawozdaniu.
Ćw. nr 5 – Kompresja danych 2013-11-09
Laboratorium Telekomunikacji Kolejowej
Zakład Telekomunikacji w Transporcie Wydziału Transportu Politechniki Warszawskiej
8
Pod żadnym pozorem nie należy „upraszczać” ćwiczenia i próbować wykonywać operacji
jednocześnie z kilku punktów instrukcji. Jest to najszybsza droga do pomyłki w identyfikacji
przebiegów i wyników, co skutkuje odrzuceniem sprawozdania.
6.
Przebieg ćwiczenia
6.1. Zapoznaj się z obsługą programów wykorzystywanych podczas ćwiczenia. Programy
kompresujące najlepiej jest wywoływać z poziomu Eksploratora Windows.
6.2. W programie IrfanView poddaj kompresji JPG wszystkie pliki graficzne BMP dla
współczynnika jakości 80, 50 i 30. Jako nazwę tworzonego pliku przyjmij nazwę
oryginalną powiększoną o wartość współczynnika jakości, np. szum80.jpg.
Pamiętaj, żeby po każdym zapisaniu pliku JPG, przed zapisem z nową wartością
współczynnika jakości, otworzyć na nowo oryginalny plik BMP.
6.3. Każdy z wymienionych w p. 5 plików oraz utworzone pliki JPG poddaj kolejno
kompresji każdym z programów wymienionych w p. 2.
6.4. Otwórz plik kompresja.xls, zawierający arkusz Excel’a dla zestawienia wyników
ćwiczenia. Zapisz ten plik pod nazwą zawierającą datę wykonania ćwiczenia, typ
studiów (DZ, ZA, SMU), grupę i semestr.
6.5. Uruchom program Kompresja danych. Otwórz kolejno każdy z plików źródłowych i
odpowiadające im pliki skompresowane. W arkuszu XLS zapisz wszystkie dane
dotyczące plików.
Zapisz na dysku histogramy plików.
6.6. Dokonaj analizy otrzymanych wyników. Jak wpływa współczynnik jakości na wielkość
pliku JPG?
Jak wpływa „treść” pliku graficznego i tekstowego na podatność na
kompresję?
Jaka jest zależność między entropią wejścia pliku a współczynnikiem
kompresji?
Kiedy plik jest najbardziej podatny na kompresję?
Który z
programów kompresujących wykazuje największą sprawność kompresji – ich pliki
wynikowe są najmniejsze?
7.
Wykonanie sprawozdania
Nie należy umieszczać w sprawozdaniu podstaw teoretycznych, opisów stanowiska
laboratoryjnego, ani wykorzystanego oprogramowania.
Ćw. nr 5 – Kompresja danych 2013-11-09
Laboratorium Telekomunikacji Kolejowej
Zakład Telekomunikacji w Transporcie Wydziału Transportu Politechniki Warszawskiej
9
Sprawozdanie musi zawierać wszystkie wyniki pomiarów i obliczeń oraz wszystkie
zarejestrowane histogramy, prezentowane w logicznym ciągu (np. plik nie skompresowany i
skompresowany kolejnymi programami). Każdy wynik i wykres musi być opatrzony
numerem punktu instrukcji wg, którego został zarejestrowany. Każdy histogram musi być
opatrzony opisem, wyjaśniającym, co przedstawia i jakiego pliku dotyczy. W sprawozdaniu
muszą się znaleźć odpowiedzi na wszystkie postawione w instrukcji pytania, ponumerowane
wg punktów, w których zostały postawione. Zarówno opisy, jak i odpowiedzi, mają być
zwięzłe, ale przedstawione pełnymi zdaniami.
Wnioski powinny zawierać podsumowanie przeprowadzonych pomiarów i obliczeń.
Szczególny nacisk należy położyć na zaprezentowanie różnic i podobieństw pomiędzy
histogramami plików nie skompresowanych, a skompresowanych z jednoczesnym
odniesieniem do ich zawartości. Sednem ćwiczenia jest znalezienie związku między
podatnością pliku danych wejściowych na kompresję a jego zawartością, a więc i statystyką.
8.
Literatura
Heim K., Metody kompresji danych, MIKOM 2000,
Sayood K., Kompresja danych - wprowadzenie, RM 2002,
Skarbek Wł. (pod redkakcją), Multimedia. Algorytmy i standardy kompresji, PLJ 1998,
Plucińska A., Pluciński E., Rachunek Prawdopodobieństwa, Statystyka matematyczna,
Procesy stochastyczne, WNT 2000.