Entroopiakodeerimise mänguväljak

Uuri, kuidas erinevad sümbolite jaotused mõjutavad Shannoni entroopiat, võrdle Huffmani kodeerimise piire ning õpi, kuidas entroopia juhib kadufunktsioone ja sõnavara ebakindlust tänapäeva tehisintellekti keelemudelites (LLM-id).

Algväärtused — Entroopiakodeerimise mänguväljak

Jaotuse parameeter (λ)	1.5

Muuda ülal mõnda juhtelementi ja tulemused arvutatakse uuesti.

Interaktiivse simulatsiooni laadimine...

Täisbitid on hind, mida Huffman maksab 🖖

Entroopiakodeerimine kasutab ära statistilist üleliigsust, et esitada sõnumeid vähemate bittidega. Shannoni allikakodeerimise teoreem ütleb, et iga kadudeta koodi absoluutne minimaalne keskmine pikkus on Shannoni entroopia: H(X) = −Σ p_i log₂ p_i. Huffmani kodeerimine on antud tähestiku puhul optimaalne, kui sümboleid kodeeritakse eraldi, kuid see on piiratud täisarvuliste koodisõnade pikkustega. See täisarvuline piirang tähendab, et Huffman võib teoreetilisest entroopiast erineda kuni 0,086 biti/sümboli võrra (ja märksa rohkem, kui mõnel sümbolil on p_i ≈ 1). Aritmeetiline kodeerimine (nt ANS) ületab selle piiri, kaardistades kogu jada murdosaintervallidele.

Seos LLM-ide ja tehisintellektiga: Tänapäeva keelemudelites (LLM-id) on entroopia kesksel kohal nii treenimise kui ka genereerimise juures. LLM-e treenitakse, minimeerides ristentroopia kadu nende sõnavaraennustuste ja tegeliku teksti vahel. Genereerimisel (järelduse tegemisel) väljastab LLM järgmise tokeni jaoks tõenäosusjaotuse üle kogu oma sõnavara. Selle jaotuse entroopia mõõdab mudeli ennustuse ebakindlust: lame jaotus (kõrge entroopia) annab loovat või juhuslikku teksti, samas kui terav jaotus (madal entroopia) annab väga ennustatavat teksti. Valimiparameetrid nagu temperatuur skaleerivad seda entroopiat otse (madalam temperatuur vähendab entroopiat, kõrgem suurendab seda), samas kui nucleus-valimine (Top-p) piirab dünaamiliselt kumulatiivset tõenäosust, et lõigata ära kõrge entroopiaga sabad.

Miks haruldased sümbolid maksavad rohkem bitte 🖖

Selle tööriista tegelik õppetund: sümboli ideaalne bittide arv on selle üllatusväärtus, −log₂ p. Sümbol, mis esineb pooltel juhtudel, väärib 1 bitti; see, mille tõenäosus on 1 tuhandest, umbes 10 bitti. Entroopia ongi lihtsalt kõigi sümbolite keskmine üllatusväärtus. Seepärast tihenevad kaldu jaotused (nagu Laplace'i või eksponentsiaalne eelseade) hästi, ühtlane tähestik aga mitte — kui kõik on võrdselt tõenäoline, pole liiasust, mida eemaldada.

Morse: entroopiakodeerimine enne Shannonit 🖖

Morsekood määras lühima märgi, üheainsa punkti, tähele E, mis on inglise keeles kõige sagedasem, ja pikad jadad haruldastele nagu Q ja Z. Pikkuste valimiseks luges Alfred Vail väidetavalt trükikoja ladumiskastis olevaid tähetüúpe, et hinnata tähtede sagedusi. See oli töötav muutuva pikkusega kodeerimine juba 1840. aastatel — ligi sajand enne, kui Shannon 1948. aastal formaalselt tõestas, miks see toimib.

ÜKS ASTE AHELAST — MIS SAABUB, MIS VÄLJUB JA MIS EDASPIDI KATKEB

Kus see kodeerimiskonveieris asub

Videokodeerija ei ole üks algoritm, vaid kaheksa astet kindlas järjekorras — ja järjekord ei ole suvaline: iga aste on olemas seetõttu, et eelmine tegi tema töö võimalikuks. See tööriist modelleerib neist üht. Allolev ahel viitab ülejäänud seitsmele.

Entroopiakodeerimise mänguväljak — pakib kvantitud sümbolid nii vähestesse bittidesse, kui nende statistika lubab

Mis saabub: Kvantitud täisarvude voog, tugevalt nulli poole kaldu.
Mis väljub: Valmis bitivoog. Siin ei visata midagi ära.
Mida järgmine aste eeldab: Midagi edasi ei tule — see on viimane kodeerimisaste. Tema eeldus on eespool: et sümbolite jaotus on tema jaoks juba viltu tehtud.
Mis siin valesti läheb: Ükski entroopiakodeerija ei suuda alla lüüa selle Shannoni entroopiat, mis talle antakse, seega määravad tema lae täielikult varasemad astmed. Kvantimata kordajatel jooksutades on vähe liiasust leida — just seepärast tuleb kadudega samm esimesena, mitte viimasena.

Eelmine aste: Kvantimine Järgmine aste: Bitikiiruse juhtimine

Ülesanne täielikult lahendatud

Huffmanist nutikama algoritmi mänguruum 16 sümboli korral 6 sammu
16 sümbolit, Laplace'i jaotus, entropia 3,010 bitti. Huffman saavutab 3,012. Arvuta, kui palju ruumi jääb nutikamale algoritmile.
1. Entropia on sellest jaotusest võetud ühe sümboli keskmine üllatus bittides. See on üksnes tõenäosuste omadus ega tea midagi ühestki koodist.
  
  $H (X) = - i = 1 \sum N p_{i} lo g_{2} p_{i} = 3.010 bits/symbol (N = 16, Laplacian, λ = 1.5)$
2. Naiivne alternatiiv annab igale sümbolile sama arvu bitte ning 16 sümbolit vajavad 4. See on lähtetase, mille suhtes kokkuhoidu mõõdetakse.
  
  $L_{fixed} = ⌈ lo g_{2} N ⌉ = ⌈ lo g_{2} 16 ⌉ = 4.0 bits/symbol$
3. Huffman annab sagedastele sümbolitele lühikesed koodid ja harva esinevatele pikad ning keskmine on tõenäosustega kaalutud pikkus.
  
  $\overset{ˉ}{L} = \sum p_{i} L_{i} = 3.012 bits/symbol$
4. Kokkuhoid võrdleb kahte koodipikkust, mitte koodi entropiaga — mistõttu on see väide selle alternatiivi, mitte piirmäära kohta.
  
  $savings = \frac{4.0 - 3.012}{4.0} = 24.7%$
5. Nüüd võrdle piirmääraga. Shannoni allikakodeerimise teoreem ütleb, et ükski prefikskood ei saa jääda alla H, ning Huffman jääb garanteeritult alla H + 1.
  
  $H \leq \overset{ˉ}{L} < H + 1 (Shannon); \overset{ˉ}{L} - H = 3.012 - 3.010 = 0.002 bits$
6. Väljenda järelejäänud vahe murruna ning optimeerimisküsimus vastab endale ise.
  
  $\frac{0.002}{3.010} = 0.07% above the floor$
Vastus

0,002 bitti sümboli kohta ehk 0,07%. Shannoni teoreem paigutab iga prefikskoodi H ja H + 1 vahele ning Huffmani kood on tõestatult neist optimaalne, seega ei saavuta ükski prefikskood sellel tekstil enam kunagi paremat tulemust kui 3,012. Püsipikkusega koodi ees saavutatud 24,7% kokkuhoid on reaalne ning järelejäänud 0,07% ongi kõik, mida parem inseneritöö eales lisada suudaks. Andmetihendus saavutab siit edasi edu koodi asemel mudeli muutmisega: kui naabersümbolid korreleeruvad, on tingimusliku jaotuse entroopia madalam kui 3,010, ja see on juba hoopis teine arv.

$\overset{ˉ}{L} - H = 0.002 bits : Huffman is 0.07% off optimal here$

Allikad (1)

Insight block 2 — entropy as average surprise, and the limit Huffman cannot beat: C. E. Shannon, "A Mathematical Theory of Communication." Bell System Technical Journal 27(3), 379–423, 1948.

42Mathi meeskond · Uuendatud 2026-07-29

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

Kõik Arvutustehnika õppetunnid →

Näiteülesanded

Ühtlane 8 - Ühtlane 8-sümboliline allikas: H=3 bits, kodeerimisvõitu pole — entroopia võrdub fikseeritud pikkusega koodiga
DCT-laadne (Laplace) - DCT-taoline Laplace'i jaotus: H≈2.1 bits, 23% kokkuhoidu — enamik video AC-kordajatest koonduvad nulli lähedale
Liikumisvektori-laadne - Liikumisvektori-taoline eksponentjaotus: H≈2.3 bits, 43% kokkuhoidu võrreldes 4-bitise fikseeritud koodiga
Bimodaalne - Bimodaalne: kaks domineerivat sümbolit annavad H≈2.5 bits, märkimisväärne Huffmani pakkimisvõit