Πέρα από Huffman: Πώς τα Asymmetric Numeral Systems φτάνουν την τέλεια συμπίεση

Σε web υπηρεσίες με εκατομμύρια requests, κάθε byte μετράει. Κόστη CDN, αποθήκευση βάσεων και χρόνοι API εξαρτώνται από την αποδοτική συμπίεση. Οι περισσότεροι προγραμματιστές πιάνουν gzip ή brotli χωρίς δεύτερη σκέψη. Και αν υπάρχει καλύτερος τρόπος που αγγίζει τα θεωρητικά όρια της θεωρίας πληροφορίας;

Το πρόβλημα της θεωρίας πληροφορίας

Όλα ξεκινούν από την ανισότητα των συμβόλων. Σε κάθε dataset, κάποια εμφανίζονται συχνότερα. Το θεώρημα του Shannon λέει ότι κάθε σύμβολο κοστίζει bits ανάλογα με τη συχνότητά του.

Παράδειγμα:

• Σύμβολο 50% → 1 bit
• Σύμβολο 25% → 2 bits
• Σύμβολο 37.5% → περίπου 1.415 bits

Το Huffman εδώ αποτυγχάνει. Δίνει σταθερού μήκους κώδικες. Δεν χωράει 1.415 bits, στρογγυλεύει σε 2 και χάνεις απόδοση.

Arithmetic Coding: Η μεγάλη ανατροπή

Ξεχνάμε τα διακριτά bit patterns. Το arithmetic coding κωδικοποιεί ολόκληρη την ακολουθία ως πράξεις σε έναν ακέραιο. Είναι μαθηματική μετατροπή, πυκνή και αναστρέψιμη.

Εδώ μπαίνουν τα rANS (range Asymmetric Numeral Systems). Η πιο κομψή υλοποίηση, παντού σε σύγχρονες βιβλιοθήκες και streaming.

Πώς δουλεύουν τα rANS

Η ιδέα είναι απλή: κρατάς έναν ακέραιο "κατάσταση" (x). Κάθε σύμβολο τον μετατρέπει με μαθηματική πράξη. Πρέπει να είναι απόλυτα αναστρέψιμη – ο decoder παίρνει σύμβολο και προηγούμενη κατάσταση.

Ο τύπος:

x′ = ⌊x/f_s⌋ × M + c_s + (x mod f_s)

Όπου:

• f_s: συχνότητα συμβόλου s
• c_s: αθροιστική συχνότητα πριν από s
• M: συνολική συχνότητα

Παράδειγμα με τρία σύμβολα:

| Σύμβολο | Συχνότητα | Αθροιστική | |---------|-----------|------------| | A | 4 | 0 | | B | 3 | 4 | | C | 1 | 7 |

M = 8. Αρχική x = 13. Κωδικοποιούμε "ABC".

A (f=4, c=0):

x′ = ⌊13/4⌋ × 8 + 0 + (13 mod 4) = 3×8 + 0 + 1 = 25

B (f=3, c=4):

x′ = ⌊25/3⌋ × 8 + 4 + (25 mod 3) = 8×8 + 4 + 1 = 69

Το τελικό 69 κρύβει όλη την "ABC". Ο decoder την ξετυλίγει αντίστροφα. Χωρίς απώλειες.

Γιατί μετράει σε σύγχρονα συστήματα

Καλύτερα ποσοστά: Πλησιάζει Shannon, 5-15% καλύτερα από Huffman.

Streaming: Δουλεύει με τρέχουσα κατάσταση, ιδανικό για real-time.

CPU φιλικό: Γρήγορες πράξεις ακεραίων, χωρίς εξειδικευμένες εντολές.

Σε χρήση: Στο Zstandard του Facebook, σε formats της Apple. Βάση performance-critical apps.

Το θέμα της αναστρεψιμότητας (λυμένο)

Πώς ξέρεις πότε τελείωσε; Κρατάς κατάσταση σε εύρος. Αν φουσκώσει, βγάζεις bits. Στο decoding, παίρνεις bits για sync. Αυτό το self-sync το κάνει δημοφιλές.

Τι σημαίνει για developers

Σε NameOcean apps, η συμπίεση API, backups ή Vibe Hosting εξοικονομεί performance και χρήμα. Huffman vs rANS = μετρήσιμα κέρδη.

Έτοιμες υλοποιήσεις: zstandard σε Python, JS options. Κώδικας δοκιμασμένος, εφαρμόσιμος τώρα.

Το ευρύτερο πλαίσιο

Τα rANS δείχνουν: οι καινοτομίες έρχονται από έξυπνη υλοποίηση παλιών ιδεών (arithmetic coding) με low overhead. Shannon έθεσε όρια το '48. Χρειάστηκαν δεκαετίες για πρακτικές λύσεις. rANS είναι τέτοια – θεωρία + engineering.

Την επόμενη φορά που η συμπίεσή σου τρέχει γρήγορα, ευχαρίστησε τα asymmetric numeral systems πίσω από την κουρτίνα.