L'algoritmo di Huffman è un particolare algoritmo per la compressione dei dati utilizzando una tecnica di codifica basato sulla lunghezza dove i caratteri più comuni sono rappresentati da codici più brevi rispetto ai caratteri che compaiono meno volte. In questo modo la sequenza di dati può essere rappresentata in modo più compatto e può essere compressa.
Vediamo ora un esempio dove viene utilizzato una frase di esempio più lunga per vedere come l'algoritmo di Huffman può essere utilizzato per comprimere sequenze di dati più complesse. Il testo viene passato alla funzione huffman_encoding, che restituisce la sequenza di dati compressa e il dizionario di codifica. La sequenza di dati compressa viene quindi decodificata utilizzando la funzione huffman_decoding per ripristinare il testo originale.
Il codice inizia importando le librerie necessarie, heapq viene utilizzato per creare una coda di priorità, defaultdict viene utilizzato per creare un dizionario in cui le chiavi sono inizializzate automaticamente a un valore predefinito (in questo caso, 0 per tutte le chiavi).
La funzione huffman_encoding(data) prende come input una stringa data e restituisce due valori: la stringa compressa encoded_data e un dizionario encoding che contiene la codifica di Huffman di ogni carattere nella stringa originale.
La funzione prima calcola la frequenza di ogni lettera nella stringa di input utilizzando un dizionario freq con i valori inizializzati a 0.
Poi crea una coda di priorità heap, con tutti i caratteri presenti nella stringa originale dove la priorità di ogni carattere è data dalla sua frequenza di apparizione nella stringa.
Quindi combina i due caratteri meno frequenti per creare un nuovo nodo nell'albero di Huffman fino a quando rimane solo un nodo radice.
Si assegna "0" al codice del carattere che va a sinistra e "1" al codice del carattere che va a destra.
Concludendo la funzione restituisce la stringa compressa utilizzando l'algoritmo di Huffman e il dizionario di codifica.
from heapq import heappush, heappop, heapify
from collections import defaultdict
def huffman_encoding(data):
if not data:
return "", None
freq = defaultdict(int)
for char in data:
freq[char] += 1
heap = [[f, [char, ""]] for char, f in freq.items()]
heapify(heap)
while len(heap) > 1:
lo = heappop(heap)
hi = heappop(heap)
for pair in lo[1:]:
pair[1] = '0' + pair[1]
for pair in hi[1:]:
pair[1] = '1' + pair[1]
heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
encoding = dict(heappop(heap)[1:])
encoded_data = ''.join(encoding[char] for char in data)
return encoded_data, encoding
def huffman_decoding(encoded_data, encoding):
if not encoded_data:
return ""
decoding = {v: k for k, v in encoding.items()}
decoded_data = ""
i = 0
while i < len(encoded_data):
j = i + 1
while encoded_data[i:j] not in decoding:
j += 1
decoded_data += decoding[encoded_data[i:j]]
i = j
return decoded_data
data = "Questo è un testo di esempio per l'algoritmo di Huffman"
encoded_data, encoding = huffman_encoding(data)
print("Testo originale: ", data)
print("Testo compresso: ", encoded_data)
print("Dizionario di codifica: ", encoding)
decoded_data = huffman_decoding(encoded_data, encoding)
print("Testo decodificato: ", decoded_data)
Output:
Testo originale: Questo è un testo di esempio per l'algoritmo di Huffman
Testo compresso: 10000001100000101110100111101110111011010111111110100001011101001111100101010111000010100001001100010100011111100000011001111101100111101000110110100001001110011010110101000011111001010101110111110110100111001101001000110111
Dizionario di codifica: {'e': '000', 'o': '001', 'm': '0100', 's': '0101', 'u': '0110', 'è': '01110', "'": '011110', 'H': '011111', 'Q': '100000', 'g': '100001', 'a': '10001', 'd': '10010', 'f': '10011', 'i': '1010', 'l': '10110', 'n': '10111', 'p': '11000', 'r': '11001', 't': '1101', ' ': '111'}
Testo decodificato: Questo è un testo di esempio per l'algoritmo di Huffman
