Informatikai Rendszerek Alapjai Dr. Kutor László
Minimális redundanciájú kódok (2) Szótár alapú tömörítő algoritmusok
2014. ősz
Óbudai Egyetem, NIK
Dr. Kutor László
IRA 8/25/1
Az információ redundanciája
HS = - ∑ p{ xi}* log2p{xi} (Shannon-Wiener) i=1
Hmax = k log (n)
(Hartley)
n
Hmax = - n ∑ 1/n * log (1/n)= - log (1/n) = log(n) Hrelatív = 2014. ősz
i=1 HS
Hmax
RS = (1 -
Óbudai Egyetem, NIK
HS Hmax
Dr. Kutor László
)*
100 IRA 8/25/2
Példa a Huffman algoritmusra (ism.) 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ó
IRA 8/25/3
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
Óbudai Egyetem, NIK
Dr. Kutor László
IRA 8/25/4
Dekódolás példa a „Huffman”algoritmhoz 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ó
IRA 8/25/5
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
Óbudai Egyetem, NIK
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) IRA 8/25/6
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 2014. ősz
(15 – 20 mp) IRA 8/25/7
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
2014. ősz
Óbudai Egyetem, NIK
0.2572167752
Dr. Kutor László
IRA 8/25/8
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
2014. ősz
Óbudai Egyetem, NIK
Dr. Kutor László
IRA 8/25/9
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 A
2/4 1/4 1/4 L
Számtartomány
0 <=tA< 0.5 0.5 <=tL< 0.75 0.75<=tM< 1 M
0 <= tA < 0. 5 0.25 <= tAL < 0.375 0.34375 <= tALM < 0.375….. 0…. <= tALMA< 0….. 2014. ősz
Óbudai Egyetem, NIK
Dr. Kutor László
IRA 8/25/10
2. példa az aritmetikai kódolásra Kódolandó szöveg: Szimbólumok
-_ A B E G I L S T
2014. ősz
BILL_GATES
Előfordulások Relatív száma gyakoriság
1 1 1 1 1 1 2 1 1
„Data Compression book Mark Nelson 1991 Számtartomány
1/10 1/10 1/10 1/10 1/10 1/10 2/10 1/10 1/10
Óbudai Egyetem, 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
IRA 8/25/11
2/2. példa az aritmetikai kódolásra BILL_GATES 0.2572167752 Számtartomány „Kódtáblázat” alsó érték felső érték
Kódolt szöveg:
0.00 0.10 0.20 0.30 0.40 0.50 0.60 0.80 0.90 2014. ősz
<= __ < <= 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
B I L L G A T E S
Óbudai Egyetem, NIK
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.257220 0.2572168 0.257216776 0.257216776 0.2572167756 IRA 8/25/12
2/3. példa az aritmetikai kódolásra: Dekódolás Kiinduló kód:
1. 0.2572167752
B
0.2572167752 0.2572167752 a 0.2 (a tartomány alsó értéke) b 0.0572167752 /0.1=0.57216… 2. 0.572167752 I tartomány „Kódtáblázat” a 0.5 b 0.072167752 /0.1=0.7216…. 0.00 <= __ < 0.10 3. 0.72167752 L 0.10 <= A < 0.20 a 0.6 0.20 <= B < 0.30 b 0.12167752/0.2= 0.6083876 0.30 <= E < 0.40 4. 0.6083876 L 0.40 <= G < 0.50 a 0.6 0.50 <= I < 0.60 b 0.0083876/0.2=0.041938 0.60 <= L < 0.80 5. 0.041938 _ a 0.0 0.80 <= S < 0.90 b 0.041938/0.1=0.41938 0.90 <= T < 1.00 6. 0.41938 G …...... 2014. ősz Óbudai Egyetem, NIK Dr. Kutor László IRA 8/25/13
Szótár alapú adattömörítés • „ Gondolkodás nélkül tanulni haszontalanság, tanulás nélkül gondolkodni veszélyes”
lap 1 sor 1 2 3 4 5 6 7
2
3
4
.
Konfucius .
N
tanulni Gondolkodás nélkül
A kód felépítése: lap bejegyzés lap bejegyzés . . . . . . . . . . 243642......... 2014. ősz
Óbudai Egyetem, NIK
Dr. Kutor László
IRA 8/25/14
A szállodai éjjeliszekrény szokásos kellékei
2014. ősz
Óbudai Egyetem, NIK
Dr. Kutor László
IRA 8/25/15
A szállodai éjjeliszekrény szokásos kelléke 2.
2014. ősz
Óbudai Egyetem, NIK
Dr. Kutor László
A szótár alapú adattömörítés blokkvázlata
szótár
szótár
forrás
2014. ősz
kódoló
csatorna
Óbudai Egyetem, NIK
dekódoló
Dr. Kutor László
vevő
IRA 8/25/17
A szótár alapú adattömörítés története • 1977 Abraham Lempel és Jakob Ziv LZ77 • „An Unversal Algorithm for Sequntial Data Compression”
•
IEEE Transaction on Information Theory 1978 Abraham Lempel és Jakob Ziv LZ78 „ Compression of Individual Sequences via Variable-Rate Coding” IEEE Transaction on Information Theory 1984 Terry Welch (Sperry Research Center) LZW „A Technique for High-Performance Data Compression” IEEE Computer 1984 June
2014. ősz
Óbudai Egyetem, NIK
Dr. Kutor László
IRA 8/25/18
Abraham Lempel, Jakab Ziv 1977
Az LZ 77 kódolás elve
• „ szótár alapú, csúszó ablak tömörítés” _for_(i=0_;i<MAX-1;i++)\r_for(=j+1;j Szöveg ablak („szótár”),(4K-64K)
<MAX;j++) \r
Kódolandó szöveg ablak (16bájt-1K)
A kódolandó karakter sorozatot egy kódhármassal helyettesítjük
13, 4, ; A kódolási lépés után az ablakok „elcsúsznak” _(i=0_;i<MAX-1;j++)\r_for(=j+1;j <MAX ;j++) \r_a(i 2014. ősz
Óbudai Egyetem, NIK
Dr. Kutor László
IRA 8/25/19
Az LZ 77 kódolás korlátai LZ77 elvű tömörítő programok:
PKZIP (PKWare) LHarc (H. Yoshizaki) ARJ (R. Jung)
1. Csak a kódolandó karaktersorozatot közvetlenül megelőző adatsoron belül (a „szótárban” ) tud keresni
2. Az egy kóddal lekódolható adat hossza korlátozott
2014. ősz
Óbudai Egyetem, NIK
Dr. Kutor László
IRA 8/25/20
Az LZ78 adattömörítés jellemzői w Adaptív, szótár alapú kódolás w A szótárat lépésről-lépésre építi w A szótárba a soron következő sorszám mellé az a karakterfüzér kerül ami korábban még nem szerepelt LZ78 elvű tömörítők: UNIX compress
ARC.ARC PKARC
2014. ősz
Óbudai Egyetem, NIK
Dr. Kutor László
(DEC, VAX) (MS-DOS) (PKWare) IRA 8/25/21
Az adaptív kódolás jellemzői • Lényege: a forrásból nyert információ alapján a kódot lépésről-lépésre , egyre hatékonyabban hozzuk létre kódoló
dekódoló
Statisztika
Statisztika vagy előfordulási információ
vagy
forrás
előfordulási
csatorna
információ
vevő
Előnye: a statisztikai információt nem kell továbbítani Hátránya: a vevő oldalon is létre kell hozni a statisztikát 2014. ősz
Óbudai Egyetem, NIK
Dr. Kutor László
IRA 8/25/22
Példa az LZ78-as kódolásra Kódolandó szöveg:
ABABABABABABABABABABA
Szótár bejegyzés
1 2 3 4 5 6 7 8 2014. ősz
A B AB ABA BA BAB ABAB ABABA
0A 0B 1B 3A2A 5B 4B 7A
Óbudai Egyetem, NIK
Dr. Kutor László
IRA 8/25/23
Az LZW adattömörítés folyamata • STR=String Ch=karakter EOF= fájl vége Start Az első karakter az STR-be Ch olvasása Igen
EOF
Igen
STR+CH van a táblázatban ?
Vége
Nem STR kódja a kimenetre STR+Ch a táblázatba STR := Ch
SRT := STR+Ch 2014. ősz
STR kódjának kiírása
Óbudai Egyetem, NIK
Dr. Kutor László
IRA 8/25/24
Kérdések:
- Mi a Huffmann és Shannon-Fano kódja a következő karaktereknek ha az üzenetben előforduló karakterek és előfordulásaik száma a következő: A(16), B(8), C(7), D (6), E (5)
- Hogyan számolható ki a következő karaktersorozat LZ78-as kódja: XYZXYZXYZXYZXYZXYZXYZXYZXYZXYZ
2014. ősz
Óbudai Egyetem, NIK
Dr. Kutor László
IRA 8/25/25