Δυαδικά δέντρα & Κωδικοποίηση

[sonyxp]

Ζόρικο πράγμα τα δέντρα Huffman, για αρχή το σκεπτικό μου έχει ως εξής

 

ΥΓ2: Ένας χαρακτήρας εμφανίζεται μόνο 1 φορά (δεν επιτρέπονται διπλότυπα), για αυτό έχω και το Frequency όπου ανάλογα θα βγάλω και τα 010101 (τους κωδικούς τους)...

#includes ....

typedef struct BTreeTAG
{
	char	Letter;
	int	Frequency;
	float	Weight;
	
	BTreeTAG *Left, *Right;
}BTree;

#define MAX_LETTERS 25

void CreateHuffmanTree(BTree* Nodes[]);
int GetFrequencyOfLetter(string Text, char letter);

int main()
{
	// Data
	float Weights[] = { 0.05f, 0.10f, 0.20f, 0.25f, 0.37f, ...., 0.85f };
	char Data[] = { 'A', 'B', 'Γ', 'Δ', 'E'...., 'Ω', ' '};
	
	// The Text we want to process
	string Text = "ΜΙΑ ΦΟΡΑ ΚΑΙ ΕΝΑΝ ΚΑΙΡΟ ΗΤΑΝ ΕΝΑΣ ΛΑΓΟΣ ΚΑΙ ΜΙΑ ΧΕΛΩΝΑ";
	
	// Greek alphabet (24) + 1 for space
	BTree* Nodes[MAX_LETTERS];
	
	/*	Generate 25 Nodes and initialise Data but don't link them
		The nodes are sorted by Weight, So are ready for Huffman Algorithm
	*/
	for(int i=0; i < MAX_LETTERS; i++)
	{
		Nodes[i] = (BTree *)malloc(sizeof(BTree));
		if (Nodes[i] != NULL)
		{
			Nodes[i]->Letter = Data[i];
			Nodes[i]->Weight = Weigts[i];
			Nodes[i]->Frequency = GetFrequencyOfLetter(Text, Data[i]);
			Nodes[i]->Code = -1;	// Initialise State (We don't know code)
			
			Nodes[i]->Left = NULL;
			Nodes[i]->Right = NULL;
			
		}
		else
		{
			perror("Wxx, Node[%d] failed to get some space! You can kill yourself now!");
			exit(1);
		}
	}
	
	....
		
	// Apply Huffman Code to Build The Huffman Tree
	CreateHuffmanTree(Nodes);
		
	....
	
}

// Create Huffman Tree
void CreateHuffmanTree(BTree* Nodes[])
{ }

int GetFrequencyOfLetter(string Text, char letter)
{
	char *Temp = new char[Text.size()+1];
	Temp[Text.size()] = 0;

	memcpy(Temp, Text.c_str(), Text.size());

	int Counter = 0;
	for(int i=0; Temp[i]; i++)
	{
		if (Temp[i] == letter)
			Counter++;
	}

	return Counter;
}

Μπορείτε να μου πείτε πως θα μπορούσε να υλοποιηθεί ο αλγόριθμος αυτός; (Βασικά θα τον καταφέρω και μόνος μου, απλά δεν υπάρχει χρόνος ...)

 

Έστω λοιπόν ότι φτιάξω το δέντρο Huffman, πως θα διασχίσω όλο το δέντρο και να εκτυπώσω για κάθε γράμμα τον κωδικό του

 

Θυμίζω: Αριστερά Code = 0; Δεξιά Code = 1;

Άρα απλά να διασχίσει όλο το δέντρο και αν πηγαίνει αριστερά να εκτυπώνει 0 αν δεξιά 1.

 

ΥΓ: Έστω ότι υπάρχουν και άλλες συναρτήσεις που  (δεν θέλω βοήθεια, τα έχω κάνει αυτά, απλά να προλάβω μερικές απορίες θέλω)

- Βρίσκουν την συχνότητα εμφάνισης ενός χαρακτήρα σε ένα κείμενο "getFrequencyOfLetter(...)"

- Φορτώνουν το κείμενο από αρχείο

- Αποθηκεύουν την κωδικοποιηση...

Επεξ/σία 27 Μαΐου 2013 από sonyxp

[Retromaniac]

http://www.programminglogic.com/implementing-huffman-coding-in-c/

[sonyxp]

το βρήκα παλικάρια μου!

 

τώρα θα πρέπει με κάποιο τρόπο να προσπελάσω να το δέντρο μέχρι το γράμμα και να καταγράφων τις κινήσεις (0 για αριστερά, 1 για δεξιά)

 

εδώ είναι το ζορι

 

1. Είτε κατά την δημιουργία του δέντρου αποθηκεύω στο Node το μονοπάτι 0101 δηλαδή ΑΛΛΑ ΠΩς

είτε

2. Το δημιουργώ και έπειτα αρχίζω και συμπληρώνω τον πίνακα με τα Codes για το κάθε γράμμα διασχίζοντας το δέντρο για κάθε γράμμα

 

Πονοκέφαλος! αν μπορεί κάποιος παρακαλώ να βοηθήσει;

Επεξ/σία 28 Μαΐου 2013 από sonyxp

[sonyxp]

ΜΗΝΥΜΑ: B E A D C