Kako stisniti besedilo

Kljub temu, da se je količina takšnega in drugačnega pomnilnika, ki nam je na voljo, v zadnjih desetletjih krepko dvignila, pa težava, ki smo jo imeli v začetku devetdesetih ni nič kaj dosti manjša od teh, ki jih imamo sedaj. Pomnilnika in prostora na disku imamo bistveno več, a tudi količine podatkov je več, tako da se vse skupaj kar nekako »pokrajša«. Sicer je res, da je sedaj pomnilni cenejši, pa naj gre za trde diske, delovne pomnilnike ali pomnilniške ključke, a težava še vedno ostaja. In kaj lahko naredimo? Ker podatkov ne bomo imeli manj, je edina druga možnost ta, da poskusimo nekako zmanjšati količino prostora, ki ga zasedajo. In kako to narediti? S stiskanjem. A to ni tako preprosto, kot bi si mislili.

Računalniki, če vse skupaj zelo poenostavimo, podatke shranjujejo v obliki blokov ničel in enic. Te lahko pomenijo barvo posamezne točke v kakšni sliki ali filmu, v besedilu pa lahko označujejo posamezne črke, številke ali ločila. Kako torej stisniti serijo ničel in enic? Je v njih kaj takšnega, kar lahko vržemo stran? Ja in ne. Kar zadeva sliko lahko recimo zmanjšamo njeno ločljivost – če jo bomo gledali le na zaslonu ali natisnili v kakšnem besedilnem dokumentu je dovolj, da je njena ločljivost med 80 in 90 pik/cm (okoli 220 pik/palec), pa bo v primeru, da široka 10 ali 15 centimetrov, na papirju videti enako dobra kot tista z desetkrat višjo ločljivostjo, saj tiskalnik takšne ločljivosti niti ne more natisniti. Pri zvoku je nekaj podobnega, saj je iz neke pesmi, kot je to v formatu mp3, mogoče »porezati« informacije, ki jih človeško uho ne sliši.

Kaj pa besedilo? Pri njem logika zmanjševanja velikosti z rezanjem tega, kar ne vidimo ali ne slišimo, ne deluje. Iz besedila ne moremo pometati ven recimo vsake druge črke, saj potem ne bi mogli ničesar prebrati. A je torej besedilne datoteke mogoče stiskati? Je, kot vam bo povedal vsak študent računalništva. In kako to poteka? Načinov je več, najbolj bazičen pa je nastal dobrih 60 let nazaj, izmislil si ga je matematik David Huffman in po njem se imenuje Huffmanovo kodiranje ali Huffmanovo drevo. In kako deluje? Stvar je v spodnjem videu pred časom lepo razložil naš zdaj že stari prijatelj Tom Scott.


In kako deluje Huffmanovo kodiranje? Da bi ga razumeli, najprej malce poenostavljene teorije. V nestisnjeni obliki je vsak znak opisan z enim bajtom, dolgim osem bitov. Tisti, ki poznate tematiko malo bolje, boste takoj skočili in rekli, da to ni res, saj gre za sedem bitov, kaj pa Unicode in tako naprej, a ostanimo pri bazični razlago osmih bitov, da bo stvar bolj razumljiva. Osem bitov je več ali manj dovolj, da se z njimi opiše vse znake, ki jih potrebujemo za pisanje besedil. Toda osem bitov je vseeno veliko. Lahko to število kako zmanjšamo? Lahko. Ideja je, da znake razvrstimo glede na pogostost pojavljanja in pogostejše znake, kot sta recimo presledek ali črka 'e', poskusimo zakodirati z manj biti, redkejše pa z več. Tako bi presledek lahko recimo označevala le ničla, črko e pa enica. A prva težava bi se pojavila že pri naslednji najpogostejši črki 't', ki bi jo morali označiti z dvema ničlama, saj računalnik ne bi vedel ali gre za dva presledka ali črko 't'.

Na prvi pogled metoda razvrščanja po pogostosti ne pelje nikamor, a omenjeni David Huffman je v njej videl potencial. Z malce predelave ideje je prišel do sistema, ki dejansko deluje. Znake v besedilu je razvrstil glede na pogostost pojavljanja, a jih ni zapisal le v nek seznam ampak je izdelal drevesno strukturo. Ta je izdelana tako, da neko zaporedje ničel in enic lahko pripelje do želenega znaka in samo do njega, tako da ne more priti do zmote. Kako je to videti v praksi najdete v videu. Precej domiselno za leto 1952, mar ne?

Vir: Tom Scott/YouTube