Codifica di Huffman

$O(|\sum |\log |\sum |)$ Algoritmo greedy.

La codifica di Huffman permette di utilizzare il minor numero possibile di bit per codificare un file di testo.

• $\sum$ alfabeto finito
• $F$ file di testo con $n$ caratter di $\sum$
• $f(c)$ frequenza di occorrenza per ogni carattere dell’alfabeto ($c\in \sum$)

In output si vuole una codifica binaria di ogni carattere $cod:\sum \to \{0,1\}\ast$ tale che

$$|F|=\sum _{c\in \sum }f(c)|cod(c)|$$

sia minimo.

L’implementazione di questo tipo di codifica sfrutta il fatto di usare meno bit per rappresentare caratteri con frequenza più alta, e più bit per quelli con frequenza minore. Prende il nome di codifica a lunghezza variabile.

La rappresentazione della codifica sarà tramite albero binario, dove i caratteri saranno presenti solo nelle foglie. L’albero dovrà essere salvato nel file.

1. Costruire una lista ordinata di nodi foglia con carattere e la sua frequenza (eg: [f, 5], [e, 9], [c, 12], [b, 13], [d, 16], [a, 45])
2. rimuovere dalla lista 2 nodi con frequenza minore fx, fy
3. nuovo nodo con frequenza somma delle due di sopra [-, 14], che è radice dell’albero con i due nodi rimossi al punto 2
4. si inserisce il nuovo nodo nella lista al posto giusto
5. l’iterazione finisce quando nella lista resta solo un elemento

Questo algoritmo funziona bene con una coda con priorità (funziona anche con una lista ordinata).

huffman(chars, f, n):
	q := new_priority_queue()
	for i = 1 to n do
		t := new_tree_node()
		t.c := alphabet[i]
		t.fr := f[i]
		t.left := nil
		t.right := nil
		enqueue(q, t, f[i])
	
	for i = 1 to n-1 do
		t1 := dequeue(q)
		t2 := dequeue(q)
		t := new_tree_node()
		t.c := "-"
		t.fr := t1.fr + t2.fr
		t.left := t1
		t.right := t2
		enqueue(q, t, t.fr)
	return dequeue(q)

Il costo computazionale di questo algoritmo è di $O(|\sum |\log |\sum |)$

asd_37