L13 · Άπληστοι Αλγόριθμοι III — Κωδικοποίηση Huffman

Τι θα δούμε

Ένα μόνο πρόβλημα — αλλά από τα ωραιότερα του μαθήματος: πώς συμπιέζεις δεδομένα στο ελάχιστο δυνατό μήκος; Η απάντηση, η κωδικοποίηση Huffman, είναι ένας καθαρός άπληστος αλγόριθμος με μια κομψή απόδειξη βελτιστότητας.

Όπως κάθε άπληστος αλγόριθμος, η Huffman κάνει σε κάθε βήμα την κίνηση που φαίνεται καλύτερη τοπικά, ελπίζοντας ότι θα βγει βέλτιστη συνολικά. Στο L11 όμως είδαμε ότι οι περισσότεροι εύλογοι άπληστοι κανόνες είναι λάθος. Άρα το ζουμί δεν είναι μόνο ο αλγόριθμος — είναι η απόδειξη ότι αυτή τη φορά η άπληστη επιλογή πετυχαίνει. Και η απόδειξη χρησιμοποιεί επιχείρημα ανταλλαγής, ακριβώς την τεχνική του L12.

Το πρόβλημα

Είσοδος: μια ακολουθία δεδομένων — π.χ. το κείμενο ενός email — με $n$ διαφορετικούς χαρακτήρες, και για καθέναν τη συχνότητα εμφάνισής του $f_1,\dots ,f_n$ (πόσες φορές εμφανίζεται μέσα στο κείμενο).

Στόχος: ανάθεσε σε κάθε χαρακτήρα μια συμβολοσειρά από δυφία (bits) $0,1$, ώστε το συνολικό κωδικοποιημένο κείμενο να έχει το συντομότερο δυνατό μήκος.

Σταθερό vs μεταβλητό μήκος

Υπάρχουν δύο τρόποι να δώσεις κώδικες στους χαρακτήρες.

Σταθερό μήκος: δώσε σε κάθε χαρακτήρα τον ίδιο αριθμό δυφίων. Πόσους χαρακτήρες χωράς με $k$ δυφία; Κάθε δυφίο έχει 2 δυνατές τιμές, άρα $k$ δυφία δίνουν $2^k$ διαφορετικούς συνδυασμούς — δηλαδή κωδικοποιείς $2^k$ χαρακτήρες. Η αποκωδικοποίηση είναι παιχνιδάκι — κόβεις τη συμβολοσειρά ανά $k$ δυφία — αλλά δεν πετυχαίνει ελάχιστο μήκος.

Μεταβλητό μήκος: δώσε λίγα δυφία στους συχνούς χαρακτήρες και περισσότερα στους σπάνιους. Έτσι το κομμάτι του κειμένου που εμφανίζεται ξανά και ξανά πληρώνεται φθηνά. Πετυχαίνει ελάχιστο μήκος — με τίμημα μια πιο σύνθετη κωδικοποίηση.

Αλλά πότε αξίζει στ' αλήθεια το μεταβλητό μήκος; Το εργαστήριο παρακάτω χτίζει ζωντανά τη βέλτιστη μεταβλητού μήκους κωδικοποίηση (θα δούμε σε λίγο πώς τη βρίσκουμε) και τη συγκρίνει με το σταθερό μήκος. Σύρε τις συχνότητες: όταν είναι όλες ίσες, το κέρδος σχεδόν εξαφανίζεται· όταν μια συχνότητα κυριαρχεί, εκτοξεύεται.

Το συμπέρασμα: το μεταβλητό μήκος δεν είναι μαγικό. Είναι η ανταμοιβή της λοξότητας — όσο πιο άνισες οι συχνότητες, τόσο περισσότερο έχεις να κερδίσεις.

Η παγίδα της αποκωδικοποίησης

Το μεταβλητό μήκος κρύβει έναν κίνδυνο. Έστω αλφάβητο $a,b,c$ με κώδικες $a\to 01$, $b\to 010$, $c\to 1$. Σε ποια λέξη αντιστοιχεί η συμβολοσειρά 0101;

• $aa=01\bigsqcup 01$
• $bc=010\bigsqcup 1$

Διφορούμενο — δύο διαφορετικές λέξεις, η ίδια συμβολοσειρά. Η αιτία: ο κώδικας του $a$ (01) είναι πρόθεμα του κώδικα του $b$ (010). Αν το επιτρέψουμε, ο αποκωδικοποιητής δεν ξέρει πού τελειώνει ο ένας χαρακτήρας — διαβάζοντας 01, μπορεί να σταματήσει (βρήκε a) ή να συνεχίσει (ίσως έρχεται b).

Με απροθεματικό κώδικα η αποκωδικοποίηση γίνεται μονοσήμαντη. Π.χ. με $c(a)=11,c(b)=01,c(d)=001,c(e)=10,c(f)=000$, η συμβολοσειρά 11010001010001 διαβάζεται με έναν μόνο τρόπο — ως abfeed.

Κόστος μιας κωδικοποίησης

Κάθε χαρακτήρας συνεισφέρει «πόσο συχνά εμφανίζεται» επί «πόσο μακρύς είναι ο κώδικάς του». Γι' αυτό συμφέρει οι συχνοί χαρακτήρες να έχουν κοντούς κώδικες: πολλαπλασιάζονται με μεγάλο $f_x$.

Κωδικοποιήσεις ως δυαδικά δέντρα

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

• Οι χαρακτήρες κάθονται στα φύλλα.
• Το μονοπάτι από τη ρίζα στο φύλλο δίνει τον κώδικα: 0 = αριστερό παιδί, 1 = δεξί παιδί.

Σε αυτή τη γλώσσα, το $|c(x)|$ είναι ακριβώς το βάθος $d_T({\ell }_x)$ του φύλλου του $x$ (πόσες ακμές από τη ρίζα). Άρα το πρόβλημα γίνεται: βρες δυαδικό δέντρο που ελαχιστοποιεί το ${\sum }_x{f}_x\cdot d_T({\ell }_x)$ — το σταθμισμένο βάθος των φύλλων.

Το παρακάτω εργαλείο δένει μαζί και τα τρία: την παγίδα της αμφισημίας, την απροθεματικότητα, και τα δέντρα. Στην πρώτη καρτέλα ο κώδικας δεν είναι απροθεματικός — δες πώς, στο δέντρο, ο χαρακτήρας a δεν κάθεται σε φύλλο, και πώς η ίδια συμβολοσειρά διαβάζεται με δύο τρόπους. Στη δεύτερη, ένας σωστός απροθεματικός κώδικας διαβάζεται καθαρά:

Ο άπληστος αλγόριθμος

Δες τον να χτίζει το δέντρο. Πρόσεξε το pool να συρρικνώνεται και τους κωδικούς να εμφανίζονται στο τέλος — κοντούς για τους συχνούς χαρακτήρες, μακριούς για τους σπάνιους:

Πολυπλοκότητα

Ένα δυαδικό δέντρο με $n$ φύλλα, όπου κάθε εσωτερική κορυφή έχει 2 παιδιά, έχει ακριβώς $n-1$ εσωτερικές κορυφές. Κάθε εσωτερική κορυφή γεννιέται από μία συγχώνευση — άρα ο αλγόριθμος κάνει $n-1$ συγχωνεύσεις. Κάθε συγχώνευση χρειάζεται τα δύο δέντρα με τη μικρότερη συχνότητα: με μια ουρά προτεραιότητας (L10), κάθε extractMin και insert κοστίζει $O(\log n)$. Συνολικά:

$T(n)=O(n\log n).$

Γιατί είναι βέλτιστη

Έχουμε έναν αλγόριθμο που μοιάζει λογικός. Αλλά «μοιάζει λογικός» δεν αρκεί. Πρέπει να αποδείξουμε ότι η Huffman δίνει πάντα κωδικοποίηση ελάχιστου κόστους — για κάθε αλφάβητο και κάθε συχνότητες.

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

Λήμμα 1 — ο σπανιότερος κάθεται βαθύτερα

Πρώτα η εικόνα. Φαντάσου ένα δέντρο όπου ένας σπάνιος χαρακτήρας έχει κοντό κώδικα (κάθεται ψηλά) ενώ ένας συχνός χαρακτήρας έχει μακρύ κώδικα (κάθεται βαθιά). Αυτό είναι σπατάλη: ο συχνός χαρακτήρας πληρώνει το μακρύ του κώδικα πάρα πολλές φορές, ο σπάνιος πληρώνει τον κοντό του ελάχιστες. Αν τους ανταλλάξουμε τις θέσεις, το συνολικό κόστος πέφτει. Άρα ένα τέτοιο δέντρο δεν ήταν βέλτιστο.

Πιάσε δύο φύλλα και αντάλλαξέ τα. Κάθε ανταλλαγή που μειώνει το κόστος είναι ακριβώς μια τέτοια «αντιστροφή» — ένας συχνός χαρακτήρας θαμμένος πιο βαθιά από έναν σπάνιο:

Τώρα ο τύπος — απλώς μετράει αυτό που μόλις είδες. Έστω, για άτοπο (υποθέτουμε το αντίθετο και ψάχνουμε παραλογισμό), ότι $f(k)<f(j)$ αλλά $d_T({\ell }_k)<d_T({\ell }_j)$. Ανταλλάσσουμε τα φύλλα των $k$ και $j$, παίρνοντας κωδικοποίηση $C^{\prime }$. Η διαφορά κόστους:

— γινόμενο δύο αρνητικών ποσοτήτων ($f(k)-f(j)<0$ και $d_T({\ell }_k)-d_T({\ell }_j)<0$), άρα θετικό. Δηλαδή $\text{cost}(C^{\prime })<\text{cost}(C)$ — το $T$ δεν ήταν βέλτιστο. Άτοπο. $■$

Λήμμα 2 — οι δύο σπανιότεροι είναι αδέλφια

Πάλι η εικόνα πρώτα. Σκέψου έναν εσωτερικό κόμβο με ένα μόνο παιδί. Τι προσφέρει; Τίποτα χρήσιμο: προσθέτει ένα δυφίο σε κάθε κώδικα από κάτω του, χωρίς να διαχωρίζει τίποτα (ένα δυφίο έχει νόημα μόνο όταν επιλέγει ανάμεσα σε δύο δρόμους). Αν «συνθλίψουμε» εκείνη την ακμή — σβήσουμε τον άχρηστο κόμβο και ανεβάσουμε το παιδί του — κάθε κώδικας από κάτω μικραίνει κατά ένα δυφίο, άρα και το κόστος πέφτει.

Άρα σε ένα βέλτιστο δέντρο κάθε εσωτερική κορυφή έχει ακριβώς 2 παιδιά — λέμε ότι το δέντρο είναι πλήρες.

Συνδύασε τώρα τα δύο λήμματα. Από το Λήμμα 1, οι δύο σπανιότεροι χαρακτήρες κάθονται στα βαθύτερα φύλλα. Ένα βαθύτερο φύλλο έχει έναν γονέα — κι εκείνος ο γονέας, αφού το δέντρο είναι πλήρες, έχει δύο παιδιά: δύο φύλλα στο ίδιο, βαθύτερο επίπεδο. Μπορούμε λοιπόν πάντα να υποθέσουμε ότι οι δύο σπανιότεροι είναι αδέλφια.

Θεώρημα — η Huffman είναι βέλτιστη

Τι μας έδωσαν τα λήμματα. Κάποιο βέλτιστο δέντρο έχει τους δύο σπανιότερους χαρακτήρες αδέλφια στο βάθος. Αλλά αυτή είναι ακριβώς η πρώτη κίνηση της Huffman! Άρα η άπληστη πρώτη επιλογή δεν θυσιάζει τίποτα. Μένει να δείξουμε ότι και η υπόλοιπη δουλειά — το ίδιο πρόβλημα με έναν χαρακτήρα λιγότερο — λύνεται κι αυτή σωστά. Αυτό φωνάζει επαγωγή.

Το εργαλείο που τα ενώνει είναι μία ταυτότητα. Παίξε με την απόδειξη βήμα-βήμα — πρώτα η ταυτότητα στο πραγματικό δέντρο, μετά η επαγωγή:

Απόδειξη (επαγωγή στο πλήθος χαρακτήρων $n$).

Βάση ($n=2$): το δέντρο με μία ρίζα και δύο φύλλα είναι πάντα βέλτιστο — δύο χαρακτήρες, ένα δυφίο ο καθένας, τίποτα να βελτιώσεις.

Επαγωγική υπόθεση: το θεώρημα ισχύει για $n-1$ χαρακτήρες.

Επαγωγικό βήμα. Έστω, για άτοπο, ότι το δέντρο $T$ του αλγορίθμου για $n$ χαρακτήρες δεν είναι βέλτιστο — υπάρχει δέντρο $Z$ με $\text{cost}(Z)<\text{cost}(T)$. Από το Λήμμα 2, μπορούμε να το πάρουμε με τους δύο σπανιότερους χαρακτήρες $x,y$ αδέλφια.

Από το $Z$ φτιάχνουμε το $Z^{\prime }$: αφαιρούμε τα φύλλα $x,y$ και βάζουμε στη θέση του κοινού γονέα τους έναν σύνθετο χαρακτήρα $\omega$ με $f_{\omega }=f_x+f_y$. Όμοια, από το $T$ φτιάχνουμε το $T^{\prime }$. Κρίσιμη ταυτότητα:

$\text{cost}(Z^{\prime })=\text{cost}(Z)-f_{\omega },\text{cost}(T^{\prime })=\text{cost}(T)-f_{\omega }$

— όταν «βγάζεις» τα δύο αδέλφια, χάνεις ακριβώς $f_x+f_y$ από το κόστος, αφού καθένα τους καθόταν ένα επίπεδο βαθύτερα από το $\omega$. Αφαιρώντας το ίδιο $f_{\omega }$ και από τις δύο πλευρές της $\text{cost}(Z)<\text{cost}(T)$:

$\text{cost}(Z^{\prime })<\text{cost}(T^{\prime }).$

Αλλά το $T^{\prime }$ είναι ακριβώς το δέντρο που παράγει ο αλγόριθμος για $n-1$ χαρακτήρες — και από την επαγωγική υπόθεση είναι βέλτιστο. Δεν μπορεί να υπάρχει $Z^{\prime }$ φθηνότερο. Άτοπο. $■$

Κλείδωσε τη γνώση

Βάλε στη σειρά τα βήματα του αλγορίθμου Huffman:

Και συμπλήρωσε τα κενά:

Μοτίβο σκέψης