border=0

Foarbyld 3.1.

Tink derom dat de folgjende tabel fan prefix-koades is:

Untfongen om it berjocht te dekodearjen:

00100010000111010101110000110

Decodearring wurdt dien troch it fytsen fan de neikommende aksjes:

(a) it lêstste karakter fan it hjoeddeisk berjocht ôfsnuttje, oan it rjochts fan it wurkkodewort oan 'e rjochter taheakje;

(b) fergelykje it wurkkodewaar mei de koade-tabel; as der gjin match is, gean nei (a);

(c) decodearret it wurkkodewurk, lêze it;

(d) kontrolearje oft der mear tekens yn it berjocht binne; as jo ja, gean nei (a).

It brûken fan dit algoritme jout:

It prosedearjen oan 'e ein bringt it berjocht: "Mom woskte it frame".

Sa kin it gebrûk fan prefix-kodearring it berjocht koarter meitsje, omdat der gjin need-tekenrjocht is. De Fano-kondysje lykwols lykwols gjin metoade foar it generearjen fan in prefix-koade, en benammen de bêste mooglikheid. Wy sjogge twa regelingen foar it bouwen fan prefix-koades.

Shannon-Fano prefix-koade

Dizze kodearringopsje waard foarsteld yn 1948-1949. ûnôfhinklik fan R. Fano en C. Shannon en dêrom wurdt foar har neamd. Besykje it skema mei it folgjende foarbyld: litte der in primêre alfabet A wêze, besteande út seis karakters in 1 ... en 6 mei problemen fan it ferskinen yn it berjocht respektivelik 0.3; 0,2; 0,2; 0.15; 0.1; 0,05. Wy regelje dizze tekens yn 'e tabel yn' e rigel fan ôfnimjende problemen (sjoch tabel 3.2). Wy splitje de tekens yn twa groepen sadat de summa fan 'e probabiliteiten yn elk fan har sawat like-like wêze soe. Yn ús foarbyld krije de earste groep 1 en in 2 mei in somme fan kâns fan 0,5 - wy jouwe se de earste sifer fan de koade "0". De som fan 'e problemen foar de oare fjouwer karakters is ek 0,5; se sille it earste karakter hawwe fan 'e koade "1". Wy trochgean de divyzje fan elke groep nei subgruppen neffens deselde regeling, d. sadat de submappen fan kâns op elke stap yn 'e buorjende ûndergroups sa ticht mooglik wêze. It resultaat is:

It is maklik om te sjen fan de koade gebouproseduere dat se befredigje oan de betingsten fan Fano en, dêrom, is de koade prefix. De gemiddelde koade lingte is:

I 1 ( A ) = 2,390 bits. It ferfangen fan de oanjûne wearden yn (3.5), krije wy it redundancyskoade Q ( A, 2) = 0.0249, d. sa'n 2,5%. Dizze koade kin lykwols net optimaal beskôge wurde, om't de kâns op it opkommen fan 0 en 1 net itselde binne (0,35 en 0,65 respektivelik). De tapassing fan it oantsjutte boustekema nei it Russyske alfabet jout in redundans koade fan 0,0147.

Huffman prefiksoade

De metoade fan optimale prefix binêre kodearring waard foarsteld troch D. Huffman. Wy sille it gebou Huffman-koaden op deselde foarbyld beskôgje. Meitsje in nije assistint-alfabet A 1 , kombinearret de twa tekens mei de lytste probabele ( in 5 en in 6 ) en ferfangt se mei ien teken (bygelyks in (1) ); de kâns op in nije teken sil wêze as de som fan 'e problemen fan dyjingen dy't opnommen binne, d. 0.15; de oerbleaune tekens fan 'e orizjinele alfabet wurde yn' e nije opnommen yn ûntwikkele; It totale oantal karakters yn it nije alfabet sil fansels 1 minder wêze as it orizjineel. Hjirmei sille wy trochgean om nije alfabetten oan te meitsjen oant der twa letteren yn 'e lêste lizze; It is dúdlik dat it oantal sokke stappen lyk is N -2, dêr't N it oantal tekens fan it orizjinele alfabet is (yn ús gefal, N = 6, dus it is needsaaklik om 4 auxiliary alfabetten te bouwen). Yn 't tuskentafele alfabetten wurdt elke kear de tekens yn' e omlizzende oarder fan probabiliteit feroare. De hiele proses fan konstruksje wurdt presintearre yn 'e foarm fan in tafel:

No yn 'e opposite rjochting sille wy it kodearingsproseduere útfiere. Wy jouwe koades 0 en 1 oan 'e twa tekens fan it lêste alfabet (oan wa't gjin rol spilet; wy akseptearje dat it top-karakter 0 hat, en de ûnderste - 1). Yn ús foarbyld is it teken in 1 (4) Alfabet A (4) hat in probleem fan 0.6, krije in koade fan 0, en in 2 (4) mei probabiliteit 0,4 - koade 1. Yn it alfabet A (3) it teken a 1 (3) ûntfangt fan in 2 (4) syn probabiliteit 0,4 en koade (1); De tekens kodearret in 2 (3) en in 3 (3) , oarspronklik út it teken fan 1 (4) mei in probabiliteit fan 0,6, sil al twa twifele wêze: har earste sifer sil har memmekoade wêze (dat, 0), en de twadde figuer - as ôfspraken - oan de top 0, oan 'e boaiem - 1; sadat in 2 (3) sil code 00 hawwe, en in 3 (3) - koade 01. De folsleine kodearingsproseduaasje is presintearre yn 't tafel op p.70.

Fanút de proseduere fan gebrûksgearkomsten is it wer dúdlik dat se de betingsten fan Fano befredigje en dêrom gjin separator hawwe. De gemiddelde koade lengte, lykas yn it foarige foarbyld is:

K (A, 2) = 0,3 ∙ 2 + 0,2 ∙ 2 + 0,2 2 + 0,15 3 + 0,1 4 + 0,05 ∙ 4 = 2,45.

De redundance is lyk oan Q ( A, 2) = 0.0249, lykwols, binne de kâns fan 0 en 1 konvertearre (0.47 en 0.53 respektivelik). De hegere effektiviteit fan 'e Huffman-koades yn' e ferliking mei de Shannon-Fano-koade wurdt sichtber as wy de redundancy-koades foar elke natuerkunde fergelykje. De tapassing fan de beskreaune metoade foar de brieven fan it Russyske alfabet bringt de koades yn 'e Tabel. 3.2. (foar beferzen fan fergeliking, wurde se yn it formaat fan Tabel 3.1 oanjûn).

Tabel 3.2

De gemiddelde koade lingte is lyk oan K (r , 2) = 4.395; Redundancy-koade Q ( r , 2) = 0.0090, i. 1 % net grutter is , wat minder minder is as de redundancy fan de koade Shannon-Fano (sjoch hjirboppe).

De koade Huffman is wichtich teoretysk, om't it bewiisd is dat it it ekonomysk fan alle mooglik is, d. Foar elke alfabetyske kodingsmetoade kin de lingte fan de koade net minder wêze as de Huffman-koade (sjoch [49, p.209-211]).

Sa kinne wy ​​konkludearje dat der in wei is om in optimale net-unifoarmlike alfabetyske koade te bouwen. Men moat net tinke dat it in oantal teoretyske be>(dynamyske Huffman-kodearring) - hawwe in breed applikaasje fûn yn archiverprogramma's, triem- en disk-opsjesprogramma's, yn ynformaasjetesystemen yn modems en faxes.





Sjoch ek:

Algoritme presintaasjemethoden

Foarbyld 2.5

Organisaasje fan datastrukturen yn RAM

Formulieren fan ynformaasje

Models kontrolearre en net ferifieare

Gean werom nei Tafel Ynhâld: Teoretyske Stiftingen fan Computer Science

2019 @ bibinar.info