{"id":95911,"date":"2020-10-05T01:42:09","date_gmt":"2020-10-04T23:42:09","guid":{"rendered":"https:\/\/prohoster.info\/blog\/administrirovanie\/eshhyo-odin-velosiped-hranim-yunikodnye-stroki-na-30-60-kompaktnee-chem-utf-8"},"modified":"2020-10-05T01:42:09","modified_gmt":"2020-10-04T23:42:09","slug":"eshhyo-odin-velosiped-hranim-yunikodnye-stroki-na-30-60-kompaktnee-chem-utf-8","status":"publish","type":"post","link":"https:\/\/prohoster.info\/ro\/blog\/administrirovanie\/eshhyo-odin-velosiped-hranim-yunikodnye-stroki-na-30-60-kompaktnee-chem-utf-8","title":{"rendered":"\u00cenc\u0103 o biciclet\u0103: stoc\u0103m \u0219iruri Unicode cu 30-60% mai compact dec\u00e2t UTF-8","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"\u00cenc\u0103
\n
\nDac\u0103 e\u0219ti dezvoltator \u0219i trebuie s\u0103 alegi o codificare, aproape \u00eentotdeauna solu\u021bia corect\u0103 va fi Unicode. Modul specific de reprezentare depinde de context, dar cel mai adesea exist\u0103 un r\u0103spuns universal \u2013 UTF-8. Este eficient pentru c\u0103 permite utilizarea tuturor simbolurilor Unicode, f\u0103r\u0103 a consuma prea<\/em> multe byte \u00een cele mai multe cazuri. Totu\u0219i, pentru limbile care folosesc nu doar literele latine, \u201enu prea multe\u201d \u00eenseamn\u0103, cel pu\u021bin dou\u0103 byte pe simbol<\/strong>. Se poate o solu\u021bie mai bun\u0103, f\u0103r\u0103 a reveni la codific\u0103rile preistorice, care ne limiteaz\u0103 la doar 256 de simboluri disponibile?<\/p>\n

Mai jos te invit s\u0103 descoperi tentativa mea de a r\u0103spunde la aceast\u0103 \u00eentrebare \u0219i implementarea unui algoritm relativ simplu, care permite stocarea \u0219irurilor \u00een majoritatea limbilor lumii, f\u0103r\u0103 a ad\u0103uga excesul pe care \u00eel are UTF-8.<\/a><\/noindex><\/p>\n

Declinarea responsabilit\u0103\u021bii.<\/i> Imediat voi face c\u00e2teva preciz\u0103ri importante: solu\u021bia descris\u0103 nu este propus\u0103 ca o \u00eenlocuire universal\u0103 a UTF-8<\/strong>, ci se potrive\u0219te doar unui num\u0103r restr\u00e2ns de cazuri (despre care vom vorbi mai jos), \u0219i nu trebuie folosit\u0103 \u00een interac\u021biunea cu API-uri externe (care nu au cuno\u0219tin\u021b\u0103 de ea). Cel mai adesea, pentru stocarea compact\u0103 a unor volume mari de date text, algoritmii de compresie generali (de exemplu, deflate) sunt mai adecva\u021bi. \u00cen plus, deja \u00een procesul de cre\u0103rii solu\u021biei mele am descoperit un standard existent \u00een cadrul Unicode-ului, care rezolv\u0103 aceea\u0219i problem\u0103 \u2013 este pu\u021bin mai complicat (\u0219i adesea mai pu\u021bin eficient), dar este, \u00een continuare, un standard acceptat, nu o solu\u021bie improvizat\u0103. De asemenea, voi vorbi despre el.<\/p>\n

Despre Unicode \u0219i UTF-8<\/h2>\n

\nMai \u00eent\u00e2i \u2013 c\u00e2teva cuvinte despre ce este, de fapt, Unicode<\/strong> \u0219i UTF-8<\/strong>.<\/p>\n

Dup\u0103 cum se \u0219tie, codific\u0103rile de 8 bi\u021bi au fost populare \u00een trecut. Cu acestea a fost simplu: 256 de simboluri pot fi numerotate cu numere de la 0 la 255, iar numerele de la 0 la 255 sunt evident reprezentabile printr-un byte. Dac\u0103 ne \u00eentoarcem la cele mai vechi origini, codificarea ASCII este limitat\u0103 la 7 bi\u021bi, astfel c\u0103 cel mai semnificativ bit \u00een reprezentarea sa byte este zero, iar majoritatea codific\u0103rilor de 8 bi\u021bi sunt compatibile cu aceasta (diferen\u021bele apar doar \u00een partea \u201esuperioar\u0103\u201d, unde cel mai semnificativ bit este unu).<\/p>\n

Cu ce se deosebe\u0219te Unicode de aceste codific\u0103ri \u0219i de ce este legat de at\u00e2t de multe reprezent\u0103ri specifice \u2013 UTF-8, UTF-16 (BE \u0219i LE), UTF-32? Hai s\u0103 analiz\u0103m pe r\u00e2nd.<\/p>\n

Standardul de baz\u0103 Unicode descrie doar coresponden\u021ba \u00eentre caractere (iar \u00een unele cazuri \u2013 componentele individuale ale caracterelor) \u0219i numerele lor. \u0218i numerele posibile din acest standard sunt foarte multe \u2013 de la 0x00<\/b><\/code> la 0x10FFFF<\/b><\/code> (1 114 112 de buc\u0103\u021bi). Dac\u0103 am dori s\u0103 stoc\u0103m un num\u0103r \u00een acest interval \u00eentr-o variabil\u0103, 1 sau 2 octe\u021bi nu ne-ar fi suficien\u021bi. \u0218i cum procesoarele noastre nu sunt foarte preg\u0103tite pentru a lucra cu numere de trei octe\u021bi, am fi nevoi\u021bi s\u0103 folosim nu mai pu\u021bin de 4 octe\u021bi pentru un singur caracter! Asta este UTF-32, dar tocmai din cauza acestei \"risipe\" acest format nu este popular.<\/p>\n

Din fericire, caracterele din Unicode nu sunt dispuse \u00eent\u00e2mpl\u0103tor. Toat\u0103 aceast\u0103 multitudine este \u00eemp\u0103r\u021bit\u0103 \u00een 17 \u201eplanuri<\/em>\u201d, fiecare con\u021bin\u00e2nd 65536 (0x10000<\/b><\/code>) \u00abpuncte de cod<\/em>\u201d. Conceptul de \u201epunct de cod\u201d se refer\u0103 pur \u0219i simplu la num\u0103rul caracterului<\/em>, atribuit lui de Unicode. Dar, a\u0219a cum s-a men\u021bionat mai sus, \u00een Unicode sunt numerotate nu doar caracterele individuale, ci \u0219i componentele lor \u0219i semnele de serviciu (iar uneori, num\u0103rul de nimic nu corespunde \u2013 poate, p\u00e2n\u0103 c\u00e2nd va fi nevoie, dar pentru noi nu este at\u00e2t de important), prin urmare, este mai corect s\u0103 vorbim despre num\u0103rul efectiv al numerelor, nu despre caractere. Totu\u0219i, pentru concizie, voi folosi adesea cuv\u00e2ntul \u201ecaracter\u201d, \u00eensemn\u00e2nd termenul \u201epunct de cod\u201d.<\/p>\n

\"\u00cenc\u0103
\nPlanurile Unicode. Dup\u0103 cum se poate observa, cea mai mare parte (planurile de la 4 la 13) este \u00eenc\u0103 neutilizat\u0103.<\/i><\/p>\n

Ceea ce este remarcabil este c\u0103 \u00eentreaga \u201emiez\u201d se afl\u0103 \u00een planul zero, cunoscut sub numele de "Basic Multilingual Plane<\/em>". Dac\u0103 linia con\u021bine text \u00eentr-o oarecare limb\u0103 modern\u0103 (inclusiv chinez\u0103), nu ve\u021bi ie\u0219i din acest plan. Dar nu se poate exclude restul Unicode-ului \u2014 de exemplu, emoji-urile se afl\u0103 \u00een principal la cap\u0103tul urm\u0103torului plan, "Supplementary Multilingual Plane<\/em>" (se \u00eentinde de la 0x10000<\/b><\/code> la 0x1FFFF<\/b><\/code>). Prin urmare, UTF-16 ac\u021bioneaz\u0103 astfel: toate caracterele care se \u00eencadreaz\u0103 \u00een Basic Multilingual Plane<\/em>, sunt codificate \u201ea\u0219a cum sunt\u201d, cu num\u0103rul de dou\u0103 octe\u021bi corespunz\u0103tor. Totu\u0219i, o parte din numere din acest interval nu reprezint\u0103 caractere specifice, ci indic\u0103 faptul c\u0103, dup\u0103 acest duo de octe\u021bi, trebuie s\u0103 privim \u00eenc\u0103 unul \u2013 combin\u00e2nd valorile acestor patru octe\u021bi, ob\u021binem un num\u0103r care acoper\u0103 \u00eentreaga gam\u0103 permis\u0103 de Unicode. Aceast\u0103 reprezentare se nume\u0219te \u201eperechi surrogate\u201d \u2013 poate a\u021bi auzit despre ele.<\/p>\n

Astfel, UTF-16 necesit\u0103 dou\u0103 sau (\u00een cazuri foarte rare) patru octe\u021bi pentru un \"punct de cod\". Este mai bine dec\u00e2t s\u0103 folose\u0219ti constant patru octe\u021bi, dar literele latine (\u0219i alte caractere ASCII) consum\u0103, prin aceast\u0103 codificare, jum\u0103tate din spa\u021biu pe zerouri. UTF-8 este destinat s\u0103 remedieze aceasta: ASCII \u00een el ocup\u0103, la fel ca \u00eenainte, doar un octet; codurile de 0x80<\/b><\/code> la 0x7FF<\/b><\/code> \u2014 dou\u0103 octe\u021bi; de 0x800<\/b><\/code> la 0xFFFF<\/b><\/code> \u2014 trei, iar de 0x10000<\/b><\/code> la 0x10FFFF<\/b><\/code> \u2014 patru. Pe de o parte, literele latine au c\u00e2\u0219tigat: s-a restabilit compatibilitatea cu ASCII, iar distribu\u021bia este mai uniform \"\u00eentins\u0103\" de la 1 la 4 octe\u021bi. Dar alfabeturile diferite de cel latin, din p\u0103cate, nu c\u00e2\u0219tig\u0103 deloc \u00een compara\u021bie cu UTF-16, iar multe necesit\u0103 acum chiar trei octe\u021bi \u00een loc de doi \u2014 intervalul acoperit de \u00eenregistrarea de doi octe\u021bi s-a restr\u00e2ns de 32 de ori, de 0xFFFF<\/b><\/code> la 0x7FF<\/b><\/code>, \u0219i nu include deja nici chineza, nici, de exemplu, georgiana. Cirilica \u0219i alte cinci alfabeturi \u2014 ura \u2014 au avut noroc, 2 octe\u021bi pe simbol.<\/p>\n

De ce se \u00eent\u00e2mpl\u0103 asta? S\u0103 vedem cum UTF-8 reprezint\u0103 codurile caracterelor:
\n\"\u00cenc\u0103
\nDirect pentru reprezentarea numerelor, aici sunt utiliza\u021bi bi\u021bi marca\u021bi cu simbolul x<\/b><\/code>. Se observ\u0103 c\u0103 \u00een \u00eenregistrarea de doi octe\u021bi sunt doar 11 bi\u021bi (din 16). Bi\u021bii de conducere au doar o func\u021bie de serviciu. \u00cen cazul \u00eenregistr\u0103rii de patru octe\u021bi, sunt aloca\u021bi 21 de bi\u021bi din 32 pentru num\u0103rul punctului de cod \u2014 p\u0103rea c\u0103 ar fi fost suficien\u021bi \u0219i trei octe\u021bi (care ofer\u0103 \u00een total 24 de bi\u021bi), dar marcajele de serviciu consum\u0103 prea mult.<\/p>\n

Este un lucru r\u0103u? De fapt, nu foarte. Pe de o parte \u2014 dac\u0103 ne preocup\u0103m foarte mult de spa\u021biul ocupat, avem algoritmi de compresie care pot elimina cu u\u0219urin\u021b\u0103 toat\u0103 entropia \u0219i redundan\u021ba. Pe de alt\u0103 parte \u2014 scopul Unicode-ului a fost s\u0103 ofere o codificare c\u00e2t mai universal\u0103. De exemplu, un lan\u021b codificat \u00een UTF-8 poate fi \u00eencredin\u021bat unui cod care \u00eenainte func\u021biona doar cu ASCII \u0219i nu ne temem c\u0103 va vedea un caracter din intervalul ASCII care de fapt nu exist\u0103 acolo (deoarece \u00een UTF-8 toate byte-urile care \u00eencep cu bitul zero sunt chiar ASCII). Iar dac\u0103 brusc dorim s\u0103 t\u0103iem un mic coad\u0103 dintr-un lan\u021b mare, f\u0103r\u0103 a-l decodifica de la \u00eenceput (sau de a recupera o parte din informa\u021bie dup\u0103 o zon\u0103 deteriorat\u0103) \u2014 nu este greu s\u0103 g\u0103sim acel offset unde \u00eencepe un anumit caracter (e suficient s\u0103 s\u0103rim peste byte-urile care au un prefix de bit 10<\/b><\/code>).<\/p>\n

De ce atunci s\u0103 invent\u0103m ceva nou?<\/h2>\n

\n\u00cen acela\u0219i timp, ocazional apar situa\u021bii \u00een care algoritmii de comprimare, cum ar fi deflate, sunt ineficien\u021bi, dar se dore\u0219te ob\u021binerea unei stoc\u0103ri compacte a \u0219irurilor. Personal, m-am confruntat cu o astfel de provocare, g\u00e2ndindu-m\u0103 la construirea unui arbore prefixat comprimat<\/a><\/noindex> pentru un dic\u021bionar mare, care include cuvinte \u00een diverse limbi. Pe de o parte, fiecare cuv\u00e2nt este foarte scurt, deci comprimarea acestuia ar fi ineficient\u0103. Pe de alt\u0103 parte, implementarea arborelui pe care o lua \u00een considerare era proiectat\u0103 astfel \u00eenc\u00e2t fiecare byte al \u0219irului stocat s\u0103 genereze un nod distinct al arborelui, iar minimizarea num\u0103rului lor era foarte util\u0103. \u00cen biblioteca mea Az.js<\/a><\/noindex> (la fel ca \u0219i \u00een pymorphy2<\/a><\/noindex>, pe care este bazat\u0103) problema de genul acesta se rezolv\u0103 simplu \u2014 \u0219irurile, \u00eempachetate \u00een un dic\u021bionar DAWG,<\/a><\/noindex>sunt stocate acolo \u00een vechea \u0219i bun\u0103 CP1251. Dar, cum este u\u0219or de \u00een\u021beles, aceasta func\u021bioneaz\u0103 bine doar pentru un alfabet restr\u00e2ns \u2014 un \u0219ir \u00een chinez\u0103 nu poate fi stocat \u00eentr-un astfel de dic\u021bionar.<\/a><\/noindex>De asemenea, vreau s\u0103 subliniez un alt aspect nepl\u0103cut care apare atunci c\u00e2nd se folose\u0219te UTF-8 \u00een o astfel de structur\u0103 de date. \u00cen imaginea de mai sus, se vede c\u0103 atunci c\u00e2nd este scris un caracter sub form\u0103 de dou\u0103 byte, bi\u021bii care \u00eei corespund nu sunt consecutivi, ci sunt \u00eentrerup\u021bi de o pereche de bi\u021bi<\/p>\n

\u00een mijloc: 10<\/b><\/code> . Din cauza acestui lucru, atunci c\u00e2nd \u00een codul caracterului se dep\u0103\u0219esc cei 6 bi\u021bi inferiori ai celui de-al doilea byte (adic\u0103 se produce o tranzi\u021bie 110xxxxx 10xxxxxx<\/b><\/code>), atunci se schimb\u0103 \u0219i primul byte. Rezultatul este c\u0103 litera \u201e\u043f\u201d este reprezentat\u0103 de byte-uri 10111111<\/b><\/code> \u2192 10000000<\/b><\/code>, iar urm\u0103toarea litera \u201e\u0440\u201d \u2014 de byte-uri 0xD0 0xBF<\/b><\/code>. \u00cen arborele prefixat, acest lucru duce la divizarea nodului p\u0103rinte \u00een dou\u0103 \u2014 unul pentru prefix 0xD1 0x80<\/b><\/code>, \u0219i altul pentru 0xD0<\/b><\/code>(de\u0219i \u00eentreaga chirilic\u0103 ar putea fi codificat\u0103 doar cu al doilea byte). 0xD1<\/b><\/code> Ce am realizat<\/p>\n

Confrunt\u00e2ndu-m\u0103 cu aceast\u0103 problem\u0103, am decis s\u0103 exersez cu bi\u021bi \u0219i, \u00een acela\u0219i timp, s\u0103 cunosc mai bine structura Unicode \u00een ansamblu. Rezultatul a fost un format de codare UTF-C (\u201eC\u201d de la<\/h2>\n

\ncompact), care nu consum\u0103 mai mult de 3 byte-uri pe un punct de cod, dar foarte adesea permite consumarea doar a unui byte suplimentar pentru \u00eentreaga linie codificat\u0103.<\/em>Aceasta duce la faptul c\u0103 pe multe alfabete non-ASCII, aceast\u0103 codare devine cu 30-60% mai compact\u0103 dec\u00e2t UTF-8.<\/strong>Am organizat exemple de implement\u0103ri ale algoritmilor de codare \u0219i decodare sub forma bibliotecilor \u00een JavaScript \u0219i Go.<\/strong>.<\/p>\n

Am realizat exemple de implementare a algoritmilor de codare \u0219i decodare sub form\u0103 de biblioteci \u00een JavaScript \u0219i Go<\/a><\/noindex>, pute\u021bi utiliza liber \u00een codul dvs. Totu\u0219i, voi sublinia c\u0103, \u00eentr-un anumit sens, acest format r\u0103m\u00e2ne un \u201ebiciclet\u0103\u201d, iar eu nu recomand s\u0103-l folosi\u021bi f\u0103r\u0103 a \u00een\u021belege de ce ave\u021bi nevoie de el<\/strong>. Este mai degrab\u0103 un experiment dec\u00e2t o \u201e\u00eembun\u0103t\u0103\u021bire\u201d serioas\u0103 a UTF-8. Cu toate acestea, codul este scris cu grij\u0103, concis, cu multe comentarii \u0219i acoperire de teste.<\/p>\n

\"\u00cenc\u0103
\nRezultatul testelor efectuate \u0219i compara\u021bia cu UTF-8<\/i><\/p>\n

De asemenea, am realizat o pagin\u0103 demo<\/a><\/noindex>, unde poate fi evaluat\u0103 func\u021bionarea algoritmului, iar apoi voi explica mai \u00een detaliu principiile \u0219i procesul de dezvoltare.<\/p>\n

Elimin\u0103m bi\u021bii redundan\u021bi<\/h2>\n

\nCa baz\u0103, am folosit, desigur, UTF-8. Primul \u0219i cel mai evident lucru pe care \u00eel putem schimba este s\u0103 reducem num\u0103rul de bi\u021bi de control din fiecare octet. De exemplu, primul octet din UTF-8 \u00eencepe \u00eentotdeauna fie cu 0<\/b><\/code>, fie cu 11<\/b><\/code> \u2014 prefixul 10<\/b><\/code> exist\u0103 doar la octetii urm\u0103tori. S\u0103 \u00eenlocuim prefixul 11<\/b><\/code> pe 1<\/b><\/code>, iar la octetii urm\u0103tori elimin\u0103m complet prefixelor. Ce va rezulta?<\/p>\n

0xxxxxxx<\/b><\/code> \u2014 1 octet
\n10xxxxxx xxxxxxxx<\/b><\/code> \u2014 2 octe\u021bi
\n110xxxxx xxxxxxxx xxxxxxxx<\/b><\/code> \u2014 3 octe\u021bi<\/p>\n

Stop, dar unde este reprezentarea pe patru octe\u021bi? Aceasta a devenit inutil\u0103 \u2014 la scrierea pe trei octe\u021bi avem acum acces la 21 de bi\u021bi \u0219i acest lucru este mai mult dec\u00e2t suficient pentru toate numerele p\u00e2n\u0103 la 0x10FFFF<\/b><\/code>.<\/p>\n

Ce am sacrificat aici? Cel mai important \u2014 detectarea limitelor caracterelor dintr-un loc aleatoriu al tamponului. Nu putem s\u0103 ne uit\u0103m \u00eentr-un octet aleatoriu \u0219i s\u0103 g\u0103sim \u00eenceputul urm\u0103torului caracter. Aceasta este o limitare a formatului nostru, dar \u00een practic\u0103 necesitatea unei astfel de func\u021bionalit\u0103\u021bi nu apare des. De obicei, suntem capabili s\u0103 parcurgem tamponul de la \u00eenceput (mai ales c\u00e2nd este vorba de \u0219iruri scurte).<\/p>\n

Situa\u021bia cu acoperirea limbilor pe 2 octe\u021bi a devenit de asemenea mai bun\u0103: acum formatul cu dou\u0103 octe\u021bi ofer\u0103 un interval de 14 bi\u021bi, iar aceasta permite coduri p\u00e2n\u0103 la 0x3FFF<\/b><\/code>. Chinezii nu au noroc (ieroglifele lor sunt \u00een principal \u00een intervalul de la 0x4E00<\/b><\/code> la 0x9FFF<\/b><\/code>), dar georgienii \u0219i multe alte na\u021biuni au devenit mai ferici\u021bi \u2014 limbile lor se \u00eencadreaz\u0103 \u0219i ele \u00een 2 octe\u021bi pe caracter.<\/p>\n

Introducem starea encoderului<\/h2>\n

\nAcum s\u0103 ne g\u00e2ndim la propriet\u0103\u021bile \u0219irurilor \u00een sine. \u00cen dic\u021bionar, cuvintele sunt adesea scrise cu caractere dintr-un singur alfabet, ceea ce este de asemenea adev\u0103rat pentru multe alte texte. Ar fi bine s\u0103 specific\u0103m o dat\u0103 acest alfabet \u0219i apoi s\u0103 indic\u0103m doar num\u0103rul literei din interiorul s\u0103u. S\u0103 vedem dac\u0103 ne ajut\u0103 pozi\u021bionarea caracterelor \u00een tabelul Unicode.<\/p>\n

Dup\u0103 cum s-a men\u021bionat mai sus, Unicode-ul este \u00eemp\u0103r\u021bit \u00een planuri<\/em> c\u00e2te 65536 coduri fiecare. Dar aceasta nu este o diviziune foarte util\u0103 (cum am spus deja, cel mai adesea ne afl\u0103m \u00een planul zero). O diviziune mai interesant\u0103 este blocuri.<\/em> Aceste intervale nu mai au o lungime fix\u0103 \u0219i au mai mult sens \u2014 de obicei, fiecare reune\u0219te caractere din aceea\u0219i alfabet.<\/p>\n

\"\u00cenc\u0103
\nUn bloc care con\u021bine caractere din alfabetul bengalez. Din p\u0103cate, din motive istorice, acesta este un exemplu de ambalare nu foarte dens\u0103 \u2014 96 de caractere sunt dispersate haotic pe 128 de puncte de cod ale blocului.<\/i><\/p>\n

\u00cent\u00e2lnirile blocurilor \u0219i dimensiunile lor sunt \u00eentotdeauna multipli de 16 \u2014 aceasta a fost f\u0103cut\u0103 pur \u0219i simplu pentru comoditate. \u00cen plus, multe blocuri \u00eencep \u0219i se termin\u0103 la valori care sunt multipli de 128 sau chiar 256 \u2014 de exemplu, chirilica de baz\u0103 ocup\u0103 256 de bytes de 0x0400<\/b><\/code> la 0x04FF<\/b><\/code>. Este destul de convenabil: dac\u0103 salv\u0103m o dat\u0103 prefixul 0x04<\/b><\/code>, atunci orice caracter chirilic poate fi scris cu un singur byte. Totu\u0219i, \u00een acest mod, vom pierde posibilitatea de a reveni la ASCII (\u0219i la orice alte caractere \u00een general). De aceea facem a\u0219a:<\/p>\n

    \n
  1. Dou\u0103 bytes 10yyyyyy yxxxxxxx<\/b><\/code> nu doar indic\u0103 un caracter cu num\u0103rul yyyyyy yxxxxxxx<\/b><\/code>, ci \u0219i schimb\u0103 alfabetul curent<\/em> pe yyyyyy y0000000<\/b><\/code> adic\u0103, memor\u0103m toate bitii, cu excep\u021bia celor de jos 7 bits<\/strong>);<\/li>\n
  2. Un byte 0xxxxxxx<\/b><\/code> este un caracter din alfabetul curent. Trebuie s\u0103-l adun\u0103m pur \u0219i simplu cu offsetul pe care l-am memorat \u00een pasul 1. P\u00e2n\u0103 c\u00e2nd alfabetul nu a fost schimbat, offsetul este zero, astfel c\u0103 compatibilitatea cu ASCII a fost men\u021binut\u0103.<\/li>\n<\/ol>\n

    \n\u00cen mod similar pentru codurile care necesit\u0103 3 bytes:<\/p>\n

      \n
    1. Trei bytes 110yyyyy yxxxxxxx xxxxxxxx<\/b><\/code> indic\u0103 un caracter cu num\u0103rul yyyyyy yxxxxxxx xxxxxxxx<\/b><\/code>, schimb\u0103 alfabetul curent<\/em> pe yyyyyy y0000000 00000000<\/b><\/code> (am memorat tot, cu excep\u021bia celor de jos 15 bits<\/strong>), \u0219i pun un steag c\u0103 acum suntem \u00een mod lung<\/em> (c\u00e2nd schimb\u0103m alfabetul \u00eenapoi la modului cu dou\u0103 bytes, acest steag va fi resetat);<\/li>\n
    2. Dou\u0103 bytes 0xxxxxxx xxxxxxxx<\/b><\/code> \u00een mod lung, acesta este caracterul din alfabetul curent. \u00cen mod similar, \u00eel adun\u0103m cu offsetul din pasul 1. Tot ce difer\u0103 este c\u0103 acum citim dou\u0103 bytes (deoarece am schimbat \u00een acest mod).<\/li>\n<\/ol>\n

      \nPare destul de bine: acum, at\u00e2t timp c\u00e2t trebuie s\u0103 codific\u0103m caractere din acela\u0219i interval de 7 bi\u021bi Unicode, cheltuim un byte suplimentar la \u00eenceput \u0219i la fiecare caracter un byte.<\/p>\n

      \"\u00cenc\u0103
      \nFunc\u021bionarea uneia dintre versiunile timpurii. Deja evit\u0103 adesea UTF-8, dar mai sunt multe de \u00eembun\u0103t\u0103\u021bit.<\/i><\/p>\n

      Ce s-a \u00eenr\u0103ut\u0103\u021bit? \u00cen primul r\u00e2nd, am ob\u021binut o stare, \u0219i anume offsetul alfabetului curent<\/em> \u0219i steagul modului lung<\/em>Aceasta ne limiteaz\u0103 suplimentar: acum acelea\u0219i caractere pot fi codificate diferit \u00een contexte diferite. C\u0103utarea sub\u0219irurilor, de exemplu, va trebui s\u0103 se fac\u0103 \u021bin\u00e2nd cont de acest aspect, nu doar compar\u00e2nd byte-urile. \u00cen al doilea r\u00e2nd, imediat ce am schimbat alfabetul, a ap\u0103rut o problem\u0103 cu codificarea caracterelor ASCII (iar asta nu se refer\u0103 doar la literele latine, ci \u0219i la punctua\u021bia de baz\u0103, inclusiv spa\u021biile) - acestea necesit\u0103 o schimbare repetat\u0103 a alfabetului \u00een 0, adic\u0103 din nou un byte suplimentar (apoi \u00eenc\u0103 unul, pentru a reveni la alfabetul nostru principal).<\/p>\n

      Un alfabet e bine, dou\u0103 sunt \u0219i mai bine.<\/h2>\n

      \nS\u0103 \u00eencerc\u0103m s\u0103 modific\u0103m pu\u021bin prefixelor noastre de bi\u021bi, ad\u0103ug\u00e2nd unul la cele trei men\u021bionate mai sus:<\/p>\n

      0xxxxxxx<\/b><\/code> \u2014 1 byte \u00een modul normal, 2 \u00een modul lung.
      \n11xxxxxx<\/b><\/code> \u2014 1 octet
      \n100xxxxx xxxxxxxx<\/b><\/code> \u2014 2 octe\u021bi
      \n101xxxxx xxxxxxxx xxxxxxxx<\/b><\/code> \u2014 3 octe\u021bi<\/p>\n

      \"\u00cenc\u0103
      \n
      \nAcum, \u00een reprezentarea de dou\u0103 byte, exist\u0103 cu un bit disponibil mai pu\u021bin - pot fi incluse puncte de cod p\u00e2n\u0103 la 0x1FFF<\/b><\/code>, nu 0x3FFF<\/b><\/code>. Cu toate acestea, este \u00eenc\u0103 semnificativ mai mult dec\u00e2t \u00een codurile de dou\u0103 byte UTF-8, cea mai mare parte a limbilor comune \u00eenc\u0103 se potrive\u0219te, cea mai notabil\u0103 pierdere fiind       hiragana<\/a><\/noindex> \u0219i katakana<\/a><\/noindex>, japonezii sunt tri\u0219ti.<\/p>\n

      Ce este noul cod 11xxxxxx<\/b><\/code>? \u042d\u0442\u043e \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u00ab\u0437\u0430\u0433\u0430\u0448\u043d\u0438\u043a\u00bb \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c \u0432 64 \u0441\u0438\u043c\u0432\u043e\u043b\u0430, \u043e\u043d \u0434\u043e\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u043d\u0430\u0448 \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u0439 \u0430\u043b\u0444\u0430\u0432\u0438\u0442, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u044f \u043d\u0430\u0437\u0432\u0430\u043b \u0435\u0433\u043e \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u043c (auxiliary<\/em>) alfabet. Atunci c\u00e2nd schimb\u0103m alfabetul curent, o parte din vechiul alfabet devine auxiliar. De exemplu, am trecut de la ASCII la chirilic\u0103 \u2013 \u00een \u201erezervor\u201d acum sunt 64 de caractere, con\u021bin\u00e2nd litere latine, cifre, un spa\u021biu \u0219i o virgul\u0103<\/strong> (cele mai frecvente inser\u021bii \u00een textele non-ASCII). Am revenit la ASCII \u2013 \u0219i alfabetul auxiliar va deveni majoritatea caracterelor chirilice.<\/p>\n

      Datorit\u0103 accesului la dou\u0103 alfabete, putem gestiona un num\u0103r mai mare de texte, av\u00e2nd costuri minime pentru schimbarea alfabetelor (punctua\u021bia va conduce cel mai adesea la revenirea \u00een ASCII, dar dup\u0103 aceea multe caractere non-ASCII le vom ob\u021bine deja din alfabetul suplimentar, f\u0103r\u0103 o schimbare repetat\u0103).<\/p>\n

      Bonus: definind alfabetul suplimentar cu un prefix 11xxxxxx<\/b><\/code> \u0219i aleg\u00e2ndu-i decalajul ini\u021bial egal cu 0xC0<\/b><\/code>, ob\u021binem compatibilitate par\u021bial\u0103 cu CP1252. Cu alte cuvinte, multe (dar nu toate) texte vest-europene codificate \u00een CP1252 vor ar\u0103ta la fel \u0219i \u00een UTF-C.<\/p>\n

      Aici, totu\u0219i, apare o dificultate: cum s\u0103 ob\u021binem alfabetul auxiliar din alfabetul principal? Poate r\u0103m\u00e2ne acela\u0219i decalaj, dar - din p\u0103cate - aici structura Unicode joac\u0103 \u00eempotriva noastr\u0103. Foarte frecvent, partea principal\u0103 a alfabetului nu se afl\u0103 la \u00eenceputul blocului (de exemplu, litera mare rus\u0103 \u201eA\u201d are cod 0x0410<\/b><\/code>, de\u0219i blocul chirilic \u00eencepe cu 0x0400<\/b><\/code>). Astfel, lu\u00e2nd \u00een \u201erezerv\u0103\u201d primele 64 de caractere, am putea pierde accesul la partea final\u0103 a alfabetului.<\/p>\n

      Pentru a remedia aceast\u0103 problem\u0103, am parcurs manual unele blocuri corespunz\u0103toare diferitelor limbi \u0219i am specificat pentru ele un offset al alfabetului auxiliar \u00een cadrul celui principal. Latinele, \u00een mod excep\u021bional, le-am reordonat complet similar cu base64.<\/p>\n

      \"\u00cenc\u0103<\/p>\n

      Retu\u0219uri finale<\/h2>\n

      \nS\u0103 ne g\u00e2ndim \u00een cele din urm\u0103 unde am mai putea \u00eembun\u0103t\u0103\u021bi ceva.<\/p>\n

      Observ\u0103m c\u0103 formatul 101xxxxx xxxxxxxx xxxxxxxx<\/b><\/code> permite codificarea numerelor p\u00e2n\u0103 la 0x1FFFFF<\/b><\/code>, iar Unicode se \u00eencheie mai devreme, la 0x10FFFF<\/b><\/code>. Cu alte cuvinte, ultimul punct de cod va fi reprezentat ca 10110000 11111111 11111111<\/b><\/code>. A\u0219adar, putem spune c\u0103 dac\u0103 primul byte are forma 1011xxxx<\/b><\/code> (unde xxxx<\/b><\/code> mai mare de 0), acesta reprezint\u0103 altceva. De exemplu, se pot ad\u0103uga \u00eenc\u0103 15 caractere, disponibile \u00een permanen\u021b\u0103 pentru codificare cu un byte, dar am decis s\u0103 fac altfel.<\/p>\n

      De aceea, alegem c\u00e2teva intervale selectate, corespunz\u0103toare emoji-urilor, hiraganei \u0219i katakanei, le renumerot\u0103m \u00eentr-o list\u0103 continu\u0103 \u0219i le codific\u0103m sub form\u0103 de dou\u0103 bytes \u00een loc de trei:<\/p>\n

      1011xxxx xxxxxxxx<\/b><\/code> <\/p>\n

      Excelent: emoji-ul men\u021bionat anterior \u200d\u200d\u200d\"\u00cenc\u0103<\/a><\/noindex>, format din 7 puncte de cod, \u00een UTF-8 ocup\u0103 25 bytes, iar noi l-am \u00eencadra \u00een 14<\/strong> (exact c\u00e2te dou\u0103 bytes pentru fiecare punct de cod). Apropo, Habr a refuzat s\u0103-l prelucreze (at\u00e2t \u00een vechiul, c\u00e2t \u0219i \u00een noul editor), a\u0219a c\u0103 a fost necesar s\u0103-l inser\u0103m ca imagine.<\/p>\n

      S\u0103 \u00eencerc\u0103m s\u0103 corect\u0103m \u00eenc\u0103 o problem\u0103. Dup\u0103 cum ne amintim, alfabetul principal este practic bitii 6 cei mai semnificativi<\/strong>, pe care \u00eei avem \u00een minte, \u0219i \u00eei lipim la codul fiec\u0103rui simbol de decodificat. \u00cen cazul caracterelor chineze\u0219ti, care se afl\u0103 \u00een blocul 0x4E00<\/b><\/code> \u2013 0x9FFF<\/b><\/code>, este fie un bit 0, fie un bit 1. Acest lucru nu este foarte practic: va trebui s\u0103 comut\u0103m constant \u00eentre aceste dou\u0103 valori ale alfabetului (adic\u0103 s\u0103 consum\u0103m c\u00e2te trei bytes). Dar s\u0103 observ\u0103m c\u0103, \u00een modul lung, din codul \u00een sine putem sc\u0103dea num\u0103rul de simboluri pe care le codific\u0103m folosind modul scurt (dup\u0103 toate trucurile descrise mai sus, acesta este 10240) \u2014 astfel, gama de hieroglife se va muta la 0x2600<\/b><\/code> \u2013 0x77FF<\/b><\/code>, \u0219i \u00een acest caz, \u00een toat\u0103 aceast\u0103 gam\u0103, cei mai semnificativi 6 bi\u021bi (din 21) vor fi egali cu 0. Astfel, secven\u021bele de hieroglife vor folosi c\u00e2te dou\u0103 bytes pe hieroglif (ceea ce este optim pentru o astfel de gam\u0103 mare), f\u0103r\u0103 a necesita comut\u0103ri \u00eentre alfabete. <\/p>\n

      Solu\u021bii alternative: SCSU, BOCU-1<\/h2>\n

      \nCuno\u0219tin\u021bele Unicode, chiar \u0219i citind titlul articolului, cel mai probabil se vor gr\u0103bi s\u0103 reaminteasc\u0103 c\u0103, printre standardele Unicode, exist\u0103 Standard Compression Scheme for Unicode<\/a><\/noindex> (SCSU), care descrie o metod\u0103 de codificare foarte similar\u0103 cu cea descris\u0103 \u00een articol.<\/p>\n

      Trebuie s\u0103 recunosc: despre existen\u021ba sa am aflat doar dup\u0103 ce m-am angajat profund \u00een scrierea propriului meu sistem. Dac\u0103 a\u0219 fi \u0219tiut despre el de la \u00eenceput, probabil c\u0103 a\u0219 fi \u00eencercat s\u0103 scriu implementarea lui \u00een loc s\u0103 inventez abordarea mea.<\/p>\n

      Ce este interesant, SCSU folose\u0219te idei foarte asem\u0103n\u0103toare cu cele la care am ajuns singur (\u00een loc de no\u021biunea de \u201ealfabet\u201d, sunt folosite \u201eferon\u201d \u0219i exist\u0103 mai multe dec\u00e2t la mine). Totu\u0219i, acest format are \u0219i dezavantaje: este pu\u021bin mai apropiat de algoritmii de comprimare dec\u00e2t de codificare. \u00cen special, standardul ofer\u0103 multe moduri de reprezentare, dar nu precizeaz\u0103 cum s\u0103 alegi din ele pe cel optim \u2014 pentru aceasta, encoderul trebuie s\u0103 aplice anumite euristici. Astfel, un encoder SCSU care ofer\u0103 o ambalare bun\u0103 va fi mai complex \u0219i mai greu de utilizat dec\u00e2t algoritmul meu.<\/p>\n

      Pentru compara\u021bie, am transferat o implementare relativ simpl\u0103 SCSU \u00een JavaScript \u2014 ca volum de cod, s-a dovedit comparabil cu al meu UTF-C, dar \u00een anumite cazuri a ar\u0103tat rezultate cu zeci de procente mai slabe (uneori poate \u0219i dep\u0103\u0219i, dar nu cu mult). De exemplu, textele \u00een ebraic\u0103 \u0219i greac\u0103 UTF-C le-a codificat cu cu 60% mai bine dec\u00e2t SCSU<\/strong> (probabil din cauza alfabetelor lor compacte).<\/p>\n

      \u00cen plus, voi ad\u0103uga c\u0103, pe l\u00e2ng\u0103 SCSU, exist\u0103 \u0219i o alt\u0103 metod\u0103 de reprezentare compact\u0103 a Unicode \u2014 BOCU-1<\/a><\/noindex>, dar acesta \u00ee\u0219i propune compatibilitatea cu MIME (ceea ce nu aveam nevoie), \u0219i folose\u0219te o abordare u\u0219or diferit\u0103 \u00een codificare. Eficien\u021ba sa nu am evaluat-o, dar mi se pare c\u0103 probabil nu va fi mai bun\u0103 dec\u00e2t SCSU.<\/p>\n

      Posibile \u00eembun\u0103t\u0103\u021biri<\/h2>\n

      \nAlgoritmul pe care l-am prezentat nu este universal prin design (\u00een aceasta, probabil, obiectivele mele se deosebesc cel mai mult de cele ale Consor\u021biului Unicode). Am men\u021bionat deja c\u0103 a fost dezvoltat \u00een principal pentru o singur\u0103 sarcin\u0103 (stocarea unui dic\u021bionar multilingv \u00een arbore prefixat), iar unele dintre tr\u0103s\u0103turile sale pot fi mai pu\u021bin potrivite pentru alte sarcini. Dar, faptul c\u0103 nu este un standard, poate fi chiar un avantaj \u2014 pute\u021bi s\u0103-l adapta\u021bi cu u\u0219urin\u021b\u0103 la nevoile dumneavoastr\u0103<\/strong>.<\/p>\n

      De exemplu, \u00een mod evident, se poate elimina starea, f\u0103c\u00e2nd codificarea f\u0103r\u0103 stare \u2014 pur \u0219i simplu nu actualiza\u021bi variabilele excursii<\/b><\/code>, auxOffs<\/b><\/code> \u0219i is21Bit<\/b><\/code> \u00een encoder \u0219i decoder. \u00cen acest caz, nu va fi posibil s\u0103 se comprime eficient secven\u021bele de caractere dintr-un anumit alfabet, dar va exista garan\u021bia c\u0103 acela\u0219i caracter este \u00eentotdeauna codificat cu acelea\u0219i octe\u021bi, indiferent de context.<\/p>\n

      \u00cen plus, se poate adapta codificatorul pentru o anumit\u0103 limb\u0103, schimb\u00e2nd starea implicit\u0103 \u2014 de exemplu, orient\u00e2ndu-se spre textele ruse\u0219ti, se pot seta la \u00eenceput encoderul \u0219i decoderul ofs = 0x0400<\/b><\/code> \u0219i auxOffs = 0<\/b><\/code>. \u00cen special, are sens \u00een cazul modului f\u0103r\u0103 stare. \u00cen general, va fi asem\u0103n\u0103tor cu utilizarea vechii codific\u0103ri pe opt bi\u021bi, doar c\u0103 nu elimin\u0103 posibilitatea de a insera caractere din \u00eentregul Unicode dup\u0103 necesitate.<\/p>\n

      O alt\u0103 deficien\u021b\u0103 men\u021bionat\u0103 anterior \u2014 \u00een textul voluminos, codificat \u00een UTF-C, nu exist\u0103 o modalitate rapid\u0103 de a g\u0103si limita caracterului cea mai apropiat\u0103 de un octet aleator. T\u0103ind din bufferul codificat ultimele, s\u0103 zicem, 100 de octe\u021bi, risca\u021bi s\u0103 ob\u021bine\u021bi gunoi, cu care nu se poate face nimic. Stocarea jurnalele de c\u00e2teva gigabytes nu este pentru care codificarea este g\u00e2ndit\u0103, dar \u00een general aceasta poate fi corectat\u0103. Octetul 0xBF<\/b><\/code> nu ar trebui s\u0103 apar\u0103 niciodat\u0103 ca primul octet (dar poate fi al doilea sau al treilea). A\u0219adar, \u00een timpul codific\u0103rii, se poate insera o secven\u021b\u0103 0xBF 0xBF 0xBF<\/b><\/code> la fiecare, s\u0103 zicem, 10 Kb \u2014 atunci, la nevoie, pentru a g\u0103si limita va fi suficient s\u0103 scana\u021bi bucata aleas\u0103 p\u00e2n\u0103 c\u00e2nd se g\u0103se\u0219te un astfel de marcaj. Urm\u00e2nd ultimul 0xBF<\/b><\/code> se va garanta \u00eenceputul caracterului. (La decodare, aceast\u0103 secven\u021b\u0103 de trei octe\u021bi trebuie, desigur, ignorat\u0103.)<\/p>\n

      \u00cen concluzie<\/h2>\n

      \nDac\u0103 ai citit p\u00e2n\u0103 aici \u2014 te felicit! Sper c\u0103, la fel ca mine, ai \u00eenv\u0103\u021bat ceva nou (sau ai re\u00eemprosp\u0103tat lucruri mai vechi) despre structura Unicode.<\/p>\n

      \"\u00cenc\u0103
      \nPagina demonstra\u021bional\u0103. Exemplul \u00een ebraic\u0103 eviden\u021biaz\u0103 avantajele at\u00e2t fa\u021b\u0103 de UTF-8, c\u00e2t \u0219i fa\u021b\u0103 de SCSU.<\/i><\/p>\n

      Nu trebuie s\u0103 consideri cercet\u0103rile de mai sus ca o \u00eenc\u0103lcare a standardelor. Totu\u0219i, sunt \u00een general mul\u021bumit de rezultatele muncii mele, a\u0219a c\u0103 sunt bucuros s\u0103 le \u00eemp\u0103rt\u0103\u0219esc<\/a><\/noindex>: de exemplu, biblioteca JS \u00een form\u0103 minificat\u0103 are doar 1710 octe\u021bi (\u0219i, desigur, nu are dependen\u021be). A\u0219a cum am men\u021bionat mai sus, po\u021bi g\u0103si informa\u021bii despre utilizarea acesteia pe pagina demo<\/a><\/noindex> (acolo exist\u0103 \u0219i un set de texte cu care poate fi comparat\u0103 cu UTF-8 \u0219i SCSU).<\/p>\n

      \u00cen final, voi mai sublinia \u00eenc\u0103 o dat\u0103 cazurile \u00een care se poate utiliza UTF-C nu merit\u0103<\/b>:<\/p>\n

      S\u0103 examin\u0103m acele blocuri Unicode care necesit\u0103 trei bytes acum. \u00cen principal, dup\u0103 cum s-a spus deja, acestea sunt caracterele chineze\u0219ti \u2014 dar este greu de f\u0103cut ceva cu ele, sunt 21 de mii. Dar mai sunt \u0219i hiragana cu katakana \u2014 iar acestea nu sunt at\u00e2t de multe, mai pu\u021bin de dou\u0103 sute. \u0218i, av\u00e2nd \u00een vedere c\u0103 ne-am amintit de japonezi \u2014 acolo se afl\u0103 \u0219i emoji-urile (de fapt, acestea sunt r\u0103sp\u00e2ndite \u00een multe locuri \u00een Unicode, dar blocurile principale sunt \u00een intervalul 0x1F300<\/b><\/code> \u2013 0x1FBFF<\/b><\/code>). Dac\u0103 ne g\u00e2ndim c\u0103 acum exist\u0103 emoji-uri care sunt formate din mai multe puncte de cod (de exemplu, emoji-ul \u200d\u200d\u200d\"\u00cenc\u0103<\/a><\/noindex> const\u0103 din 7 coduri!), devine cu adev\u0103rat frustrant s\u0103 cheltuim trei bytes pentru fiecare (7\u00d73 = 21 bytes pentru un singur simbol, un co\u0219mar).<\/p>\n