> shannon | fano | entropi <
// Shannon-Fano – Top-down-entropikoding for datakompresjon
Entropibasert
Bruker informasjonsteori til å lage effektive koder med variabel lengde.
Top-down-tilnærming
Deler symboler rekursivt i grupper med lignende sannsynlighet.
Historisk algoritme
Banebrytende metode som har påvirket moderne komprimeringsteknikker.
>> teknisk informasjon
Hvordan Shannon-Fano fungerer:
Shannon-Fano-koding sorterer symboler etter frekvens og deler dem rekursivt i to grupper med så lik total sannsynlighet som mulig. Hver deling legger til ett bit i koden (0 til venstre, 1 til høyre). Resultatet er en prefikskode med variabel lengde.
Kodeprosess:
Tekst: "AAABBCD" Frekvenser: A:3, B:2, C:1, D:1 Oppdeling: [A] | [B,C,D] Koder: A: 0 B: 10 C: 110 D: 111 Kodet: 0 0 0 10 10 110 111
Hvorfor bruke Shannon-Fano:
- >Enkel å implementere
- >God komprimeringsgrad
- >Historisk betydning
- >Nyttig i undervisning
- >Prefikskoder
>> vanlige spørsmål
Hva er Shannon-Fano-koding?
Shannon-Fano-koding er en entropikodingsteknikk utviklet på 1940-tallet av Claude Shannon og Robert Fano. Det var en av de første algoritmene som brukte koder med variabel lengde basert på sannsynligheten til symbolene.
Shannon-Fano eller Huffman?
Begge produserer koder med variabel lengde, men Huffman er optimal og gir kortest mulig gjennomsnittlig kodelengde. Shannon-Fano er enklere, men kan gi noe lengre koder. Huffman bygger treet nedenfra og opp, Shannon-Fano ovenfra og ned.
Hvordan fungerer oppdelingen av symboler?
Symbolene sorteres etter frekvens og deles i to grupper med så lik total sannsynlighet som mulig. Prosessen gjentas rekursivt til hver gruppe bare inneholder ett symbol.
Brukes Shannon-Fano fortsatt?
Shannon-Fano brukes i dag hovedsakelig som et historisk og pedagogisk eksempel. I praksis er det stort sett erstattet av Huffman-koding, som gir optimale koder. Det er likevel nyttig for å forstå grunnleggende komprimeringskonsepter.