Come discriminare da due nodi con frequenze identiche nell'albero di Huffman?

Se il tuo compito non specifica come discriminare tra frequenze identiche, il formato di compressione è sottodescritto e generalmente non puoi aspettarti che le implementazioni indipendenti interagiscano.

Potrebbe trattarsi di una svista da parte dell'insegnante, oppure potrebbe tentare di rendere un punto memorabile di tutto ciò.

Vorrei prima provare a chiedere dei chiarimenti, ma in assenza di ulteriori input, sceglierei un metodo facile da implementare e documentare, quindi scrivere uno standard che documenti chiaramente la tua scelta (tale che i tuoi compagni di classe potrebbero prontamente usarlo per assicurarti che la loro implementazione fosse compatibile con la tua) e consegnarlo con il tuo incarico.

Se stai solo scrivendo i tuoi algoritmi di codifica e decodifica, non importa come distingui tra nodi con valore uguale, fintanto che ogni metà dell'operazione utilizza la stessa metodologia.

La risposta deriva dall'implementazione della coda di priorità. Quando viene aggiunto nuovamente un valore già esistente nella coda, il nuovo elemento viene considerato inferiore o superiore rispetto all'elemento esistente con lo stesso valore di priorità. Questo è ciò di cui hai bisogno per assicurarti che il tuo algoritmo sia compatibile con quelli dei tuoi compagni di classe.

Scegli semplicemente uno dei nodi. Devi includere informazioni su come ricostruire comunque l'albero nel file compresso.

Wikipedia dice (sulla decompressione):

Before this can take place, however, the Huffman tree must be somehow reconstructed. In the simplest case, where character frequencies are fairly predictable, the tree can be preconstructed (and even statistically adjusted on each compression cycle) and thus reused every time, at the expense of at least some measure of compression efficiency. Otherwise, the information to reconstruct the tree must be sent a priori.

Per la codifica di huffman, se due nodi hanno la stessa frequenza, per scopi di compressione sono identici, quindi puoi scegliere l'uno o l'altro e otterrai una compressione uguale.

Provalo: imposta il tuo programma in modo che possa essere configurato in modo da poterlo scegliere. Quindi esegui alcuni dati di test attraverso di esso e verifica se i dati compressi risultanti cambiano di dimensioni.