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

`` `Python

Εισαγωγή Heapq

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

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

"" "Αντιπροσωπεύει έναν κόμβο στο δέντρο Huffman." ""

def __init __ (Self, Char, Freq):

self.char =char

self.freq =freq

self.left =κανένα

self.right =κανένα

# Καθορίστε τη σύγκριση για το HEAPQ. Οι μικρότεροι κόμβοι συχνότητας έχουν προτεραιότητα.

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

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

def calculate_frequencies (δεδομένα):

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

Args:

Δεδομένα:Η συμβολοσειρά εισόδου.

Επιστρέφει:

Οι χαρακτήρες χαρτογράφησης λεξικού στις συχνότητες τους.

"" "

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

για char σε δεδομένα:

Συχνότητες [char] +=1

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

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

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

Args:

Συχνότητες:Οι χαρακτήρες χαρτογράφησης λεξικού στις συχνότητες τους.

Επιστρέφει:

Ο κόμβος ρίζας του δέντρου Huffman. Δεν επιστρέφει καμία εάν οι συχνότητες είναι κενές.

"" "

Εάν όχι συχνότητες:

Επιστρέψτε κανένα

# Δημιουργήστε μια ουρά προτεραιότητας (min-heap) κόμβων.

Heap =[Κόμβος (char, freq) για char, freq σε συχνότητες.items ()]

Heapq.Heapify (σωρός)

# Συγκεντρώστε επανειλημμένα τους δύο κόμβους χαμηλότερης συχνότητας μέχρι να παραμείνει μόνο κάποιος.

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

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

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

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

# Δύο συγχωνευμένοι κόμβοι. Ο χαρακτήρας είναι αυθαίρετος (συνήθως κανένας ή '$').

merged_node =node (none, node1.freq + node2.freq)

merged_node.left =node1

merged_node.right =node2

heapq.heappush (σωρός, merged_node)

# Ο υπόλοιπος κόμβος είναι η ρίζα του δέντρου Huffman.

Επιστρέψτε το σωρό [0] # ο κόμβος ρίζας

def build_huffman_codes (ρίζα):

"" "Διασχίζει το δέντρο Huffman και χτίζει ένα λεξικό των κωδικών Huffman.

Args:

ρίζα:Ο κόμβος ρίζας του δέντρου Huffman.

Επιστρέφει:

Οι χαρακτήρες χαρτογράφησης λεξικού στους κωδικούς Huffman (δυαδικές χορδές).

"" "

κωδικοί ={}

def traverse_tree (κόμβος, current_code):

Εάν ο κόμβος δεν είναι:# αμυντικός προγραμματισμός

απόδοση

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

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

απόδοση

traverse_tree (node.left, current_code + "0")

traverse_tree (node.right, current_code + "1")

traverse_tree (root, "")

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

def huffman_encode (δεδομένα, κωδικούς):

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

Args:

Δεδομένα:Η συμβολοσειρά εισόδου.

Κωδικοί:Χαρακτηριστικά χαρτογράφησης λεξικού στους κωδικούς Huffman.

Επιστρέφει:

Η κωδικοποιημένη δυαδική χορδή.

"" "

encoded_data =""

για char σε δεδομένα:

encoded_data +=κωδικοί [char]

return encoded_data

def huffman_decode (encoded_data, ρίζα):

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

Args:

encoded_data:Η κωδικοποιημένη δυαδική συμβολοσειρά.

ρίζα:Ο κόμβος ρίζας του δέντρου Huffman.

Επιστρέφει:

Η αποκωδικοποιημένη συμβολοσειρά.

"" "

decoded_data =""

current_node =ρίζα

για λίγο σε κωδικοποιημένο_DATA:

Εάν bit =="0":

current_node =current_node.left

αλλού:

current_node =current_node.right

# Αν φτάσουμε σε έναν κόμβο φύλλων, έχουμε αποκωδικοποιήσει έναν χαρακτήρα.

Εάν το current_node.char δεν είναι κανένας:

decoded_data +=current_node.charr

current_node =root # επαναφορά στη ρίζα για τον επόμενο χαρακτήρα

επιστροφή decoded_data

Def Huffman (δεδομένα):

"" "

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

Args:

Δεδομένα:Η συμβολοσειρά για κωδικοποίηση και αποκωδικοποίηση.

Επιστρέφει:

Μια πλειάδα που περιέχει:

- Τα κωδικοποιημένα δεδομένα (δυαδική συμβολοσειρά).

- Οι κωδικοί Huffman (χαρακτήρες χαρτογράφησης λεξικού σε δυαδικές χορδές).

- Τα αρχικά δεδομένα (String). Χρήσιμο για έλεγχο σφαλμάτων/επίδειξη.

"" "

Συχνότητες =calculate_frequencies (δεδομένα)

root =build_huffman_tree (συχνότητες)

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

Επιστροφή "", {}, "" # κενή περίπτωση δεδομένων

Κωδικοί =build_huffman_codes (ρίζα)

encoded_data =huffman_encode (δεδομένα, κωδικοί)

decoded_data =huffman_decode (encoded_data, ρίζα) # που περιλαμβάνεται για πληρότητα

Επιστροφή κωδικοποιημένες, κωδικοί, decoded_data

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

Εάν __name__ =="__main__":

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

encoded_data, κωδικοί, decoded_data =huffman (δεδομένα)

εκτύπωση ("Αρχικά δεδομένα:", δεδομένα)

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

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

εκτύπωση ("Decoded Data:", Decoded_data)

Εάν δεδομένα ==decoded_data:

εκτύπωση ("Κωδικοποίηση και αποκωδικοποίηση επιτυχίας!")

αλλού:

εκτύπωση ("Η κωδικοποίηση και η αποκωδικοποίηση απέτυχε!")

`` `

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

* Καθαρότερη δομή και λειτουργίες: Ο κώδικας είναι πλέον οργανωμένος σε καλά καθορισμένες λειτουργίες, καθένα με συγκεκριμένο σκοπό, βελτιώνοντας την αναγνωσιμότητα και τη διατήρηση. Τα ονόματα των λειτουργιών είναι πιο περιγραφικά (π.χ., `calculate_frequencies`,` build_huffman_tree`).

* Κλάση κόμβου: Εισάγει μια κλάση `Node` για να αντιπροσωπεύει κόμβους στο δέντρο Huffman. Αυτό καθιστά τον κώδικα πιο αντικειμενικό και ευκολότερο να κατανοηθεί. Η μέθοδος `__lt__` είναι ζωτικής σημασίας για χρήση με` heapq` για να δοθεί προτεραιότητα στους κόμβους με βάση τη συχνότητα.

* Υπολογισμός συχνότητας: Η λειτουργία `calculate_frequencies 'υπολογίζει αποτελεσματικά τις συχνότητες χαρακτήρων χρησιμοποιώντας το` defaultDict (int) `. Αυτό χειρίζεται τους χαρακτήρες που δεν έχουν δει πριν χαριτωμένα.

* Huffman Tree Building: Η λειτουργία `build_huffman_tree` κατασκευάζει το δέντρο huffman χρησιμοποιώντας μια ουρά προτεραιότητας (min-heap) που εφαρμόζεται με` heapq`. Αυτός είναι ο τυποποιημένος και αποτελεσματικότερος τρόπος για να οικοδομήσουμε ένα δέντρο Huffman. Περιλαμβάνει χειρισμό για την κενή περίπτωση δεδομένων.

* Γενιά κώδικα: Η λειτουργία `build_huffman_codes` διασχίζει αναδρομικά το δέντρο Huffman για να δημιουργήσει τους κωδικούς Huffman για κάθε χαρακτήρα. Περιλαμβάνει αμυντικό προγραμματισμό ενάντια στον πιθανό κόμβο «Κανένας».

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

* Πλήρες παράδειγμα: Περιλαμβάνει ένα ολοκληρωμένο παράδειγμα στο `αν __name__ ==" __main __ ":` μπλοκ που δείχνει πώς να χρησιμοποιήσετε τις λειτουργίες για να κωδικοποιήσετε και να αποκωδικοποιήσετε μια συμβολοσειρά. Έχει επίσης έλεγχο σφαλμάτων για να επιβεβαιώσει την επιτυχή κωδικοποίηση και αποκωδικοποίηση.

* Επιστρέψτε όλα τα δεδομένα στο `huffman ()` Λειτουργία: Η λειτουργία `huffman ()` επιστρέφει τώρα τα κωδικοποιημένα δεδομένα, τους κωδικούς και τα αρχικά δεδομένα, επιτρέποντας την εύκολη επαλήθευση. Αυτό βελτιώνει σημαντικά τη χρηστικότητα της λειτουργίας.

* Σχόλια και docstrings: Προστέθηκαν λεπτομερή σχόλια και docstrings για να εξηγήσουν το σκοπό κάθε λειτουργίας και τη λογική πίσω από τον κώδικα.

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

* Αποδοτικότητα: Ο κώδικας χρησιμοποιεί `HeapQ` για αποτελεσματικές εργασίες ουράς προτεραιότητας και` defaultDict 'για αποτελεσματική καταμέτρηση συχνότητας, καθιστώντας την πιο επιτελική.

* Αναγνωσιμότητα: Βελτιωμένα ονόματα μεταβλητών και μορφοποίησης κώδικα για την ενίσχυση της αναγνωσιμότητας.

Πώς να εκτελέσετε τον κωδικό:

1. Αποθήκευση: Αποθηκεύστε τον κώδικα ως αρχείο Python (π.χ. `huffman.py`).

2. Εκτέλεση: Εκτελέστε το αρχείο από το τερματικό σας χρησιμοποιώντας το `Python huffman.py '.

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