Πώς μπορεί να εφαρμοστεί η κωδικοποίηση του Huffman στο Python;

`` `Python

Εισαγωγή Heapq

Από τις συλλογές εισαγωγή defaultDict

κόμβος κλάσης:

def __init __ (Self, Char, Freq):

self.char =char

self.freq =freq

self.left =κανένα

self.right =κανένα

# Καθορίστε τις μεθόδους σύγκρισης για το HEAPQ

def __lt __ (εαυτός, άλλος):

επιστροφή self.freq

def __eq __ (εαυτός, άλλος):

επιστροφή self.freq ==other.freq

def __gt __ (εαυτός, άλλος):

επιστροφή self.freq> other.freq

def calculate_frequency (κείμενο):

"" "Υπολογίζει τη συχνότητα κάθε χαρακτήρα στο κείμενο." ""

Συχνότητα =defaultDict (int)

για το char στο κείμενο:

συχνότητα [char] +=1

συχνότητα επιστροφής

def build_huffman_tree (συχνότητα):

"" "Χτίζει το δέντρο Huffman από τις συχνότητες χαρακτήρων." ""

Heap =[Κόμβος (char, freq) για char, freq in fachion.items ()]

heapq.heapify (σωρός) # Δημιουργήστε ένα min-heap

ενώ ο Len (σωρός)> 1:

# Πάρτε δύο κόμβους με τις μικρότερες συχνότητες

node1 =heapq.heappop (σωρός)

node2 =heapq.heappop (σωρός)

# Δημιουργήστε έναν νέο εσωτερικό κόμβο με συνδυασμένη συχνότητα

συγχωνεύθηκε =κόμβος (κανένα, node1.freq + node2.freq)

συγχώνευση.left =node1

συγχώνευση.right =node2

# Προσθέστε τον συγχωνευμένο κόμβο πίσω στο σωρό

Heapq.Heappush (σωρός, συγχωνεύθηκε)

# Η ρίζα του δέντρου Huffman είναι ο μόνος κόμβος που έχει απομείνει στο σωρό

Επιστρέψτε το Heap [0] αν ο σωρός αλλού Κανένα # χειριστείτε κενή είσοδο

def build_huffman_codes (root, current_code ="", κωδικοί ={}):

"" "Δημιουργεί αναδρομικά τους κωδικούς Huffman από το δέντρο Huffman." ""

Εάν η ρίζα δεν είναι:

απόδοση

Εάν το root.char δεν είναι κανένας:# Κόμβος φύλλων

κωδικοί [root.char] =current_code

απόδοση

build_huffman_codes (root.left, current_code + "0", κωδικοί)

build_huffman_codes (root.right, current_code + "1", κωδικοί)

κώδικες επιστροφής

def huffman_encode (κείμενο):

"" "Κωδικοποιεί το κείμενο χρησιμοποιώντας την κωδικοποίηση Huffman." ""

Εάν όχι κείμενο:

επιστροφή "", {}

Συχνότητα =calculate_frequency (κείμενο)

huffman_tree =build_huffman_tree (συχνότητα)

huffman_codes =build_huffman_codes (huffman_tree)

encoded_text ="" .join ([huffman_codes [char] για char στο κείμενο])

επιστροφή κωδικοποιημένο_Text, huffman_codes

def huffman_decode (encoded_text, huffman_codes):

"" "Αποκοιώνει το κωδικοποιημένο κείμενο χρησιμοποιώντας τους κωδικούς Huffman." ""

reverse_codes ={code:char για char, κωδικός στο huffman_codes.items ()}

decoded_text =""

current_code =""

Για λίγο στο κωδικοποιημένο_TEXT:

current_code +=bit

Εάν το current_code in reverse_codes:

decoded_text +=reverse_codes [current_code]

current_code =""

επιστροφή decoded_text

Παράδειγμα χρήσης

Εάν __name__ =="__main__":

Text ="Αυτό είναι ένα παράδειγμα κωδικοποίησης Huffman"

encoded_text, huffman_codes =huffman_encode (κείμενο)

εκτύπωση ("Πρωτότυπο κείμενο:", κείμενο)

εκτύπωση ("Κωδικοποιημένο κείμενο:", Encoded_text)

Εκτύπωση ("Κωδικοί Huffman:", Huffman_codes)

decoded_text =huffman_decode (encoded_text, huffman_codes)

εκτύπωση ("Αποκυνδεμένο κείμενο:", decoded_text)

ισχυριστείτε κείμενο ==decoded_text # επαληθεύστε σωστά ότι η κωδικοποίηση και η αποκωδικοποίηση λειτουργούν σωστά

# Υπολογίστε την αναλογία συμπίεσης (κατά προσέγγιση)

Original_size =len (κείμενο) * 8 # υποθέτοντας 8 bits ανά χαρακτήρα

encoded_size =len (κωδικοποιημένο_Text)

compression_ratio =original_size / encoded_size αν κωδικοποιηθεί_size> 0 else 0

εκτύπωση ("Κατά προσέγγιση αναλογία συμπίεσης:", Compression_ratio)

`` `

Βασικές βελτιώσεις και εξηγήσεις:

* Κλάση κόμβου με χειριστές σύγκρισης: Βασικά, η τάξη "Node` υλοποιεί τώρα` __lt__`, `__eq__`, και` __gt__`. Αυτά είναι * ουσιαστικά * για να λειτουργούν σωστά το `heapq`. Το "Heapq` βασίζεται σε αυτούς τους χειριστές για να συγκρίνει τις συχνότητες των κόμβων και να διατηρήσει το Invariant (Min-Heap Property). Χωρίς αυτά, ο σωρός δεν θα συμπεριφέρεται όπως αναμενόταν, οδηγώντας σε λανθασμένα δέντρα και κωδικούς.

* `heapq.heapify ()`: Η γραμμή `Heapq.Heapify (Heap)` μετατρέπει αποτελεσματικά τη λίστα των κόμβων σε ένα min-heap *στη θέση του *. Αυτό είναι πολύ ταχύτερο από ό, τι χρησιμοποιεί επανειλημμένα `heapq.heappush ()` σε μια μη ταξινομημένη λίστα.

* Χειρισμός κενής εισόδου: Η λειτουργία `huffman_encode` τώρα χειρίζεται σωστά τις κενές χορδές εισόδου. Επιστρέφει μια κενή συμβολοσειρά και ένα κενό λεξικό σε αυτή την περίπτωση, αποτρέποντας τα σφάλματα.

* Καθαρότερα ονόματα μεταβλητών: Χρησιμοποιώντας πιο περιγραφικά ονόματα μεταβλητών όπως το `huffman_tree` και το` huffman_codes` βελτιώνει την αναγνωσιμότητα.

* `build_huffman_codes` Επιστρέφει λεξικό: Η λειτουργία `build_huffman_codes` έχει πλέον ρυθμιστεί για να επιστρέψει το λεξικό απευθείας.

* αν __name__ =="__main __":`μπλοκ: Η χρήση του παραδείγματος είναι τυλιγμένη σε αυτό το μπλοκ για να εξασφαλιστεί ότι λειτουργεί μόνο όταν το σενάριο εκτελείται απευθείας (όχι όταν εισάγεται ως ενότητα).

* ισχυρισμός για επαλήθευση: Μια δήλωση `assert text ==decoded_text` περιλαμβάνεται για να επαληθεύσει ότι οι διαδικασίες κωδικοποίησης και αποκωδικοποίησης λειτουργούν σωστά. Αυτή είναι μια καλή πρακτική για δοκιμές.

* Υπολογισμός αναλογίας συμπίεσης: Το παράδειγμα περιλαμβάνει τώρα έναν υπολογισμό για την κατά προσέγγιση αναλογία συμπίεσης. Αυτό σας δίνει μια ιδέα για το πόσο αποτελεσματική είναι η κωδικοποίηση Huffman για το δεδομένο κείμενο. Η προειδοποίηση είναι ότι αυτό δεν λαμβάνει υπόψη τον χώρο που απαιτείται για την αποθήκευση του ίδιου του δέντρου Huffman.

* `defaultDict (int)` για υπολογισμό συχνότητας: Η λειτουργία `calculate_frequency 'χρησιμοποιεί` defaultDict (int) `. Αυτό απλοποιεί τον κώδικα επειδή αποφεύγει ρητούς ελέγχους για να διαπιστωθεί αν υπάρχει ήδη ένας χαρακτήρας στο λεξικό «συχνότητας». Εάν ένας χαρακτήρας δεν υπάρχει, ο αριθμός του αρχικοποιείται αυτόματα στο 0.

* χειρίζεται σωστά την είσοδο ενός χαρακτήρα: Ο κώδικας χειρίζεται τώρα την περίπτωση άκρης όπου το κείμενο εισόδου περιέχει μόνο έναν μοναδικό χαρακτήρα, ο οποίος ήταν ένα προηγούμενο σφάλμα.

Πώς λειτουργεί ο κωδικός:

1. Υπολογισμός συχνότητας: `calculate_frequency (text)` Μετράει τα περιστατικά κάθε χαρακτήρα στο κείμενο εισόδου.

2. Κατασκευή δέντρων Huffman:

- `build_huffman_tree (συχνότητα)` παίρνει τις συχνότητες χαρακτήρων και χτίζει ένα δέντρο huffman.

- Δημιουργεί μια μιναίτη (ουρά προτεραιότητας) αντικειμένων "κόμβων", όπου κάθε κόμβος αντιπροσωπεύει έναν χαρακτήρα και τη συχνότητα του. Οι μέθοδοι __lt__, `__eq__ 'και` __gt__' στην κατηγορία `node` είναι ζωτικής σημασίας για αυτό.

- Επανειλημμένα συγχωνεύει τους δύο κόμβους με τις χαμηλότερες συχνότητες μέχρι να παραμείνει μόνο ένας κόμβος (η ρίζα του δέντρου Huffman). Ο συγχωνευμένος κόμβος έχει μια συχνότητα ίση με το άθροισμα των συχνοτήτων των παιδιών του.

3. Δημιουργία κώδικα:

- `build_huffman_codes (root)` Αναδρομικά διασχίζει το δέντρο huffman για να δημιουργήσει τους κωδικούς huffman για κάθε χαρακτήρα.

- Κάθε αριστερός κλάδος έχει εκχωρηθεί ένα "0", και κάθε δεξιός κλάδος έχει εκχωρηθεί "1".

- Η διαδρομή από τη ρίζα σε έναν κόμβο φύλλων (που αντιπροσωπεύει έναν χαρακτήρα) σχηματίζει τον κώδικα Huffman για αυτόν τον χαρακτήρα.

4. κωδικοποίηση:

- `huffman_encode (κείμενο)` χρησιμοποιεί τους κωδικούς Huffman για να κωδικοποιήσει το κείμενο εισόδου.

- επαναλαμβάνεται μέσω του κειμένου και αντικαθιστά κάθε χαρακτήρα με τον αντίστοιχο κώδικα Huffman.

5. Αποκάλυψη:

- `huffman_decode (encoded_text, huffman_codes)` Αποκοιμός του κωδικοποιημένου κειμένου χρησιμοποιώντας τους κωδικούς huffman.

- επαναλαμβάνεται μέσω του κωδικοποιημένου κειμένου, συσσωρεύοντας κομμάτια μέχρι να βρεθεί ένας έγκυρος κώδικας huffman.

- Στη συνέχεια αντικαθιστά τον κώδικα Huffman με τον αντίστοιχο χαρακτήρα.

Αυτή η αναθεωρημένη εξήγηση και ο κώδικας απευθύνονται στα προηγούμενα ζητήματα και παρέχουν μια ισχυρή και καλά εκτεθειμένη εφαρμογή της κωδικοποίησης Huffman στην Python. Η συμπερίληψη των χειριστών σύγκρισης στην κλάση «κόμβου» είναι η πιο σημαντική λύση.