Hafmena kods

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. …