Bebro kodas

Taškai: 6

Bebriukė Laima gavo dovanų du antspaudus: gėlytę ir saulutę. Bebriukė sugalvojo būdą, kaip užrašyti savo ir draugių vardus šiais antspaudais, t. y., kaip užkoduoti vardų raides gėlyčių ir saulučių sekomis.

Štai taip užkoduojamas vardas LAIMA:  
Bebriukė užkodavo draugių vardus ir juos išspausdino atskirose kortelėse, bet korteles netyčia sumaišė. Kurie kodai kuriuos vardus atitinka? Nutempkite.

Paaiškinimas

Paprasčiausia apdoroti vienodo ilgio ženklų kodus. Kai svarbu, kad duomenys užimtų kuo mažiau vietos, naudojami skirtingo ilgio kodai: dažnesniems ženklams – trumpesni, retesniems – ilgesni. Šio uždavinio koduose į ženklų dažnį nebuvo atsižvelgta.

Tačiau kodai turi būti tokie, kad juos būtų galima vienareikšmiškai iškoduoti. Imkime pavyzdį, parodantį, kaip gali atsirasti nevienareikšmiškumas.

Raidė

B

A

Kodas

Ką šiuo atveju reiškia kodas  ? Juo gali būti užkoduota ir BB, ir A.

Vienas iš būdų išvengti nevienareikšmiškumo yra prefiksinis kodavimas. Šiuo būdu koduojant, kodu, panaudotu kuriai nors raidei koduoti, negali prasidėti jokios kitos raidės kodas. Taigi raidei A čia parodytas kodas netinka.

Tekstams koduoti naudojamas Huffmano metodas. Raidžių kodai parenkami pagal jų dažnį konkrečiame tekste. Todėl kartu su koduotu tekstu pateikiami ir raidžių kodai. Žinoma, tekstas pailgėja, tačiau santykinai mažai, ypač jei pats tekstas ilgas.

Reikšminiai žodžiai: Huffmano kodavimas, duomenų glaudinimas, prefiksinis kodas.

Atsakymas

Teisingas atsakymas:

ALINA

ALMA

INA

LINA

Interaktyvi užduotis

 

 
Informacija atnaujinta 2016-10-18 10:55:36