Esercizio - codice di Huffman con frequenze in progressione geometrica, trie e codeword (compito del 29 gennaio 2026, es. 2)

Prima di cominciare: le frequenze sono ammissibili

Le $f_j$ sono positive e $$\sum_{j=1}^{n} f_j = \frac{1}{2^n - 1} \sum_{j=1}^{n} 2^{j-1} = \frac{2^n - 1}{2^n - 1} = 1,$$ per la somma di una progressione geometrica (SommatorieIl simbolo di sommatoria, le sue proprietà (linearità, additività, cambio di indice) e le somme notevoli di Gauss e geometrica.Sommatorie →). Ogni frequenza è il doppio della precedente: $f_{j+1} = 2 f_j$. È la proprietà che governa tutto l'esercizio.

Punto (a): $n = 4$

Qui $2^4 - 1 = 15$ e $$(f_1, f_2, f_3, f_4) = \left( \tfrac{1}{15}, \tfrac{2}{15}, \tfrac{4}{15}, \tfrac{8}{15} \right).$$ Si indica con $z_j$ la foglia del carattere $c_j$ e si esegue HUFFMAN (Codifica di Huffman - codici prefissi, algoritmo e ottimalitàCompressione con codifica per carattere: la lunghezza variabile risparmia bit ma deve essere iniettiva, e i codici prefissi lo garantiscono; un codice prefisso è un trie binario con una foglia per carattere, di costo B(T) = somma di f(c) d_T(c), e quello ottimo è un albero pieno con n-1 nodi interni. L'algoritmo di Huffman fonde ripetutamente i due alberi di frequenza minima usando una coda con priorità (2n-1 estrazioni, costo O(n log n)); l'ottimalità si prova con la scelta greedy (i due caratteri più rari sono foglie sorelle di profondità massima, per scambio) e la sottostruttura (B(T) = B(T') + f(x) + f(y)). Esempio completo con 6 caratteri, B = 2,24.Codifica di Huffman - codici prefissi, algoritmo e ottimalità →): $n - 1 = 3$ iterazioni, ciascuna fonde i due nodi di frequenza minima, con il più leggero a sinistra.

Il trie (i pesi sono in quindicesimi, 0 a sinistra e 1 a destra):

                         (15)
                       0/    \1
                  (7)          c4: 8
                0/   \1
            (3)        c3: 4
          0/   \1
      c1: 1     c2: 2

Parole di codice: $e(c_1) = 000$, $e(c_2) = 001$, $e(c_3) = 01$, $e(c_4) = 1$. Costo (lunghezza media): $$B(T) = \tfrac{1}{15} \cdot 3 + \tfrac{2}{15} \cdot 3 + \tfrac{4}{15} \cdot 2 + \tfrac{8}{15} \cdot 1 = \tfrac{3 + 6 + 8 + 8}{15} = \tfrac{25}{15} = \tfrac{5}{3} \approx 1{,}67 \text{ bit per carattere}.$$ Controllo con la somma dei pesi dei nodi interni: $\frac{3 + 7 + 15}{15} = \frac{25}{15}$. Il codice a lunghezza fissa ne userebbe $2$.

Nota sulla soluzione del corso: riporta $B(T) = \frac{25}{15} \approx 1{,}78$, ma $\frac{25}{15} = 1{,}\overline{6}$; l'approssimazione $1{,}78$ è un errore di stampa (la frazione è giusta).

Punto (b): $n$ generico

Passo 1: ogni frequenza supera la somma di tutte le precedenti. Per $1 \le k \le n - 1$, $$\sum_{j=1}^{k} f_j = \frac{1}{2^n - 1} \sum_{j=1}^{k} 2^{j-1} = \frac{2^k - 1}{2^n - 1} < \frac{2^k}{2^n - 1} = f_{k+1}. \tag{$\ast$}$$ La disuguaglianza è stretta, quindi non ci sono mai pareggi nelle scelte dell'algoritmo, e il trie è univocamente determinato.

Passo 2: lo svolgimento di Huffman. Si indica con $z_{1..k}$ il nodo che ha per foglie $c_1, \dots, c_k$ (con $z_{1..1} = z_1$) e con $w(z_{1..k}) = \sum_{j \le k} f_j = \frac{2^k - 1}{2^n - 1}$ il suo peso.

Affermazione. Per $1 \le k \le n - 1$, all'inizio dell'iterazione $k$ la coda contiene esattamente i nodi $z_{1..k}, z_{k+1}, z_{k+2}, \dots, z_n$. L'iterazione $k$ estrae per primo $z_{1..k}$ (diventa il figlio sinistro), poi $z_{k+1}$ (figlio destro), e crea $z_{1..k+1}$ di peso $\frac{2^{k+1} - 1}{2^n - 1}$.

Dimostrazione per induzione su $k$.

• $k = 1$: la coda contiene le $n$ foglie $z_1, z_2, \dots, z_n$ con pesi $f_1 < f_2 < \dots < f_n$ (la sequenza è strettamente crescente): i due minimi sono $z_1 = z_{1..1}$ e $z_2$, estratti in questo ordine; nasce $z_{1..2}$ con peso $f_1 + f_2 = \frac{3}{2^n - 1}$.
• Passo $k \to k + 1$ (con $k + 1 \le n - 1$): alla fine dell'iterazione $k$ la coda contiene $z_{1..k+1}, z_{k+2}, \dots, z_n$ (i nodi $z_{1..k}$ e $z_{k+1}$ sono stati sostituiti da $z_{1..k+1}$). All'inizio dell'iterazione $k + 1$ i pesi sono $w(z_{1..k+1}) = \frac{2^{k+1} - 1}{2^n - 1}$ e $f_{k+2} < f_{k+3} < \dots < f_n$. Per $(\ast)$ con $k+1$ al posto di $k$ vale $w(z_{1..k+1}) < f_{k+2}$, quindi il minimo è $z_{1..k+1}$ e il secondo minimo è $z_{k+2}$, senza pareggi. Si fondono nell'ordine (sinistro, destro) $= (z_{1..k+1}, z_{k+2})$, con peso $w(z_{1..k+1}) + f_{k+2} = \frac{2^{k+2} - 1}{2^n - 1}$. $\square$

Dopo l'iterazione $n - 1$ resta il solo $z_{1..n}$, di peso $\frac{2^n - 1}{2^n - 1} = 1$ (controllo), la radice. Il confronto di sinistra e destra rispetta la convenzione del testo, perché il figlio sinistro è sempre quello di frequenza minore.

Passo 3: la forma del trie. I nodi interni sono $z_{1..2}, z_{1..3}, \dots, z_{1..n}$ ($n - 1$ nodi, come deve essere per un albero pieno con $n$ foglie) e il figlio sinistro di $z_{1..k+1}$ è $z_{1..k}$, il destro è la foglia $z_{k+1}$. Quindi il trie è una catena sinistra: un unico cammino dalla radice $z_{1..n}$ alla foglia più a sinistra $z_1$ che passa per $z_{1..n}, z_{1..n-1}, \dots, z_{1..2}, z_1$, in cui ogni nodo interno ha come figlio destro una foglia: $z_n$ sotto la radice, $z_{n-1}$ sotto $z_{1..n-1}$, ..., $z_2$ sotto $z_{1..2}$.

 radice z_{1..n} --0--> z_{1..n-1} --0--> ... --0--> z_{1..2} --0--> c_1
     |1                      |1                          |1
    c_n                    c_{n-1}                      c_2

Passo 4: le parole di codice. Il nodo $z_{1..k}$ sta a profondità $n - k$ (la radice $z_{1..n}$ a profondità $0$, e ogni passo verso sinistra scende di un livello), e il suo cammino dalla radice è $0^{n-k}$. Allora:

• per $2 \le j \le n$ la foglia $c_j$ è il figlio destro di $z_{1..j}$ (a profondità $n - j$): la parola è $0^{n-j}$ seguita da $1$, lunga $n - j + 1$;
• la foglia $c_1$ è il figlio sinistro di $z_{1..2}$ (a profondità $n - 2$): la parola è $0^{n-2}\,0 = 0^{n-1}$, lunga $n - 1$.

$$e(c_1) = 0^{n-1}, \qquad e(c_j) = 0^{n-j}\,1 \quad (2 \le j \le n).$$

Per $n = 4$: $e(c_1) = 000$, $e(c_2) = 001$, $e(c_3) = 01$, $e(c_4) = 1$, come nel punto (a). In particolare il carattere più frequente ha una parola di un solo bit, e le lunghezze sono $\lvert e(c_j) \rvert = n - j + 1$ per $j \ge 2$, cioè la parola si accorcia di un bit ogni volta che la frequenza raddoppia.

Costo. Con la somma dei pesi dei nodi interni, $w(z_{1..k}) = \frac{2^k - 1}{2^n - 1}$ per $k = 2, \dots, n$: $$B(T_n) = \sum_{k=2}^{n} \frac{2^k - 1}{2^n - 1} = \frac{(2^{n+1} - 4) - (n - 1)}{2^n - 1} = \frac{2^{n+1} - n - 3}{2^n - 1} .$$ Per $n = 4$: $\frac{32 - 7}{15} = \frac{25}{15}$, come nel punto (a). Per $n \to \infty$ tende a $2$ bit per carattere, anche se il cammino più lungo ha $n - 1$ bit.

Ottimalità. Il trie ottenuto è quello ritornato da HUFFMAN, quindi è ottimo per il teorema di correttezza dell'algoritmo; la forma a catena è l'unica possibile con questo input perché le scelte sono forzate dalle disuguaglianze strette.

Verifica

Con Python (HUFFMAN con heapq e frazioni esatte) per ogni $n$ da $2$ a $20$: le parole sono esattamente $0^{n-1}$ e $0^{n-j}1$, il figlio sinistro ha sempre frequenza $\le$ del destro, e il costo è $\frac{2^{n+1} - n - 3}{2^n - 1}$, uguale alla somma dei pesi dei nodi interni; per $n = 4$ vengono $000, 001, 01, 1$ e $\frac{25}{15} = \frac{5}{3}$.