-
Hafmena kods
Nr. | Sadaļas nosaukums | Lpp. |
ANOTĀCIJA | 2 | |
IEVADS | 4 | |
1. | HAFMENA KODS | 5 |
1.1. | Prefikss kodi | 6 |
1.2. | Hafmena koda uzbūve | 8 |
1.3. | Hafmena algoritma korektums | 11 |
SECINĀJUMI | 14 | |
LITERATŪRA | 15 |
Mēs izskatām tikai tos kodus, kuros neviens koda vārds nav prefikss kādam citam koda vārdam. Šādus kodus sauc par prefikss kodiem ( prefix codes) . Var parādīt ( kaut arī šeit mēs to nedarīsim ), ka optimāla datu arhivēšana, ko var sasniegt ar kodu palīdzību, vienmēr sasniedzama ar prefikss koda izmantošanu, tēpēc tikai vienu prefikss koda izskatīšana nevedīs pie kopības zaudējuma.
Jebkura binārā simbolu koda teksta kodēšana ir ļoti viegls process – vajag vienkārši savienot koda vārdus, kas attēlo katru simbolu failā. Piemēram, kodējumā ar mainīgā garuma prefikss koda palīdzību, kas parādīts tabulā 1.1. 3 – simbolu fails abc izskatās šādi :
0 * 101 * 100 = 0101100,
kur simbols ‘ * ’ nozīmē konkatenācijas operāciju.[2]
Priekšroka prefikss kodiem tiek dota tādēļ, ka tie atvieglina dekodēšanu. Tā iemesla dēļ, ka neviens koda vārds nav cita vārda prefikss, koda vārds, ar kuru sākas iekodētais fails, tiek noteikts viennozīmīgi. Sākuma koda vārds ir viegli identificējams, pārveidojams sākuma stāvoklī ( simbolā ) un turpināt atlikušā iekodētā faila dekodēšanu. Izskatāmajā piemērā rinda 001011101 viennozīmīgi sadalās uz apakšrindām 0 * 0 * 101 * 1101, kas dekodējas kā aabe.
Dekodēšanas procesa vienkāršošanai tiek prasīts ērts prefikss koda attēlojums. Viens no šādiem attēlojumiem ir binārais koks, kura lapas ir kodējamie simboli. Binārais koda vārds, kas attēlo simbolu, tiek interpretēts kā ceļš no saknes pie šī simbola. Šāda interpretācijā 0 nozīmē „ pāriet pie kreisā meitas mezgla ”, bet 1 – „ pāriet pie labā meitas mezgla”. Zīmējumā 1.1.1. parādīti šādi koki diviem kodiem, kas ņemti no mūsu piemēra. Katra lapa zīmējumā apzīmēta ar tai atbilstošo simbolu un parādīšanās biežumu, bet iekšējais mezgls – ar tā apakškoka lapu biežumu summu. a) daļā parādīts koks, kas atbilst fiksētā garuma kodam, kur a = 000, ..., f = 101. b) daļā parādīts koks, kas atbilst optimālajam prefikss kodam a = 0, b = 101, ..., f = 1100. …
Šīs referāts ir par tēmu - datu arhivēšana, kas mūsdienās ir diezgan aktuāla tēma datoru lietotājiem. Bieži vien ir tā, ka lietotājam ir nepieciešamība pārnest liela apjoma failus no viena datora uz otru. Daudziem lietotājam nav datoru tīklu, kurā var kopēt failus, tad var rasties nepieciešamība nokopēt failu uz disku, bet faila izmērs var būt lielāks par diska ietilpību. Var būt arī gadījums, kad lietotājam ir nepieciešams palielināt cietā diska brīvu vietu bez datu zaudējumiem. Šajos gadījumos rekomendē izmantot programmas - arhivatorus (t.i. programmas, kuri ļauj samazināt failu izmērus bez datu zaudējumus). Un tieši šeit palīgā nāk Hafmena kods, uz kura bāzes tiek veidotas šīs arhivēšanas programmas. Šajā darbā izklāstīta metodes teorija un pierādīts tās korektums.
- E-pasts un tā iespējas
- Hafmena kods
- Informatīvā sistēma - Klubs
-
Tu vari jebkuru darbu ātri pievienot savu vēlmju sarakstam. Forši!E-pasts un tā iespējas
Referāts vidusskolai12
Novērtēts! -
Informatīvā sistēma - Klubs
Referāts vidusskolai48
-
Failu arhivēšana
Referāts vidusskolai20
Novērtēts! -
Patstāvīgais darbs informātikā
Referāts vidusskolai18
-
Lotus Notes izmantošana biroja darba automatizācijā
Referāts vidusskolai30