Dane, informacja, wiedza i mądrość: wzajemne re-
lacje oraz przetwarzanie
Dane losowa grupa prostych faktów i zdarzeń
Informacja proste fakty, poprawnie zagregowane w
bardziej złożone (kompleksowe) fakty
Wiedza sumaryczny wynik naszych procesów per-
cepcyjnych, tak zorganizowany, aby moż-
na było wyciągać znaczące wnioski
Mądrość zazwyczaj definiowana jako zdrowy roz-
sądek, lub właściwy osąd
W informatyce można przyjąć, że:
Wiedza = dane + reguły rozsądnego ich użycia
Trójkąt: Dane, Informacja, Wiedza, Mądrość
Typy zadań w informatyce
Zadanie
!
!
!
!
Semantyczne Wiedza
Morfologiczne Informacja
Obliczeniowe Dane
ę!
ę!
ę!
ę!
Przetwarzanie
Teoria informacji
Punktem wyjścia w całej informatyce jest pojęcie infor-
macji. Jest to pojęcie trudne do ścisłego, pełnego opisa-
nia i wyczerpującego scharakteryzowania, bowiem moż-
na mówić o różnych aspektach informacji: jej znacze-
niu, wartości, nośnikach na których informację zapisa-
no, itd. Nas jednak interesować będzie głównie ilościowy
aspekt informacji, czyli próba znalezienia odpowiedzi
na pytanie:
Jak zmierzyć ilość informacji?
Podstawy ilościowej teorii informacji dał C. Shannon w
1948 roku. Głownym elementem wywodów Shannona,
zmierzających do sformułowania miary informacji, jest
określenie miary niepewności.
Jeśli uda się ilościowo wyrazić niepewność związaną z
pewnym wydarzeniem A, to wówczas nadejście komuni-
katu B, zmniejszającego tę niepewność, będzie mogło zo-
stać rozpatrzone w następujący sposób:
Ilość informacji I zawarta w komunikacie B o zdarzeniu
A równa jest różnicy między początkową niepewnością
zdarzenia A a niepewnością, jaka pozostaje na temat
zdarzenia A po nadejściu komunikatu B:
I(A ł
łB) = H(A) H(A/B)
ł
ł
Oznaczenie H(A) użyto do zapisu początkowej (pierwot-
nej) niepewności zdarzenia A, natomiast H(A/B) jest nie-
pewnością jaka pozostaje mimo odebrania komunikatu
B.
Można sobie wyobrazić, że H(A/B) = 0, wtedy komuni-
kat całkowicie wyjaśnia sytuację, jednak można także
rozpatrywać przypadek gdy H(A/B) = H(A), co oznacza,
że komunikat nie wnosi żadnej użytecznej informacji.
W sytuacji gdy H(A/B) > H(A), to po otrzymaniu komu-
nikatu wiemy jeszcze mniej, niż przed jego odebraniem
czyli mamy do czynienia z dezinformacją. Jak wynika
z przytoczonych sformułowań, kluczowym problemem
w teorii informacji jest określenie miary niepewności H.
Kolejnym, bardzo celnym pomysłem Shannona było po-
wiązanie miary niepewności H(A) zdarzenia z prawdo-
podobieństwem p(A) tego zdarzenia. Punktem wyjścia
były tu trzy bardzo naturalne i oczywiste postulaty:
1). Niepewność zdarzenia pewnego wynosi zero:
jeśli p(A) = 1, to H(A) = 0
2). Im mniejsze prawdopodobieństwo, tym większa nie-
pewność:
jeśli p(A) > p(C), to H(A) < H(C)
3). Jeśli rozważane zdarzenie A jest złożeniem dwóch
niezależnych zdarzeń C i D, wówczas niepewność takie-
go zdarzenia jest równa sumie niepewności składowych
zdarzeń:
H(A) = H(C) + H(D)
Na podstawie tych postulatów bez trudu można ustalić,
jaka powinna być postać matematycznej formuły opisu-
jącej niepewność:
H(A) = log p(A)
Wyjaśnienia wymaga kwestia jednostek, w jakich wyra-
ża się niepewność H, a tym samym informację I. Jed-
nostki te zależą od podstawy używanego logarytmu: zas-
tosowanie najłatwiej dostępnych logarytmów dziesięt-
nych prowadzi do jednostek nazywanych dit (decimal
information unit). Cenione przez teoretyków logarytmy
naturalne pozwalają operować jednostką nazywaną nit
(natural information unit), jednak najczęściej używane
są jednostki nazywane bit (binary information unit), sto-
sowane gdy podstawą logarytmu jest liczba dwa.
Należy zwrócić uwagę na fakt, że termin bit jest pow-
szechnie używany w innym kontekście, jako nazwa pew-
nego elementu komputera, a mianowicie najmniejszego
fragmentu pamięci, w którym można zapamiętać poje-
dyncze zero lub pojedynczą jedynkę. Wbrew pozorom
nie ma tu żadnej sprzeczności. Zastanówmy się bowiem,
czemu odpowiada bit rozumiany jako jednostka ilości
informacji: będzie to pojemnośc takiego komunikatu,
który usunął niepewność wyrażającą się możliwością
wyboru jednej z dwóch jednakowo prawdopodobnych
ewentualności, ponieważ H = log2p = 1, gdy p = . Za-
tem, zgadza się: bit rozumiany jako fragment struktury
komputera, może przechowywać dokładnie jeden bit in-
formacji.
Sytuacja, w której zdarzeniu A można przypisać (jedno)
określone prawdopodobieństwo, jest nadmiernie upro-
szczona. Znacznie bardziej celowe jest rozważenie moż-
liwosci występowania (z różnymi prawdopodobieństwa-
mi) rozmaitych wariantów zdarzenia A. Przykładem ta-
kiej sytuacji jest czytanie dowolnego tekstu: tu, zdarze-
niem, które w takim przypadku można rozważać jest
czytanie następnej litery tekstu, a wariantami mogą być:
litera A, litera B, itd. W celu nadania rozważaniom cech
ogólności przyjmijmy, że możliwych jest n wariantów,
występujących odpowiednio z prawdopodobieństwami
p1, p2, p3, p4 ,..., pN, przy czym oczywiście któryś z warian-
tów musi wystąpić, zatem
Podany wzór jest bardzo ważny i często używany. Spró-
bujmy zbadać, jaki musi być rozkład prawdopodobień-
stw pi, aby niepewność była największa z możliwych?
Okazuje się, że rozkład ten powinien być powinien być
równomierny, to znaczy prawdopodobieństwa powinny
spełniać warunek p1 = p2 = p3 = p4 = pN = 1/N.
...
Niepewność wówczas wynosi
Hmax(A) = log2N
Analiza tej zależności umożliwia dokonanie oceny, czy
dany system przekazywania informacji (np. w rozpatry-
wanym przypadku, język polski) koduje przekazywane
informacje w sposób oszczędny. Mianowicie, wiedząc ja-
ka jest rzeczywista niepewność H(A) wystąpienia jednej
litery w tekście i porównując ją z maksymalną możliwą
niepewnością Hmax(A), można na tej podstawie wyrobić
sobie pogląd na rozpatrywany temat. Ilość informacji
I(A ł
łB) można bowiem wyznaczyć na dwa sposoby:
ł
ł
I(A ł
łB) = H(A) H(A/B) = H(B) H(B/A)
ł
ł
Oznaczenia występujące w drugiej części wzoru są dość
łatwe do odszyfrowania: H(B) to entropia komunikatu,
natomiast H(B/A) to niepewność dotycząca komunikatu
w momencie, kiedy zdarzenie którego dotyczy komuni-
kat jest całkowicie zdeterminowane (zauważmy, że ist-
nieje bezpośredni związek pomiędzy pojęciem niepewno-
ści wprowadzonym w teorii informacji i pojęciem ent-
ropii, używanym przez fizykochemików zwykle stosuje
się te dwa terminy zamiennie). Z przytoczonej zależ-
ności wynika, że
I(A ł
łB) >= H(B)
ł
ł
ponieważ zawsze
H(B/A) >=0.
Komunikat ma więc tym większą pojemność informa-
cyjną, im większa jest jego własna entropia. Z tego po-
wodu przy wyborze sposobów kodowania, dążymy do
maksymalizacji entropii komunikatów. Dla każdego sys-
temu kodowania możemy oszacować jego maksymalną
pojemność informacyjną Hmax i rzeczywistą entropię H.
Ponieważ zwykle H < Hmax , więc pojawia się niekorzyst-
ne zjawisko: każdy symbol (np. każda litera w tekście)
przenosi mniej informacji, niż by mógł. Jest to strata:
dla przesłania lub zapamiętania tej samej ilości infor-
macji trzeba użyć większej liczby symboli a to kosz-
tuje. Zjawisko to nazywamy nadmiarem lub redundancją
(oznaczając R), i możemy oszacować wzorem
Hmax H
R = = 1 H/ Hmax
Hmax
Oszacowanie redundancji R dla wielu naturalnych sys-
temów przekazywania informacji dało zaskakujące wy-
niki. Na przykład dla języka polskiego (biorąc pod uwa-
gę pojedyncze litery) H = 5.26 bita/literę, zaś Hmax = 1.
Zatem nadmiarowośc języka polskiego wynosi
R = 4.26/5.26 * 100 = ok. 81%,
co oznacza, że 4/5 wszystkiego co mówimy lub piszemy,
z informatycznego punktu widzenia, jest zbędne. Podob-
ne wyniki uzyskano dla innych badanych języków, a to
wskazuje, że nie jest to przypadek, lecz jakaś głębsza
prawidłowość. Oczywiście poszczególne języki różnią się
wielkością redundancji między sobą, np. język angielski
ma mniejszą nadmiarowość niż język polski, co powo-
duje (m. inn.), że tekst przetłumaczony z języka angiel-
skiego na język polski zajmuje zawsze więcej miejsca od
tekstu pierwotnego. Fakt ten utrudnia prace nad polo-
nizacją wielu licencyjnych programów. Są jednak języ-
ki bardziej nadmiarowe, niż język polski na przykład
język portugalski.
Okazuje się jednak, że redundancja zawarta w językach
naturalnych wnosi pewne elementy pozytywne, służy do
tego, by uczynić komunikację między ludzmi maksymal-
nie niezawodną. Dzięki temu, że nie wszystkie zestawy
liter są sensownymi słowami, możemy poprawnie odczy-
tać i właściwie zrozumieć słowa, które napisano z błę-
dem. Przykładowo, widząc napis
KRWKÓW
bez trudu rozpoznajemy błąd i potrafimy powiedzieć,
jaka litera została zamieniona (ciekawy przykład wyko-
rzystania nadmiarowości do prawidłowego odczytania błę-
dnego komunikatu zostanie przedstawiony podczas dysku-
sji działania sztucznych sieci neuronowych). Natomiast
znajdując w opisie wypadku drogowego informację, że
samochów-sprawca miał numer rejestracyjny
KRW 35827
w żaden sposób nie możemy się domyślić, że w istocie
rzeczy był to numer KRA 35827 i tylko chochlik dru-
karski wymienił czcionki. Dzieje się tak właśnie dlatego,
że w systemie znaków rejestracyjnych samochodów, re-
dundancji nie ma.
Wiedząc o redundancji języków naturalnych, możemy
poszukiwać metod takiego rejestrowania tekstów (np. w
pamięci komputera), by chociaż częściowo eliminując
nadmiar, doprowadzić do bardziej gęstego upakowa-
nia wiadomości. Z drugiej strony, wiedząc o przydatnej
często roli redundancji, możemy ją celowo wprowadzać
do przesyłanych wiadomości, by zmniejszyć ich podat-
ność na zakłócenia.
Kompresja danych
Wspomnimy tu o pewnym praktycznym zastosowaniu
przytoczonych wniosków wynikających z teorii informa-
cji. Chodzi tu o zmniejszenie potrzebnej przestrzeni do
przechowywania informacji w pamięciach (stałych i ulo-
tnych) komputerów. Daje się to zrobić przy pomocy al-
gorytmów archiwizacji (metody są różne, bardzo często
stosuje się metodę Huffmana). Nie wchodząc w szczegó-
ły techniczne wspomnianych algorytmów, trzeba stwier-
dzić, że redukują one objętość plików tekstowych śred-
nio o około 60%, co stanowi wprawdzie jedynie część
możliwego do uzyskania efektu (dlaczego?). Jednak w
stosunku do tekstów nie upakowanych oznacza to bar-
dzo duży zysk, gdyż na danym nośniku można zapisać
ponad dwukrotnie większą ilość danych.
Jak się to odbywa? Dotychczasowy plik tekstowy niniej-
szego rozdziału ma rozmiar 1680 KB, natomiast po zar-
chiwizowaniu narzędziem ARJ otrzymujemy objętość
jedynie 60 KB. Zmiejszenie objętości pliku jest tu wyjąt-
kowo duże. Część tego skompresowanego tekstu wyglą-
da następująco:
ę( - >
7 8MON.ARJ Bą `ę+ - =7 > "DC8MON_05.DOCńP
T& V ż
@ * Trh6 ,Daet Q `]1%1łe'gd%1ł eW pZPh:TJVą1Ć^_Ó 8
P ppGZ"ęf ÓFś7+m8_0 żŁŁ}Żżb$ H@^-p
bnHp: %3ńbs7sTbo ąńŻ >Ź o! > B{%0ń |
- Fł9ń8ą?dq(q49 ś=N ':~*o1(D!Y UK 8 Ź 1 ` X Ty
@ Ź ThŹ ęhG Ź - Y uTuU~ć Ucżżc?:F: A9u
~n
Kody Huffmana
Kody Huffmana to jedna z powszechnie stosowanych metod kompresji
danych. Metoda ta jest oparta o strategię zachłanną. Kompresja ta po-
lega na zastępowaniu znaków kompresowanego pliku krótszymi koda-
mi (a ściślej ciągami bitów), dzięki czemu wynikowy ciąg bitów jest
znacznie krótszy od wejściowego. Jak wiadomo znaki są kodowane na
8 bitach, dzięki czemu można zakodować aż do 256 znaków (kody
ASCII od 0 do 255). Bardzo rzadko się jednak zdarza, by w pliku
występowały wszystkie znaki ASCII, wobec tego można wykorzystać
mniej bitów i przez to zaoszczędzić dużo miejsca.
Znaki można kodować na dwa sposoby:
" Za pomocą kodów o stałej długości
"
"
"
" Za pomocą kodów o zmiennej długości
"
"
"
Metoda pierwsza jest bardzo prosta, lecz mniej skuteczna niż metoda
kodowania za pomocą kodów o zmiennej długości. Polega na przypisa-
niu znakom liczb porządkowych. Załóżmy na przykład, że nasz plik
został zapisany za pomocą znaków alfabetu A={a, b, c, d, e). Alfabet
ten składa się tylko z 5 znaków; jest to dużo mniej niż 256, nie potrze-
bujemy więc aż 8 bitów, wystarczą nam 3, gdyż 23=8, bo za pomocą 3
bitów można zapisać 8 znaków. Gdyby nasz alfabet składał się z 4
znaków, wówczas wystarczyłyby tylko 2 bity, gdyż 22=4. Załóżmy, że
nasz plik ma dokładnie 1MB, czyli 1024*1024=1.048.576 bajtów.
Każdy bajt jest kodowany na 8 bitach, więc w postaci pierwotnej
(nieskompresowanej) zajmuje 8*1.048.576=8.388.608 bitów. Jak zau-
ważyliśmy jednak, wystarczą nam po 3 bity na znak. Przypiszemy za-
tem każdemu znakowi liczbę porządkową (zapisaną binarnie): a=000,
b=001, c=010, d=011, e=100. Zamiast używać 8 bitowych kodów
ASCII, używamy własne 3 bitowe kody. Sprawdzmy, jakie odnieśliś-
my na tym korzyści: 1.048.576*3=3.145.728 bitów, czyli 37,5% pliku
wejściowego. Zauważmy jednak, że tak dobry wynik osiągamy dlate-
go, że nasz alfabet miał tylko 5 znaków. Im większy alfabet, tym gor-
szy wynik. Przy alfabecie składającym się ze wszystkich 256 znaków,
będziemy potrzebowali 8 bitów (28=256). Alternatywą dla opisanych
powyżej kodów o stałej długości są kody o długości zmiennej. Wyka-
zują one lepsze własności w odniesieniu do znaków częściej wystę-
pujących. Zauważmy bowiem, że lepiej jest przypisać mniej bitów
znakom częściej występującym i więcej bitów znakom rzadziej wys-
tępującym. Wiąże się z tym jednak pewien problem: w przypadku
kodów o stałej długości, dekompresując plik nie było problemu z
pobieraniem kolejnych kodów z ciągu bitów (każdy miał np. 3 bity).
Jeśli kody mają różną długość nie wiadomo, kiedy kończy się stary
kod a zaczyna nowy. Dlatego należy posługiwać się kodami prefikso-
wymi tzn. takimi, że żaden kod znaku nie jest prefiksem innego znaku,
czyli nie jest częścią początkową innego kodu.
Przykład:
Kod 101 jest prefiksem kodu 10111, bo kod 10111 zaczyna się od ciągu
101, będącego pierwszym kodem. Z kolei kod 101 nie jest prefiksem
kodu 100111. Odczytując kody prefiksowe z ciągu bitów wiemy, kiedy
kończy się stary a zaczyna nowy, np. dla kodów prefiksowych 0, 101,
100 nie ma problemu z odczytaniem ciągu 001001010:
Pobieramy pierwszy bit 0: spośród naszych 3 kodów tylko jeden za-
czyna się od 0: 0. Odcinamy go i pobieramy następny: znów 0. Po od-
cięciu dwóch 0 mamy ciąg 1001010, pobieramy kolejny bit: tym razem
dwa kody zaczynają się od 1, pobieramy więc kolejny bit: 0 (mamy już
10) i nadal dwa kody do niego pasują, pobieramy więc kolejny bit: 0 i
otrzymujemy 100 (trzeci kod), odcinamy go i postępując tak samo dla
ciągu 1010 otrzymamy 101 i 0. Tym sposobem rozłożyliśmy ciąg
001001010 na kody 0, 0, 100, 101, i 0, mimo, że mają one zmienną dłu-
gość.
Istnieje dowód, że za pomocą kodów prefiksowych można otrzymać
maksymalny stopień kompresji. Problem przydziału kodów prefikso-
wych znakom rozwiązał Huffman. Metoda Huffmana polega na anali-
zie częstości wystąpień poszczególnych znaków i stosowaniu drzew bi-
narnych postaci:
W każdym liściu (prostokąt) znajduje się znak Zi oraz liczba fi, oz-
naczająca częstość wystąpień znaku Z w kompresowanym tekście. W
każdym węzle (elipsa) znajduje się liczba W (waga) będąca sumą
j
liczb W lub f swoich potomków, czyli:
W4=f4+ f5, W2=f1+ f2, W3=f3+ W4 oraz W1=W2+ W3.
Ciekawą cechą kodów Huffmana jest fakt, że reprezentujące je drze-
wo binarne jest regularne, tzn. każdy węzeł ma dwóch potomków. Na
rysunku widać etykiety nadane krawędziom drzewa: 0 dla lewej kra-
wędzi i 1 dla krawędzi prawej. Te etykiety służą do wyznaczania kodu
Huffmana dla znaku: tworzy go ciąg etykiet krawędzi od korzenia do
liścia z danym znakiem.
Dla naszego drzewa :
Znak Kod
Z1 00
Z2 01
Z3 10
Z4 110
Z5 111
Jak widać kody te nie mają równej długości, ze sposobu tworzenia
drzewa wynika fakt, że znaki o większej wartości f mają krótsze kody.
Budowa tego drzewa następuje poprzez scalanie poddrzew. Począt-
kowo każdy znak tworzy odrębne poddrzewo, waga korzenia jest
równa liczbie f danego znaku.
Algorytm Huffmana ma następujący przebieg:
1. Dodaj do posortowanej kolejki Q wszystkie znaki z alfabetu A
2. Wybierz dwa drzewa o najmniejszej wadze w korzeniu
3. Scal te drzewa i zsumuj wagi ich korzeni, przypisz tą sumę ko-
rzeniowi nowego drzewa
4. Wstaw nowe drzewo do kolejki (sortując ją)
5. Jeżeli w kolejce jest więcej niż jedno drzewo, wróć do 2.
Po utworzeniu drzewa należy nadać etykiety krawędziom: lewym 0 i
prawym 1. Następnie można już odczytywać kody znaków. Kompre-
sowanie polega na zastąpieniu ciągu bitów pliku wejściowego konkate-
nacją kodów Huffmana poszczególnych znaków. Dekompresja to opi-
sany powyżej rozbiór ciągu bitów pliku skompresowanego na kody
Huffmana i odczytanie odpowiednich znaków. Jak widać, jest to me-
toda trochę trudniejsza niż stosowanie kodów o stałej długości. Zo-
baczmy, czy ten wysiłek się opłaca. Przeanalizujmy ten sam plik o
wielkości 1MB składający się z ciągu znaków z alfabetu A={a, b, c, d,
e} o następujących częstościach wystąpień:
f(a)=187.723, f(b)=506.035, f(c)=102.060, f(d)=125.457, f(e)=127.301.
Oczywiście f(a)+f(b)+f(c)+f(d)+f(e)=1048576 bajtów, czyli 1MB. Zgod-
nie z algorytmem znaki te początkowo tworzą odrębne drzewa o wa-
dze korzenia równej liczbie f, umieszczamy je zatem w kolejce po-
sortowanej niemalejąco wg wag:
Wybieramy dwa pierwsze drzewa (na najmniejszej wadze korzeni) i
łączymy je w jedno drzewo sumując wagi korzeni, a następnie wsta-
wiamy nowe drzewo do kolejki (na trzecie miejsce, ponieważ waga ko-
rzenia nowego drzewa wynosi 227.517):
Tworzymy kolejne drzewo, tym razem ze znaków e i a:
Scalamy ostatnie dwa drzewa w całość i nadajemy krawędziom ety-
kiety:
Bezpośrednio z drzewa odczytujemy kody znaków:
Znak Kod
a 111
b 0
c 100
d 101
e 110
Jak widać, najkrótszy kod ma litera b, która występuje w pliku naj-
większą ilość razy; policzmy teraz ile zyskaliśmy, stosując kody o
zmiennej długości. Wyznaczymy tzw. koszt drzewa, czyli sumę iloczy-
nów długości kodu i liczby wystąpień w pliku. Koszt drzewa jest liczbą
bitów potrzebną do zapisania skompresowanego ciągu znaków:
B(T)=
3*187.723+1*506.035+3*102.060+3*125.457+3*127.301=2.133.658
bitów, co stanowi 25.4% pliku wejściowego. Kompresując ten sam plik
za pomocą kodów o stałej długości otrzymaliśmy 37.5% pliku pier-
wotnego.
W rzeczywistości należy doliczyć jeszcze kilka bitów do ciągu wyniko-
wego, gdyż liczba 2.133.658 nie dzieli się przez 8, a na komputerze
można zapisać jedynie liczby bitów będących wielokrotnością ósemki.
Dodajemy więc 6 bitów nieznaczących i otrzymujemy 2.133.664 bitów,
co daje 266.708 bajtów (plik wejściowy miał 1MB).
Wyszukiwarka
Podobne podstrony:
8zti8zti8zti&8zti uzup8zti8zti8zti8zti8zti8zti8zti8zti8zti8zti8zti8zti8zti8ztiwięcej podobnych podstron