Reprezentacja podstawowych

informacji w systemach

informatycznych dla medycyny

Wykład nr 4 z kursu IT dla

Wykład nr 4 z kursu IT dla

Inżynierii Biomedycznej

prowadzonego przez

Prof. Ryszarda Tadeusiewicza

Komputery nie są urządzeniami, które
istnieją „same dla siebie”.

Ich użyteczność wynika z tego, że z pomocą technologii informacyjnych
można:

• rejestrować,

• ewidencjonować,

2

• opisywać,

• badać,

• analizować,

• sterować

• i przewidywać...

różne fakty dotyczące rzeczywistego świata.

Aby to było możliwe – fakty te trzeba właściwie

odwzorowywać

w rejestrach

i pamięciach systemów komputerowych. Przywołuje to problem

... reprezentacji danych w
systemach informatycznych

3

Reprezentacja informacji w systemach
komputerowych

Wszelkie informacje przetwarzane,
przechowywane oraz przesyłane
w systemach komputerowych mają postać
binarną

4

Jeśli są to dane liczbowe, to są ona zapisane w
systemie dwójkowym, czyli w systemie
pozycyjnym o podstawie 2

Jeśli są to dane inne niż wartości liczbowe, to są
one

kodowane za pomocą symboli binarnych.

Sygnały (dźwięki, obrazy, rejestracje EKG itd. są
umieszczane w komputerze jako tablice liczb.

Jednostki ilości informacji

5

Reprezentacja wartości liczbowych.

6

Reprezentacja wartości liczbowych.

Pozycyjne systemy liczenia (1)

Każda liczba całkowita N ≥

≥

≥

≥ 2 może być

podstawą systemu liczenia (mówimy
wówczas o systemie o podstawie N).

System dziesiętny (system o podstawie

7

System dziesiętny (system o podstawie
równej 10) jest przykładem pozycyjnego
systemu liczenia

System binarny jest także przykładem

pozycyjnego

systemu liczenia

Pozycyjne systemy liczenia (2)

Do zapisu liczb wykorzystywane są cyfry:

w systemie dwójkowym: 0, 1;

w systemie dziesiętnym: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9;

w systemie ósemkowym: 0, 1, 2, 3, 4, 5, 6, 7;

w systemie szesnastkowym: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

8

w systemie szesnastkowym: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
A, B, C, D, E, F;

w systemie o podstawie N: 0, 1, ..., N - 1

Cechą charakterystyczną systemów pozycyjnych jest
to, że wartość cyfry uzależniona jest od jej pozycji.

Przykłady zapisów liczb i ich interpretacja
w różnych systemach pozycyjnych

9

To, co warto zapamiętać:

10

Obliczanie wartości liczby (1)

system dziesiętny (system o podstawie 10)

353

(10)

= 3 * 100 + 5 * 10 + 3 * 1 = 3 * 10

2

+

5 * 10

1

+ 3 * 10

0

11

5 * 10 + 3 * 10

2,4

(10)

= 2 * 1 + 4 * 0,1 = 2 * 10

0

+ 4 * 10

-1

∑

⋅

=

i

i

i

c

W

10

Obliczanie wartości liczby (2)

System dwójkowy (system o podstawie 2)

Analizowana liczba 101,11

(2)

12

∑

⋅

=

i

i

i

c

W

2

Obliczanie wartości liczby (3)

Uogólnienie:

System o podstawie N

∑

⋅

=

i

i

i

N

c

W

13

Zamiana liczb dziesiętnych na system
binarny (1)

14

Zamiana liczb dziesiętnych na system
binarny (2)

15

Zamiana liczb dziesiętnych na system
binarny (3)

Wniosek: ułamek
dziesiętny o skończonej

16

dziesiętny o skończonej
liczbie cyfr może wymagać
ułamka binarnego o
nieskończonej liczbie cyfr.

System szesnastkowy

dzielimy liczbę binarną na grupy po 4 cyfry -
w lewo i prawo rozpoczynając od pozycji
separatora dziesiętnego;

wartość każdej wydzielonej grupy zapisujemy

17

wartość każdej wydzielonej grupy zapisujemy
za pomocą jednej cyfry szesnastkowej.

Przykład:

1111100000

(2)

= ?

(16)

0011 | 1110 | 0000 = 3E0
1111100000

(2)

= 3E0

(16)

Zamiana liczby binarnej na heksadecymalną
(nad cyframi napisano wagi pozycji):

18

Przyczyny stosowania systemu
szesnastkowego

znacznie większa zwięzłość zapisu w
porównaniu z zapisem binarnym (4 cyfry
binarne = 1 cyfra szesnastkowa)

prosta konwersja pomiędzy systemem

19

prosta konwersja pomiędzy systemem
binarnym i szesnastkowym

liczba bitów w jednej komórce jest zwykle
wielokrotnością liczby 4, co znacznie ułatwia
przedstawienie jej zawartości w systemie
szesnastkowym.

Reprezentacja liczb całkowitych (1)

a)

liczby całkowite bez znaku

na kolejnych bitach przechowywane są
poszczególne cyfry binarne

Np. liczba 41

(10)

w komórce ośmiobitowej

20

(10)

przechowywana jest w następujący sposób:

Reprezentacja liczb całkowitych (2)

b)

prosta reprezentacja liczb całkowitych ze
znakiem (reprezentacja typu znak-moduł,
reprezentacja bezpośrednia)

Kodowanie informacji o znaku:

21

plus



0

minus



1

Np. liczba -41 w komórce ośmiobitowej
przechowywana jest w następujący sposób:

Reprezentacja liczb całkowitych (3)

Wady reprezentacji znak-moduł:

możliwe są dwa sposoby reprezentacji zera:

10000000

00000000

22

występują problemy przy realizacji obliczeń na
liczbach ujemnych (np. -2 + 3)

10000010

(-2)

00000011

(+3)

10000101

(-5)

Reprezentacja liczb całkowitych (4)

c)

kod uzupełnieniowy

Kod uzupełnieniowy służy do reprezentacji
liczb całkowitych:

liczby całkowite nieujemne przyjmują

23

postać:

bit znaku, moduł liczby

Reprezentacja liczb całkowitych (5)

liczby całkowite ujemne przyjmują postać:

bit znaku, uzupełnienie do dwóch modułu liczby

24

Reprezentacja liczb całkowitych (6)

Pojęcie „uzupełnienia do dwóch”

Uzupełnieniem do dwóch dodatniej liczby binarnej b zapisanej

na N bitach jest wartość u wyrażona wzorem:

u = 2

N

– b.

Należy zauważyć, że 2

N

jest wartością większą o jeden od

największej liczby zapisanej na N bitach – czyli liczby

25

największej liczby zapisanej na N bitach – czyli liczby

składającej się z N jedynek.

Przykład:

Niech N = 4.
Poszukujemy uzupełnienia do dwóch liczby b = 0011

(2)

= 3

(10)

2

N

= 2

4

= 16

(10)

= 10000

(2)

2

N

– b = 16

(10)

– 3

(10)

= 13

(10)

= 1101

(2)

Uzupełnieniem do dwóch liczby 0011

(2)

jest 1101

(2)

.

Reprezentacja liczb całkowitych (7)

Przykład: Przedstaw wartość -41

(10)

w kodzie

uzupełnieniowym w komórce 8-bitowej

26

Reprezentacja liczb całkowitych (8)

Zamiana pomiędzy reprezentacją w kodzie
prostym i uzupełnieniowym

zapis liczby dodatniej w kodzie prostym i
uzupełnieniowym jest identyczny;

27

konwersja liczby ujemnej z zapisu w kodzie
prostym na kod uzupełnieniowy (lub z kodu
uzupełnieniowego na prosty):

dokonaj negacji wszystkich bitów z wyjątkiem bitu
znaku,

do otrzymanej wartości dodaj (binarnie) jedynkę.

Reprezentacja liczb całkowitych (9)

Przykład:

Przedstaw sposób reprezentacji w kodzie
uzupełnieniowym w komórce 8-bitowej liczby
-41

(10)

.

28

-41

(10)

.

10101001

(2)

,

kod prosty

11010110

(2)

,

negacja wartości (bez bitu znaku)

00000001

(2)

,

jedynka

11010111

(2)

,

suma (wart. w kodzie uzupeł.)

Reprezentacja liczb całkowitych (10)

Zamiana wartości z kodu uzupełnieniowego na
system dziesiętny

Kolejnym pozycjom przypisywane są
współczynniki będące kolejnymi potęgami liczby 2,
przy czym współczynnik odpowiadający pozycji

29

przy czym współczynnik odpowiadający pozycji
wysuniętej najbardziej w lewo (bit znaku)
uwzględniany jest ze znakiem minus

Przy konwersji na system dziesiętny sumowane
są współczynniki znajdujące się na pozycjach
jedynek w rozpatrywanej liczbie binarnej.

Reprezentacja liczb całkowitych (11)

Przykład:

przedstaw w systemie dziesiętnym wartość
wyrażoną w kodzie uzupełnieniowym jako
10000011

30

Reprezentacja liczb całkowitych (12)

Przykład:

przedstaw w systemie dziesiętnym wartość
wyrażoną w kodzie uzupełnieniowym jako
10000000

31

Reprezentacja liczb całkowitych (13)

Kod uzupełnieniowy:

trudny do stosowany dla człowieka,

ułatwia wykonywanie działań na liczbach
całkowitych ze znakiem - w trakcie obliczeń bit

32

znaku jest traktowany w taki sam sposób jak
pozostałe bity.

Reprezentacja liczb całkowitych (14)

Przykład

:

-2 + 3
-2

10000010

(kod prosty)

11111101

(negacja, bez bitu znaku)

00000001

(jedynka)

11111110

(kod uzupełnieniowy)

33

11111110

(kod uzupełnieniowy)

+3

00000011

(kod prosty)

00000011

(kod uzupełnieniowy)

-2 + 3

11111110

(-2, kod uzupełnieniowy)

00000011

(+3, kod uzupełnieniowy)

1 00000001

(wynik, kod uzupeł., bit przeniesienia jest ignorowany)

00000001

(wynik, kod prosty)

Reprezentacja liczb całkowitych (15)

Cechy maszynowej reprezentacji liczb całkowitych:

w systemach komputerowych mogą być reprezentowane

wartości całkowite z pewnego zakresu - uzależnionego od:

liczby bitów przeznaczonych na przechowywanie jednej

wartości numerycznej,

przyjętego sposobu reprezentacji.

34

wartości całkowite mieszczące się w dopuszczalnym

zakresie przechowywane są w sposób dokładny

wyniki obliczeń realizowanych na liczbach całkowitych są

dokładne (pod warunkiem, że mieszczą się na przyjętej

liczbie bitów)

podstawowym problemem mogącym pojawić się w trakcie

obliczeń na liczbach całkowitych jest błąd nadmiaru -

powstaje wtedy, gdy wynik nie mieści się na przyjętej liczbie

bitów

ilość
bitów

nazwa

zakres

8

char

−128 — +127 (ze znakiem)
0 — +255 (bez znaku)

16

short int

−32 768 — +32 767 (ze znakiem)

35

16

short int

0 — +65 535 (bez znaku)

32

int, long int

−2 147 483 648 — [phone] (ze znakiem)
0 — [phone] (bez znaku)

64

long long int

−9 223 372 036 854 775 808 — [phone] 775 807
(ze znakiem)
0 — [phone] 551 615 (bez znaku)

Reprezentacja liczb rzeczywistych (1)

Do reprezentacji wartości rzeczywistych
stosuje się:

reprezentację stałopozycyjną
(stałoprzecinkową),

36

reprezentację zmiennopozycyjną
(zmiennoprzecinkową, półlogarytmiczną).

Reprezentacja liczb rzeczywistych (2)

Reprezentacja stałopozycyjna:

do przechowania jednej wartości rzeczywistej
wykorzystuje się N bitów,

bit najbardziej wysunięty w lewo przechowuje

37

informację o znaku liczby (0 - dodatnia, 1 -
ujemna)

liczba bitów służących do przechowania
części całkowitej i części ułamkowej jest stała
(stała jest pozycja separatora dziesiętnego -
stąd określenie stałopozycyjny).

Reprezentacja liczb rzeczywistych (3)

Przykład zastosowania reprezentacji
stałopozycyjnej:

do przechowania jednej wartości rzeczywistej
przeznaczono 32 bity, przy czym

38

Zapis liczb rzeczywistych w komputerze
nawiązuje do wykładniczego zapisu liczb,
stosowanego także w arytmetyce dziesiętnej

39

Reprezentacja liczb rzeczywistych (4)

Cechy reprezentacji stałopozycyjnej:

w systemie komputerowym mogą być przechowywane wartości

rzeczywiste z pewnego zakresu,

komputerowa reprezentacja liczb rzeczywistych ma charakter
dyskretny (a nie ciągły),

0.00000000(2) = 0

(10)

40

0.00000000(2) = 0

(10)

0.00000001(2) = 1*2

-8

= 1/256 = 0,00390625

0.00000010(2) = 1 * 2

-7

= 1/128 = 0,0078125

0.00000011(2) = 1 * 2

-7

+ 1 * 2

-8

= 0,01171875

......

więc np. liczba 0,005

(10)

= 0,0000000101...

(2)

Liczby rzeczywiste

nie są

przechowywane w sposób dokładny!!!

Reprezentacja liczb rzeczywistych (5)

Cechy reprezentacji stałopozycyjnej:

pamięć przeznaczona do przechowywania wartości

rzeczywistej nie jest wykorzystywana w sposób

optymalny

np. wartość 0,0000011111 przechowywana jest

41

np. wartość 0,0000011111

(2)

przechowywana jest

jako:

0

00000000000000000000000

00000111

Pominięte zostały dwie ostatnie cyfry, a część

przeznaczona na przechowywanie części

całkowitej nie jest wykorzystana!

Reprezentacja liczb rzeczywistych (6)

Cechy reprezentacji stałopozycyjnej:

może wystąpić błąd nadmiaru

np. liczba złożona z „1” i dwudziestu pięciu „0” nie
może być przechowywana

42

Reprezentacja liczb rzeczywistych (7)

Reprezentacja zmiennopozycyjna

(zmiennoprzecinkowa, półlogarytmiczna)

Każda liczba rzeczywista X może być

przedstawiona w postaci:

X = mantysa * 2

cecha

43

X = mantysa * 2

cecha

gdzie:
mantysa jest wartością rzeczywistą (dodatnią lub

ujemną),

cecha jest wartością całkowitą (dodatnią lub ujemną).

Stosując reprezentację zmiennopozycyjną w

systemie komputerowym przechowywana jest

mantysa oraz cecha liczby.

Liczby rzeczywistej mogą być w pojedynczej (float)

i w podwójnej (double) dokładności (wg. norm IEEE 754)

Załóżmy, że m to liczba cyfr przeznaczonych na mantysę, natomiast n+1 to liczba
cyfr przeznaczonych na wykładnik (n cyfr dla wartości i 1 dla znaku wykładnika).

44

Uznaje się również, że jedna dodatkowa pozycja (najstarsza) zarezerwowana

jest dla zapisu znaku całej liczby. Wówczas wartości maksymalne i minimalne dla
M i E określone są następująco:

Wykładnik E:

E

min

= − B

n

+ 1

E

max

= B

n

− 1

Mantysa M:

M

min

= 1

M

max

= B − B

− (m − 1)

Stąd najmniejsza i największa liczba dodatnia
możliwa do zapisania w takiej reprezentacji to:

Jeśli komputer wygeneruje w trakcie obliczeń liczbę o wartości bezwzględnej

|x| < x

min

to uważa się, że jest to wartość błędna (underflow),

zwykle zamieniana na 0

.

Jeśli komputer wygeneruje w trakcie obliczeń liczbę o wartości bezwzględnej

|x| > x

max

to uważa się, że jest to wartość błędna (overflow) co

zwykle przerywa obliczenia!

Reprezentacja liczb rzeczywistych (9)

Przykładowa liczba: 7(10) = 111(2)

111 = 111 * 2

0

= 11,1 * 2

1

= 1,11 * 2

10

= 0,111 * 2

11

zawsze wybiera się taki sposób reprezentacji, w
którym mantysa (w zapisie binarnym) zaczyna się od
0,1…. Dzięki temu nie ma potrzeby zapamiętywania

46

0,1…. Dzięki temu nie ma potrzeby zapamiętywania
znaków „0,”. Prezentacja spełniająca ten warunek
określana jest jako znormalizowana.

Ostatecznie, liczba rzeczywista 7 przechowywana
jest w postaci:

0111000000000011

Reprezentacja liczb rzeczywistych (10)

Cechy prezentacji zmiennopozycyjnej:

zbiór reprezentowanych wartości jest:

ograniczony,

dyskretny,

liczby rzeczywiste nie są przechowywane w

47

liczby rzeczywiste nie są przechowywane w

sposób dokładny - szczególnie niebezpieczne

jest kumulowanie się błędów w trakcie

obliczeń,

reprezentacja zmiennopozycyjna pozwala

zwykle na lepsze wykorzystanie pamięci niż

reprezentacja stałopozycyjna.

Reprezentacja liczb rzeczywistych (11)

Wybór pomiędzy reprezentacją stało-
i zmiennopozycyjną

Reprezentacja zmiennopozycyjna:

możliwość reprezentowania wartości z większego
zakresu.

48

zakresu.

Reprezentacja stałopozycyjna:

wartości reprezentowane są z taką samą
dokładnością (co jest istotne np. w obliczeniach
finansowych).

Maszynowa reprezentacja informacji

49

Maszynowa reprezentacja informacji

nienumerycznych.

Reprezentacja znaków

W systemie komputerowym każdy tekst
przechowywany jest w postaci binarnej

Jest to możliwe, ponieważ każdy znak (litera,
cyfra, znak przestankowy itp.) jest zamieniany

50

cyfra, znak przestankowy itp.) jest zamieniany
w kod znaku (będący liczbą całkowitą).

Liczbami binarnymi są także informacje
sterujące, określające format tekstu (na
przykład wielkość i kolor czcionki, rozmiar
strony, wielkość marginesu itp.)

Kod ASCII

ASCII - American Standard Code for
Information Interchange.

w wersji podstawowej - 7 bitowy (128 znaków)

w wersji rozszerzonej - 8 bitowy (256 znaków)

51

w wersji rozszerzonej - 8 bitowy (256 znaków)

Kod ASCII

52

Kod ASCII

53

Kod ASCII – problem polskich
znaków

Znaki specyficzne dla języka polskiego

(ąćęłńóśżźĄĆĘŁŃÓŚŻŹ) przypisane mają kody

większe od 128  utrudnia to proces sortowanie,

wyszukiwania i porządkowania danych!!!

Istnieją różne sposoby kodowania polskich znaków
 utrudnia to wymianę dokumentów tekstowych

pomiędzy różnymi systemami.

54

 utrudnia to wymianę dokumentów tekstowych

pomiędzy różnymi systemami.

Podstawowe sposoby kodowania polskich znaków:

MS Windows CP 1250 (Windows Latin-2, Windows-

1250) - sposób kodowania wprowadzony przez firmę

Microsoft wraz z systemem Windows 3.11 PL

ISO Latin-2 (ISO-8859-2, Polska Norma PN-93 T-

42118) - sposób kodowania określony przez ISO,

stosowany powszechnie w Internecie.

Polskie znaki – standardy kodowania

55

Unicode (Unikod)

Unikod (ang. Unicode lub UCS - Universal Character
Set) – sposób kodowania znaków uwzględniający
większości wykorzystywanych znaków w różnych
językach na całym świecie.

Znaki uwzględnione w Unikodzie podzielone zostały

56

Znaki uwzględnione w Unikodzie podzielone zostały
na:

podstawowy zestaw znaków (określany jako Basic
Multilingual Plane - BMP lub Plane 0) – dla tych
znaków stosowane są kody 16 bitowe;

dodatkowy zestaw znaków – stosowane są kody 32
bitowe.

Reprezentacja unikodów

UTF - Unicode Transformation Format – metody

przechowywania unikodów w pamięci komputera:

UTF-8 – kody znaków wchodzących w skład

podstawowego zestawu ASCII zapisywane są jako

wartości jednobajtowe; pozostałe kody zapisywane są

na dwóch, trzech, czterech, pięciu lub sześciu bajtach

57

na dwóch, trzech, czterech, pięciu lub sześciu bajtach

(znaki o kodach zapisywanych na trzech i większej

liczbie bajtów spotykane są we współczesnych

językach bardzo rzadko);

UTF-16 – kody znaków zapisywane są na dwóch,

trzech lub czterech bajtach (najczęściej

wykorzystywane są znaki o kodach dwubajtowych);

UTF-32 – kody znaków zapisywane są na 4 bajtach.

Unicode jest międzynarodowym standardem zbioru
znaków, który może być wykorzystany do pisania
dokumentów w niemalże każdym istniejącym języku.

Wersja 4.0.1 z czerwca 2004 roku zawiera

96 447

znaków z prawie wszystkich języków na świecie.

Unicode z łatwością mieści cały alfabet łaciński, ale
również pismo pochodzenia greckiego, włączając

58

również pismo pochodzenia greckiego, włączając
starożytne i współczesne odmiany oraz cyrylicę używaną
np. w Serbii.

Prawdopodobnie jedna osoba na milion obywateli świata
obecnie mówi językiem, który nie może być sensownie
przedstawiony w Unicode.

W wielu zastosowaniach napisy koduje się
z pomocą kodów kreskowych

59

Kody kreskowe są łatwe do wytworzenia
(zrobi je każda drukarka) i łatwe do

(zrobi je każda drukarka) i łatwe do
automatycznego odczytywania

60

Stosowany w Polsce i Europie trzynastocyfrowy kod
paskowy EAN-13, widziany na większości produktów
kupowanych w sklepach, pozwala kodować jedynie cyfry.

61

Bitmapowa reprezentacja grafiki

Reprezentacja bitmapowa (rastrowa) -
zapamiętywane są parametry każdego
punktu składającego się na obraz.

62

Charakterystyka reprezentacji
bitmapowej

bardzo duże zapotrzebowanie na pamięć,

trudne przekształcenie obrazu (skalowanie,
obrót),

przydatna przy reprezentacji zdjęć (ale nie

63

przydatna przy reprezentacji zdjęć (ale nie
medycznych!).

Obrazy bitmapowe (rastrowe) bywają
często kompresowane (żeby zajmowały
mniej miejsca)

Formaty graficzne:

• GIF

• TIF

64

• TIF

• JPG

Wektorowa reprezentacja grafiki

Reprezentacja wektorowa - przechowywany
jest matematyczny opis elementów
składających się na rysunek

65

Charakterystyka reprezentacji
wektorowej

mniejsze zapotrzebowanie na pamięć
w porównaniu z grafiką rastrową,

łatwiejsze przekształcenie obrazu
(skalowanie, obrót).

66

(skalowanie, obrót).

Zmiana sposobu reprezentacji grafiki

rasteryzacja - budowanie mapy bitowej,
zwykle na podstawie opisu wektorowego.

wektoryzacja - przejście do reprezentacji
wektorowej.

67

wektorowej.

Kompresja jako zmiana sposobu
reprezentacji informacji

Kompresja - przekształcenie sposobu
reprezentacji informacji mające na celu
zmniejszenie zapotrzebowania na pamięć
(wewnętrzną, zewnętrzną) przeznaczoną do
jej przechowywania.

68

jej przechowywania.

Dekompresja - odtworzenie pierwotnego
sposobu reprezentacji informacji.

Rodzaje kompresji

Operacje kompresji i dekompresji najczęściej
dotyczą plików.

Rodzaje kompresji:

bezstratna – plik po dekompresji jest

69

bezstratna – plik po dekompresji jest
dokładnie taki sam jak plik poddany kompresji
(kompresja tekstów, programów),

stratna – plik po dekompresji jest zbliżony do
pliku poddanego kompresji (kompresja
dźwięku, grafiki, filmów).

Kodowanie Huffmana jako przykład
algorytmu kompresji bezstratnej

metoda kompresji bezstratnej (przydatna do

kompresji tekstów, programów),

metoda ta wykorzystuje różnice

w częstościach występowania

poszczególnych znaków w tekście (krótsze

70

poszczególnych znaków w tekście (krótsze

kody przypisywane są znakom częściej się

pojawiającym, zaś dłuższe znakom rzadko

występującym),

metoda ta wykorzystywana jest

w popularnych programach pakujących

(np. pkzip, arj, rar).

Przykładowe zastosowanie algorytmu
Huffmana (1)

Załóżmy, że:

w tekście występują tylko cztery znaki: A, B, C, D,

długość tekstu wynosi 1000 znaków

Przed kompresją:

do zakodowania jednego znaku potrzebne są 2 bity:

71

do zakodowania jednego znaku potrzebne są 2 bity:

A – 00
B – 01
C – 10
D – 11

do zakodowania tekstu o długości 1000 znaków
potrzebny jest obszar pamięci o wielkości 2000 bitów.

Przykładowe zastosowanie algorytmu
Huffmana (2)

Proces kompresji:

wyznacza się częstości wystąpienia każdego
ze znaków

72

ze znaków

A (45%)
B (15%)
C (35%)
D (5%)

Przykładowe zastosowanie algorytmu
Huffmana (3)

Proces kompresji:

porządkuje się elementy względem częstości
występowania (od najrzadziej do najczęściej

73

występowania (od najrzadziej do najczęściej
występującego)

D (5%)
B (15%)
C (35%)
A (45%)

Przykładowe zastosowanie algorytmu
Huffmana (4)

Proces kompresji:

w kolejnych krokach pobiera się dwa

najrzadziej

występujące elementy, łączy w jeden

74

występujące elementy, łączy w jeden

i umieszcza na odpowiedniej pozycji listy

krok 1 – połączenie elementów D i B

(D, B) (20%)
C

(35%)

A

(45%)

Przykładowe zastosowanie algorytmu
Huffmana (5)

Proces kompresji:

krok 2 – połączenie (D, B) i C

A

(45%)

75

A

(45%)

((D, B), C)

(55%)

krok 3 – połączenie A i ((D, B), C)

(A, ((D, B), C)) (100%)

Przykładowe zastosowanie algorytmu
Huffmana (6)

Proces kompresji:

Uzyskany element (A, ((D, B), C)) przedstawia
się w postaci drzewa

76

się w postaci drzewa

C

A

D

B

Kody znaków

A – 0
B – 101
C – 11
D – 100

Przykładowe zastosowanie algorytmu
Huffmana (7)

Długość tekstu w postaci skompresowanej

A: 1 * 0.45 * 1000 = 450 bitów
B: 3 * 0.15 * 1000 = 450 bitów
C: 2 * 0.35 * 1000 = 700 bitów

77

C: 2 * 0.35 * 1000 = 700 bitów
D: 3 * 0.05 * 1000 = 150 bitów
SUMA:

1750 bitów

Realizacja kompresji bezstratnej

78