huffman algorithm

Συζητήσεις για την γλώσσα C και C++

Συντονιστές: WebDev Moderators, Super-Moderators

Απάντηση
alone24
Δημοσιεύσεις: 18
Εγγραφή: 14 Οκτ 2007 21:15

huffman algorithm

Δημοσίευση από alone24 » 03 Ιαν 2008 21:26

καλησπερα και καλη χρονια!!

ασχολούμαι αυτή τη περίοδο με δενδρικές δομές δεδομένων σε C. Μήπως μπορει κάποιος να με βοηθησει στην δημιουργια δένδρου Huffman.βασικα εχω τα εξης:


1-υπολογισμός πιθανοτήτων
2-δημιουργία δένδρου Huffman
3-κωδικοποίηση αρχείου
4-αποκωδικοποίηση αρχείου
Αναλυτικά:
1-πρέπει να έχω μια εντολή $huffman -p sample.txt probfile.txt όπου -p το όρισμα για τις πιθανότητες των χαρακτήρων, sample.txt έστω ένα μεγάλο αρχείο κειμένου και probfile.txt το αποτέλεσμα του προγράμματος για τους 128 χαρακτήρες ASCII.
2-για το δένδρο Huffman, πρέπει να εκτυπώνει στην οθόνη τους κωδικούς των χαρακτήρων ASCII(32-126) και να τυπώνει σε ένα αρχείο codes.txt τους κωδικούς των χαρακτήρων ASCII (0-127). $huffman -s probfile.txt
3-μια τυπική εντολή τύπου: $huffman -e probfile.txt data.txt data.txt.enc για να κωδικοποιεί το αρχείο κειμένου.
4-αντίστοιχα για την αποκωδικοποίηση: $huffman -d probfile.txt data.txt.enc data.txt.new
βασικα θελω την βοηθεια σας στο θεμα 2.τα αλλα τα εχω κανει.σας παραθετω τον κωδικα μου μεχρι το θεμα 2.εχω κανει κατι για το θεμα 2 αλλα δεν ξερω αν ειναι σωστο.η βοηθεια σας θα μου ειναι πολυτιμη.σας ευχαριστω εκ των προτερων!!
Συνημμένα
huffman.zip
(3.46 KiB) Μεταφορτώθηκε 582 φορές

alone24
Δημοσιεύσεις: 18
Εγγραφή: 14 Οκτ 2007 21:15

huffman algorithm

Δημοσίευση από alone24 » 06 Ιαν 2008 19:55

geia sas paidia.xreiazomai tin voitheia sas giati an then xekollisw apo auto to simeio den tha paradwsw tin ergasia mou.sas parakalw voithiste me!!
sas euxaristw ek twn proterwn!!

Άβαταρ μέλους
MannyCalavera
Δημοσιεύσεις: 13
Εγγραφή: 11 Δεκ 2007 23:00
Επικοινωνία:

huffman algorithm

Δημοσίευση από MannyCalavera » 06 Ιαν 2008 23:30

Η κωδικοποίηση huffman δεν είναι κι απ' τα ευκολότερα πράγματα στον κόσμο και προϋποθέτει πολλές γνώσεις πάνω σε δομές δεδομένων, κωδικοποίηση και προγραμματισμό. Επιπλέον, και γνώσεις να έχεις, όταν διαβάζεις τον κώδικα κάποιου άλλου και μάλιστα τέτοιου μεγέθους, το κάνει ακόμα πιο δύσκολο (δε βοηθά και το ποστ σου στην κατανόηση)
Μην απορείς που δεν κάνει ουρά ο κόσμος να βοηθήσει :wink:

Στο δια ταύτα λοιπόν.
Α)Έχεις υπολογίσει σωστά τα τις πιθανότητες κάθε χαρακτήρα στο βήμα 1

Β)Έχεις γράψει τον κώδικα για το (min heap) priority queue και τον κώδικα για τη δημιουργία του huffman tree.

Δεν έχεις όμως πουθενά κάποιο κώδικα που να τεστάρει αν η όλη διαδικασία priority queue->huffman tree δουλέυει κανονικά, με αποτέλεσμα να κάθομαι να τεστάρω μόνος μου αν ο κώδικάς τους λειτουργεί σωστά(στην ουσία πουθενά στην εκφώνηση του προβλήματος δεν αναφέρεις που ΑΚΡΙΒΩΣ αντιμετωπίζεις πρόβλημα).
Τέλοσπάντων, με ένα πρόχειρο τεστ που έκανα φαίνεται να λειτουργεί σωστά και να βγάζει το σωστό huffman tree.

Συνεπώς το πρόβλημά σου μάλλον είναι η κωδικοποίηση, δηλαδή τα bit με τα οποία κωδικοποιείται κάθε χαρακτήρας, που μάλλον το υλοποιείς στη συνάρτηση

Κώδικας: Επιλογή όλων

void traverse(treenode *r,int level,char code_so_far[],char *codes[])
Να σου πω την αλήθεια δεν κατάλαβα τι ακριβώς κάνεις εδώ . Υποθέτω προσπαθείς να κάνεις traverse το δέντρο για κάθε root-to-leaf διαδρομή και να σχηματίσεις στην πορεία, ανάλογα με τη διαδρομή (ένα μηδενικό για κάθε left, ένας άσσος για κάθε right), των κώδικα κάθε χαρακτήρα, σωστά;

Δώσε μου κάποιες επιπλέον πληροφορίες μήπως μπορέσω να σε βοηθήσω.

ΥΓ.
Όταν δεσμεύεις μνήμη με malloc και calloc, να θυμάσαι κάθε φορά να την ελευθερώνεις. Στον κώδικά σου αυτό δε γίνεται πουθενά με αποτέλεσμα να έχεις memory leak.
The living still give me the creeps

Απάντηση

Επιστροφή στο “C, C++”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 0 επισκέπτες