HuffmanCodes

Per eseguire il codice è necessario avere il file Python Node.py, nel quale viene definita la classe Node e i suoi relativi metodi. Per importarlo nel progetto non è necessario eseguire nessuna azione particolare in quanto viene importato automaticamente nel codice tramite lo statement:

from Node import *

L’unica accortezza è quella di mettere entrambi i file Python nella stessa cartella.

Inoltre è stata utilizzata la seguente libreria:

• numpy

Una volta eseguito il codice, l’utente può scegliere tra una lista di funzioni disponibili che vengono stampate a schermo, semplicemente inserendo il numero corrispondente.

Mostriamo dunque adesso una breve descrizione delle seguenti funzioni e cosa richiedono in input.

1. Generare un codice istantaneo ottimo

Funzione che serve per generare un codice istantaneo (o prefix-free) ottimo.

All’utente viene richiesto in input:

• il numero di lettere dell’alfabeto inglese da utilizzare.

Dato il numero di lettere ad ognuna viene assegnata una propria distribuzione di probabilità, tramite la seguente funzione:

def alphabet_distribution(n_letter, choice):
	'''some code'''
	return distribution

Quando viene chiamato questo metodo l'utente può decidere se assegnare all'alfabeto la distribuzione dell'alfabeto inglese oppure una distribuzione randomica generata tramite random.rand(…), nel seguente modo:

Una volta selezionata una delle due opzioni, la funzione restituisce in output il codice di Huffman generato, il quale è un codice prefix-free ottimo.

Nel codice la funzione che genera il codice di Huffman prendendo in input i nodi è la seguente:

def huffman_code(nodes):
	'''some code'''
	return code

Mentre la funzione che imposta i valori dei parametri in input è:

def set_huffman_code():
	'''some code'''

Test di Esempio

Generare un codice prefix-free ottimo composto dalle prime 10 lettere dell’alfabeto, utilizzando come distribuzione per ogni singola lettera quella relativa all’alfabeto inglese:

2. Decoding

Funzione che implementa una procedura di decodifica.

La funzione chiede all’utente di inserire il numero di lettere dell’alfabeto per poter andare a genererare un codice prefix-free.

Dopo aver inserito il numero di lettere, sempre all’utente viene chiesto che tipo di codice prefix-free vuole generare:

1. Un codice di Huffman
2. Un generico codice prefix-free ottenuto tramite una personale scelta implementativa.

Se viene scelto di generare un codice di Huffman, all’utente viene inoltre richiesto, come nel caso del punto 1., con quale distribuzione si vuole generare tale codice:

Una volta generato il codice è possibile passare alla decodifica di una stringa binaria.

Nel codice la funzione che esegue la procedura di decodifica è la seguente:

def binary_strign_decoding(prefix_free_code, binary_string):
	'''some code'''
	return plaintext

Mentre la funzione che imposta i valori dei parametri in input è:

def set_decoding():
	'''some code'''

Test di Esempio

Decodificare la parola “edifici” con un codice di Huffman composto dalle prime 10 lettere dell'alfabeto, generato utilizzando una distribuzione casuale per ogni singola lettera:

Osservazione

Se l’utente sceglie di utilizzare un generico codice prefix-free (“Generic Prefix-Free Code”) come codice per il test di esempio, il consiglio è quello di non utilizzare un numero di lettere superiore a 22, in quanto impiegherebbe molto tempo per generarlo a causa di una alta complessità computazionale, dovuta alla mia personale scelta implementativa.