> 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.
// Esempio svolto
| Symbol | Freq | Code | Bits |
|---|---|---|---|
| A | 15 | 00 | 2 |
| B | 7 | 01 | 2 |
| C | 6 | 10 | 2 |
| D | 6 | 110 | 3 |
| E | 5 | 111 | 3 |
// Esempi di codice
Frequencies A=15 B=7 C=6 D=6 E=5 (39 symbols)
1. Sort symbols by frequency (descending).
2. Split the list where the two halves' totals are closest:
{A,B}=22 | {C,D,E}=17 -> first bit 0 / 1
3. Recurse on each half until single symbols remain:
{A}|{B} -> 00, 01 {C}|{D,E} -> 10, 11.. then {D}|{E} -> 110, 111
Total 15*2 + 7*2 + 6*2 + 6*3 + 5*3 = 89 bits
Huffman on the same data: A=1 bit, others 3 bits -> 87 bits
>> Altre domande
D: Come differisce Shannon-Fano da Huffman?
R: Shannon-Fano divide la lista ordinata dall’alto in basso in due metà di frequenza il più possibile uguale; Huffman costruisce l’albero dal basso fondendo i simboli più rari. Huffman è dimostrabilmente ottimale, Shannon-Fano non sempre.
D: Shannon-Fano è sempre ottimale?
R: No. Nell’esempio servono 89 bit contro 87 di Huffman. Entrambi producono codici senza prefissi, ma la regola di divisione di Shannon-Fano può scegliere tagli sfavorevoli.
D: Dove si usa Shannon-Fano?
R: Soprattutto come metodo storico e didattico (Claude Shannon e Robert Fano, 1948/49). Una variante è nell’algoritmo IMPLODE del formato ZIP; i compressori moderni usano Huffman o la codifica aritmetica.