Az Informatika Elméleti Alapjai dr. Kutor László
Az üzenet információ-tartalma és redundanciája Tömörítő algoritmusok elemzése http://mobil.nik.bmf.hu/tantárgyak/iea.html Felhasználónév: iea 2008. ősz
BMF NIK
Jelszó: IEA07 dr. Kutor László
IEA 7/1
Az információ mérésére vonatkozó függvény Additivitás:
I (Xk) + I (Cj)= I (Xk, Cj) f1 (n) + f1 (m) = f1 (n * m) f = log? f2 (1/n) + f2 (1/m) = f2 (1/n * 1/m) ˘ f3 (p{Xk}) + f3 (p{Cj})= f3 (p{Xk*Cj} 2008. ősz
BMF NIK
dr. Kutor László
IEA 7/2
R. Hartley „formula” (egyenlő előfordulási valószínűségű) „dolgok” kiválasztásához kapcsolódó 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,
bit]
H = k * loge n [ Nat ] 2008. ősz
BMF NIK
dr. Kutor László
IEA 7/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)) 2008. ősz
BMF NIK
dr. Kutor László
IEA 7/4
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 2008. ősz
BMF NIK
dr. Kutor László
IEA 7/5
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) ?! 2008. ő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
Hrelatív =
HS Hmax
2008. ősz
(Hartley)
= az információ-forrás „jósága” 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 2008. ő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. 2008. ő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. 2008. ő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. 2008. ő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 2008. ő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
2008. ő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 2008. ő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”) 2008. ő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”) 2008. ő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”) 2008. ő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”) 2008. ő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”) 2008. ő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”) 2008. ő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”) 2008. ő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”) 2008. ő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”) 2008. ő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”) 2008. ő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”) 2008. ő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”) 2008. ősz
BMF NIK
dr. Kutor László
IEA 7/26