Informatikai Rendszerek Alapjai

Informatikai Rendszerek Alapjai Dr. Kutor László

A redundancia fogalma és mérése Minimális redundanciájú kódok 1. http://uni-obuda.hu/users/kutor/ IRA 2014 könyvtár 2014. ősz

Óbudai Egyetem, NIK

Dr. Kutor László

IEA 7/31/1

Betű kiválasztása a 8 bites ASCII karakterkészletből

H=log 2 256

2014. ősz


Dr. Kutor László

=8

IEA 7/31/2

R. Hartley „formula” (egyenlő előfordulási valószínűségű) „elemek” kiválasztásához kapcsolódó információ mérésére (nagyságának kiszámolására)

H= k * log n

H = I !!!

Ahol H = az információ (I) mennyiség egy üzenet (szó) kiválasztásakor n = az üzenet - ABC betűinek száma k = a betűk száma az üzenetben (szóban) Az információ mértékegységei különböző logaritmusok estén: I = k * log10 n [ Hartley] I = k * log2 n [ Shannon, I = k * loge n [ Nat ] 2014. ősz


bit]

Dr. Kutor László

IEA 7/31/3

Példák az egy elem kiválasztását leíró információ nagyságára

I = 1,

2,

3,

4,

5

I(xi) = log2 (n), vagy - log2 (1/n), vagy - log2 (p(xi))

2014. ősz


Dr. Kutor László

IEA 7/31/4

C. E. Shannon „formula”

R. Hartley „formula” (különböző előfordulási valószínűségű) „elemek” kiválasztásához kapcsolódó információ mérésére (nagyságának kiszámolására) vagyis

Hány bit szükséges egy tetszőleges üzenet elem továbbításához?! Legyenek: x1,x2,x3,….xi,

xn

egyedi közlemények

S = x1+x2+x3+…+xi+….. xn az összes üzenet I(S) = az összes üzenet információ tartalma p(x1), p(x2), p(x3), p(xi), p(xn) = az üzenetek előfordulási valószínűsége 2014. ősz


Dr. Kutor László

IEA 7/31/5

A Shannon „formula” magyarázata Ha a kibocsátott üzenetek száma: M, akkor Xi előfordulásának száma:

IM =

gi = M * p(xi)

g1*I(x1) + …gi*I(xi)

+

gn*I(Xn)

I(xi) = az i-ik üzenet információ tartalma = - log2 p(xi)

IM= - M* ∑ p( xi) * log2p(xi) I (S) = - ∑ p(xi) * log2p(xi) ?! 2014. ősz


Dr. Kutor László

IEA 7/31/6

A relatív információ. Redundancia köznapi értelmezése: terjengősség A redundancia információelméleti értelmezése: n

IS = - ∑ p(xi)* log2p(xi) i=1

n

(Shannon)

A kód információ tartalma ténylegesen

Imax = - ∑ 1/n * log (1/n)= - log (1/n) = log (n) i=1

(Hartley) A kód információ tartalma, ha a kódban lévő elemek egyenlő előfordulási valószínűségűek lennének IS

Irelatív = 2014. ősz

Imax

= az információ-forrás „jósága”


Dr. Kutor László

IEA 7/31/7

Az információ redundanciája 2. IS = a hírforrás információ tartalma Imax = a hírforrás maximális információ tartalma Irelatív =

IS

= az információ forrás „jósága”

Imax

RS = (1 -

IS Imax

) * 100

A hírforrás által közölt információ hány százaléka „felesleges”

1.684 Példa: IS = 1.684 Imax = 2 Irelatív = 0.842 2 = RS = (1 – 0.842) * 100 = 15.8 ~~ 16% 2014. ősz


Dr. Kutor László

IEA 7/31/8

A magyar nyelv betűgyakorisága és információ tartalma 10 000 szavas újságszöveg alapján Fülöp Géza

http://www.mek.oszk.hu/03100/03118/html/#5

Gyakoriság Információ Gyakoriság Információ Gyakoriság Információ (% ) tartalom (bit) (% ) tartalom (bit) (% ) tartalom (bit)

A Á B C D E É F G H I 2014. ősz

9,35 3,72 1,72 0,60 1,71 9,71 3,87 0,88 3,55 1,23 4,39

3,43 4,77 5,87 7,40 5,90 3,37 4,71 6,87 4,83 6,37 4,53

J K L M N O Ö P R S T U

1,21 5,35 6,30 3,92 5,47 4,47 2,14 1,04 4,22 6,57 7,87 1,29


6,39 4,24 4,00 4,69 4,21 4,50 5,57 6,61 4,58 3,94 3,68 6,30

Ü V X Y Z

0,93 1,81 0,01 2,21 4,46

6,77 5,81 13,33 5,52 4,50

I átlag = 4.44 bit

Dr. Kutor László

IEA 7/31/9

Az angol nyelv betűgyakorisága Betű A B C D E F G H I J K L M

Betű Információ [bit] gyakoriság 8,4966% 3,5570 2,0720% 5,5928 4,5388% 4,4615 3,3844% 4,8850 11,1607% 3,1635 1,8121% 5,7862 2,4705% 5,3391 3,0034% 5,0573 7,5448% 3,7284 0,1965% 8,9913 1,1016% 6,5043 5,4893% 4,1872 3,0129% 5,0527

Betű N O P Q R S T U V W X Y Z

Betű Információ[bit] gyakoriság 6,6544% 3,9095 7,1635% 3,8032 3,1671% 4,9807 0,1961% 8,9942 7,5809% 3,7215 5,7351% 4,1240 6,9509% 3,8467 3,6308% 4,7836 1,0074% 6,6332 1,2899% 6,2766 0,2902% 8,4287 1,7779% 5,8137 0,2722% 8,5211

I átlag = 4.22 bit 2014. ősz


Dr. Kutor László

IEA 7/31/10

Az információ redundanciája (példa) IS = a hírforrás információ tartalma (entrópiája) Imax = a hírforrás maximális információ tartalma Irelatív =

IS

= az információ forrás „jósága”

Imax

RS = 1 -

IS Imax

A hírforrás által közölt információ * 100 hány százaléka „felesleges”

1.684 Példa: IS = 1.684 Imax = 2 Hr = = 0.842 2 RS = (1 – 0.842) * 100 = 15.8 ~~ 16% 2014. ősz


Dr. Kutor László

IEA 7/31/11

A kódolás folyamata és fogalmai U Forrás

A Kódoló

A* Csatorna

U* Dekódoló

Vevő

A kódolás céljai: U-nak A-ba történő leképezése minimális redundancia létrehozásával

„Forrás kódolás”

U-nak A-ba történő leképezése növelt redundancia létrehozásával

„Csatorna kódolás”

U-nak A-ba történő leképezése a kódrendszer titkos megváltoztatásával

„Titkosító kódolás”

2014. ősz


Dr. Kutor László

IEA 7/31/12

A kódolással szemben támasztott

követelmények 1. Egyértelmű dekódolhatóság: nem redukálható = „irreducibilis” kód ! Feltétele: hogy egyik kódszó sem lehet a másik kódszó része 2. Forráskódolásnál a minimális szóhossz 3. Csatornakódolásnál a hibák észlelése és javítása 4. Titkosító kódolásnál a „megfelelően” nehéz dekódolhatóság 2014. ősz


Dr. Kutor László

IEA 7/31/13

Morse távíró

2014. ősz


Dr. Kutor László

Morse kód (redukálható) A .J .--- S ... B -... K -.- T C -.-. L .-.. U ..D -.. M -- V ...W .-E . N -. X -..F ..-. O --Y -.-G --. P .--. Z --.. H .... Q --.- 0 ----I .. R .-. 1 .---2014. ősz


2 ..--3 ...-4 ....5 ..... 6 -.... 7 --... 8 ---.. 9 ----. Fullstop .-.-.Comma --..-Query ..--..

Dr. Kutor László

IEA 7/31/15

Tömörítő programok hatékonysága A kiinduló fájl típusa:

.exe

.img

.txt

A kiinduló fájl mérete:

277 766

168 974

151 579

Huffman

103 408

57 383

42 576

LZW

117 811

55 108

48 322

Aritmetikai

177 042

79 870

101 322

PKZIP

96 525

56 380

39 953

ARJ

92 560

50 236

36 913 Koschek Vilmos

2014. ősz


Dr. Kutor László

IEA 7/31/16

Tömörítő programok tesztje 1. Szövegfájlok „méret szerint” Kiinduló fájlok mérete: 1.22 MBájt

www.internews.hu 2014. ősz


Dr. Kutor László

IEA 7/31/17

Tömörítő programok tesztje 3. .doc fájlok „méret szerint” Kiinduló fájl mérete: 12.34 MBájt

2014. ősz


Dr. Kutor László

IEA 7/31/18

Tömörítő programok tesztje 2. . exe fájlok „méret szerint” Kiinduló fájl mérete: 8.47 MBájt

2014. ősz


Dr. Kutor László

IEA 7/31/19

Tömörítő programok tesztje 7. kép fájlok (.png) „méret szerint” Kiinduló fájl mérete: 70.62 MBájt

2014. ősz


Dr. Kutor László

IEA 7/31/20

Tömörítő programok tesztje 9. hang fájlok (.wav) „méret szerint” Kiinduló fájl mérete: 15.66 MBájt

www.internews.hu 2014. ősz


Dr. Kutor László

(„Kamil”)

IEA 7/31/21

Statisztikára épülő adattömörítés Forrás

Kódoló

Csatorna

Statisztika

Dekódoló

Vevő

Statisztika

Előnye: biztosítja a minimális átlagos szóhosszat (minimum redundanciát) Hátránya: a statisztikát is továbbítani kell 2014. ősz


Dr. Kutor László

IEA 7/31/22

Minimum redundanciájú kódok 1: Shannon-Fano kód Claude Shannon Bell Lab.

~1950

R.M. Fano M.I.T.

Az üzenetek (szimbólumok) előfordulási gyakoriságának (valószínűségének) ismeretében létrehozható olyan kód amely ♦ egyértelműen dekódolható ♦ változó (szó) hosszúságú ♦ a kódszavak hossza a kódolt szimbólumok előfordulási valószínűségétől függ

2014. ősz

Gyakori szimbólum

rövid kód

Ritka szimbólum

hosszú kód


Dr. Kutor László

IEA 7/31/23

A Shannon-Fano algoritmus 1.  Az üzenetekben előforduló szimbólumok előfordulási 2.  3.  4.  5. 

2014. ősz

gyakoriságának meghatározása A szimbólumok gyakoriság szerinti csökkenő sorrendbe rendezése A lista két részre osztása úgy, hogy a két részben lévő szimbólumok összesített gyakorisága (közel) egyenlő legyen A lista felső részéhez „0”-át, az alsó részéhez „1”-et rendelünk (vagy fordítva) A 3.-ik és 4.-ik eljárást addig ismételjük, amíg a kettéosztott lista mindkét részében csak 1-1 szimbólum található


Dr. Kutor László

IEA 7/31/24

Példa a Shannon – Fano algoritmusra Szimbólumok

A B C D E A (15) (22) 0 B (7) C (6) D (6) (17) 1 E (5) 2014. ősz

Előfordulások száma

15 7 6 6 5

A (15) B (7) C (6) D (6) E (5)

Információ tartalom

1.38 2.48 2.7 2.7 2.96

0 1 0 D (6) 0 1 E (5) 1


A= B= C= D= E=

Bitek száma

20.68 17.35 16.2 16.2 14.82 00 01 10 110 111

ASCII 39* 8 = 312 Shannon-Fano 89?

Dr. Kutor László

IEA 7/31/25

Minimum redundanciájú kódok 2: D.A. Huffman (1952) Huffman kód 1.  Az üzenetekben előforduló szimbólumok előfordulási

gyakoriságának meghatározása 2.  A szimbólumok gyakoriság szerinti csökkenő sorrendbe rendezése 3.  A két legkevésbé gyakori szimbólumot összevonjuk és beírjuk a szimbólumok közé a gyakorisági sorba 4.  A 3.-ik pontot addig ismételjük, amíg 2 elemű lesz a lista. Ekkor az egyik elemhez „0”-át a másikhoz „1”-et rendelünk. 5.  Visszalépünk az előző összevont szimbólumhoz, és az előbbivel azonos sorrendben a két szimbólumhoz „0”-át és „1”-etrendelünk, mindaddig, míg vissza nem jutunk az egyes szimbólumokhoz 2014. ősz


Dr. Kutor László

IEA 7/31/26

Példa a Huffman algoritmusra Szimbólumok

A B C D E A (15) B (7) C (6) D (6) 1 E (5) 0 2014. ősz

Előfordulások száma

15 7 6 6 5

Információ tartalom

1.38 2.48 2.7 2.7 2.96

A (15) A (15) BCDE(24) 1 DE (11) BC(13) 1 A (15) 0 B (7) 1 DE (11) 0 C (6) 0

Bitek száma

20.68 17.35 16.2 16.2 14.82 A= 0 B = 111 C = 110 D = 101 E = 100

ASCII 39* 8 = 312 Huffmann 87? Óbudai Egyetem, NIK

Dr. Kutor László

IEA 7/31/27

1/2 példa a „Huffman”algoritmusra: Dekódolás Dekódolandó üzenet: 1101001010111101000110…

Kódtábla: A= 0 B = 111 C = 110 D = 101 E = 100 Visszafejtett kód:

2014. ősz

C

E D A B D AAAC

CEDABDAAAC Óbudai Egyetem, NIK

Dr. Kutor László

IEA 7/31/28

A kódolási példa fa szerkezete D D

E 1

0

DE 0

B

C

E B 1

0 1

A „levelek” C

A= 0 B = 111 C = 110 D = 101 E = 100

BC

BCDE 1 0 A „gyökér” 2014. ősz


Dr. Kutor László

IEA 7/31/29

2. példa a „Huffman” algoritmusra: Kódolandó szöveg: ” Semmi nem olyan egyszerű,

mint amilyennek látszik” 1. A karakterek gyakoriságának meghatározása „= 2, S=1, e=6, m=5, i=4, _=6, n=5, o=1, l=3, y=3, a=2, g=1, s=2, z=2, r=1, ű=1, ,=1, t=2, k=2 ∑=50 2. Gyakoriság szerinti rendezés 3. A kevésbé gyakori karaktereket kettesével összevonjuk és beírjuk a gyakorisági sorba, ami két elemű lesz a lista 4. A lista elemekhez rendre 0-át és 1-et rendelve létrehozzuk, majd kiolvassuk a kódot 2014. ősz


Dr. Kutor László

e(6) (6) m(5) n(5) i(4) l(3) y(3) ”(2) a(2) s(2) z(2) t(2) k(2) o(1) r(1) ű(1) g(1) ,(1) IEA 7/31/30

Kérdések: -  Hogyan befolyásolja a eseménytér egyes eseményeinek előfordulási valószínűsége a kiválasztásukhoz tartozó információ nagyságát? -  Miért van nagy jelentősége a redundanciának az informatikában és az életben? -  Miért lehet veszteségmentesen tömöríteni az emberi kommunikációból származó információkat?

2014. ősz


Dr. Kutor László

IEA 7/31/31

Informatikai Rendszerek Alapjai

Recommend Documents