Codifica di Huffman - codici prefissi, algoritmo e ottimalità

Applicazione notevole del paradigma greedy (Paradigma greedy - scelta golosa, sottostruttura e selezione delle attivitàIl paradigma greedy compie subito una scelta localmente migliore (scelta greedy), pulisce l'istanza (clean-up) e risolve l'unica sottoistanza residua, con ricorsione di coda eliminabile; il codice è facile, la correttezza no e richiede due proprietà, la scelta greedy (esiste un ottimo che la contiene) e la sottostruttura ottima (cut-and-paste), da cui la correttezza segue per induzione. Caso di studio: la selezione delle attività, con l'algoritmo del primo che finisce, correttezza completa, complessità Theta(n) dopo l'ordinamento e controesempi per le scelte greedy sbagliate.Paradigma greedy - scelta golosa, sottostruttura e selezione delle attività →). Il punto di vista della teoria dell'informazione (entropia, limiti di Shannon, efficienza) è in Codici di Shannon-Fano e di HuffmanIn un codice ottimo le parole più probabili non sono più lunghe di quelle meno probabili e le due parole più lunghe differiscono solo per l'ultimo simbolo. Shannon-Fano costruisce l'albero dall'alto dividendo ripetutamente i simboli in due gruppi di probabilità quasi uguali; Huffman lo costruisce dal basso unendo ogni volta i due simboli meno probabili ed è sempre ottimo tra i codici a prefisso. La lunghezza media $L_y$ è la somma delle probabilità dei nodi uniti, l'efficienza è $\eta=\frac{H}{L_y}$.Codici di Shannon-Fano e di Huffman →, Codici a prefisso - Kraft-McMillan e limiti di Shannon sulla lunghezza mediaLa codifica di sorgente senza perdite associa a ogni parola emessa dalla sorgente una parola di codice binaria (o $M_y$-aria) di lunghezza variabile, in modo invertibile; la qualità si misura con la lunghezza media $L_y=\sum p_{\underline x}(\underline a),l(\underline a)$. In un codice a prefisso nessuna parola è l'inizio di un'altra, quindi la decodifica è istantanea. Kraft-McMillan: ogni codice decodificabile ha $\sum M_y^{-l_i}\le1$, e se interi $l_i$ la soddisfano esiste un codice a prefisso con quelle lunghezze. Shannon: $\frac{H(\underline x)}{\log_2M_y}\le L_y<\frac{H(\underline x)}{\log_2M_y}+1$ per il codice a prefisso ottimo, con $L_y=\frac{H}{\log_2M_y}$ solo se le probabilità sono potenze di $\frac1{M_y}$.Codici a prefisso - Kraft-McMillan e limiti di Shannon sulla lunghezza media →, Codici di Shannon, Huffman ed Elias e codifica aritmeticaIl codice di Shannon(-Fano) assegna alla parola $i$ lunghezza $l_i=\lceil-\log_{M_y}p_i\rceil$, soddisfa Kraft-McMillan e ha $H\le L_y<H+1$; è ottimo solo se le probabilità sono potenze di $\frac1{M_y}$. Il codice ottimo (lunghezza media minima) dà parole più lunghe ai simboli meno probabili e ha almeno due parole di lunghezza massima che differiscono solo nell'ultimo simbolo: lo costruisce la procedura di Huffman, che unisce a ogni passo i due nodi meno probabili. Il codice di Elias prende le prime $l_i=\lceil-\log_2p_i\rceil+1$ cifre del punto medio dell'intervallo di ampiezza $p_i$ in $[0,1)$: è a prefisso ma subottimo ($H+1\le L_y<H+2$), e si adatta alla codifica aritmetica adattativa.Codici di Shannon, Huffman ed Elias e codifica aritmetica → e Codifica lossless - entropia, Huffman e codifiche a dizionarioLa codifica lossless rappresenta i simboli di una sorgente con parole di codice a lunghezza variabile in modo invertibile; si usano codici a prefisso (istantanei). L'entropia $H(X)=\sum p_i\log_2\frac1{p_i}$ è il limite: $H(X)\le\mathcal L^*<H(X)+1$ (Shannon), con uguaglianza se le probabilità sono potenze di 1/2. Il codice di Huffman è ottimo ma lascia fino a 1 bit di overhead per simbolo; raggruppando $K$ simboli (codifica a blocchi) si tende al tasso entropico $\mathcal H(X)\le H(X)$, ma la complessità cresce come $M^K$; la codifica aritmetica ($\mathcal L<H+2$ per messaggio) ha complessità lineare. Altre tecniche: dizionario (LZ, DEFLATE di ZIP e PNG, ANS in Zstandard), Exp-Golomb e categoria/ampiezza (usati in JPEG e nei codec video) per interi con probabilità decrescente col modulo, codifica predittiva (si codifica l'errore di predizione, che ha entropia molto più bassa).Codifica lossless - entropia, Huffman e codifiche a dizionario →. Qui contano la dimostrazione di ottimalità (scelta greedy e sottostruttura) e la complessità con la coda con priorità.

Codifica per carattere e codici a lunghezza fissa

Un file $F$ è una stringa su un alfabeto $C$ di caratteri. Una codifica per carattere associa a ogni $c \in C$ una parola binaria $e(c)$ (la codeword); la codifica del file è la concatenazione delle parole dei suoi caratteri, $$e(x_1 x_2 \cdots x_n) = e(x_1)\, e(x_2) \cdots e(x_n).$$ Si chiede che la codifica sia invertibile (altrimenti si distrugge l'informazione) e calcolabile in modo efficiente, con la compressione migliore possibile; la qualità si misura con la lunghezza in bit della stringa compressa rispetto alla codifica diretta (8 bit per carattere ASCII).

Caso di studio. Un file di $100$ milioni di caratteri ASCII (800 Mbit in codifica diretta) usa solo sei caratteri, con frequenze $f(a)=0{,}45$, $f(b)=0{,}13$, $f(c)=0{,}12$, $f(d)=0{,}16$, $f(e)=0{,}09$, $f(f)=0{,}05$. Si leggono con una scansione lineare del file e sommano sempre a $1$. Il numero di occorrenze di $c$ è $f(c) \cdot \lvert F \rvert$.

Con sei caratteri bastano 3 bit ($2^3 = 8 \ge 6$): codice a lunghezza fissa $a=000$, $b=001$, $c=010$, $d=011$, $e=100$, $f=101$. Il file occupa $300$ Mbit (risparmio del $62{,}5\%$ su 800), più la tabella dei caratteri, e si comprime e decomprime in tempo lineare. Ma questo codice ignora le frequenze: l'idea è dare parole più corte ai caratteri più frequenti.

Attenzione: la lunghezza variabile, da sola, può rompere l'invertibilità. Il codice $a=0$, $b=10$, $c=11$, $d=1$, $e=100$, $f=101$ costerebbe soltanto $$\big[(0{,}45 + 0{,}16)\cdot 1 + (0{,}13 + 0{,}12)\cdot 2 + (0{,}09 + 0{,}05)\cdot 3\big] \cdot 100 = 153 \text{ Mbit},$$ ma non è iniettivo sulle stringhe: daadaa e ee danno entrambe 100100. Il risparmio sarebbe illusorio, perché non si può decomprimere.

Codici prefissi e trie

Definizione (codice prefisso). Una codifica è libera da prefissi (prefix-code) se nessuna parola è prefisso di un'altra.

Nel codice sbagliato di prima $e(d) = 1$ è prefisso di $e(b), e(c), e(e), e(f)$ e $e(b) = 10$ lo è di $e(e), e(f)$.

Teorema. Un codice prefisso è invertibile sulle stringhe, e si decodifica con una sola scansione leggendo i bit fino a incontrare una parola.

Dimostrazione. Si legge dall'inizio il minimo numero di bit che forma una parola: questa è l'unica parola con tale inizio, perché una seconda parola, essendo anch'essa un inizio della stessa sequenza, sarebbe prefisso della prima o viceversa. Il primo carattere è dunque determinato; si ripete dal bit successivo. $\square$

Anche il codice a lunghezza fissa è un codice prefisso. La condizione è sufficiente, non necessaria, per la decodifica unica; ci si può però restringere ai codici prefissi senza perdere nulla in lunghezza media, per il teorema di Kraft-McMillan (Codici a prefisso - Kraft-McMillan e limiti di Shannon sulla lunghezza mediaLa codifica di sorgente senza perdite associa a ogni parola emessa dalla sorgente una parola di codice binaria (o $M_y$-aria) di lunghezza variabile, in modo invertibile; la qualità si misura con la lunghezza media $L_y=\sum p_{\underline x}(\underline a),l(\underline a)$. In un codice a prefisso nessuna parola è l'inizio di un'altra, quindi la decodifica è istantanea. Kraft-McMillan: ogni codice decodificabile ha $\sum M_y^{-l_i}\le1$, e se interi $l_i$ la soddisfano esiste un codice a prefisso con quelle lunghezze. Shannon: $\frac{H(\underline x)}{\log_2M_y}\le L_y<\frac{H(\underline x)}{\log_2M_y}+1$ per il codice a prefisso ottimo, con $L_y=\frac{H}{\log_2M_y}$ solo se le probabilità sono potenze di $\frac1{M_y}$.Codici a prefisso - Kraft-McMillan e limiti di Shannon sulla lunghezza media →).

Rappresentazione ad albero

Un codice prefisso si rappresenta con un trie: albero binario con archi etichettati $0$ verso il figlio sinistro e $1$ verso il destro, in cui a ogni nodo corrisponde la stringa dei bit lungo il cammino dalla radice. Vale che:

• le parole sono sulle foglie. Se un carattere fosse su un nodo interno, la sua parola sarebbe prefisso della parola di un discendente. Quindi il trie ha $\lvert C \rvert$ foglie;
• c'è una corrispondenza biunivoca tra codici prefissi su $C$ e trie binari con $\lvert C \rvert$ foglie, per cui si parla indifferentemente del codice $e$ o del trie;
• la profondità di $c$ nel trie è la lunghezza della sua parola: $d_T(c) = \lvert e(c) \rvert$.

La decodifica con il trie parte dalla radice, segue 0 a sinistra e 1 a destra per ogni bit letto fino a una foglia, emette il carattere e ricomincia dalla radice.

Esempio. Con il codice prefisso $a=0$, $b=101$, $c=100$, $d=111$, $e=1101$, $f=1100$ la stringa badface diventa $101\,0\,111\,1100\,0\,100\,1101$, cioè 1010111110001001101 (19 bit, contro $7 \cdot 3 = 21$ del codice fisso), e il trie la riporta a badface (verificato con Python).

Costo di un trie

Il numero di bit del file compresso è $$\sum_{c \in C} \lvert e(c) \rvert\,\big(f(c) \lvert F \rvert\big) = \Big( \sum_{c \in C} d_T(c)\, f(c) \Big) \lvert F \rvert .$$

Definizione (costo di un trie). $B(T) = \displaystyle\sum_{c \in C} d_T(c)\, f(c)$ (lunghezza media in bit per carattere).

Problema (codifica ottima di carattere). Dati $C$ e le frequenze $f : C \to \mathbb{Q}^+$, trovare il codice prefisso, cioè il trie binario $T^\ast$ con $\lvert C \rvert$ foglie, che minimizza $B(T)$.

Non serve conoscere il file, solo l'alfabeto e le frequenze (come per la catena di matrici bastavano le dimensioni, Matrix Chain Multiplication - parentesizzazione ottimadato il vettore p delle dimensioni di una catena di n matrici compatibili (A_i è p_(i-1) x p_i), si cerca la parentesizzazione che minimizza il numero di prodotti tra scalari. Le parentesizzazioni sono numeri di Catalan (esponenziali). Sottostruttura: i due sottoalberi dell'ultimo prodotto sono ottimi (cut-and-paste). Ricorrenza c(i,j) = min su k di c(i,k) + c(k+1,j) + p_(i-1) p_k p_j, c(i,i) = 0. D&C: 3^(n-1) - 1 operazioni. Bottom-up per diagonali crescenti con tabelle m e s: (n^3 - n)/3 prodotti, Theta(n^3). La memoizzazione ha lo stesso costo e non risparmia mai.Matrix Chain Multiplication - parentesizzazione ottima →).

Il trie ottimo è pieno. Un albero binario è pieno se ogni nodo interno ha esattamente due figli. Dimostrazione per assurdo: sia $T^\ast$ ottimo con un nodo interno $u$ con un solo figlio $v$ (diciamo il sinistro) e sia $T'$ il sottoalbero di radice $v$ (può essere la sola foglia $v$). Si contraggono $u$ e $v$ in un solo nodo: il risultato $\hat T$ è ancora un trie con le stesse $n$ foglie, quindi un codice valido, e l'arco $(u,v)$, cioè un bit, scompare dal cammino di ogni foglia di $T'$, che ha almeno una foglia $c'$. Allora $d_{\hat T}(c') f(c') = d_{T^\ast}(c') f(c') - f(c') < d_{T^\ast}(c') f(c')$ (le frequenze sono positive), mentre per gli altri caratteri $d_{\hat T}(c) \le d_{T^\ast}(c)$. Dunque $B(\hat T) < B(T^\ast)$, assurdo. $\square$

Per esempio il codice a lunghezza fissa dei 6 caratteri ha un trie non pieno (le parole $110$ e $111$ sono inutilizzate): non è ottimo. Un albero binario pieno con $n$ foglie ha sempre $n - 1$ nodi interni (Divide and conquer - proprietà di sottostruttura e albero delle chiamateUn algoritmo divide and conquer nasce da una proprietà di sottostruttura (funzioni Divide e Conquer, base n0) con sottoistanze di taglia strettamente minore; l'albero delle chiamate ne descrive l'esecuzione, e il D&C non ha memoria (ripete le sottoistanze uguali). Esempio completo: MAX di un array, con correttezza per induzione, ricorrenza e conteggio esatto n-1 tramite il teorema sugli alberi binari pieni.Divide and conquer - proprietà di sottostruttura e albero delle chiamate →: contando gli archi, $2I = I + n - 1$ da cui $I = n - 1$).

Costo come somma dei nodi interni. Se a ogni nodo $v$ si dà un peso $w(v)$ = somma delle frequenze delle foglie sotto di lui, vale $$B(T) = \sum_{v \text{ interno}} w(v),$$ perché la frequenza di una foglia $c$ compare nel peso di ciascuno dei suoi $d_T(c)$ antenati propri. È la formula con cui si controlla a mano un risultato.

L'algoritmo di Huffman

Idea. Si costruisce il trie dal basso. Si parte da una foresta di $n = \lvert C \rvert$ alberi, uno per carattere (la foglia con la sua frequenza). A ogni passo si fondono due alberi creando una nuova radice che li ha come figli sinistro e destro e come peso la somma dei pesi: la foresta perde un albero, quindi dopo $n - 1$ fusioni resta un albero pieno con $n$ foglie, il trie.

Ogni fusione aumenta di 1 la profondità di tutte le foglie dei due alberi, quindi allunga di un bit le loro parole; l'impatto sul costo è il peso dell'albero. La scelta greedy è dunque fondere i due alberi di peso minimo.

L'implementazione usa una coda con priorità $Q$ (Code con prioritàEntry chiave-valore; ADT coda con priorità (insert, min, removeMin) con chiave minima = priorità massima; esempio di esecuzione; applicazioni; implementazioni con lista non ordinata e ordinata e relativi costi; ordinamento tramite coda con priorità.Code con priorità →, HeapAlbero binario completo e sua altezza floor(log2 n); heap = albero completo con heap-order property; proprietà (radice minima, cammini non decrescenti); rappresentazione su array con level numbering; insert con up-heap bubbling, removeMin con down-heap bubbling, rimozione di una entry qualsiasi; invarianti e costi Theta(log n); esempio svolto.Heap →) di nodi con chiave $z.f$, con insert ed extractmin in $O(\log n)$ se $n$ è il numero massimo di elementi. Un nodo ha i campi left, right, f e char (significativo solo per le foglie, che hanno left e right nulli).

HUFFMAN(C, f)
    n <- |C|
    Q <- {}
    for c in C do
        z <- newnode(); z.f <- f(c); z.char <- c; z.left <- null; z.right <- null
        Q.insert(z)
    for i <- 1 to n-1 do
        x <- Q.extractmin()
        y <- Q.extractmin()
        z <- newnode()
        z.f <- x.f + y.f
        z.left <- x; z.right <- y            // convenzione: il sinistro e' il piu' leggero
        Q.insert(z)
    return Q.extractmin()                    // la radice del trie

La codifica del file si fa dopo, leggendo le parole dai cammini radice-foglia. Convenzione: il figlio sinistro (arco $0$) è quello estratto per primo, cioè di frequenza non superiore; con frequenze uguali il trie può cambiare ma il costo no.

Esempio eseguito a mano

Frequenze in percentuale: $a\,45$, $b\,13$, $c\,12$, $d\,16$, $e\,9$, $f\,5$. La coda a ogni passo, con il nodo creato:

Il trie (i numeri sono i pesi, gli archi sono $0$ a sinistra e $1$ a destra):

                   (100)
                 0/      \1
               a:45      (55)
                      0/      \1
                   (25)        (30)
                  0/  \1      0/   \1
               c:12  b:13   (14)   d:16
                           0/  \1
                        f:5    e:9

Parole: $e(a) = 0$, $e(b) = 101$, $e(c) = 100$, $e(d) = 111$, $e(e) = 1101$, $e(f) = 1100$. Costo $$B(T) = 0{,}45 \cdot 1 + (0{,}13 + 0{,}12 + 0{,}16) \cdot 3 + (0{,}09 + 0{,}05) \cdot 4 = 0{,}45 + 1{,}23 + 0{,}56 = 2{,}24,$$ cioè $224$ Mbit per il file, contro i $300$ del codice fisso. Controllo con i nodi interni: $14 + 25 + 30 + 55 + 100 = 224$ (in centesimi). L'entropia della sorgente è $H \approx 2{,}22$ bit, e vale $H \le B < H + 1$ (Codici a prefisso - Kraft-McMillan e limiti di Shannon sulla lunghezza mediaLa codifica di sorgente senza perdite associa a ogni parola emessa dalla sorgente una parola di codice binaria (o $M_y$-aria) di lunghezza variabile, in modo invertibile; la qualità si misura con la lunghezza media $L_y=\sum p_{\underline x}(\underline a),l(\underline a)$. In un codice a prefisso nessuna parola è l'inizio di un'altra, quindi la decodifica è istantanea. Kraft-McMillan: ogni codice decodificabile ha $\sum M_y^{-l_i}\le1$, e se interi $l_i$ la soddisfano esiste un codice a prefisso con quelle lunghezze. Shannon: $\frac{H(\underline x)}{\log_2M_y}\le L_y<\frac{H(\underline x)}{\log_2M_y}+1$ per il codice a prefisso ottimo, con $L_y=\frac{H}{\log_2M_y}$ solo se le probabilità sono potenze di $\frac1{M_y}$.Codici a prefisso - Kraft-McMillan e limiti di Shannon sulla lunghezza media →).

L'ottimo non è unico. Con frequenze $1, 1, 2, 2$ ci sono due esecuzioni valide (dopo la fusione $1+1 = 2$ si hanno tre alberi di peso 2): fondendo i due originali da 2 le parole hanno tutte lunghezza 2, fondendone uno con il nodo creato si ottengono lunghezze $1, 2, 3, 3$; il costo è $12$ in entrambi i casi (forza bruta: $12$ è il minimo).

Complessità

Il modello conta i confronti tra frequenze; $n = \lvert C \rvert$.

• La prima fase fa $n$ inserzioni, ciascuna $O(\log n)$: $O(n \log n)$ (con la costruzione bottom-up dello heap, Costruzione di uno heapCostruire uno heap da un array di n entry: approccio top-down con n-1 insert, Theta(n log n); approccio bottom-up con down-heap dalle foglie verso la radice, Theta(n), con dimostrazione della somma; esempi svolti, in loco; unione di due alberi con heap-order.Costruzione di uno heap →, scenderebbe a $O(n)$).
• Il ciclo ha $n - 1$ iterazioni e ognuna fa 2 estrazioni e 1 inserzione, cioè $O(\log n)$.
• Il return fa un'ultima estrazione.

In totale le estrazioni del minimo sono $2(n-1) + 1 = 2n - 1$ (per $n = 13$: $25$) e anche le inserzioni sono $n + (n-1) = 2n - 1$. La complessità è $O(n \log n)$ (Notazione asintoticaDefinizioni di O, Omega, Theta e o piccolo con le costanti c ed n0; esempi con costanti esplicite; proprietà (polinomi, esponenziali, logaritmi, somme, implicazioni tra notazioni); sommatorie notevoli; terminologia (logaritmica, lineare, polinomiale, esponenziale).Notazione asintotica →). Se i caratteri arrivano già ordinati per frequenza si può scendere a $O(n)$ con due code ordinate, una per le foglie e una per i nodi creati (che nascono in ordine non decrescente); ordinare i caratteri costa però $O(n \log n)$.

import heapq, itertools

def huffman(freq):                       # freq: dict carattere -> frequenza
    cnt = itertools.count()              # spareggio per l'heap: i nodi non si confrontano mai
    Q = [(f, next(cnt), (c,)) for c, f in freq.items()]   # un nodo foglia e' (carattere,)
    heapq.heapify(Q)
    for _ in range(len(freq) - 1):
        fx, _, x = heapq.heappop(Q)
        fy, _, y = heapq.heappop(Q)
        heapq.heappush(Q, (fx + fy, next(cnt), (x, y)))   # un nodo interno e' (sinistro, destro)
    return Q[0][2]

def codici(t, p=""):
    if len(t) == 1: return {t[0]: p or "0"}
    return {**codici(t[0], p + "0"), **codici(t[1], p + "1")}

Correttezza

Lo spazio delle scelte è l'insieme degli alberi della foresta, ciascuno con la frequenza somma delle sue foglie; ogni scelta è la coppia da fondere, e dopo la fusione i due alberi sono sostituiti da uno di frequenza uguale alla somma. Ogni albero della foresta si può vedere come un supercarattere con quella frequenza, di cui calcolare la codifica ottima: la parola del supercarattere sarà il prefisso comune di tutte le foglie del sottoalbero. La foresta dopo una fusione è la sottoistanza residua, con un carattere in meno.

Notazione: $x, y$ sono i due caratteri di frequenza minima, $f(x) \le f(y) \le f(c)$ per ogni altro $c$; $C' = (C \setminus \{x, y\}) \cup \{z\}$ con $f(z) = f(x) + f(y)$ è l'alfabeto residuo.

Lemma di scambio. Siano $a, b$ due foglie di un trie $T$ con $f(a) \le f(b)$ e $d_T(a) \le d_T(b)$ e sia $T'$ il trie ottenuto scambiando i caratteri $a$ e $b$. Allora $B(T') \le B(T)$.

Dimostrazione. Dopo lo scambio $a$ sta alla profondità di $b$ e viceversa, e gli altri caratteri non si muovono: $$B(T') - B(T) = f(a) d_T(b) + f(b) d_T(a) - f(a) d_T(a) - f(b) d_T(b) = \big(f(a) - f(b)\big)\big(d_T(b) - d_T(a)\big) \le 0,$$ perché i due fattori sono entrambi $\le 0$. $\square$

In parole: il carattere più raro può solo guadagnare scendendo più in basso, e quello più frequente salendo.

Proprietà di scelta greedy. Esiste un trie ottimo in cui $x$ e $y$ sono foglie sorelle (figlie dello stesso padre) alla profondità massima.

Dimostrazione. Sia $T^\ast$ un trie ottimo; è pieno. Sia $m$ la profondità massima e sia $w$ una foglia a profondità $m$: il suo fratello è una foglia $z$ (se avesse discendenti ci sarebbe una foglia più profonda), a profondità $m$.

1. Se $x \notin \{w, z\}$ si scambiano $x$ e $w$: valgono $f(x) \le f(w)$ ($x$ ha frequenza minima) e $d(x) \le d(w) = m$, quindi per il lemma il costo non aumenta. (Se $x \in \{w, z\}$ si chiama $w$ la foglia $x$.) Ora $x$ è a profondità $m$ con fratello $z$ (foglia).
2. Se $y \ne z$ si scambiano $y$ e $z$: valgono $f(y) \le f(z)$ (perché $z \ne x$ e $y$ è il più raro tra i caratteri diversi da $x$) e $d(y) \le d(z) = m$, quindi il costo non aumenta. Lo scambio non sposta $x$, che ha ora per fratello $y$.

Il trie ottenuto ha $x, y$ sorelle alla profondità massima e costo $\le B(T^\ast)$, quindi, per l'ottimalità di $T^\ast$, uguale: è ottimo. $\square$

(Il testo del corso scambia direttamente le due coppie $x \leftrightarrow w$ e $y \leftrightarrow z$ e calcola la differenza con la formula completa; il passaggio in due tempi evita di trattare a parte i casi in cui $x$, $y$, $w$, $z$ non sono distinti.)

Proprietà di sottostruttura ottima. Sia $T$ un trie per $C$ in cui $x$ e $y$ sono foglie sorelle e sia $T'$ il trie per $C'$ ottenuto potando le foglie $x$ e $y$: il loro padre diventa la foglia $z$. Gli altri caratteri hanno la stessa profondità in $T$ e in $T'$, e $d_{T'}(z) = d_T(x) - 1 = d_T(y) - 1$. Quindi $$\begin{aligned} B(T) &= \sum_{c \in C \setminus \{x,y\}} f(c)\, d_{T'}(c) + \big(f(x) + f(y)\big)\, d_T(x) \\ &= \sum_{c \in C \setminus \{x,y\}} f(c)\, d_{T'}(c) + f(z)\big(d_{T'}(z) + 1\big) \\ &= B(T') + f(x) + f(y). \end{aligned}$$ Questa relazione tra costo e costo della residua vale per ogni coppia $(T, T')$, ed è biunivoca: ogni trie per $C'$ si ottiene da un unico trie per $C$ facendo di $z$ il padre di due foglie $x, y$. Perciò il minimo di $B$ sui trie per $C$ con $x, y$ sorelle è $\mathrm{OPT}(C') + f(x) + f(y)$, e per la scelta greedy è anche $\mathrm{OPT}(C)$: $$\mathrm{OPT}(C) = \mathrm{OPT}(C') + f(x) + f(y).$$ (Per assurdo, con cut-and-paste: se in un ottimo $\hat T$ con $x,y$ sorelle il trie potato $T'$ non fosse ottimo per $C'$, sostituendolo con un ottimo $T''$ e rimettendo le foglie $x, y$ sotto $z$ si avrebbe un trie per $C$ di costo $B(T'') + f(x) + f(y) < B(\hat T)$.)

Teorema. $\mathrm{HUFFMAN}(C, f)$ ritorna un trie ottimo, per ogni alfabeto con $n \ge 1$ caratteri.

Dimostrazione. Induzione su $n$. Base $n = 1$: un solo nodo, costo $0$ (o $f$ con parola di un bit per convenzione), l'unico trie. Passo $n \ge 2$: la prima iterazione fonde $x, y$ in $z$ e quello che resta è esattamente l'esecuzione di $\mathrm{HUFFMAN}(C', f')$, che per ipotesi induttiva (alfabeto di $n-1$ caratteri) ritorna un trie ottimo $T'$ per $C'$. L'algoritmo ritorna il trie $T$ ottenuto da $T'$ rendendo $z$ padre di $x, y$. Per la relazione dei costi $$B(T) = B(T') + f(x) + f(y) = \mathrm{OPT}(C') + f(x) + f(y) = \mathrm{OPT}(C). \quad \square$$

Ancora una volta il codice è semplice e la dimostrazione di correttezza è la parte difficile.

Domande d'esame

1. Il numero complessivo di estrazioni del minimo effettuate da HUFFMAN su un alfabeto di $n = 13$ caratteri. Risposta: $12$ iterazioni con $2$ estrazioni, più $1$ nel return: $24 + 1 = 25 = 2n - 1$. Vedi Esercizio - domande di prima parte su greedy e Huffman (simulazioni d'esame).
2. Perché il trie di un codice ottimo è pieno? Quanti nodi interni ha? Traccia: se un nodo interno ha un solo figlio si contrae l'arco e si accorcia di un bit almeno una parola, quindi il costo diminuisce; un albero pieno con $n$ foglie ha $n-1$ nodi interni.
3. Enunciare e dimostrare la proprietà di scelta greedy per Huffman. Traccia: lemma di scambio $B(T') - B(T) = (f(a) - f(b))(d(b) - d(a))$; si portano $x$ e $y$ sulle due foglie sorelle più profonde.
4. Frequenze $f_j = 2^{j-1}/(2^n - 1)$: forma del trie e parole. Vedi Esercizio - codice di Huffman con frequenze in progressione geometrica, trie e codeword (compito del 29 gennaio 2026, es. 2).