Huffmani kodeerimise visualiseerija

Sisesta tekst, et näha, kuidas Huffmani kodeerimine annab sagedastele tähemärkidele lühemad koodid.

Näidisarvutus — Huffmani kodeerimise visualiseerija

Algne (8-bitine ASCII)	88
Huffmani kodeeritud bitid	32
Kokkuhoid	63.6%
'l' (3×)	10
'␣' (1×)	000
'w' (1×)	001
'r' (1×)	010
'd' (1×)	011

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Huffman ei saa kunagi kulutada vähem kui ühe biti 🖖

Huffmani koodid on optimaalsed, kuid ainult reegli sees, mis neile kallilt maksma läheb: iga sümbol peab saama täisarvu bitte. Shannoni piir ütleb, et sümbol, mis esineb 90% ajast, on väärt umbes 0,15 bitti, ja allikas, mis koosneb 90% ulatuses ühest märgist ja 10% ulatuses teisest, kannab vaid 0,469 bitti entroopiat sümboli kohta. Huffman ei oska kirjutada bitiosa, nii et ta annab 1 ja 1 — kulutades rohkem kui kaks korda üle selle, mida info väärt on. Just see vahe on põhjus, miks tugevalt kaldu andmed siin pettumust valmistavalt pakituvad, ja miks on olemas aritmeetilised ja vahemikukoodrid: need kodeerivad kogu sõnumi ühe arvuna ja tohivad kulutada murdosa bitte. Huffman on optimaalne täisbitiliste koodide seas, mis on kitsam väide kui lihtsalt optimaalne.

Alati liidetakse kaks haruldasemat 🖖

Puu kasvab alt üles: kõigepealt loetletakse iga märk selle sageduse järgi, seejärel liidetakse korduvalt kaks kõige harvemat elementi väikeseks alampuuks ja käsitletakse seda ühe kimbuna. Seda korratakse, kuni jääb üksainus puu; koodid loetakse siis ülevalt alla — vasak on 0, parem on 1. See "ahne" komme alati kaks väikseimat ühendada tundub lühinägelik, kuid annab tõestatavalt lühimad võimalikud koodid.

Seminaritöö, mis võitis professori 🖖

David Huffman leiutas selle 1951. aastal MIT-i kraadiõppurina, kui professor Robert Fano pakkus klassile valida lõpueksami ja kõige tõhusamat koodi käsitleva töö vahel. Fano ja Claude Shannon olid seda juba proovinud, ehitades oma puid ülalt alla. Huffman peaaegu loobus, kuid taipas siis, et alt üles ehitamine — kõigepealt haruldasemate sümbolite liitmine — on optimaalne, edestades oma õpetaja meetodit.

HUFFMANI KODEERING — MILLAL SEE AITAB JA KUI LÄHEDAL OPTIMUMILE ON?

Millise pakkimisjuhtumiga on tegemist?

Huffman annab sagedastele sümbolitele lühikesed ja haruldastele pikad koodid ning on tõestatult parim, kuni iga sümbol saab täisarvu bitte. Kui palju see säästab, sõltub täielikult sellest, kui ebaühtlased sagedused on. Täiesti ühtlaste korral ei ole midagi ära kasutada; väga ebaühtlaste korral on võit suur — kuni punktini, kus piiri ei sea enam sagedused, vaid täisarvulised bitid.

Kaldu sagedused — täpselt see, milleks meetod on p_i ↑ ⇒ ℓ_i ↓

Kõik sümbolid võrdselt sagedased — ära kasutada pole midagi p_i = 1/n ⇒ ℓ = log₂n

Tavaline tekst — ühe biti kaugusel teoreetilisest põrandast H ≤ ℓ < H + 1

Ainult üks sümbol — põrand, millest Huffman allapoole ei pääse n = 1 ⇒ ℓ = 1

Kaldu sagedused — täpselt see, milleks meetod on

Mida te teate: Teksti valitseb mõni üksik sümbol. Just need saavad lühimad koodid ja kogupikkus langeb tublisti allapoole püsiva pikkusega kodeeringut.

Maksumus: p_i ↑ ⇒ ℓ_i ↓

Näidisarvutus: „mississippi": 11 märki, 4 erinevat sümbolit, kodeeritud 21 bitiga võrreldes 88-ga 8-bitiste märkide korral — kokkuhoid 76,1 %

Ava see juhtum: mississippi

Kaldu sagedused — täpselt see, milleks meetod on. Kaks kõige sagedasemat sümbolit saavad lühimad koodid ja kogupikkus langeb vastavalt. Teksti valitseb mõni üksik sümbol. Just need saavad lühimad koodid ja kogupikkus langeb tublisti allapoole püsiva pikkusega kodeeringut. — Kaks kõige sagedasemat sümbolit saavad lühimad koodid ja kogupikkus langeb vastavalt.

Kõik sümbolid võrdselt sagedased — ära kasutada pole midagi

Mida te teate: Lameda jaotuse korral ei ole sagedasi sümboleid, keda premeerida. Huffman taandub millekski, mis on püsiva pikkusega koodile väga lähedal.

Maksumus: p_i = 1/n ⇒ ℓ = log₂n

Näidisarvutus: „abcdef": 6 erinevat sümbolit, igaüks üks kord, kodeeritud 16 bitiga. Lihtne 3-bitine kood kuue sümboli jaoks kulutaks 18.

Ava see juhtum: ühtlane

Kõik sümbolid võrdselt sagedased — ära kasutada pole midagi. Lame jaotus annab peaaegu ühtlase puu ja kõik koodid on umbes sama pikad. Lameda jaotuse korral ei ole sagedasi sümboleid, keda premeerida. Huffman taandub millekski, mis on püsiva pikkusega koodile väga lähedal. — Lame jaotus annab peaaegu ühtlase puu ja kõik koodid on umbes sama pikad.

Tavaline tekst — ühe biti kaugusel teoreetilisest põrandast

Mida te teate: Realistlik segu korduvatest ja ühekordsetest sümbolitest. See on igapäevane juhtum ja tulemus jääb napilt entroopiapiirist ülespoole.

Maksumus: H ≤ ℓ < H + 1

Näidisarvutus: „hello world": 11 märki, 8 erinevat sümbolit, kodeeritud 32 bitiga võrreldes 88-ga — säästetud 63,6 %, entroopiapõrand on 31,3 bitti

Ava see juhtum: hello world

Tavaline tekst — ühe biti kaugusel teoreetilisest põrandast. Segunenud jaotus annab kaldu puu ja kogusumma jääb napilt entroopiapiirist kõrgemale. Realistlik segu korduvatest ja ühekordsetest sümbolitest. See on igapäevane juhtum ja tulemus jääb napilt entroopiapiirist ülespoole. — Segunenud jaotus annab kaldu puu ja kogusumma jääb napilt entroopiapiirist kõrgemale.

Ainult üks sümbol — põrand, millest Huffman allapoole ei pääse

Mida te teate: Tekst, milles ei ole mingit vaheldust. Tema entroopia on null, aga Huffman peab ikkagi väljastama vähemalt ühe biti sümboli kohta, sest ühest bitist lühemat koodi ei ole.

Maksumus: n = 1 ⇒ ℓ = 1

Näidisarvutus: „aaaaaaaaaa": 10 märki, üks ainus sümbol, kodeeritud 10 bitiga. Teksti entroopia on 0 bitti.

Ava see juhtum: üks korduv märk

Ainult üks sümbol — põrand, millest Huffman allapoole ei pääse. Üks sümbol, üks bitt igaühe kohta: ära kasutada pole jaotust ja lühemat koodi ei ole olemas. Tekst, milles ei ole mingit vaheldust. Tema entroopia on null, aga Huffman peab ikkagi väljastama vähemalt ühe biti sümboli kohta, sest ühest bitist lühemat koodi ei ole. — Üks sümbol, üks bitt igaühe kohta: ära kasutada pole jaotust ja lühemat koodi ei ole olemas.

Allikad (1)

Insight block 3 — the term paper itself: D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes." Proceedings of the IRE 40(9), 1098–1101, 1952.

Ülesanne täielikult lahendatud

Sääst sõne "hello world" kodeerimisel Huffmani kodeeringuga 5 sammu
Kodeeri "hello world" Huffmani koodiga. Leia sääst — seejärel leia piir, mis näitab, kui palju paremini ükskõik milline kood saaks üldse toimida.
1. Fikseeritud pikkusega ASCII kulutab iga märgi jaoks samad kaheksa bitti, olenemata selle esinemissagedusest. See ongi raiskamine, mille Huffman eemaldab: sagedased sümbolid saavad lühikesed koodid, haruldased pikad koodid.
  
  $"hello world" : 11 chars \times 8 bits = 88 bits$
2. Loenda kõigepealt sümbolid, sest kood ehitatakse arvu põhjal. Vaid 'l' ja 'o' korduvad; ülejäänud kuus märki esinevad igaüks ühe korra.
  
  $ℓ = 3, o = 2, others = 1 each (8 distinct symbols)$
3. Shannoni entroopia on keskmine informatsioonihulk sümboli kohta ning ühtlasi range alampiir: ükski üheselt dekodeeritav kood ei saa olla keskmiselt lühem. Kogu arvutus põhineb kolmel eri tõenäosusel: 3/11 tähe „l“, 2/11 tähe „o“ ja 1/11 iga ülejäänud kuue tähe korral. Seega on summa (3/11)(1,8745) + (2/11)(2,4594) + (6/11)(3,4594).
  
  $H = - i \sum p_{i} lo g_{2} p_{i} = 2.845 bits/symbol$
4. Korruta sõne pikkusega, et saada alumine piir bittides. Huffman peab tulema sellest suurem või sellega võrdne ja üldjuhul ei saa ta seda saavutada, sest koodipikkused on täisarvud bittides, samal ajal kui entropia seda ei ole.
  
  $11 \times 2.845 = 31.3 bits (entropy floor) \leq 32 (Huffman)$
5. Tegeliku pikkuse leidmiseks koosta puu. Huffmani algoritm ühendab igal sammul kaks vähimat kaalu: 1+1, 1+1, 1+1, seejärel 2+2, siis 2+2, 3+4 ja lõpuks 4+7. Iga ühendamine lisab kõigile selle all olevatele sümbolitele ühe biti, mistõttu kodeeritud sõnumi pikkus võrdub ühendatud kaalude summaga: 2+2+2+4+4+7+11 = 32. Sama tulemuse näitab visualiseerija.
  
  $Huffman = 32 bits ⟹ saving = 1 - \frac{32}{88} = 63.6%$
Vastus

88 bits 32-le — 63.6% sääst. Nende sageduste entropia alumine piir on 31.3 bits, ja Huffman andis tulemuseks 32 — 0.7 bits üle optimaalse, mis kulus kaheksa koodipikkuse ümardamiseks täisbittideni. Garantii on vahemik H ≤ keskmine pikkus < H + 1: Huffman ei ole kunagi rohkem kui ühe bitti võrra sümboli kohta üle optimaalse. See ühebitine vahe on täpselt põhjus, miks aritmeetiline kodeerimine on olemas.

$88 \to 32 bits (63.6%) H \leq \overset{ˉ}{ℓ} < H + 1$

Õpitee

Käsitsi tihendamine

Viib edasi LZ77 erineva pikkusega koodid, kus lühemaid kasutatakse sagedasemate märkide tähistamiseks.

42Mathi meeskond · Uuendatud 2026-07-27

Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud. Toimetamispõhimõtted · Parandused

Kõik Arvutustehnika õppetunnid →

Näiteülesanded

hello world - ASCII-koodi 88 bitist jääb järele 32: kokkuhoid on 63,6% ning entroopia alampiirist 31,3 kulub vaid 0,7 bitti rohkem.
mississippi - Üheteistkümne märgi seas on neli erinevat: 88 bitist saab 21 ning s saab ühebitise koodi. Siin on ka suurim vahe entroopia alampiiriga: 0,95 bitti.
ühtlane - Kuus sümbolit, igaüks esineb ühe korra, seega pole midagi ära kasutada. Ometi kulub 16 bitti võrreldes püsipikkusega koodi 18 bitiga, sest kuus sümbolit ei kasuta kolme biti kõiki kombinatsioone.
üks korduv märk - Kümme ühesugust märki kannavad täpselt 0 bitti informatsiooni, kuid Huffmani kood kulutab siiski 10 bitti: ühe iga sümboli kohta, sest alla ühe biti ei saa üht sümbolit kodeerida.