Κωδικοποίηση / αποκωδικοποίηση Base91

Το Base91 είναι τρόπος γραφής αυθαίρετων byte μόνο με εκτυπώσιμους χαρακτήρες ASCII, το ίδιο έργο που κάνει και το Base64, αλλά χωρά περισσότερα bit σε κάθε χαρακτήρα. Αντί να κόβει την είσοδο σε ομάδες των 6 bit και να εκτυπώνει έναν χαρακτήρα ανά ομάδα, συλλέγει bit μέχρι να έχει τουλάχιστον 13 και στη συνέχεια εκτυπώνει δύο χαρακτήρες που μαζί ονομάζουν την τιμή αυτών των 13 (ή 14) bit.

Δύο χαρακτήρες από ένα αλφάβητο 91 μπορούν να ονομάσουν 91 × 91 = 8281 διαφορετικές τιμές, και 2¹³ = 8192, οπότε δύο χαρακτήρες έχουν πάντα χώρο για 13 bit — με 89 τιμές περισσότερες. Αυτό είναι όλο το κόλπο: 13 bit ανά 2 χαρακτήρες είναι 6,5 bit ανά χαρακτήρα, έναντι των 6 του Base64, και εξασφαλίζει επιβάρυνση περίπου 23% αντί για 33%.

Το ζεύγος χαρακτήρων μπορεί να ονομάσει 91 × 91 = 8281 τιμές, που είναι περισσότερες από 2¹³ = 8192 αλλά λιγότερες από 2¹⁴ = 16384. Άρα ένα ζεύγος χαρακτήρων μπορεί πάντα να μεταφέρει 13 bit, και μερικές φορές 14. Ο κωδικοποιητής δοκιμάζει πρώτα τα 13 bit: αν η τιμή των 13 bit είναι μεγαλύτερη από 88, την εκτυπώνει ως δύο χαρακτήρες· διαφορετικά παίρνει και ένα 14ο bit και εκτυπώνει αντ' αυτού την προκύπτουσα τιμή των 14 bit.

Το όριο στο 88 δεν είναι αυθαίρετο. Η μεγαλύτερη τιμή που μπορούν να ονομάσουν δύο χαρακτήρες είναι 90 + 91 × 90 = 8280, και το 8192 + 89 = 8281 βρίσκεται ήδη πέρα από αυτήν. Άρα καμία ομάδα 14 bit δεν μπορεί ποτέ να έχει χαμηλό παράθυρο 13 bit τουλάχιστον 89, πράγμα που σημαίνει ότι ο αποκωδικοποιητής μπορεί να ξεχωρίσει τις δύο περιπτώσεις κοιτάζοντας μόνο την ίδια την τιμή:

Τι βλέπει ο αποκωδικοποιητής	Bit που καταναλώθηκαν	Γιατί
value & 8191 είναι 89 έως 8191	13 bit	Τιμές από 89 και πάνω μπορούν να προέρχονται μόνο από τον κλάδο των 13 bit, επειδή μια ομάδα 14 bit με τόσο υψηλό χαμηλό παράθυρο 13 bit θα έπρεπε να είναι τουλάχιστον 8281 — κάτι που κανένα ζεύγος χαρακτήρων δεν μπορεί να ονομάσει.
value & 8191 είναι 0 έως 88	14 bit	Ο κωδικοποιητής καταφεύγει στα 14 bit μόνο όταν η ανάγνωση των 13 bit ήταν 88 ή μικρότερη, οπότε αυτός ο κλάδος είναι η εναλλακτική και τίποτε άλλο.

Ό,τι περισσεύει στο τέλος — από 1 έως 13 bit — εκτυπώνεται ως ένας χαρακτήρας, και ένας δεύτερος όταν το υπόλοιπο χρειάστηκε πραγματικά περισσότερα από 7 bit. Γι' αυτό το μήκος της κωδικοποίησης αυξάνεται σε βήματα των δύο χαρακτήρων και μερικές φορές τελειώνει σε περιττό πλήθος.

Το εκτυπώσιμο ASCII περιέχει 94 χαρακτήρες, από το ! (0x21) έως το ~ (0x7E). Το Base91 χρησιμοποιεί 91 από αυτούς, και οι τρεις που αφήνει έξω είναι η παύλα -, το απόστροφο ' και η ανάστροφη κάθετος \. Γράμματα, ψηφία και σχεδόν όλα τα σημεία στίξης βρίσκονται στο αλφάβητο ακριβώς μία φορά, με τη σειρά που φαίνεται στον πίνακα παραπάνω· οι χαρακτήρες 92 έως 94 του εκτυπώσιμου εύρους απλώς δεν είναι διευθύνσιμοι.

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

Κωδικοποίηση	Bit ανά χαρακτήρα	Μέγεθος σε σχέση με την είσοδο	Σημειώσεις
Base16 (hex)	4	200%	Δύο χαρακτήρες ανά byte, τετριμμένα αναγνώσιμο, χωρίς αλφάβητο για αναζήτηση.
Base32	5	160%	Χωρίς διάκριση πεζών και κεφαλαίων και ασφαλές για ανθρώπινη υπαγόρευση, το πιο σπάταλο της ομάδας.
Base58	~5,86	~137%	Επιλέχθηκε για διευθύνσεις και όχι για πυκνότητα: αποφεύγει όμοιους χαρακτήρες.
Base64	6	133%	Η προεπιλογή παντού: 4 χαρακτήρες ανά 3 byte, με τα 6 αχρησιμοποίητα bit του τελευταίου χαρακτήρα να πηγαίνουν χαμένα.
Ascii85 / Base85	6,4	125%	5 χαρακτήρες ανά 4 byte, χωρίς πίνακα αναζήτησης, αλλά διαιρεί με το 85 — βλ. τον μετατροπέα Ascii85.
Base91	~6,5	~123%	Το πυκνότερο από αυτά: 13 bit ανά 2 χαρακτήρες, με κάποιες ομάδες 14 bit εδώ κι εκεί.

Τα ποσοστά είναι ασυμπτωτικά κόστη κάθε κωδικοποίησης, στρογγυλοποιημένα· τα μετρημένα μήκη χαρακτήρων για μία πραγματική είσοδο 92 byte βρίσκονται στον πίνακα πιο πάνω σε αυτή τη σελίδα. Το Base91 βρίσκεται κοντά στο βέλτιστο που μπορεί να επιτύχει κάποια κωδικοποίηση με εκτυπώσιμο ASCII: τα 7 bit ανά χαρακτήρα θα σήμαιναν χρήση 128 διακριτών χαρακτήρων, κάτι που το εύρος των εκτυπώσιμων δεν μπορεί να παράσχει.

• Δεν είναι πρότυπο. Δεν υπάρχει RFC. Η υλοποίηση αναφοράς είναι το basE91 0.6.0 του Joachim Henke, που διανέμεται με άδεια BSD 3 clause· το "Base91" χρησιμοποιείται και για αλφάβητα που δεν είναι αυτό.
• Δεν είναι κρυπτογράφηση. Κάθε χαρακτήρας είναι απλή αναδιαμόρφωση των bit εισόδου, και όποιος έχει το αλφάβητο μπορεί να την αναιρέσει σε ένα πέρασμα.
• Δεν είναι ασφαλές για URL. Το αλφάβητο περιέχει τα #, %, &, /, ? και ", που αλλάζουν όλα νόημα σε URL, οπότε η έξοδος Base91 πρέπει να κωδικοποιηθεί με ποσοστά πριν μπει σε συμβολοσειρά ερωτήματος.
• Δεν είναι ασφαλές για HTML. Περιέχει επίσης τα <, >, & και ", οπότε μια συμβολοσειρά Base91 που τοποθετείται σε markup πρέπει να διαφευχθεί με τον μετατροπέα οντοτήτων HTML.
• Δεν είναι σταθερού μήκους. Το μήκος της εξόδου εξαρτάται από το μοτίβο των bit, όχι μόνο από το πλήθος των byte, οπότε δύο είσοδοι του ίδιου μεγέθους μπορεί να εκτυπωθούν με διαφορά ενός χαρακτήρα.

• Το αλφάβητο σε αυτή τη σελίδα είναι το αναφοράς. Αν άλλο εργαλείο παράγει διαφορετική έξοδο για την ίδια είσοδο, πρέπει πρώτα να συγκριθεί το αλφάβητό του πριν θεωρηθεί ότι κάποιο από τα δύο είναι χαλασμένο. Οι 91 χαρακτήρες πρέπει να εμφανίζονται με την ίδια σειρά.
• Ένας μόνο λάθος χαρακτήρας μπορεί να αλλάξει ολόκληρη την ουρά. Τα όρια των ομάδων καθορίζονται από τις τιμές που προηγήθηκαν, οπότε μια αλλαγή νωρίς στη συμβολοσειρά μετατοπίζει όλα όσα ακολουθούν, και η ουρά αποκωδικοποιείται μόνο με τα περισσεύοντα bit της τελευταίας ομάδας.
• Περιττό μήκος εξόδου είναι φυσιολογικό. Δεν σημαίνει ότι η συμβολοσειρά κόπηκε· η τελική ομάδα εκτυπώνει έναν χαρακτήρα όταν η περίσσειά της χωράει σε 7 bit ή λιγότερα.
• Ένα δημοσιευμένο παράδειγμα μπορεί να περιέχει αλλαγή γραμμής που δεν πληκτρολογήθηκε. Μια εντολή φλοιού που προσθέτει τον χαρακτήρα τέλους γραμμής είναι η συνήθης αιτία για την οποία μια γνωστή τιμή Base91 είναι ένας χαρακτήρας μεγαλύτερη από ό,τι παράγει το ίδιο κείμενο εδώ: echo "Hello, World!" δίνει στον κωδικοποιητή 14 byte και εκτυπώνει >OwJh>}AQ;r@@Y?FF, ενώ τα 13 byte του κειμένου μόνο εκτυπώνουν >OwJh>}AQ;r@@Y?F. Και τα δύο είναι σωστά, για διαφορετικά πλήθη byte, και το πλήθος κάτω από το πλαίσιο εξόδου δείχνει σε ποιο από τα δύο αντιστοιχεί η έξοδος.
• Η αποκωδικοποίηση δυαδικών δεδομένων ως κείμενο δεν θα λειτουργήσει. Αν τα αποκωδικοποιημένα byte δεν είναι έγκυρο UTF-8, δεν υπάρχει λογικό κείμενο για εμφάνιση· γι' αυτό υπάρχει η λειτουργία δεκαεξαδικής εξόδου.

“Γιατί αυτή η σελίδα εμφανίζει τιμή που διαφέρει κατά έναν χαρακτήρα από άλλο εργαλείο Base91;”

Σχεδόν πάντα διαφορετικό αλφάβητο. Η δεύτερη πιο συνηθισμένη αιτία είναι ένα εργαλείο που χρησιμοποιεί μόνο τον κλάδο των 13 bit και ποτέ την εναλλακτική των 14 bit· αυτή η παραλλαγή είναι μικρότερη σε κώδικα, αλλά παράγει διαφορετική έξοδο από τον αλγόριθμο αναφοράς που χρησιμοποιείται εδώ.

Υπάρχει επίσης μία ακριβής περίπτωση που λύνεται με καταμέτρηση byte, και εξηγεί το πιο ευρέως αναφερόμενο παράδειγμα: έναν τελικό χαρακτήρα αλλαγής γραμμής. Τα περισσότερα δημοσιευμένα διανύσματα παράχθηκαν με εντολή φλοιού, και ο φλοιός προσθέτει τον χαρακτήρα τέλους γραμμής που ολοκληρώνει τη γραμμή. Τα 13 byte του Hello, World! εκτυπώνουν εδώ 16 χαρακτήρες, ενώ τα 14 byte του Hello, World! ακολουθούμενα από αλλαγή γραμμής εκτυπώνουν τους 17 χαρακτήρες >OwJh>}AQ;r@@Y?FF. Επικόλληση οποιασδήποτε από τις δύο τιμές στην Αποκωδικοποίηση: η σελίδα αναφέρει το πλήθος byte, ώστε οι δύο αναγνώσεις να ξεχωρίζουν χωρίς να συζητιούνται. Το κουμπί Δείγμα φορτώνει εκείνη από τις δύο που αντιστοιχεί στον αναγνώστη που χρησιμοποιείται, και ακολουθεί τον διακόπτη Κωδικοποίηση / Αποκωδικοποίηση και τον επιλογέα Η είσοδος είναι / Η έξοδος ως: ο αναγνώστης κειμένου παίρνει την τιμή των 16 χαρακτήρων, ο δεκαεξαδικός αναγνώστης παίρνει την τιμή των 17 με το τελικό byte 0A ορατό, και ο κωδικοποιητής παίρνει το κείμενο προς κωδικοποίηση και όχι συμβολοσειρά Base91.

“Είναι το Base91 μικρότερο από το Base64;”

Ναι, κατά περίπου 8% του μεγέθους της κωδικοποίησης: 13 bit ανά 2 χαρακτήρες έναντι 6 bit ανά χαρακτήρα. Σε 92 byte κειμένου, το Base64 εκτυπώνει 124 χαρακτήρες και το Base91 114.

“Μπορεί να αποκωδικοποιηθεί αυτό με αποκωδικοποιητή Base64, ή το αντίστροφο;”

Όχι. Τα αλφάβητα επικαλύπτονται στα γράμματα και στα ψηφία, οπότε ένας αποκωδικοποιητής Base64 θα δεχτεί μια συμβολοσειρά Base91 ως "έγκυρους" χαρακτήρες και θα παράγει σιωπηλά σκουπίδια. Συμφωνούν μόνο ως προς τη γενική μορφή της μεθόδου.

“Τελειώνει η έξοδος με συμπλήρωση όπως το Base64;”

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

“Πώς ξέρω ότι το αποτέλεσμα αυτής της σελίδας είναι σωστό;”

Με το κουμπί Αυτοέλεγχος 0 έως 64 byte κωδικοποιούνται και αποκωδικοποιούνται 130 μοτίβα byte που καλύπτουν κάθε μήκος όπου αλλάζει η διάσπαση σε 13 και 14 bit, και συγκρίνονται τα byte που επιστρέφουν με τα byte που μπήκαν. Τα διανύσματα του κουμπιού Δείγμα διασταυρώνονται επιπλέον με δεύτερη υλοποίηση γραμμένη για τα εργαλεία δοκιμών του ιστότοπου.

Η σελίδα αυτή υλοποιεί τον αλγόριθμο της υλοποίησης αναφοράς basE91 (έκδοση 0.6.0) του Joachim Henke, που διανέμεται με άδεια BSD 3 clause, με το αλφάβητο που εκτυπώνεται παραπάνω. Η αποκωδικοποίηση δέχεται και αγνοεί τα κενά, όπως το εργαλείο αναφοράς.

Το κείμενο της σελίδας γράφτηκε για αυτόν τον ιστότοπο· ο αλγόριθμος δεν αντιγράφηκε από πουθενά. Οι τιμές του κουμπιού Δείγμα είναι το ένα παράδειγμα που συνοδεύει το πακέτο αναφοράς (με σήμανση "παράδειγμα αναφοράς") και οι τιμές που παράγονται από δεύτερη, ανεξάρτητη υλοποίηση που φυλάσσεται στα εργαλεία δοκιμών αυτού του ιστότοπου (με σήμανση "διασταύρωση").