Informatikai Rendszerek Alapjai

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 -


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


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


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


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


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


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


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


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


Dr. Kutor László

IRA 8/25/14

A szállodai éjjeliszekrény szokásos kellékei

2014. ősz


Dr. Kutor László

IRA 8/25/15

A szállodai éjjeliszekrény szokásos kelléke 2.

2014. ősz


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


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


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


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


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


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


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


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


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


Dr. Kutor László

IRA 8/25/25

Informatikai Rendszerek Alapjai

Recommend Documents