> shannon | fano | entropi <
// Shannon-Fano – Top-down entropikodning til datakomprimering
Entropibaseret
Bruger informationsteori til at skabe effektive koder med variabel længde.
Top-down tilgang
Deler symboler rekursivt i grupper med lignende sandsynlighed.
Historisk algoritme
Banebrydende metode, der har påvirket moderne komprimeringsteknikker.
>> tekniske detaljer
Sådan fungerer Shannon-Fano:
Shannon-Fano-kodning sorterer symboler efter frekvens og deler dem derefter rekursivt i to grupper med så ens samlet sandsynlighed som muligt. Hver opdeling tilføjer et bit til koden (0 til venstre, 1 til højre). Resultatet er en præfiks-kode med variabel længde.
Kodningsproces:
Tekst: "AAABBCD" Frekvenser: A:3, B:2, C:1, D:1 Opdeling: [A] | [B,C,D] Koder: A: 0 B: 10 C: 110 D: 111 Kodet: 0 0 0 10 10 110 111
Hvorfor bruge Shannon-Fano:
- >Let at implementere
- >Gode komprimeringsforhold
- >Historisk betydning
- >God til undervisning
- >Præfiks-koder
>> ofte stillede spørgsmål
Hvad er Shannon-Fano-kodning?
Shannon-Fano-kodning er en entropikodningsteknik udviklet i 1940’erne af Claude Shannon og Robert Fano. Det var en af de første algoritmer, der brugte koder med variabel længde baseret på symbolers sandsynlighed.
Shannon-Fano vs. Huffman?
Begge producerer koder med variabel længde, men Huffman er optimal og giver den korteste gennemsnitlige kodelængde. Shannon-Fano er enklere, men kan give en smule længere koder. Huffman bygger træet nedefra og op, Shannon-Fano oppefra og ned.
Hvordan fungerer opdelingen af symboler?
Symbolerne sorteres efter frekvens og deles i to grupper med så ens samlet sandsynlighed som muligt. Processen gentages rekursivt, indtil hver gruppe kun indeholder ét symbol.
Bliver Shannon-Fano stadig brugt?
Shannon-Fano bruges i dag primært som historisk og pædagogisk eksempel. I praksis er det stort set afløst af Huffman-kodning, som garanterer optimale koder. Det er stadig nyttigt til at forstå grundlæggende komprimeringsprincipper.