Εάν είστε προγραμματιστής και αντιμετωπίζετε το καθήκον να επιλέξετε μια κωδικοποίηση, τότε το Unicode θα είναι σχεδόν πάντα η σωστή λύση. Η συγκεκριμένη μέθοδος αναπαράστασης εξαρτάται από το πλαίσιο, αλλά τις περισσότερες φορές υπάρχει μια καθολική απάντηση και εδώ - UTF-8. Το καλό με αυτό είναι ότι σας επιτρέπει να χρησιμοποιείτε όλους τους χαρακτήρες Unicode χωρίς να ξοδεύετε πάρα πολύ πολλά byte στις περισσότερες περιπτώσεις. Είναι αλήθεια ότι για γλώσσες που χρησιμοποιούν περισσότερα από το λατινικό αλφάβητο, το «όχι πάρα πολύ» είναι τουλάχιστον δύο byte ανά χαρακτήρα. Μπορούμε να τα καταφέρουμε καλύτερα χωρίς να επιστρέψουμε σε προϊστορικές κωδικοποιήσεις που μας περιορίζουν σε μόλις 256 διαθέσιμους χαρακτήρες;
Παρακάτω προτείνω να εξοικειωθείτε με την προσπάθειά μου να απαντήσω σε αυτήν την ερώτηση και να εφαρμόσετε έναν σχετικά απλό αλγόριθμο που σας επιτρέπει να αποθηκεύετε γραμμές στις περισσότερες γλώσσες του κόσμου χωρίς να προσθέτετε τον πλεονασμό που υπάρχει στο UTF-8.
Αποποίηση ευθυνών. Θα κάνω αμέσως μερικές σημαντικές επιφυλάξεις: η περιγραφόμενη λύση δεν προσφέρεται ως καθολική αντικατάσταση του UTF-8, είναι κατάλληλο μόνο σε μια στενή λίστα περιπτώσεων (περισσότερα για αυτές παρακάτω) και σε καμία περίπτωση δεν πρέπει να χρησιμοποιείται για αλληλεπίδραση με API τρίτων (που δεν το γνωρίζουν καν). Τις περισσότερες φορές, οι αλγόριθμοι συμπίεσης γενικής χρήσης (για παράδειγμα, deflate) είναι κατάλληλοι για συμπαγή αποθήκευση μεγάλων όγκων δεδομένων κειμένου. Επιπλέον, ήδη στη διαδικασία δημιουργίας της λύσης μου, βρήκα ένα υπάρχον πρότυπο στο ίδιο το Unicode, το οποίο λύνει το ίδιο πρόβλημα - είναι κάπως πιο περίπλοκο (και συχνά χειρότερο), αλλά εξακολουθεί να είναι ένα αποδεκτό πρότυπο και όχι απλώς μαζί στο γόνατο. Θα σου πω και γι' αυτόν.
Σχετικά με το Unicode και το UTF-8
Για αρχή, λίγα λόγια για το τι είναι Unicode и UTF-8.
Όπως γνωρίζετε, οι κωδικοποιήσεις 8-bit ήταν δημοφιλείς. Με αυτούς, όλα ήταν απλά: 256 χαρακτήρες μπορούν να αριθμηθούν με αριθμούς από το 0 έως το 255 και οι αριθμοί από το 0 έως το 255 μπορούν προφανώς να αναπαρασταθούν ως ένα byte. Αν πάμε πίσω στην αρχή, η κωδικοποίηση ASCII περιορίζεται εντελώς στα 7 bit, επομένως το πιο σημαντικό bit στην αναπαράσταση byte είναι μηδέν και οι περισσότερες κωδικοποιήσεις 8 bit είναι συμβατές με αυτό (διαφέρουν μόνο στο "επάνω" μέρος, όπου το πιο σημαντικό κομμάτι είναι ένα ).
Πώς διαφέρει το Unicode από αυτές τις κωδικοποιήσεις και γιατί συνδέονται τόσες πολλές συγκεκριμένες αναπαραστάσεις με αυτό - UTF-8, UTF-16 (BE και LE), UTF-32; Ας το τακτοποιήσουμε με τη σειρά.
Το βασικό πρότυπο Unicode περιγράφει μόνο την αντιστοιχία μεταξύ χαρακτήρων (και σε ορισμένες περιπτώσεις, μεμονωμένων στοιχείων χαρακτήρων) και των αριθμών τους. Και υπάρχουν πολλοί πιθανοί αριθμοί σε αυτό το πρότυπο - από 0x00 να 0x10FFFF (1 τεμάχια). Αν θέλαμε να βάλουμε έναν αριθμό σε ένα τέτοιο εύρος σε μια μεταβλητή, δεν θα μας αρκούσαν ούτε 114 ούτε 112 byte. Και επειδή οι επεξεργαστές μας δεν είναι πολύ σχεδιασμένοι για να εργάζονται με αριθμούς τριών byte, θα αναγκαστούμε να χρησιμοποιήσουμε έως και 1 byte ανά χαρακτήρα! Αυτό είναι το UTF-2, αλλά ακριβώς λόγω αυτής της «σπατάλης» αυτή η μορφή δεν είναι δημοφιλής.
Ευτυχώς, η σειρά των χαρακτήρων στο Unicode δεν είναι τυχαία. Όλο το σετ τους χωρίζεται σε 17"αεροπλάνα", καθένα από τα οποία περιέχει 65536 (0x10000) «σημεία κωδικού" Η έννοια του "κωδικού σημείου" εδώ είναι απλά αριθμός χαρακτήρα, που του έχει ανατεθεί από το Unicode. Αλλά, όπως αναφέρθηκε παραπάνω, στο Unicode δεν αριθμούνται μόνο μεμονωμένοι χαρακτήρες, αλλά και τα στοιχεία και τα σήματα υπηρεσιών τους (και μερικές φορές τίποτα δεν αντιστοιχεί στον αριθμό - ίσως προς το παρόν, αλλά για εμάς αυτό δεν είναι τόσο σημαντικό), οπότε Είναι πιο σωστό πάντα να μιλάμε συγκεκριμένα για τον αριθμό των αριθμών και όχι για τα σύμβολα. Ωστόσο, στη συνέχεια, για λόγους συντομίας, θα χρησιμοποιώ συχνά τη λέξη «σύμβολο», υπονοώντας τον όρο «κωδικό σημείο».
αεροπλάνα Unicode. Όπως μπορείτε να δείτε, το μεγαλύτερο μέρος του (επίπεδα 4 έως 13) είναι ακόμα αχρησιμοποίητο.
Αυτό που είναι πιο αξιοσημείωτο είναι ότι όλος ο κύριος «πολτός» βρίσκεται στο μηδενικό επίπεδο, ονομάζεται «Βασικό πολύγλωσσο επίπεδο". Εάν μια γραμμή περιέχει κείμενο σε μία από τις σύγχρονες γλώσσες (συμπεριλαμβανομένων των κινεζικών), δεν θα προχωρήσετε πέρα από αυτό το επίπεδο. Αλλά δεν μπορείτε να κόψετε το υπόλοιπο Unicode - για παράδειγμα, τα emoji βρίσκονται κυρίως στο τέλος του το επόμενο αεροπλάνο»Συμπληρωματικό πολύγλωσσο επίπεδο"(εκτείνεται από 0x10000 να 0x1FFFF). Έτσι το UTF-16 κάνει αυτό: όλοι οι χαρακτήρες εμπίπτουν μέσα Βασικό πολύγλωσσο επίπεδο, κωδικοποιούνται "ως έχουν" με αντίστοιχο αριθμό δύο byte. Ωστόσο, ορισμένοι από τους αριθμούς σε αυτό το εύρος δεν υποδεικνύουν καθόλου συγκεκριμένους χαρακτήρες, αλλά υποδεικνύουν ότι μετά από αυτό το ζεύγος byte πρέπει να εξετάσουμε ένα άλλο - συνδυάζοντας τις τιμές αυτών των τεσσάρων byte μαζί, παίρνουμε έναν αριθμό που καλύπτει ολόκληρη την έγκυρη σειρά Unicode. Αυτή η ιδέα ονομάζεται «παρένθετα ζευγάρια»—μπορεί να έχετε ακούσει γι' αυτά.
Άρα το UTF-16 απαιτεί δύο ή (σε πολύ σπάνιες περιπτώσεις) τέσσερα byte ανά «κωδικό σημείο». Αυτό είναι καλύτερο από τη χρήση τεσσάρων byte συνεχώς, αλλά τα λατινικά (και άλλοι χαρακτήρες ASCII) όταν κωδικοποιούνται με αυτόν τον τρόπο σπαταλά το μισό χώρο στα μηδενικά. Το UTF-8 έχει σχεδιαστεί για να το διορθώνει: Το ASCII σε αυτό καταλαμβάνει, όπως και πριν, μόνο ένα byte. κωδικοί από 0x80 να 0x7FF - δύο byte. από 0x800 να 0xFFFF - τρία, και από 0x10000 να 0x10FFFF - τέσσερα. Από τη μία πλευρά, το λατινικό αλφάβητο έχει γίνει καλό: η συμβατότητα με το ASCII έχει επιστρέψει και η διανομή είναι πιο ομοιόμορφα "απλωμένη" από 1 έως 4 byte. Αλλά τα άλλα αλφάβητα εκτός από τα λατινικά, δυστυχώς, δεν ωφελούνται με κανέναν τρόπο σε σύγκριση με το UTF-16, και πολλά τώρα απαιτούν τρία byte αντί για δύο - το εύρος που καλύπτεται από μια εγγραφή δύο byte έχει περιοριστεί κατά 32 φορές, με 0xFFFF να 0x7FF, και δεν περιλαμβάνονται σε αυτό ούτε κινέζικα ούτε, για παράδειγμα, γεωργιανά. Κυριλλικό και άλλα πέντε αλφάβητα - hurray - lucky, 2 byte ανά χαρακτήρα.
Γιατί συμβαίνει αυτό; Ας δούμε πώς το UTF-8 αντιπροσωπεύει τους κωδικούς χαρακτήρων:
Απευθείας για την αναπαράσταση αριθμών, εδώ χρησιμοποιούνται bits που σημειώνονται με το σύμβολο x. Μπορεί να φανεί ότι σε μια εγγραφή δύο byte υπάρχουν μόνο 11 τέτοια bit (από τα 16). Τα κύρια bit εδώ έχουν μόνο μια βοηθητική λειτουργία. Στην περίπτωση μιας εγγραφής τεσσάρων byte, 21 από τα 32 bit εκχωρούνται για τον αριθμό του κωδικού σημείου - φαίνεται ότι τρία byte (που δίνουν συνολικά 24 bit) θα ήταν αρκετά, αλλά οι δείκτες υπηρεσίας τρώνε πάρα πολύ.
Είναι κακό αυτό; Όχι πραγματικά. Από τη μία, αν μας ενδιαφέρει πολύ ο χώρος, έχουμε αλγόριθμους συμπίεσης που μπορούν εύκολα να εξαλείψουν όλη την επιπλέον εντροπία και τον πλεονασμό. Από την άλλη πλευρά, ο στόχος του Unicode ήταν να παρέχει την πιο καθολική δυνατή κωδικοποίηση. Για παράδειγμα, μπορούμε να εμπιστευτούμε μια γραμμή κωδικοποιημένη σε UTF-8 σε κώδικα που λειτουργούσε προηγουμένως μόνο με ASCII και να μην φοβόμαστε ότι θα δει έναν χαρακτήρα από το εύρος ASCII που στην πραγματικότητα δεν υπάρχει (εξάλλου, στο UTF-8 όλα byte που ξεκινούν από το μηδενικό bit - αυτό ακριβώς είναι το ASCII). Και αν θέλουμε ξαφνικά να κόψουμε μια μικρή ουρά από μια μεγάλη συμβολοσειρά χωρίς να την αποκωδικοποιήσουμε από την αρχή (ή να επαναφέρουμε μέρος των πληροφοριών μετά από μια κατεστραμμένη ενότητα), είναι εύκολο για εμάς να βρούμε τη μετατόπιση από όπου ξεκινά ένας χαρακτήρας (αρκεί για να παραλείψετε byte που έχουν πρόθεμα bit 10).
Γιατί τότε να εφεύρουμε κάτι νέο;
Ταυτόχρονα, υπάρχουν περιστασιακά περιπτώσεις όπου αλγόριθμοι συμπίεσης όπως το deflate δεν εφαρμόζονται καλά, αλλά θέλετε να επιτύχετε συμπαγή αποθήκευση συμβολοσειρών. Προσωπικά, αντιμετώπισα αυτό το πρόβλημα όταν σκεφτόμουν την κατασκευή για ένα μεγάλο λεξικό που περιλαμβάνει λέξεις σε αυθαίρετες γλώσσες. Από τη μία πλευρά, κάθε λέξη είναι πολύ σύντομη, επομένως η συμπίεσή της θα είναι αναποτελεσματική. Από την άλλη πλευρά, η υλοποίηση δέντρου που εξέτασα σχεδιάστηκε έτσι ώστε κάθε byte της αποθηκευμένης συμβολοσειράς να δημιουργεί μια ξεχωριστή κορυφή δέντρου, επομένως η ελαχιστοποίηση του αριθμού τους ήταν πολύ χρήσιμη. Στη βιβλιοθήκη μου (Οπως λέμε , στο οποίο βασίζεται) ένα παρόμοιο πρόβλημα μπορεί να λυθεί απλά - συσκευασμένες συμβολοσειρές -λεξικό, αποθηκευμένο εκεί μέσα . Αλλά, όπως είναι εύκολο να γίνει κατανοητό, αυτό λειτουργεί καλά μόνο για ένα περιορισμένο αλφάβητο - μια γραμμή στα κινέζικα δεν μπορεί να προστεθεί σε ένα τέτοιο λεξικό.
Ξεχωριστά, θα ήθελα να σημειώσω μια ακόμη δυσάρεστη απόχρωση που προκύπτει όταν χρησιμοποιείτε το UTF-8 σε μια τέτοια δομή δεδομένων. Η παραπάνω εικόνα δείχνει ότι όταν ένας χαρακτήρας γράφεται ως δύο byte, τα bit που σχετίζονται με τον αριθμό του δεν έρχονται σε μια σειρά, αλλά χωρίζονται από ένα ζεύγος bit 10 στη μέση: 110xxxxx 10xxxxxx. Εξαιτίας αυτού, όταν τα κατώτερα 6 bit του δεύτερου byte υπερχειλίσουν στον κώδικα χαρακτήρων (δηλ., συμβαίνει μια μετάβαση 10111111 → 10000000), τότε αλλάζει και το πρώτο byte. Αποδεικνύεται ότι το γράμμα "p" συμβολίζεται με byte 0xD0 0xBF, και το επόμενο "r" είναι ήδη 0xD1 0x80. Σε ένα δέντρο προθέματος, αυτό οδηγεί στη διαίρεση του γονικού κόμβου σε δύο - ένα για το πρόθεμα 0xD0, και άλλο για 0xD1 (αν και ολόκληρο το κυριλλικό αλφάβητο μπορούσε να κωδικοποιηθεί μόνο από το δεύτερο byte).
Τι πήρα
Αντιμέτωπος με αυτό το πρόβλημα, αποφάσισα να εξασκηθώ παίζοντας παιχνίδια με bits και ταυτόχρονα να εξοικειωθώ λίγο καλύτερα με τη δομή του Unicode στο σύνολό του. Το αποτέλεσμα ήταν η μορφή κωδικοποίησης UTF-C ("C" για συμπαγής), το οποίο δεν ξοδεύει περισσότερα από 3 byte ανά σημείο κώδικα και πολύ συχνά σας επιτρέπει να ξοδεύετε μόνο ένα επιπλέον byte για ολόκληρη την κωδικοποιημένη γραμμή. Αυτό οδηγεί στο γεγονός ότι σε πολλά αλφάβητα που δεν είναι ASCII αποδεικνύεται ότι υπάρχει τέτοια κωδικοποίηση 30-60% πιο συμπαγές από το UTF-8.
Έχω παρουσιάσει παραδείγματα υλοποίησης αλγορίθμων κωδικοποίησης και αποκωδικοποίησης στη φόρμα , μπορείτε να τα χρησιμοποιήσετε ελεύθερα στον κώδικά σας. Αλλά θα εξακολουθώ να τονίζω ότι κατά μία έννοια αυτή η μορφή παραμένει "ποδήλατο" και δεν συνιστώ τη χρήση της χωρίς να καταλάβεις γιατί το χρειάζεσαι. Αυτό είναι ακόμα περισσότερο ένα πείραμα παρά μια σοβαρή "βελτίωση του UTF-8". Παρόλα αυτά, ο κώδικας εκεί είναι γραμμένος τακτοποιημένα, συνοπτικά, με μεγάλο αριθμό σχολίων και δοκιμαστική κάλυψη.
Αποτελέσματα δοκιμής και σύγκριση με UTF-8
έκανα κι εγώ , όπου μπορείτε να αξιολογήσετε την απόδοση του αλγορίθμου και στη συνέχεια θα σας πω περισσότερα για τις αρχές και τη διαδικασία ανάπτυξής του.
Εξάλειψη περιττών bits
Πήρα ως βάση το UTF-8 φυσικά. Το πρώτο και πιο προφανές πράγμα που μπορεί να αλλάξει σε αυτό είναι να μειωθεί ο αριθμός των bits υπηρεσίας σε κάθε byte. Για παράδειγμα, το πρώτο byte στο UTF-8 ξεκινά πάντα με ένα από τα δύο 0, ή με 11 - ένα πρόθεμα 10 Μόνο τα παρακάτω byte το έχουν. Ας αντικαταστήσουμε το πρόθεμα 11 επί 1, και για τα επόμενα byte θα αφαιρέσουμε εντελώς τα προθέματα. Τι θα συμβεί?
0xxxxxxx — 1 byte
10xxxxxx xxxxxxxx - 2 byte
110xxxxx xxxxxxxx xxxxxxxx - 3 byte
Περιμένετε, πού είναι η εγγραφή τεσσάρων byte; Αλλά δεν χρειάζεται πλέον - όταν γράφουμε σε τρία byte, έχουμε τώρα διαθέσιμα 21 bit και αυτό είναι αρκετό για όλους τους αριθμούς μέχρι 0x10FFFF.
Τι έχουμε θυσιάσει εδώ; Το πιο σημαντικό πράγμα είναι η ανίχνευση ορίων χαρακτήρων από μια αυθαίρετη θέση στο buffer. Δεν μπορούμε να δείξουμε ένα αυθαίρετο byte και να βρούμε την αρχή του επόμενου χαρακτήρα από αυτό. Αυτός είναι ένας περιορισμός της μορφής μας, αλλά στην πράξη αυτό είναι σπάνια απαραίτητο. Συνήθως μπορούμε να περάσουμε μέσα από το buffer από την αρχή (ειδικά όταν πρόκειται για σύντομες γραμμές).
Η κατάσταση με την κάλυψη γλωσσών με 2 byte έχει επίσης βελτιωθεί: τώρα η μορφή δύο byte δίνει εύρος 14 bit και αυτοί είναι κωδικοί μέχρι 0x3FFF. Οι Κινέζοι είναι άτυχοι (οι χαρακτήρες τους κυμαίνονται κυρίως από 0x4E00 να 0x9FFF), αλλά οι Γεωργιανοί και πολλοί άλλοι λαοί διασκεδάζουν περισσότερο - οι γλώσσες τους χωρούν επίσης σε 2 byte ανά χαρακτήρα.
Εισαγάγετε την κατάσταση του κωδικοποιητή
Ας σκεφτούμε τώρα τις ιδιότητες των ίδιων των γραμμών. Το λεξικό τις περισσότερες φορές περιέχει λέξεις γραμμένες με χαρακτήρες του ίδιου αλφαβήτου, και αυτό ισχύει και για πολλά άλλα κείμενα. Καλό θα ήταν να αναφέρετε αυτό το αλφάβητο μία φορά και μετά να αναφέρετε μόνο τον αριθμό του γράμματος μέσα σε αυτό. Ας δούμε αν θα μας βοηθήσει η διάταξη των χαρακτήρων στον πίνακα Unicode.
Όπως αναφέρθηκε παραπάνω, το Unicode χωρίζεται σε επίπεδο 65536 κωδικοί έκαστος. Αλλά αυτό δεν είναι μια πολύ χρήσιμη διαίρεση (όπως ήδη ειπώθηκε, τις περισσότερες φορές βρισκόμαστε στο μηδενικό επίπεδο). Πιο ενδιαφέρουσα είναι η διαίρεση κατά μπλοκ. Αυτά τα εύρη δεν έχουν πλέον σταθερό μήκος και έχουν μεγαλύτερη σημασία - κατά κανόνα, το καθένα συνδυάζει χαρακτήρες από το ίδιο αλφάβητο.
Ένα μπλοκ που περιέχει χαρακτήρες του βεγγαλικού αλφαβήτου. Δυστυχώς, για ιστορικούς λόγους, αυτό είναι ένα παράδειγμα όχι πολύ πυκνής συσκευασίας - 96 χαρακτήρες είναι χαοτικά διάσπαρτοι σε 128 σημεία κωδικού μπλοκ.
Οι αρχές των μπλοκ και τα μεγέθη τους είναι πάντα πολλαπλάσια του 16 - αυτό γίνεται απλά για ευκολία. Επιπλέον, πολλά μπλοκ ξεκινούν και τελειώνουν σε τιμές που είναι πολλαπλάσια του 128 ή ακόμα και του 256 - για παράδειγμα, το βασικό κυριλλικό αλφάβητο καταλαμβάνει 256 byte από 0x0400 να 0x04FF. Αυτό είναι αρκετά βολικό: αν αποθηκεύσουμε το πρόθεμα μία φορά 0x04, τότε οποιοσδήποτε κυριλλικός χαρακτήρας μπορεί να γραφτεί σε ένα byte. Είναι αλήθεια ότι έτσι θα χάσουμε την ευκαιρία να επιστρέψουμε στο ASCII (και σε οποιουσδήποτε άλλους χαρακτήρες γενικά). Επομένως κάνουμε αυτό:
- Δύο byte
10yyyyyy yxxxxxxxδεν δηλώνουν μόνο ένα σύμβολο με έναν αριθμόyyyyyy yxxxxxxx, αλλά και αλλαγή τρέχον αλφάβητο επίyyyyyy y0000000(δηλαδή θυμόμαστε όλα τα κομμάτια εκτός από τα λιγότερο σημαντικά Bit 7); - Ένα byte
0xxxxxxxαυτός είναι ο χαρακτήρας του τρέχοντος αλφαβήτου. Απλώς πρέπει να προστεθεί στη μετατόπιση που θυμηθήκαμε στο βήμα 1. Αν και δεν αλλάξαμε το αλφάβητο, η μετατόπιση είναι μηδέν, επομένως διατηρήσαμε τη συμβατότητα με το ASCII.
Ομοίως για κωδικούς που απαιτούν 3 byte:
- Τρία byte
110yyyyy yxxxxxxx xxxxxxxxυποδεικνύουν ένα σύμβολο με έναν αριθμόyyyyyy yxxxxxxx xxxxxxxx, αλλαγή τρέχον αλφάβητο επίyyyyyy y0000000 00000000(θυμήθηκα τα πάντα εκτός από τους νεότερους Bit 15) και επιλέξτε το πλαίσιο στο οποίο βρισκόμαστε τώρα μακρύς λειτουργία (όταν αλλάξουμε το αλφάβητο σε διπλό byte, θα επαναφέρουμε αυτήν τη σημαία). - Δύο byte
0xxxxxxx xxxxxxxxσε μακρά λειτουργία είναι ο χαρακτήρας του τρέχοντος αλφαβήτου. Ομοίως, το προσθέτουμε με τη μετατόπιση από το βήμα 1. Η μόνη διαφορά είναι ότι τώρα διαβάζουμε δύο byte (επειδή περάσαμε σε αυτή τη λειτουργία).
Ακούγεται καλό: τώρα, ενώ χρειάζεται να κωδικοποιήσουμε χαρακτήρες από το ίδιο εύρος Unicode 7-bit, ξοδεύουμε 1 επιπλέον byte στην αρχή και συνολικά ένα byte ανά χαρακτήρα.
Λειτουργεί από μία από τις προηγούμενες εκδόσεις. Ήδη συχνά νικάει το UTF-8, αλλά υπάρχει ακόμα περιθώριο βελτίωσης.
Τι είναι χειρότερο? Πρώτον, έχουμε έναν όρο, δηλαδή τρέχουσα μετατόπιση αλφαβήτου και πλαίσιο ελέγχου μακρά λειτουργία. Αυτό μας περιορίζει περαιτέρω: τώρα οι ίδιοι χαρακτήρες μπορούν να κωδικοποιηθούν διαφορετικά σε διαφορετικά περιβάλλοντα. Η αναζήτηση για υποσυμβολοσειρές, για παράδειγμα, θα πρέπει να γίνει λαμβάνοντας υπόψη αυτό, και όχι μόνο με σύγκριση byte. Δεύτερον, μόλις αλλάξαμε το αλφάβητο, έγινε κακό με την κωδικοποίηση χαρακτήρων ASCII (και αυτό δεν είναι μόνο το λατινικό αλφάβητο, αλλά και τα βασικά σημεία στίξης, συμπεριλαμβανομένων των κενών) - απαιτούν αλλαγή του αλφαβήτου ξανά στο 0, δηλαδή, και πάλι ένα επιπλέον byte (και μετά άλλο ένα για να επιστρέψουμε στο κύριο θέμα μας).
Ένα αλφάβητο είναι καλό, δύο είναι καλύτερα
Ας προσπαθήσουμε να αλλάξουμε λίγο τα προθέματά μας bit, συμπιέζοντας ένα ακόμα στα τρία που περιγράφονται παραπάνω:
0xxxxxxx — 1 byte σε κανονική λειτουργία, 2 σε λειτουργία μεγάλης διάρκειας
11xxxxxx — 1 byte
100xxxxx xxxxxxxx - 2 byte
101xxxxx xxxxxxxx xxxxxxxx - 3 byte
Τώρα σε μια εγγραφή δύο byte υπάρχει ένα λιγότερο διαθέσιμο bit - ο κώδικας δείχνει μέχρι 0x1FFFαλλά όχι 0x3FFF. Ωστόσο, εξακολουθεί να είναι αισθητά μεγαλύτερο από ό,τι σε κωδικούς UTF-8 δύο byte, οι περισσότερες κοινές γλώσσες εξακολουθούν να ταιριάζουν, η πιο αισθητή απώλεια έχει πέσει έξω и , οι Ιάπωνες είναι λυπημένοι.
Τι είναι αυτός ο νέος κωδικός; 11xxxxxx? Αυτό είναι ένα μικρό "αποθήκη" 64 χαρακτήρων σε μέγεθος, συμπληρώνει το κύριο αλφάβητό μας, γι 'αυτό το ονόμασα βοηθητικό (βοηθητική) αλφάβητο. Όταν αλλάζουμε το τρέχον αλφάβητο, ένα κομμάτι από το παλιό αλφάβητο γίνεται βοηθητικό. Για παράδειγμα, αλλάξαμε από ASCII σε Κυριλλικό - το stash περιέχει τώρα 64 χαρακτήρες που περιέχουν Λατινικό αλφάβητο, αριθμοί, διάστημα και κόμμα (πιο συχνές παρεμβολές σε κείμενα εκτός ASCII). Επιστρέψτε στο ASCII - και το κύριο μέρος του κυριλλικού αλφαβήτου θα γίνει το βοηθητικό αλφάβητο.
Χάρη στην πρόσβαση σε δύο αλφάβητα, μπορούμε να χειριστούμε μεγάλο αριθμό κειμένων με ελάχιστο κόστος για την εναλλαγή αλφαβήτων (τα σημεία στίξης τις περισσότερες φορές οδηγούν σε επιστροφή στο ASCII, αλλά μετά από αυτό θα λάβουμε πολλούς χαρακτήρες που δεν είναι ASCII από το πρόσθετο αλφάβητο, χωρίς αλλαγή ξανά).
Μπόνους: προσθήκη του υποαλφαβήτου 11xxxxxx και επιλέγοντας να είναι η αρχική του μετατόπιση 0xC0, έχουμε μερική συμβατότητα με το CP1252. Με άλλα λόγια, πολλά (αλλά όχι όλα) δυτικοευρωπαϊκά κείμενα που κωδικοποιούνται στο CP1252 θα φαίνονται ίδια στο UTF-C.
Εδώ, όμως, προκύπτει μια δυσκολία: πώς να αποκτήσετε ένα βοηθητικό από το κύριο αλφάβητο; Μπορείτε να αφήσετε το ίδιο offset, αλλά - δυστυχώς - εδώ η δομή Unicode παίζει ήδη εναντίον μας. Πολύ συχνά το κύριο μέρος του αλφαβήτου δεν βρίσκεται στην αρχή του μπλοκ (για παράδειγμα, το ρωσικό κεφαλαίο "A" έχει τον κωδικό 0x0410, αν και το κυριλλικό μπλοκ αρχίζει με 0x0400). Έτσι, έχοντας λάβει τους πρώτους 64 χαρακτήρες στο απόθεμα, μπορεί να χάσουμε την πρόσβαση στο ουραίο τμήμα του αλφαβήτου.
Για να διορθώσω αυτό το πρόβλημα, πέρασα με μη αυτόματο τρόπο ορισμένα μπλοκ που αντιστοιχούν σε διαφορετικές γλώσσες και καθόρισα τη μετατόπιση του βοηθητικού αλφαβήτου εντός του κύριου για αυτές. Το λατινικό αλφάβητο, κατ' εξαίρεση, γενικά αναδιατάχθηκε όπως το βασικό64.
Τελικές πινελιές
Ας σκεφτούμε επιτέλους πού αλλού μπορούμε να βελτιώσουμε κάτι.
Σημειώστε ότι η μορφή 101xxxxx xxxxxxxx xxxxxxxx σας επιτρέπει να κωδικοποιήσετε αριθμούς μέχρι 0x1FFFFF, και το Unicode τελειώνει νωρίτερα, στο 0x10FFFF. Με άλλα λόγια, το τελευταίο σημείο κωδικού θα αναπαρασταθεί ως 10110000 11111111 11111111. Επομένως, μπορούμε να πούμε ότι αν το πρώτο byte είναι της μορφής 1011xxxx (Οπου xxxx μεγαλύτερο από 0), τότε σημαίνει κάτι άλλο. Για παράδειγμα, μπορείτε να προσθέσετε άλλους 15 χαρακτήρες εκεί που είναι συνεχώς διαθέσιμοι για κωδικοποίηση σε ένα byte, αλλά αποφάσισα να το κάνω διαφορετικά.
Ας δούμε τώρα εκείνα τα μπλοκ Unicode που απαιτούν τρία byte. Βασικά, όπως ήδη αναφέρθηκε, αυτοί είναι κινεζικοί χαρακτήρες - αλλά είναι δύσκολο να κάνετε κάτι με αυτούς, υπάρχουν 21 χιλιάδες από αυτούς. Αλλά και η hiragana και η katakana πέταξαν εκεί - και δεν είναι τόσα πολλά πια, λιγότερα από διακόσια. Και, αφού θυμηθήκαμε τους Ιάπωνες, υπάρχουν και emoji (στην πραγματικότητα, είναι διάσπαρτα σε πολλά σημεία στο Unicode, αλλά τα κύρια μπλοκ είναι στην περιοχή 0x1F300 - 0x1FBFF). Αν σκεφτείτε το γεγονός ότι τώρα υπάρχουν emoji που συγκεντρώνονται από πολλά σημεία κώδικα ταυτόχρονα (για παράδειγμα, το emoji αποτελείται από έως και 7 κωδικούς!), τότε είναι εντελώς κρίμα να ξοδέψετε τρία byte για το καθένα (7×3 = 21 bytes για χάρη ενός εικονιδίου, ενός εφιάλτη).
Επομένως, επιλέγουμε μερικές επιλεγμένες περιοχές που αντιστοιχούν σε emoji, hiragana και katakana, τις επαναριθμούμε σε μια συνεχή λίστα και τις κωδικοποιούμε ως δύο byte αντί για τρία:
1011xxxx xxxxxxxx
Εξαιρετικό: το προαναφερθέν emoji, που αποτελείται από 7 σημεία κώδικα, παίρνει 8 byte σε UTF-25 και το τοποθετούμε σε 14 (ακριβώς δύο byte για κάθε σημείο κώδικα). Παρεμπιπτόντως, ο Habr αρνήθηκε να το χωνέψει (τόσο στον παλιό όσο και στον νέο επεξεργαστή), οπότε έπρεπε να το βάλω με μια εικόνα.
Ας προσπαθήσουμε να διορθώσουμε ένα ακόμη πρόβλημα. Όπως θυμόμαστε, το βασικό αλφάβητο είναι ουσιαστικά υψηλό 6 bit, το οποίο έχουμε υπόψη μας και κολλάμε στον κωδικό κάθε επόμενου αποκωδικοποιημένου συμβόλου. Στην περίπτωση των κινεζικών χαρακτήρων που βρίσκονται στο μπλοκ 0x4E00 - 0x9FFF, αυτό είναι είτε bit 0 είτε 1. Αυτό δεν είναι πολύ βολικό: θα χρειαστεί να αλλάζουμε συνεχώς το αλφάβητο μεταξύ αυτών των δύο τιμών (δηλαδή να ξοδεύουμε τρία byte). Αλλά σημειώστε ότι στη μακρά λειτουργία, από τον ίδιο τον κώδικα μπορούμε να αφαιρέσουμε τον αριθμό των χαρακτήρων που κωδικοποιούμε χρησιμοποιώντας τη σύντομη λειτουργία (μετά από όλα τα κόλπα που περιγράφονται παραπάνω, αυτό είναι 10240) - τότε το εύρος των ιερογλυφικών θα μετατοπιστεί σε 0x2600 - 0x77FF, και σε αυτήν την περίπτωση, σε όλο αυτό το εύρος, τα πιο σημαντικά 6 bit (από τα 21) θα είναι ίσα με 0. Έτσι, οι ακολουθίες ιερογλυφικών θα χρησιμοποιούν δύο byte ανά ιερογλυφικό (που είναι βέλτιστο για ένα τόσο μεγάλο εύρος), χωρίς προκαλώντας αλλαγές αλφαβήτου.
Εναλλακτικές λύσεις: SCSU, BOCU-1
Οι ειδικοί της Unicode, έχοντας μόλις διαβάσει τον τίτλο του άρθρου, πιθανότατα θα σπεύσουν να σας υπενθυμίσουν ότι άμεσα μεταξύ των προτύπων Unicode υπάρχει (SCSU), η οποία περιγράφει μια μέθοδο κωδικοποίησης παρόμοια με αυτή που περιγράφεται στο άρθρο.
Το παραδέχομαι ειλικρινά: έμαθα για την ύπαρξή του μόνο αφού βυθίστηκα βαθιά στη συγγραφή της απόφασής μου. Αν το ήξερα από την αρχή, πιθανότατα θα προσπαθούσα να γράψω μια υλοποίηση αντί να καταλήξω στη δική μου προσέγγιση.
Αυτό που είναι ενδιαφέρον είναι ότι το SCSU χρησιμοποιεί ιδέες πολύ παρόμοιες με αυτές που σκέφτηκα μόνος μου (αντί για την έννοια των "αλφαβήτων" χρησιμοποιούν "παράθυρα" και υπάρχουν περισσότερα από αυτά διαθέσιμα από μένα). Ταυτόχρονα, αυτή η μορφή έχει επίσης μειονεκτήματα: είναι λίγο πιο κοντά στους αλγόριθμους συμπίεσης από τους αλγόριθμους κωδικοποίησης. Συγκεκριμένα, το πρότυπο δίνει πολλές μεθόδους αναπαράστασης, αλλά δεν λέει πώς να επιλέξετε τη βέλτιστη - γι 'αυτό, ο κωδικοποιητής πρέπει να χρησιμοποιήσει κάποιο είδος ευρετικής. Έτσι, ένας κωδικοποιητής SCSU που παράγει καλή συσκευασία θα είναι πιο περίπλοκος και πιο περίπλοκος από τον αλγόριθμό μου.
Για σύγκριση, μετέφερα μια σχετικά απλή υλοποίηση του SCSU σε JavaScript - από άποψη όγκου κώδικα αποδείχθηκε συγκρίσιμο με το UTF-C μου, αλλά σε ορισμένες περιπτώσεις το αποτέλεσμα ήταν δεκάδες τοις εκατό χειρότερο (μερικές φορές μπορεί να το ξεπεράσει, αλλά όχι πολύ). Για παράδειγμα, τα κείμενα στα εβραϊκά και στα ελληνικά κωδικοποιήθηκαν από το UTF-C 60% καλύτερο από το SCSU (μάλλον λόγω των συμπαγών αλφαβήτων τους).
Ξεχωριστά, θα προσθέσω ότι εκτός από το SCSU υπάρχει επίσης ένας άλλος τρόπος για συμπαγή αναπαράσταση του Unicode - , αλλά στοχεύει στη συμβατότητα MIME (που δεν χρειαζόμουν) και ακολουθεί μια ελαφρώς διαφορετική προσέγγιση στην κωδικοποίηση. Δεν έχω αξιολογήσει την αποτελεσματικότητά του, αλλά μου φαίνεται ότι είναι απίθανο να είναι υψηλότερο από το SCSU.
Πιθανές βελτιώσεις
Ο αλγόριθμος που παρουσίασα δεν είναι καθολικός από τη σχεδίασή του (εδώ πιθανώς οι στόχοι μου διαφέρουν περισσότερο από τους στόχους της κοινοπραξίας Unicode). Έχω ήδη αναφέρει ότι αναπτύχθηκε κυρίως για μία εργασία (αποθήκευση ενός πολυγλωσσικού λεξικού σε δέντρο προθέματος) και ορισμένες από τις δυνατότητες του μπορεί να μην είναι κατάλληλες για άλλες εργασίες. Αλλά το γεγονός ότι δεν είναι πρότυπο μπορεί να είναι ένα συν - μπορείτε εύκολα να το τροποποιήσετε για να ταιριάζει στις ανάγκες σας.
Για παράδειγμα, με τον προφανή τρόπο μπορείτε να απαλλαγείτε από την παρουσία κατάστασης, να κάνετε κωδικοποίηση χωρίς ιθαγένεια - απλώς μην ενημερώσετε τις μεταβλητές offs, auxOffs и is21Bit στον κωδικοποιητή και στον αποκωδικοποιητή. Σε αυτήν την περίπτωση, δεν θα είναι δυνατό να συσκευαστούν αποτελεσματικά ακολουθίες χαρακτήρων του ίδιου αλφαβήτου, αλλά θα υπάρχει εγγύηση ότι ο ίδιος χαρακτήρας κωδικοποιείται πάντα με τα ίδια byte, ανεξάρτητα από το περιβάλλον.
Επιπλέον, μπορείτε να προσαρμόσετε τον κωδικοποιητή σε μια συγκεκριμένη γλώσσα αλλάζοντας την προεπιλεγμένη κατάσταση - για παράδειγμα, εστιάζοντας σε ρωσικά κείμενα, ορίστε τον κωδικοποιητή και τον αποκωδικοποιητή στην αρχή offs = 0x0400 и auxOffs = 0. Αυτό είναι ιδιαίτερα λογικό στην περίπτωση της κατάστασης ανιθαγένειας. Σε γενικές γραμμές, αυτό θα είναι παρόμοιο με τη χρήση της παλιάς κωδικοποίησης οκτώ bit, αλλά χωρίς να αφαιρείται η δυνατότητα εισαγωγής χαρακτήρων από όλο το Unicode, όπως απαιτείται.
Ένα άλλο μειονέκτημα που αναφέρθηκε προηγουμένως είναι ότι σε μεγάλο κείμενο που κωδικοποιείται σε UTF-C δεν υπάρχει γρήγορος τρόπος να βρείτε το όριο χαρακτήρων που βρίσκεται πιο κοντά σε ένα αυθαίρετο byte. Εάν κόψετε τα τελευταία, ας πούμε, 100 byte από το κωδικοποιημένο buffer, κινδυνεύετε να πάρετε σκουπίδια με τα οποία δεν μπορείτε να κάνετε τίποτα. Η κωδικοποίηση δεν έχει σχεδιαστεί για την αποθήκευση αρχείων καταγραφής πολλών gigabyte, αλλά γενικά αυτό μπορεί να διορθωθεί. Ψηφιόλεξη 0xBF δεν πρέπει ποτέ να εμφανίζεται ως το πρώτο byte (αλλά μπορεί να είναι το δεύτερο ή το τρίτο). Επομένως, κατά την κωδικοποίηση, μπορείτε να εισαγάγετε την ακολουθία 0xBF 0xBF 0xBF κάθε, ας πούμε, 10 KB - τότε, αν χρειαστεί να βρείτε ένα όριο, θα είναι αρκετό να σαρώσετε το επιλεγμένο κομμάτι μέχρι να βρεθεί ένας παρόμοιος δείκτης. Ακολουθώντας το τελευταίο 0xBF είναι εγγυημένο ότι είναι η αρχή ενός χαρακτήρα. (Κατά την αποκωδικοποίηση, αυτή η ακολουθία των τριών byte, φυσικά, θα πρέπει να αγνοηθεί.)
Ανακεφαλαίωση
Αν έχετε διαβάσει μέχρι εδώ, συγχαρητήρια! Ελπίζω ότι, όπως εγώ, μάθατε κάτι νέο (ή φρεσκάρατε τη μνήμη σας) σχετικά με τη δομή του Unicode.
Επίδειξη σελίδας. Το παράδειγμα της Εβραϊκής δείχνει τα πλεονεκτήματα τόσο έναντι του UTF-8 όσο και του SCSU.
Η έρευνα που περιγράφεται παραπάνω δεν θα πρέπει να θεωρείται ως παραβίαση των προτύπων. Ωστόσο, γενικά είμαι ικανοποιημένος από τα αποτελέσματα της δουλειάς μου, οπότε είμαι ευχαριστημένος από αυτά : για παράδειγμα, μια ελαχιστοποιημένη βιβλιοθήκη JS ζυγίζει μόνο 1710 byte (και φυσικά δεν έχει εξαρτήσεις). Όπως προανέφερα, το έργο της βρίσκεται στο (υπάρχει επίσης ένα σύνολο κειμένων στα οποία μπορεί να συγκριθεί με το UTF-8 και το SCSU).
Τέλος, θα επιστήσω και πάλι την προσοχή σε περιπτώσεις στις οποίες χρησιμοποιείται το UTF-C δεν αξίζει τον κόπο:
- Εάν οι γραμμές σας είναι αρκετά μεγάλες (από 100-200 χαρακτήρες). Σε αυτήν την περίπτωση, θα πρέπει να σκεφτείτε να χρησιμοποιήσετε αλγόριθμους συμπίεσης όπως το deflate.
- Αν χρειάζεσαι Διαφάνεια ASCII, δηλαδή, είναι σημαντικό για εσάς οι κωδικοποιημένες ακολουθίες να μην περιέχουν κωδικούς ASCII που δεν ήταν στην αρχική συμβολοσειρά. Η ανάγκη για αυτό μπορεί να αποφευχθεί εάν, όταν αλληλεπιδράτε με API τρίτων κατασκευαστών (για παράδειγμα, εργάζεστε με μια βάση δεδομένων), μεταβιβάζετε το αποτέλεσμα κωδικοποίησης ως αφηρημένο σύνολο byte και όχι ως συμβολοσειρές. Διαφορετικά, κινδυνεύετε να εμφανίσετε απροσδόκητα τρωτά σημεία.
- Εάν θέλετε να μπορείτε να βρίσκετε γρήγορα όρια χαρακτήρων σε αυθαίρετη μετατόπιση (για παράδειγμα, όταν ένα μέρος μιας γραμμής είναι κατεστραμμένο). Αυτό μπορεί να γίνει, αλλά μόνο σαρώνοντας τη γραμμή από την αρχή (ή εφαρμόζοντας την τροποποίηση που περιγράφεται στην προηγούμενη ενότητα).
- Εάν χρειάζεται να εκτελέσετε γρήγορα λειτουργίες στα περιεχόμενα των συμβολοσειρών (ταξινόμηση, αναζήτηση για υποσυμβολοσειρές σε αυτές, συνένωση). Αυτό απαιτεί πρώτα να αποκωδικοποιηθούν οι συμβολοσειρές, επομένως το UTF-C θα είναι πιο αργό από το UTF-8 σε αυτές τις περιπτώσεις (αλλά πιο γρήγορο από τους αλγόριθμους συμπίεσης). Εφόσον η ίδια συμβολοσειρά κωδικοποιείται πάντα με τον ίδιο τρόπο, δεν απαιτείται ακριβής σύγκριση της αποκωδικοποίησης και μπορεί να γίνει ανά byte.
Ενημέρωση: χρήστη δημοσίευσε ένα γράφημα που επισημαίνει τα όρια εφαρμογής του UTF-C. Δείχνει ότι το UTF-C είναι πιο αποτελεσματικό από έναν αλγόριθμο συμπίεσης γενικής χρήσης (μια παραλλαγή του LZW) εφόσον η συσκευασμένη συμβολοσειρά είναι μικρότερη ~ 140 χαρακτήρες (Ωστόσο, σημειώνω ότι η σύγκριση πραγματοποιήθηκε σε ένα κείμενο· για άλλες γλώσσες το αποτέλεσμα μπορεί να διαφέρει).
Πηγή: www.habr.com