Az Informatika Elméleti Alapjai Dr. Kutor László
Az üzenet információ-tartalma és redundanciája Minimális redundanciájú kódok Statisztika alapú tömörítő algoritmusok http://mobil.nik.bmf.hu/tantargyak/iea.html Felhasználónév: iea 2010. tavasz
OE NIK
Jelszó: IEA07 Dr. Kutor László
IEA 8/1
C. E. Shannon és N.Wiener információ értelmezése Kérdés: „Véges számú közleményből
véletlenszerűen kiválasztunk ki egyet, és ebből milyen következtetést vonhatunk le az egész közlemény bizonytalanságára?”
Hány bit szükséges egy üzenet továbbításához?! Legyen: x1,x2,x3,….xi,
xn
= az egyedi közlemények
S = x1+x2+x3+…+xi+….. xn (Az összes üzenet) H(S) = a közlemény információ tartalma P{x1}, P{x2}, P{x3}, P{xi}, P{xn} = az üzenetek előfordulási valószínűsége 2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/2
A „Shannon összefüggés” 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) H(S) = - p( xi)* log2p(xi) ?! 2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/3
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
Hrelatív =
2010. tavasz
HS Hmax
(Hartley)
= az információ-forrás „jósága” OE NIK
Dr. Kutor László
IEA 8/4
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 2010. tavasz
OE NIK
Hr =
Dr. Kutor László
IEA 8/5
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. 2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/6
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. 2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/7
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. 2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/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
9,35 3,72 1,72 0,60 1,71 9,71 3,87 0,88 3,55 1,23 4,39 2010. tavasz
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 OE 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
Ü 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 8/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 2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/10
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
2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/11
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”) 2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/12
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”) 2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/13
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”) 2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/14
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”) 2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/15
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”) 2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/16
Tömörítő programok tesztje 6. . exe fájlok
Kiinduló fájl mérete: 8.47 MBájt
www.internews.hu („Kamil”) 2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/17
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”) 2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/18
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”) 2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/19
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”) 2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/20
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”) 2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/21
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”) 2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/22
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”) 2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/23
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”
2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/24
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 2010. tavasz
OE NIK
Dr. Kutor László
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 .. 2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/25
2 ..--3 ...-4 ....5 ..... 6 -.... 7 --... 8 ---.. 9 ----. Fullstop .-.-.Comma --..-Query ..--.. IEA 8/26
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 2010. tavasz
OE NIK
Dr. Kutor László
Minimum redundanciájú kódok 1. Shannon-Fano kód Claude Shannon Bell Lab.
IEA 8/27
~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 Gyakori szimbólum
rövid kód
Ritka szimbólum
hosszú kód
2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/28
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ó
2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/29
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) 2010. tavasz
Előfordulások száma
15 7 6 6 5
A (15) B (7) C (6) D (6) E (5) OE NIK
Információ tartalom
1.38 2.48 2.7 2.7 2.96
0 1 0 D (6) 0 1 E (5) 1 Dr. Kutor László
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? IEA 8/30
Minimum redundanciájú kódok 2. D.A. Huffmann (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 2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/31
Példa a Huffman algoritmusra Szimbólumok
A B C D E
Előfordulások száma
15 7 6 6 5
Információ tartalom
1.38 2.48 2.7 2.7 2.96
Bitek száma
20.68 17.35 16.2 16.2 14.82
A (15) A (15) BCDE(24) A (15) 1 A= 0 DE (11) BC(13) 1 A (15) B (7) = 111 0 B C = 110 C (6) B (7) 1 DE (11) 0 D = 101 D (6) 1 C (6) 0 E = 100 E (5) 0 ASCII 39* 8 = 312 Huffmann
2010. tavasz
OE NIK
Dr. Kutor László
87?
IEA 8/32
1/2 példa a „Huffman”algoritmusra: Dekódolás Dekódolandó üzenet: 1101001010111101000110…
Kódtábla:
C
A= 0 B = 111 C = 110 D = 101 E = 100 Visszafejtett kód:
E D A B D AAAC
CEDABDAAAC
2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/33
A kódolási példa fa szerkezete BCDE 1 0
DE
D
1
1
D 2010. tavasz
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 OE NIK
A „levelek” Dr. Kutor László
IEA 8/34
2. példa a „Huffman” algoritmusra: 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) 2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/35
FAX gépek adattömörítése CCITT szerint G1, G2, G3 (G4?) G1 G2 G3
A4-es oldal továbbításához szükséges idő: 6 perc 3 perc 40-60 s
felbontás (vonal/mm) 3.85 3.85 3.85(7.7)
átvitel vivő
analóg (1300.1700 Hz) analóg (2100) CCITT (2400 bit/s)
A 215 mm hosszú sor 1728 pontból áll Egydimenziós kódolás
Kétdimenziós kódolás (15 – 20 mp) 2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/36
Minimum redundanciájú kódok 3. (1952) Aritmetikai kód US Pat. #: 4,905,297 Az egész üzenetet egy számmal helyettesítjük
Például: BILL GATES
2010. tavasz
OE NIK
0.2572167752
Dr. Kutor László
IEA 8/37
Az aritmetikai kódolás algoritmusa 1. Az üzenetekben előforduló szimbólumok előfordulási
gyakoriságának meghatározása 2. Minden szimbólumhoz hozzárendelünk egy 0 – 1 közé eső számtartományt. A számtartomány nagysága arányos a szimbólum relatív gyakoriságával 3. A teljes karaktersorozatot egy számmá alakítjuk. Az átalakítást úgy végezzük, hogy az üzenetben egymás után következő karakterek által kijelölt számtartományt lépésről lépésre beszűkítjük, míg végül egy számhoz jutunk
2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/38
1. példa az aritmetikai kódolásra Kódolandó szöveg: ALMA Szimbólumok Előfordulások Relatív száma gyakoriság
A L M
2 1 1
2/4 1/4 1/4
A
Számtartomány
0 <=tA< 0.5 0.5 <=tL< 0.75 0.75<=tM< 1
L
M
0 <= tA < 0. 5 0.25 <= tAL < 0.375 0…. <= tALM < 0….. 0…. <= tALMA< 0….. 2010. tavasz
OE NIK
Dr. Kutor László
IEA 8/39
2. példa az aritmetikai kódolásra Kódolandó szöveg: Szimbólumok
-_ A B E G I L S T
2010. tavasz
„Data Compression book Mark Nelson 1991 Számtartomány
BILL_GATES
Előfordulások Relatív száma gyakoriság
1 1 1 1 1 1 2 1 1
1/10 1/10 1/10 1/10 1/10 1/10 2/10 1/10 1/10
OE NIK
0.00 0.10 0.20 0.30 0.40 0.50 0.60 0.80 0.90
Dr. Kutor László
<= t_< <= tA< <= tB< <= tE< <= tG< <= tI< <= tL< <= tS< <= tT<
0.10 0.20 0.30 0.40 0.50 0.60 0.80 0.90 1.00
IEA 8/40
2/2. példa az aritmetikai kódolásra Kódolt szöveg:
BILL_GATES
Számtartomány
„Kódtáblázat” 0.00 0.10 0.20 0.30 0.40 0.50 0.60 0.80 0.90
<= __ < <= A < <= B < <= E < <= G < <= I < <= L < <= S < <= T <
0.10 0.20 0.30 0.40 0.50 0.60 0.80 0.90 1.00
2010. tavasz
0.2572167752
B I L L G A T E S
OE NIK
alsó érték
felső érték
0.2 0.25 0.256 0.2572 0.25720 0.257216 0.2572164 0.257216772 0.257216772 0.2572167752
Dr. Kutor László
0.3 0.26 0.258 0.2576 0.25724 0.2572220 0.2572168 0.257216776 0.257216776 0.2572167756 IEA 8/41
2/3. példa az aritmetikai kódolásra: Dekódolás 1. 0.2572167752
Kiinduló kód:
0.2572167752
„Kódtáblázat” 0.00 0.10 0.20 0.30 0.40 0.50 0.60 0.80 0.90 2010. tavasz
<= __ < <= A < <= B < <= E < <= G < <= I < <= L < <= S < <= T <
0.10 0.20 0.30 0.40 0.50 0.60 0.80 0.90 1.00 OE NIK
B 0.2572167752 a 0.2 (a tartomány alsó értéke) b 0.0572167752 /0.1=0.57216… 2. 0.572167752 I tartomány a 0.5 b 0.072167752 /0.1=0.7216…. 3. 0.72167752 L a 0.6 b 0.12167752/0.2= 0.6083876 4. 0.6083876 L a 0.6 b 0.0083876/0.2=0.041938 5. 0.041938 _ a 0.0 b 0.041938/0.1=0.41938 6. 0.41938 G …...... Dr. Kutor László
IEA 8/42