Huffman kode: primeri, aplikacije

Trenutno malo ljudi razmišlja o tem, kako deluje kompresija. V primerjavi s preteklostjo je uporaba osebnega računalnika postala veliko lažja. In praktično vsak, ki dela z datotečnim sistemom, uporablja arhive. Toda malo ljudi razmišlja o tem, kako delajo, in o tem, kje je stiskanje datotek. Prva različica tega postopka je bila Huffmanova koda, ki se še vedno uporablja v različnih priljubljenih arhivih. Mnogi uporabniki sploh ne mislijo, kako enostavno je stiskati datoteko in glede na to, na kateri shemi deluje. V tem članku si bomo ogledali, kako je stiskanje kaj tonov pomagala pospešiti in poenostaviti postopek kodiranja, pa tudi, kaj je načelo drevesa kodiranja.

Zgodovina algoritma

Prvi algoritem za učinkovito kodiranje elektronskih informacij je bila koda, ki jo je Huffman predlagal sredi dvajsetega stoletja, in sicer leta 1952. Trenutno je glavni osnovni element večine programov, ustvarjenih za stiskanje informacij. Trenutno je eden od najbolj priljubljenih virov, ki uporabljajo to kodo, arhiv ZIP, ARJ, RAR in mnogi drugi. Uporablja se tudi ta Huffmanov algoritem stiskanje slik JPEG in druge grafične predmete. No, vsi sodobni faksi uporabljajo kodiranje, izumil leta 1952. Kljub dejstvu, da je od nastanka kode toliko časa minilo, se danes uporablja v najnovejših školjkah in na opremi starih in sodobnih vrst.

Načelo učinkovitega kodiranja

Huffmanov algoritem temelji na shemi, ki omogoča zamenjavo najbolj verjetnih, najpogosteje naletenih simbolov binarne kode sistem. Tiste, ki so manj pogoste, se zamenjajo z daljšimi kodami. Prehod na dolge Huffmanove kode se zgodi šele po tem, ko sistem uporabi vse najmanjše vrednosti. Ta tehnika vam omogoča, da zmanjšate dolžino kode za vsak znak prvotnega sporočila kot celote. Pomembna točka je, da je na začetku kodiranja verjetnost pojava črk že znana. Iz teh je sestavljeno zadnje sporočilo. Na podlagi teh podatkov se zgradi drevo kode Huffman, na podlagi katerega se bo izvajal proces kodiranja črk v arhivu.

Huffmanova koda, primer

Za ponazoritev algoritma si vzemimo grafično različico konstruiranja drevesa kode. Za uporabo te metode je bilo učinkovito, je smiselno pojasniti opredelitev nekaterih vrednosti, potrebnih za koncept te metode. Niz lokov in vozlišč, ki so usmerjeni od vozlišča do vozlišča, se ponavadi imenujejo graf. Drevo sam je graf s skupino določenih lastnosti:

• v vsakem vozlišču lahko vnesemo največ eno od lokov;
• ena od vozlišč mora biti koren drevesa, to pomeni, da ga sploh ne bi vnesel lok;
• če bi se iz korenin začel gibati vzdolž lokov, bi ta proces moral omogočiti, da bi se popolnoma ujeli v katero koli vozlišče.

Obstaja tudi tak koncept, ki je vključen v Huffmanove kode, kot list drevesa. To je vozlišče, iz katerega noben lok ne bo ušel. Če sta dve vozlišči povezani z lokom, eden od njih je eden od staršev drugega otroka, odvisno od tega, iz katerega vozlišča lok ugasne, in kaj je vključeno. Če imata dve vozlišči isto matično vozlišče, se navadno imenujejo bratske vozlišča. Če poleg vozlišč v vozliščih obstaja več lokov, se to drevo imenuje binarno. To je ravno drevo Huffmana. Posebnost gradnje enot je, da je teža vsakega starša enako vsoti uteži vseh svojih otrok vozlišča.

Algoritem za konstruiranje drevesa po Huffmanu

Konstrukcija Huffmanove kode je narejena iz črk vhodne abecede. Ustvari se seznam tistih vozlišč, ki so brezplačna v prihodnjem kodnem drevesu. Teža vsakega vozlišča na tem seznamu mora biti enaka verjetnosti pojava črke sporočila, ki ustreza temu vozlišču. V tem primeru je med redkimi brezplačnimi vozlišči prihodnjega drevesa izbrano tisto, ki tehta najmanj. Hkrati, če so minimalni kazalniki opazovani v več vozliščih, je mogoče prosto izbirati kateri koli od parov. Po tem se ustvari matično vozlišče, ki mora tehtati toliko, kolikor vsota tega para vozlišč tehta. Po tem se staršu pošlje na seznam brezplačnih vozlišč in otroci se izbrišejo. Hkrati dobijo ustrezni indeksi, tisti in ničle. Ta postopek se ponovi točno tako dolgo, kot je potrebno, da zapusti samo eno vozlišče. Po tem se binarne številke zapisujejo od zgoraj navzdol.

Izboljšanje učinkovitosti stiskanja

Da bi povečali učinkovitost stiskanja, je treba v drevo gradnjo kodo uporabiti vse podatke o verjetnosti pojava črk v nekem spisu, pritrjeno na drevo, in ne dovoli, da so razpršene po številnih besedilnih dokumentov. Če je pred sprehod skozi te datoteke, lahko takoj izračunati statistične podatke o tem, kako pogosto so črke objekta, ki je predmet stiskanja.

Pospeševanje procesa stiskanja

Pospešiti delo algoritem, definicija črke je treba izvesti ne glede na indekse verjetnosti pojava posamezne črke, temveč zaradi pogostosti njenega pojavljanja. Zahvaljujoč temu postane algoritem enostavnejši in delo z njim je zelo pospešeno. To se izogne ​​tudi operacijam, povezanim s plavajočimi vejicami in delitvijo. Poleg tega se v tem načinu, dinamična Huffmanova koda ali celo sam algoritem ne spreminjajo. To je predvsem posledica dejstva, da so verjetnosti neposredno sorazmerne s frekvencami. Posebno pozornost je treba nameniti dejstvu, da bo končna teža datoteke ali tako imenovane korenske vozlišča enaka vsoti števila črk v objektu, ki ga želite obdelati.

Zaključek

Huffmanove kode so preprost in dolgotrajni algoritem, ki ga še vedno uporabljajo številni znani programi in podjetja. Njena preprostost in jasnost omogočata doseganje učinkovitih rezultatov stiskanja datotek vseh velikosti in bistveno zmanjšanje prostora, ki ga zasedajo na disku za shranjevanje. Z drugimi besedami, Huffmanov algoritem je dolgo preučevana in dobro zasnovana shema, katere pomen se do danes še ne zmanjša. Zahvaljujoč možnosti, da zmanjšate velikost datotek, jih prenesete prek omrežja ali na druge načine, postane lažje, hitrejše in bolj priročno. Delo z algoritmom lahko popolnoma stisnete vse informacije, ne da bi pri tem ogrozili njegovo strukturo in kakovost, vendar z največjim učinkom zmanjšanja teže datoteke. Z drugimi besedami, Kodiranje kod Huffman je bilo in ostaja najbolj priljubljena in dejanska metoda kompresije velikosti datoteke.