Az Informatika Elméleti Alapjai dr. Kutor László
Az üzenet információ-tartalma, redundanciája Minimális redundanciájú kódok http://mobil.nik.bmf.hu/tantárgyak/iea.html Felhasználónév: iea 2007. ősz
BMF NIK
Jelszó: IEA07 dr. Kutor László
IEA 7/1
Az Információ értelmezése Az információ szó szinonimái a köznapi használatban: Tájékoztatás Hír, Újság Adat Felvilágosítás Közlés Tudás Bejelentés Jellemzés Értesülés Tudományos értelemben: Az információ olyan „mennyiség” amely egy eseményrendszer egyik vagy másik eseményének bekövetkezéséről, (illetve egy állapottér egyik vagy másik állapotáról) elemi szimbólumok sorozatával közölhető. Az információ a bizonytalanság csökkentésének mennyisége 2007. ősz
BMF NIK
dr. Kutor László
IEA 7/2
Egy kártya kiválasztásához tartozó információ. 4
5
2
3
1
2007. ősz
BMF NIK
dr. Kutor László
IEA 7/3
R. Hartley „formula” az információ mérésére
H= k * log n Ahol H = az információ 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: H = k * log10 n [ Hartley] H = k * log2 n [ Shannon, 2007. ősz
H = k * loge n [ Nat ] BMF NIK
bit]
dr. Kutor László
IEA 7/4
C. E. Shannon és N.Wiener információ értelmezése Véges számú közleményből véletlenszerűen választunk ki egyet Kérdés: „Milyen következtetést vonhatunk le az egész közlemény bizonytalanságára?”
H(S) = - ∑ p{ xi}* log2p{xi} Ahol
H(S) = a közlemény információ tartalma S(x1,x2,x3,….xi, xn) = a közlemények
P{x1}, P{x2}, P{x3}, P{xi}, P{xn} = az üzenetek előfordulási valószínűsége 2007. ősz
BMF NIK
dr. Kutor László
IEA 7/5
Shannon információra vonatkozó összefüggése Kibocsátott üzenetek száma: M Xi előfordulásának száma:
IM = g1*I(x1)
gi = M * Xi
+ …gi*I(xi)
+
gn*I(Xn)
IM= - M* ∑ p{ xi}* log2p{xi} H(S) = - ∑ p{ xi}* log2p{xi} 2007. ősz
?
BMF NIK
dr. Kutor László
IEA 7/6
Az információ redundanciája 1. Redundancia köznapi értelmezése: terjengősség A redundancia információ elméleti értelmezése: n HS = - ∑ p{ xi}* log2p{xi} (Shannon) i=1 n
Hmax = - ∑ 1/n * log (1/n)= - log (1/n) = log (n) i=1
(Hartley)
HS
Hrelatív =
= az információ forrás „jósága”
Hmax
2007. ősz
BMF NIK
dr. Kutor László
IEA 7/7
Az információ redundanciája 2. HS = a hírforrás információ tartalma (entrópiája) Hmax = a hírforrás maximális információ tartalma HS
Hrelatív =
Hmax
RS = 1 -
HS Hmax
= az információ forrás „jósága”
*
A hírforrás által közölt információ 100 hány százaléka „felesleges”
1.684 = 0.842 2 = (1 – 0.842) * 100 = 15.8 ~~ 16%
Példa: HS = 1.684 Hmax = 2
RS 2007. ősz
BMF NIK
Hr =
dr. Kutor László
IEA 7/8
Példa az írott szöveg redundancájára 1 ( a szöveg minden 3 karakteréből 2 elhagyva) A programozók (minden ellenkező híresztelés ellenére) emberek, akik éjnek éjjelén, teljesen alkalmatlan fejlesztőprogramokkal, hibáktól hemzsegő hardverek egymáshoz nem illeszthető konglomerátumán megkísérlik, hogy a feladatra alkalmatlan megbízóik megrendelésére megbízóik egymásnak ellentmondó kívánságait olyan programokká alakítsák át, amelyeket aztán a végén, senki sem fog használni. 2007. ősz
BMF NIK
dr. Kutor László
IEA 7/9
Példa az írott szöveg redundancájára 2 ( a szöveg minden 3 karakteréből 1 elhagyva) A programozók (minden ellenkező híresztelés ellenére) emberek, akik éjnek éjjelén, teljesen alkalmatlan fejlesztőprogramokkal, hibáktól hemzsegő hardverek egymáshoz nem illeszthető konglomerátumán megkísérlik, hogy a feladatra alkalmatlan megbízóik megrendelésére megbízóik egymásnak ellentmondó kívánságait olyan programokká alakítsák át, amelyeket aztán a végén, senki sem fog használni. 2007. ősz
BMF NIK
dr. Kutor László
IEA 7/10
Példa az írott szöveg redundancájára 1 ( a szöveg minden karaktere kiírva) A programozók (minden ellenkező híresztelés ellenére) emberek, akik éjnek éjjelén, teljesen alkalmatlan fejlesztőprogramokkal, hibáktól hemzsegő hardverek egymáshoz nem illeszthető konglomerátumán megkísérlik, hogy a feladatra alkalmatlan megbízóik megrendelésére megbízóik egymásnak ellentmondó kívánságait olyan programokká alakítsák át, amelyeket aztán a végén, senki sem fog használni. 2007. ősz
BMF NIK
dr. Kutor László
IEA 7/11
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
9,35 3,72 1,72 0,60 1,71 9,71 3,87 0,88 3,55 1,23 4,39 2007. ősz
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 BMF NIK
6,39 4,24 4,00 4,69 4,21 4,50 5,57 6,61 4,58 3,94 3,68 6,30
dr. Kutor László
Ü 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 IEA 7/12
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
Huffmann
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
2007. ősz
BMF NIK
dr. Kutor László
IEA 7/13
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 2007. ősz
BMF NIK
dr. Kutor László
IEA 7/14
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 („Kamil”) 2007. ősz
BMF NIK
dr. Kutor László
IEA 7/15
Tömörítő programok tesztje 2. Szövegfájlok „idő szerint” Kiinduló fájlok mérete: 1.22 MBájt
www.internews.hu („Kamil”) 2007. ősz
BMF NIK
dr. Kutor László
IEA 7/16
Tömörítő programok tesztje 3. .doc fájlok „méret szerint” Kiinduló fájl mérete: 12.34 MBájt
www.internews.hu („Kamil”) 2007. ősz
BMF NIK
dr. Kutor László
IEA 7/17
Tömörítő programok tesztje 4. .doc fájlok „idő szerint” Kiinduló fájl mérete: 12.34 MBájt
www.internews.hu („Kamil”) 2007. ősz
BMF NIK
dr. Kutor László
IEA 7/18
Tömörítő programok tesztje 2. . exe fájlok „méret szerint” Kiinduló fájl mérete: 8.47 MBájt
www.internews.hu („Kamil”) 2007. ősz
BMF NIK
dr. Kutor László
IEA 7/19
Tömörítő programok tesztje 6. . exe fájlok
Kiinduló fájl mérete: 8.47 MBájt
www.internews.hu („Kamil”) 2007. ősz
BMF NIK
dr. Kutor László
IEA 7/20
Tömörítő programok tesztje 7. kép fájlok (.png) „méret szerint” Kiinduló fájl mérete: 70.62 MBájt
www.internews.hu („Kamil”) 2007. ősz
BMF NIK
dr. Kutor László
IEA 7/21
Tömörítő programok tesztje 8. kép fájlok (.png) „idő szerint” Kiinduló fájl mérete: 70.62 MBájt
www.internews.hu („Kamil”) 2007. ősz
BMF NIK
dr. Kutor László
IEA 7/22
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 („Kamil”) 2007. ősz
BMF NIK
dr. Kutor László
IEA 7/23
Tömörítő programok tesztje 10. hang fájlok (.wav) „idő szerint” Kiinduló fájl mérete: 15.66 MBájt
www.internews.hu („Kamil”) 2007. ősz
BMF NIK
dr. Kutor László
IEA 7/24
Tömörítő programok tesztje 11. Tömörítvények (.zip) „méret szerint” Kiinduló fájl mérete: 6.61 MBájt
www.internews.hu („Kamil”) 2007. ősz
BMF NIK
dr. Kutor László
IEA 7/25
Tömörítő programok tesztje 12. Tömörítvények (.zip) „idő szerint” Kiinduló fájl mérete: 6.61 MBájt
www.internews.hu („Kamil”) 2007. ősz
BMF NIK
dr. Kutor László
IEA 7/26
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”
2007. ősz
BMF NIK
dr. Kutor László
IEA 7/27
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 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
2007. ősz
BMF NIK
dr. Kutor László
IEA 7/28
Morse kód (redukálható) J .--- S ... A .B -... K -.- T C -.-. L .-.. U ..D -.. M -- V ...N -. W .-E . X -..F ..-. O --Y -.-G --. P .--. Z --.. H .... Q --.- 0 ----R .-. 1 .---I .. 2007. ősz
BMF NIK
2 ..--3 ...-4 ....5 ..... 6 -.... 7 --... 8 ---.. 9 ----. Fullstop .-.-.Comma --..-Query ..--..
dr. Kutor László
IEA 7/29
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 2007. ősz
BMF NIK
dr. Kutor László
IEA 7/30
Minimum redundanciájú kódok 1. Shannon-Fano kód Claude Snannon 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
2007. ősz
Gyakori szimbólum
rövid kód
Ritka szimbólum
hosszú kód BMF NIK
dr. Kutor László
IEA 7/31
A Shannon-Fano algoritmus 1. Az üzenetekben előforduló szimbólumok előfordulási 2. 3. 4. 5.
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ó
2007. ősz
BMF NIK
dr. Kutor László
IEA 7/32
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) 2007. ő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
BMF NIK
Bitek száma
20.68 17.35 16.2 16.2 14.82
A = 00 B = 01 C = 10 D = 110 E = 111 ASCII 39* 8 = 312 Shannon-Fano 89?
dr. Kutor László
IEA 7/33
Minimum redundanciájú kódok 2. Huffmann kód D.A. Huffmann (1952) 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 2007. ősz
BMF NIK
dr. Kutor László
IEA 7/34
Példa a Huffmann algoritmusra Szimbólumok
A B C D E A (15) B (7) C (6) D (6) 1 E (5) 0
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
2007. ősz
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? BMF NIK
dr. Kutor László
IEA 7/35
1/2 példa a „Huffmann”algoritmusra: Dekódolás Dekódolandó üzenet: 1101001010111101000110…
Kódtábla: A= 0 B = 111 C = 110 D = 101 E = 100 Visszafejtett kód:
2007. ősz
C
E D A B D AAAC
CEDABDAAAC BMF NIK
dr. Kutor László
IEA 7/36
A kódolási példa fa szerkezete BCDE 1 0
DE
D
1
1
D 2007. ősz
0
0
„gyökér”
A= 0 B = 111 C = 110 D = 101 E = 100
BC
E B 1
E
A
B
0
C
C BMF NIK
A „levelek” dr. Kutor László
IEA 7/37
2. példa a „Huffmann” algoritmusra: Kódolás Kódolandó szöveg: ” Semmi nem olyan egyszerű,
e(6) (6) m(5) mint amilyennek látszik” n(5) 1. A karakterek gyakoriságának meghatározása i(4) l(3) „= 2, S=1, e=6, m=5, i=4, _=6, n=5, y(3) o=1, l=3, y=3, a=2, g=1, s=2, z=2, ”(2) r=1, ű=1, ,=1, t=2, k=2 ∑=50 a(2) 2. Gyakoriság szerinti rendezés s(2) z(2) 3. A kevésbé gyakori karaktereket kettesével t(2) összevonjuk és beírjuk a gyakorisági sorba, k(2) o(1) ami két elemű lesz a lista r(1) 4. A lista elemekhez rendre 0-át és 1-et rendelve ű(1) g(1) létrehozzuk, majd kiolvassuk a kódot ,(1) 2007. ősz
BMF NIK
dr. Kutor László
IEA 7/38