> shannon | fano | entropia <
// Shannon-Fano – Codifica per entropia top-down per la compressione dei dati
Basato sull’entropia
Utilizza la teoria dell’informazione per creare codici efficienti a lunghezza variabile.
Approccio top-down
Divide ricorsivamente i simboli in gruppi con probabilità simili.
Algoritmo storico
Metodo pionieristico che ha influenzato molti algoritmi di compressione moderni.
>> informazioni tecniche
Come funziona Shannon-Fano:
La codifica Shannon-Fano ordina i simboli per frequenza e li divide ricorsivamente in due gruppi con probabilità totali il più possibile simili. Ogni divisione aggiunge un bit al codice (0 a sinistra, 1 a destra). Il risultato è un codice prefisso a lunghezza variabile.
Processo di codifica:
Testo: "AAABBCD" Frequenze: A:3, B:2, C:1, D:1 Divisione: [A] | [B,C,D] Codici: A: 0 B: 10 C: 110 D: 111 Codificato: 0 0 0 10 10 110 111
Perché usare Shannon-Fano:
- >Semplice da implementare
- >Buoni rapporti di compressione
- >Rilevanza storica
- >Utile per la didattica
- >Codici prefisso
>> domande frequenti
Che cos’è la codifica Shannon-Fano?
La codifica Shannon-Fano è una tecnica di codifica per entropia sviluppata negli anni ’40 da Claude Shannon e Robert Fano. È stato uno dei primi algoritmi a utilizzare codici a lunghezza variabile basati sulla probabilità dei simboli.
Shannon-Fano o Huffman?
Entrambi producono codici a lunghezza variabile, ma Huffman è ottimale e minimizza la lunghezza media del codice. Shannon-Fano è più semplice, ma può produrre codici leggermente più lunghi. Huffman costruisce l’albero dal basso verso l’alto, Shannon-Fano dall’alto verso il basso.
Come funziona la suddivisione dei simboli?
I simboli vengono ordinati per frequenza e suddivisi in due gruppi con probabilità totali il più possibile simili. Il processo si ripete in modo ricorsivo finché ogni gruppo contiene un solo simbolo.
Shannon-Fano è ancora utilizzato?
Oggi Shannon-Fano viene usato principalmente per scopi storici e didattici. Nella pratica è stato in gran parte sostituito dalla codifica di Huffman, che garantisce l’ottimalità. Rimane comunque utile per comprendere i concetti di base della compressione.